MADNESS  0.10.1
macrotaskpartitioner.h
Go to the documentation of this file.
1 //
2 // Created by Florian Bischoff on 12/10/20.
3 //
4 
5 #ifndef MADNESS_MACROTASKPARTITIONER_H
6 #define MADNESS_MACROTASKPARTITIONER_H
7 
8 #include<vector>
9 #include<list>
10 #include<string>
11 #include<iomanip>
12 #include<sstream>
14 
15 
16 namespace madness {
17 template<typename ... Ts>
18 constexpr auto decay_types(std::tuple<Ts...> const &)
19 -> std::tuple<std::remove_cv_t<std::remove_reference_t<Ts>>...>;
20 
21 template<typename T>
22 using decay_tuple = decltype(decay_types(std::declval<T>()));
23 
24 template<typename>
25 struct is_madness_function_vector : std::false_type {
26 };
27 
28 template<typename T, std::size_t NDIM>
29 struct is_madness_function_vector<std::vector<typename madness::Function<T, NDIM>>> : std::true_type {
30 };
31 
32 template<typename Q> struct is_vector : std::false_type { };
33 template<typename Q> struct is_vector<std::vector<Q>> : std::true_type { };
34 
35 /// given a tuple return the index of the first argument that is a vector of Function<T,NDIM>
36 template<typename tupleT, std::size_t I>
37 constexpr std::size_t get_index_of_first_vector_argument() {
38 
39  typedef decay_tuple <tupleT> argtupleT; // removes const, &, etc
40 
41  if constexpr(I >= std::tuple_size_v<tupleT>) {
42  // Last case, if nothing is left to iterate, then exit the function
43 // MADNESS_EXCEPTION("there is no madness function vector argument in the list, cannot partition the tasks", 1);
44  return I;
45  } else {
46  using typeT = typename std::tuple_element<I, argtupleT>::type;// use decay types for determining a vector
47  if constexpr (is_vector<typeT>::value) {
48  return I;
49  } else {
50  // Going for next element.
51  return get_index_of_first_vector_argument<tupleT,I+1>();
52  }
53  }
54 }
55 
56 /// given a tuple return the index of the second argument that is a vector of Function<T,NDIM>
57 template<typename tupleT, std::size_t I>
58 constexpr std::size_t get_index_of_second_vector_argument() {
59  constexpr std::size_t index0=get_index_of_first_vector_argument<tupleT,0>();
60  return get_index_of_first_vector_argument<tupleT,index0+1>();
61 }
62 
63 class Batch_1D {
64  friend class MacroTaskPartitioner;
65 
66 public:
67  long begin=0, end=-1; ///< first and first past last index [begin,end)
68 
69  Batch_1D() {}
70  Batch_1D(const Slice& s) : begin(s.start), end(s.end) {
71  MADNESS_CHECK(s.step==1);
72  }
73  Batch_1D(const long& begin, const long& end) : begin(begin), end(end) {}
74 
75  bool operator==(const Batch_1D& other) const {
76  return (end==other.end && begin==other.begin);
77  }
78 
79  long size() const {
80  return end - begin;
81  }
82 
83  bool is_full_size() const {
84  return (begin==0 and end==-1);
85  }
86 
87  /// select the relevant vector elements from the argument tuple
88  template<typename tupleT, std::size_t appearance>
89  tupleT copy_batch(const tupleT& arg) const {
90 
91  constexpr std::size_t index = (appearance==0) ? get_index_of_first_vector_argument<tupleT,0>() :
92  get_index_of_second_vector_argument<tupleT,0>();
93  if constexpr (index>=std::tuple_size<tupleT>::value) {
94  MADNESS_CHECK(is_full_size()); // better: not set by user..
95  return arg;
96  } else {
97  auto v = std::get<index>(arg);
98  auto v_batch=copy_batch(v);
99  tupleT batched_arg = arg;
100  std::get<index>(batched_arg) = v_batch;
101  return batched_arg;
102  }
103  }
104 
105  /// given vector v, copy vector elements of v_batch into vector
106  template<typename vecT>
107  vecT insert_batch(vecT v, const vecT& v_batch) const {
108  MADNESS_CHECK(v_batch.size()==size_t(this->size()) or this->is_full_size());
109  std::copy(v_batch.begin(), v_batch.end(), v.begin()+begin);
110  return v;
111  }
112 
113  /// given vector v, return those vector elements inside this batch
114  template<typename vecT>
115  vecT copy_batch(const vecT v) const {
116  vecT result_batch;
117  long end1 = (end > 0) ? end : v.end() - v.begin();
118  std::copy(v.begin() + begin, v.begin() + end1, std::back_inserter(result_batch));
119  return result_batch;
120  }
121 
122  friend std::ostream& operator<<(std::ostream& os, const Batch_1D& batch) {
123  std::stringstream ss;
124  if (batch.is_full_size()) ss << "[ ---- )";
125  else ss << "[" << std::setw(3) << batch.begin << ", " << std::setw(3) << batch.end << ")";
126  os << ss.str();
127  return os;
128  }
129 };
130 
131 /// a batch consists of a 2D-input batch and a 1D-output batch: K-batch <- (I-batch, J-batch)
132 class Batch {
133 public:
134  friend class MacroTaskPartitioner;
135  std::vector<Batch_1D> input;
137 
138  Batch() {}
139  Batch(const Batch& other) {
140  *this=other;
141  }
142  Batch& operator=(const Batch& other) {
143  if (this==&other) return *this;
144  result=other.result;
145  input=other.input;
146  return *this;
147  }
148 
149  Batch(Batch_1D input1, Batch_1D result) : input{input1}, result(result) {}
151  : input{input1,input2}, result(result) {}
152 
153  std::size_t size_of_input() const {
154  std::size_t result=1;
155  for (auto i: input) result*=i.size();
156  return result;
157  }
158 
159  /// select the relevant vector elements from the argument tuple
160  template<typename tupleT>
161  tupleT copy_input_batch(const tupleT& arg) const {
162  if (input.size()==0) return arg;
163  tupleT arg1=input[0].template copy_batch<tupleT,0>(arg);
164  if (input.size()>1) arg1=input[1].template copy_batch<tupleT,1>(arg1);
165  MADNESS_CHECK(input.size()<=2);
166  return arg1;
167  }
168 
169  /// copy v_batch into the result vector
170  template<typename vecT>
171  vecT insert_result_batch(vecT v, const vecT& v_batch) const {
172  return result.template insert_batch(v,v_batch);
173  }
174 
175  /// pretty print this batch
176  friend std::ostream& operator<<(std::ostream& os, const Batch& batch) {
177  std::stringstream ss;
178  ss << batch.result<< " <-- ";
179  if (batch.input.size()>0) ss << batch.input[0];
180  if (batch.input.size()>1) ss << ", " << batch.input[1];
181  os << ss.str();
182  return os;
183  }
184 };
185 
186 /// partition one (two) vectors into 1D (2D) batches.
187 
188 /// derive from this class and override the \it{do_partitioning} method if you want to implement
189 /// your custom partitioner
191  friend class Batch;
192 
193 public:
194  typedef std::list<std::pair<Batch,double>> partitionT;
195  std::size_t min_batch_size=5; ///< minimum batch size
196  std::size_t max_batch_size = 10; ///< maximum batch size (for memory management)
197  std::size_t nsubworld=1; ///< number of worlds (try to have enough batches for all worlds)
198  std::string policy = "guided"; ///< how to partition the batches
199  std::size_t dimension = 1; ///< partition one or two vectors
200 
202 
204 
206  nsubworld=n;
207  return *this;
208  }
209  MacroTaskPartitioner& set_policy(const std::string& n) {
210  policy=n;
211  return *this;
212  }
213  MacroTaskPartitioner& set_dimension(const std::size_t& n) {
214  dimension=n;
215  return *this;
216  }
218  min_batch_size=n;
219  return *this;
220  }
222  max_batch_size=n;
223  return *this;
224  }
225 
226  /// this will be called by MacroTask, it will *always* partition first (and possibly second) vector of arguments
227  template<typename tupleT>
228  partitionT partition_tasks(const tupleT& argtuple) const {
229 
230  constexpr std::size_t I1 = get_index_of_first_vector_argument<tupleT, 0>();
231  constexpr std::size_t I2 = get_index_of_second_vector_argument<tupleT, 1>();
232  std::size_t vsize1=1,vsize2=1;
233  if constexpr (I2 < std::tuple_size_v<tupleT>) { // found at least 2 vectors of madness functions
234  constexpr std::size_t I2 = get_index_of_second_vector_argument<tupleT, 0>();
235  vsize2 = std::get<I2>(argtuple).size();
236  }
237  if constexpr (I1 < std::tuple_size_v<tupleT>) { // found at least 1 vector
238  constexpr std::size_t I1 = get_index_of_first_vector_argument<tupleT, 0>();
239  vsize1 = std::get<I1>(argtuple).size();
240  } else {
241  std::string msg="confused partitioning dimension: "+std::to_string(dimension) +" typeid " + typeid(tupleT).name();
242  MADNESS_EXCEPTION(msg.c_str(),1);
243  }
244 
245  return do_partitioning(vsize1,vsize2,policy);
246  }
247 
248  /// override this if you want your own partitioning
249  virtual partitionT do_partitioning(const std::size_t& vsize1, const std::size_t& vsize2,
250  const std::string policy) const {
251  if (dimension == 1) {
252  return do_1d_partition(vsize1, policy);
253  } else if (dimension == 2) {
254  return do_2d_partition(vsize1, vsize2, policy);
255  }
256  return partitionT();
257  }
258 
259  partitionT do_1d_partition(const std::size_t vsize, const std::string policy) const {
260  partitionT result;
261  if (policy == "guided") {
262  long begin = 0;
263  long end = 0;
264  while (end < long(vsize)) {
265  end += std::min(max_batch_size, std::max(min_batch_size, ((vsize - end) / nsubworld)));
266  end = std::min(end, long(vsize));
267  Batch batch(Batch_1D(begin, end),Batch_1D(begin,end));
268  double priority=MacroTaskPartitioner::compute_priority(batch);
269  result.push_back(std::make_pair(batch,priority));
270  begin = end;
271  }
272  } else {
273  std::string msg = "unknown partitioning policy: " + policy;
274  MADNESS_EXCEPTION(msg.c_str(), 1);
275  }
276  return result;
277  }
278 
279  /// outer product of 2 1d-partitionings -- result batches correspond to first input batches
280 
281  /// [begin1,end1) <-- [begin1,end1) [begin2,end2)
282  partitionT do_2d_partition(const std::size_t vsize, const std::size_t v2size, const std::string policy) const {
283  partitionT partition1=do_1d_partition(vsize,policy);
284  partitionT partition2=do_1d_partition(v2size,policy);
285  partitionT result;
286  for (auto p1 : partition1) {
287  for (auto p2 : partition2) {
288  Batch batch(p1.first.input[0],p2.first.input[0],p1.first.result);
289  double priority=compute_priority(batch);
290  result.push_back(std::make_pair(batch,priority));
291  }
292  }
293  return result;
294  }
295 
296  virtual double compute_priority(const Batch& batch) const {
297  return batch.size_of_input();
298  }
299 
300 };
301 
302 }
303 
304 #endif //MADNESS_MACROTASKPARTITIONER_H
Definition: macrotaskpartitioner.h:63
friend std::ostream & operator<<(std::ostream &os, const Batch_1D &batch)
Definition: macrotaskpartitioner.h:122
Batch_1D(const long &begin, const long &end)
Definition: macrotaskpartitioner.h:73
bool is_full_size() const
Definition: macrotaskpartitioner.h:83
tupleT copy_batch(const tupleT &arg) const
select the relevant vector elements from the argument tuple
Definition: macrotaskpartitioner.h:89
long size() const
Definition: macrotaskpartitioner.h:79
vecT copy_batch(const vecT v) const
given vector v, return those vector elements inside this batch
Definition: macrotaskpartitioner.h:115
long end
first and first past last index [begin,end)
Definition: macrotaskpartitioner.h:67
Batch_1D(const Slice &s)
Definition: macrotaskpartitioner.h:70
vecT insert_batch(vecT v, const vecT &v_batch) const
given vector v, copy vector elements of v_batch into vector
Definition: macrotaskpartitioner.h:107
Batch_1D()
Definition: macrotaskpartitioner.h:69
long begin
Definition: macrotaskpartitioner.h:67
bool operator==(const Batch_1D &other) const
Definition: macrotaskpartitioner.h:75
a batch consists of a 2D-input batch and a 1D-output batch: K-batch <- (I-batch, J-batch)
Definition: macrotaskpartitioner.h:132
Batch(Batch_1D input1, Batch_1D input2, Batch_1D result)
Definition: macrotaskpartitioner.h:150
Batch_1D result
Definition: macrotaskpartitioner.h:136
friend std::ostream & operator<<(std::ostream &os, const Batch &batch)
pretty print this batch
Definition: macrotaskpartitioner.h:176
vecT insert_result_batch(vecT v, const vecT &v_batch) const
copy v_batch into the result vector
Definition: macrotaskpartitioner.h:171
Batch()
Definition: macrotaskpartitioner.h:138
Batch(Batch_1D input1, Batch_1D result)
Definition: macrotaskpartitioner.h:149
tupleT copy_input_batch(const tupleT &arg) const
select the relevant vector elements from the argument tuple
Definition: macrotaskpartitioner.h:161
Batch(const Batch &other)
Definition: macrotaskpartitioner.h:139
Batch & operator=(const Batch &other)
Definition: macrotaskpartitioner.h:142
std::size_t size_of_input() const
Definition: macrotaskpartitioner.h:153
std::vector< Batch_1D > input
Definition: macrotaskpartitioner.h:135
partition one (two) vectors into 1D (2D) batches.
Definition: macrotaskpartitioner.h:190
std::string policy
how to partition the batches
Definition: macrotaskpartitioner.h:198
MacroTaskPartitioner & set_dimension(const std::size_t &n)
Definition: macrotaskpartitioner.h:213
MacroTaskPartitioner & set_nsubworld(const long &n)
Definition: macrotaskpartitioner.h:205
virtual partitionT do_partitioning(const std::size_t &vsize1, const std::size_t &vsize2, const std::string policy) const
override this if you want your own partitioning
Definition: macrotaskpartitioner.h:249
std::size_t nsubworld
number of worlds (try to have enough batches for all worlds)
Definition: macrotaskpartitioner.h:197
std::list< std::pair< Batch, double > > partitionT
Definition: macrotaskpartitioner.h:194
MacroTaskPartitioner & set_policy(const std::string &n)
Definition: macrotaskpartitioner.h:209
partitionT partition_tasks(const tupleT &argtuple) const
this will be called by MacroTask, it will always partition first (and possibly second) vector of argu...
Definition: macrotaskpartitioner.h:228
virtual ~MacroTaskPartitioner()
Definition: macrotaskpartitioner.h:203
std::size_t dimension
partition one or two vectors
Definition: macrotaskpartitioner.h:199
MacroTaskPartitioner & set_max_batch_size(const long &n)
Definition: macrotaskpartitioner.h:221
MacroTaskPartitioner()
Definition: macrotaskpartitioner.h:201
partitionT do_2d_partition(const std::size_t vsize, const std::size_t v2size, const std::string policy) const
outer product of 2 1d-partitionings – result batches correspond to first input batches
Definition: macrotaskpartitioner.h:282
partitionT do_1d_partition(const std::size_t vsize, const std::string policy) const
Definition: macrotaskpartitioner.h:259
MacroTaskPartitioner & set_min_batch_size(const long &n)
Definition: macrotaskpartitioner.h:217
virtual double compute_priority(const Batch &batch) const
Definition: macrotaskpartitioner.h:296
std::size_t min_batch_size
minimum batch size
Definition: macrotaskpartitioner.h:195
std::size_t max_batch_size
maximum batch size (for memory management)
Definition: macrotaskpartitioner.h:196
A slice defines a sub-range or patch of a dimension.
Definition: slice.h:103
Fcwf copy(Fcwf psi)
Definition: fcwf.cc:338
Tensor< typename Tensor< T >::scalar_type > arg(const Tensor< T > &t)
Return a new tensor holding the argument of each element of t (complex types only)
Definition: tensor.h:2502
static const double v
Definition: hatom_sf_dirac.cc:20
#define max(a, b)
Definition: lda.h:51
Defines madness::MadnessException for exception handling.
#define MADNESS_CHECK(condition)
Check a condition — even in a release build the condition is always evaluated so it can have side eff...
Definition: madness_exception.h:190
#define MADNESS_EXCEPTION(msg, value)
Macro for throwing a MADNESS exception.
Definition: madness_exception.h:119
File holds all helper structures necessary for the CC_Operator and CC2 class.
Definition: DFParameters.h:10
constexpr auto decay_types(std::tuple< Ts... > const &) -> std::tuple< std::remove_cv_t< std::remove_reference_t< Ts >>... >
constexpr std::size_t get_index_of_first_vector_argument()
given a tuple return the index of the first argument that is a vector of Function<T,...
Definition: macrotaskpartitioner.h:37
decltype(decay_types(std::declval< T >())) decay_tuple
Definition: macrotaskpartitioner.h:22
std::string type(const PairType &n)
Definition: PNOParameters.h:18
std::string name(const FuncType &type, const int ex=-1)
Definition: ccpairfunction.h:28
constexpr std::size_t get_index_of_second_vector_argument()
given a tuple return the index of the second argument that is a vector of Function<T,...
Definition: macrotaskpartitioner.h:58
Definition: mraimpl.h:50
Definition: macrotaskpartitioner.h:25
Definition: macrotaskpartitioner.h:32
static const double_complex I
Definition: tdse1d.cc:164