DASH  0.3.0
LoadBalancePattern.h
1 #ifndef DASH__LOAD_BALANCE_PATTERN_H__INCLUDED
2 #define DASH__LOAD_BALANCE_PATTERN_H__INCLUDED
3 
4 #include <functional>
5 #include <array>
6 #include <type_traits>
7 
8 #include <dash/Types.h>
9 #include <dash/Distribution.h>
10 #include <dash/Exception.h>
11 #include <dash/Dimensional.h>
12 #include <dash/Cartesian.h>
13 #include <dash/Team.h>
14 
15 #include <dash/pattern/PatternProperties.h>
16 #include <dash/pattern/internal/PatternArguments.h>
17 
18 #include <dash/util/TeamLocality.h>
19 #include <dash/util/LocalityDomain.h>
20 
21 #include <dash/internal/Math.h>
22 #include <dash/internal/Logging.h>
23 
24 
25 namespace dash {
26 
28 {
29 private:
32 
33 public:
39  static std::vector<double> unit_weights(
40  const TeamLocality_t & tloc)
41  {
42  std::vector<double> unit_cpu_capacities;
43  double sum = 0;
44 
45  for (auto u : tloc.global_units()) {
46  auto unit_loc = tloc.unit_locality(u);
47  double unit_cpu_cap = unit_loc.num_cores() *
48  unit_loc.num_threads() *
49  unit_loc.cpu_mhz();
50  sum += unit_cpu_cap;
51  unit_cpu_capacities.push_back(unit_cpu_cap);
52  }
53  double mean = sum / tloc.global_units().size();
54  std::transform(unit_cpu_capacities.begin(),
55  unit_cpu_capacities.end(),
56  unit_cpu_capacities.begin(),
57 
58  [&](double v) { return v / mean; });
59  return unit_cpu_capacities;
60  }
61 };
62 
64 {
65 private:
68 
69 public:
98  static std::vector<double> unit_weights(
99  const TeamLocality_t & tloc)
100  {
101  std::vector<double> unit_mem_perc;
102 
103 #if 0
104  // TODO: Calculate and assign neutral weights for units located at
105  // cores with unknown memory bandwidth.
106 
107  std::vector<size_t> unit_mem_capacities;
108  size_t total_mem_capacity = 0;
109 
110  // Calculate average memory bandwidth first:
111  for (auto u : tloc.units()) {
112  auto & unit_loc = tloc.unit_locality(u);
113  size_t unit_mem_cap = std::max<int>(0, unit_loc.max_shmem_mbps());
114  if (unit_mem_cap > 0) {
115  total_mem_capacity += unit_mem_cap;
116  }
117  unit_mem_capacities.push_back(unit_mem_cap);
118  }
119  if (total_mem_capacity == 0) {
120  total_mem_capacity = tloc.units().size();
121  }
122  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_mem_bandwidth_weights",
123  total_mem_capacity);
124  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_mem_bandwidth_weights",
125  unit_mem_capacities);
126 
127  double avg_mem_capacity = static_cast<double>(total_mem_capacity) /
128  tloc.units().size();
129 
130  // Use average value for units with unknown memory bandwidth:
131  for (auto membw = unit_mem_capacities.begin();
132  membw != unit_mem_capacities.end(); ++membw) {
133  if (*membw <= 0) {
134  *membw = avg_mem_capacity;
135  }
136  }
137 #endif
138 
139  std::vector<double> unit_bytes_per_cycle;
140  double total_bytes_per_cycle = 0;
141 
142  // Calculating bytes/cycle per core for every unit:
143  for (auto u : tloc.global_units()) {
144  auto unit_loc = tloc.unit_locality(u);
145  double unit_mem_bw = std::max<int>(0, unit_loc.max_shmem_mbps());
146  double unit_core_fq = unit_loc.num_threads() *
147  unit_loc.cpu_mhz();
148  double unit_bps = unit_mem_bw / unit_core_fq;
149  unit_bytes_per_cycle.push_back(unit_bps);
150  total_bytes_per_cycle += unit_bps;
151  }
152 
153  double avg_bytes_per_cycle =
154  static_cast<double>(total_bytes_per_cycle) / tloc.global_units().size();
155 
156  unit_mem_perc.reserve(unit_bytes_per_cycle.size());
157  for (auto unit_bps : unit_bytes_per_cycle) {
158  unit_mem_perc.push_back(unit_bps / avg_bytes_per_cycle);
159  }
160  return unit_mem_perc;
161  }
162 };
163 
173 template<
174  dim_t NumDimensions,
175  typename CompBasedMeasure = UnitClockFreqMeasure,
176  typename MemBasedMeasure = BytesPerCycleMeasure,
177  MemArrange Arrangement = dash::ROW_MAJOR,
178  typename IndexType = dash::default_index_t >
180 
198 template<
199  typename CompBasedMeasure,
200  typename MemBasedMeasure,
201  MemArrange Arrangement,
202  typename IndexType >
204  1, CompBasedMeasure, MemBasedMeasure, Arrangement, IndexType>
205 {
206 private:
207  static const dim_t NumDimensions = 1;
208 
209 public:
210  static constexpr char const * PatternName = "LoadBalancePattern1D";
211 
212 public:
215  // Minimal number of blocks in every dimension, i.e. one block
216  // per unit.
218  // Block extents are constant for every dimension.
220  // Identical number of elements in every block.
222  // Size of blocks may differ.
224  // Partitioning is dynamic.
226  // Partitioning is load-balanced.
227 // pattern_partitioning_tag::load_balanced
231  // Number of blocks assigned to a unit may differ.
236  // Elements are contiguous in local memory within single block.
238  // Local element order corresponds to a logical linearization
239  // within single blocks.
242 
243 private:
245  typedef LoadBalancePattern<
246  NumDimensions,
247  CompBasedMeasure,
248  MemBasedMeasure,
249  Arrangement,
250  IndexType>
251  self_t;
253  typedef typename std::make_unsigned<IndexType>::type
254  SizeType;
260  BlockSpec_t;
264  TeamSpec_t;
266  SizeSpec_t;
268  ViewSpec_t;
269  typedef internal::PatternArguments<NumDimensions, IndexType>
270  PatternArguments_t;
275 
276 public:
277  typedef IndexType index_type;
278  typedef SizeType size_type;
279  typedef ViewSpec_t viewspec_type;
280  typedef struct {
281  team_unit_t unit;
282  IndexType index{};
283  } local_index_t;
284  typedef struct {
285  team_unit_t unit;
286  std::array<index_type, NumDimensions> coords;
287  } local_coords_t;
288 
289 public:
295  const SizeSpec_t & sizespec,
297  TeamLocality_t & team_loc)
298  : _size(sizespec.size()),
299  _unit_cpu_weights(
300  CompBasedMeasure::unit_weights(team_loc)),
301  _unit_membw_weights(
302  MemBasedMeasure::unit_weights(team_loc)),
303  _unit_load_weights(
304  initialize_load_weights(
305  _unit_cpu_weights,
306  _unit_membw_weights)),
307  _local_sizes(
308  initialize_local_sizes(
309  sizespec.size(),
310  team_loc)),
311  _block_offsets(
312  initialize_block_offsets(
313  _local_sizes)),
314  _memory_layout(
315  std::array<SizeType, 1> {{ _size }}),
316  _blockspec(
317  initialize_blockspec(
318  _local_sizes)),
319  _distspec(dash::BLOCKED),
320  _team(&team_loc.team()),
321  _myid(_team->myid()),
322  _teamspec(*_team),
323  _nunits(_team->size()),
324  _local_size(
325  initialize_local_extent(
326  _team->myid(),
327  _local_sizes)),
328  _local_memory_layout(
329  std::array<SizeType, 1> {{ _local_size }}),
330  _local_capacity(
331  initialize_local_capacity(
332  _local_sizes))
333  {
334  DASH_LOG_TRACE("LoadBalancePattern()", "(sizespec, dist, team)");
335  DASH_ASSERT_EQ(
336  _local_sizes.size(), _nunits,
337  "Number of given local sizes " << _local_sizes.size() << " " <<
338  "does not match number of units" << _nunits);
339  initialize_local_range();
340  DASH_LOG_TRACE("LoadBalancePattern()", "LoadBalancePattern initialized");
341  }
342 
348  const SizeSpec_t & sizespec,
350  dash::Team & team = dash::Team::All())
351  : LoadBalancePattern(sizespec, TeamLocality_t(team))
352  { }
353 
354  LoadBalancePattern(const self_t & other) = default;
355  LoadBalancePattern(self_t && other) = default;
356  self_t & operator=(const self_t & other) = default;
357  self_t & operator=(self_t && other) = default;
358 
359 
366  LoadBalancePattern(self_t & other)
367  : LoadBalancePattern(static_cast<const self_t &>(other))
368  { }
369 
375  const self_t & other) const
376  {
377  if (this == &other) {
378  return true;
379  }
380  // no need to compare all members as most are derived from
381  // constructor arguments.
382  return(
383  _size == other._size &&
384  _local_sizes == other._local_sizes &&
385  _teamspec == other._teamspec
386  );
387  }
388 
394  const self_t & other) const
395  {
396  return !(*this == other);
397  }
398 
404  IndexType lbegin() const
405  {
406  return _lbegin;
407  }
408 
414  IndexType lend() const
415  {
416  return _lend;
417  }
418 
422 
430  const std::array<IndexType, NumDimensions> & coords,
432  const ViewSpec_t & viewspec) const
433  {
434  return unit_at(coords[0] + viewspec.offset(0));
435  }
436 
443  const std::array<IndexType, NumDimensions> & g_coords) const
444  {
445  return unit_at(g_coords[0]);
446  }
447 
455  IndexType global_pos,
457  const ViewSpec_t & viewspec) const
458  {
459  return unit_at(global_pos + viewspec.offset(0));
460  }
461 
469  IndexType g_index) const
470  {
471  DASH_LOG_TRACE_VAR("LoadBalancePattern.unit_at()", g_index);
472 
473  for (team_unit_t unit_idx{0}; unit_idx < _nunits; ++unit_idx) {
474  if (g_index < _local_sizes[unit_idx]) {
475  DASH_LOG_TRACE_VAR("LoadBalancePattern.unit_at >", unit_idx);
476  return unit_idx;
477  }
478  g_index -= _local_sizes[unit_idx];
479  }
480  DASH_THROW(
482  "LoadBalancePattern.unit_at: " <<
483  "global index " << g_index << " is out of bounds");
484  }
485 
489 
499  IndexType extent(dim_t dim) const
500  {
501  DASH_ASSERT_EQ(
502  0, dim,
503  "Wrong dimension for Pattern::local_extent. " <<
504  "Expected dimension = 0, got " << dim);
505  return _size;
506  }
507 
519  IndexType local_extent(dim_t dim) const
520  {
521  DASH_ASSERT_EQ(
522  0, dim,
523  "Wrong dimension for Pattern::local_extent. " <<
524  "Expected dimension = 0, got " << dim);
525  return _local_size;
526  }
527 
539  std::array<SizeType, NumDimensions> local_extents(
540  team_unit_t unit) const
541  {
542  DASH_LOG_DEBUG_VAR("LoadBalancePattern.local_extents()", unit);
543  DASH_LOG_DEBUG_VAR("LoadBalancePattern.local_extents >",
544  _local_sizes[unit]);
545  return std::array<SizeType, 1> {{ _local_sizes[unit] }};
546  }
547 
551 
558  IndexType local_at(
560  const std::array<IndexType, NumDimensions> & local_coords,
562  const ViewSpec_t & viewspec) const
563  {
564  return local_coords[0] + viewspec.offset(0);
565  }
566 
572  IndexType local_at(
574  const std::array<IndexType, NumDimensions> & local_coords) const
575  {
576  return local_coords[0];
577  }
578 
587  local_coords_t local(
588  const std::array<IndexType, NumDimensions> & g_coords) const
589  {
590  local_index_t l_index = local(g_coords[0]);
591  local_coords_t l_coords;
592  l_coords.unit = l_index.unit;
593  l_coords.coords[0] = l_index.index;
594  return l_coords;
595  }
596 
604  local_index_t local(
605  IndexType g_index) const
606  {
607  DASH_LOG_TRACE_VAR("LoadBalancePattern.local()", g_index);
608  local_index_t l_index;
609 
610  for (team_unit_t unit_idx{0}; unit_idx < _nunits; ++unit_idx) {
611  if (g_index < _local_sizes[unit_idx]) {
612  l_index.unit = unit_idx;
613  l_index.index = g_index;
614  DASH_LOG_TRACE("LoadBalancePattern.local >",
615  "unit:", l_index.unit,
616  "index:", l_index.index);
617  return l_index;
618  }
619  g_index -= _local_sizes[unit_idx];
620  }
621  DASH_THROW(
623  "LoadBalancePattern.local: " <<
624  "global index " << g_index << " is out of bounds");
625  }
626 
633  std::array<IndexType, NumDimensions> local_coords(
634  const std::array<IndexType, NumDimensions> & g_coords) const
635  {
636  local_index_t l_index = local(g_coords[0]);
637  return std::array<IndexType, 1> {{ l_index.index }};
638  }
639 
646  local_index_t local_index(
647  const std::array<IndexType, NumDimensions> & g_coords) const
648  {
649  return local(g_coords[0]);
650  }
651 
655 
661  std::array<IndexType, NumDimensions> global(
662  team_unit_t unit,
663  const std::array<IndexType, NumDimensions> & local_coords) const
664  {
665  DASH_LOG_DEBUG_VAR("LoadBalancePattern.global()", unit);
666  DASH_LOG_DEBUG_VAR("LoadBalancePattern.global()", local_coords);
667  DASH_LOG_TRACE_VAR("LoadBalancePattern.global", _nunits);
668  if (_nunits < 2) {
669  return local_coords;
670  }
671  // Initialize global index with element phase (= local coords):
672  index_type glob_index = _block_offsets[unit] + local_coords[0];
673  DASH_LOG_TRACE_VAR("LoadBalancePattern.global >", glob_index);
674  return std::array<IndexType, 1> {{ glob_index }};
675  }
676 
682  std::array<IndexType, NumDimensions> global(
683  const std::array<IndexType, NumDimensions> & l_coords) const
684  {
685  return global(_team->myid(), l_coords);
686  }
687 
696  IndexType global(
697  team_unit_t unit,
698  IndexType l_index) const
699  {
700  return global(unit, std::array<IndexType, 1> {{ l_index }})[0];
701  }
702 
711  IndexType global(
712  IndexType l_index) const
713  {
714  return global(_team->myid(), std::array<IndexType, 1> {{ l_index }})[0];
715  }
716 
725  IndexType global_index(
726  team_unit_t unit,
727  const std::array<IndexType, NumDimensions> & l_coords) const
728  {
729  auto g_index = global(unit, l_coords[0]);
730  return g_index;
731  }
732 
736 
745  IndexType at(
746  const std::array<IndexType, NumDimensions> & g_coords) const
747  {
748  return local_coords(g_coords)[0];
749  }
750 
758  IndexType at(
759  const std::array<IndexType, NumDimensions> & g_coords,
760  const ViewSpec_t & viewspec) const
761  {
762  auto vs_coords = g_coords;
763  vs_coords[0] += viewspec.offset(0);
764  return local_coords(vs_coords)[0];
765  }
766 
774  template<typename ... Values>
775  IndexType at(IndexType value, Values ... values) const
776  {
777  static_assert(
778  sizeof...(values) == NumDimensions-1,
779  "Wrong parameter number");
780  std::array<IndexType, NumDimensions> inputindex = {
781  value, (IndexType)values...
782  };
783  return at(inputindex);
784  }
785 
789 
795  inline bool is_local(
796  IndexType index,
797  team_unit_t unit) const
798  {
799  DASH_LOG_TRACE_VAR("LoadBalancePattern.is_local()", index);
800  DASH_LOG_TRACE_VAR("LoadBalancePattern.is_local()", unit);
801  bool is_loc = index >= _block_offsets[unit] &&
802  (unit == _nunits-1 ||
803  index < _block_offsets[unit+1]);
804  DASH_LOG_TRACE_VAR("LoadBalancePattern.is_local >", is_loc);
805  return is_loc;
806  }
807 
814  inline bool is_local(
815  IndexType index) const
816  {
817  auto unit = team().myid();
818  DASH_LOG_TRACE_VAR("LoadBalancePattern.is_local()", index);
819  DASH_LOG_TRACE_VAR("LoadBalancePattern.is_local", unit);
820  bool is_loc = index >= _block_offsets[unit] &&
821  (unit == _nunits-1 ||
822  index < _block_offsets[unit+1]);
823  DASH_LOG_TRACE_VAR("LoadBalancePattern.is_local >", is_loc);
824  return is_loc;
825  }
826 
830 
834  const BlockSpec_t & blockspec() const
835  {
836  return _blockspec;
837  }
838 
844  index_type block_at(
846  const std::array<index_type, NumDimensions> & g_coords) const
847  {
848  DASH_LOG_TRACE_VAR("LoadBalancePattern.block_at()", g_coords);
849 
850  auto block_idx = static_cast<index_type>(unit_at(g_coords[0]));
851 
852  DASH_LOG_TRACE_VAR("LoadBalancePattern.block_at >", block_idx);
853  return block_idx;
854  }
855 
860  ViewSpec_t block(
861  index_type g_block_index) const
862  {
863  DASH_LOG_DEBUG_VAR("LoadBalancePattern<1>.block >", g_block_index);
864  index_type offset = _block_offsets[g_block_index];
865  auto block_size = _local_sizes[g_block_index];
866  std::array<index_type, NumDimensions> offsets = {{ offset }};
867  std::array<size_type, NumDimensions> extents = {{ block_size }};
868  ViewSpec_t block_vs(offsets, extents);
869  DASH_LOG_DEBUG_VAR("LoadBalancePattern<1>.block >", block_vs);
870  return block_vs;
871  }
872 
877  ViewSpec_t local_block(
878  index_type l_block_index) const
879  {
880  DASH_LOG_DEBUG_VAR("LoadBalancePattern<1>.local_block()", l_block_index);
881  DASH_ASSERT_EQ(
882  0, l_block_index,
883  "LoadBalancePattern always assigns exactly 1 block to a single unit");
884  index_type block_offset = _block_offsets[_team->myid()];
885  size_type block_size = _local_sizes[_team->myid()];
886  std::array<index_type, NumDimensions> offsets = {{ block_offset }};
887  std::array<size_type, NumDimensions> extents = {{ block_size }};
888  ViewSpec_t block_vs(offsets, extents);
889  DASH_LOG_DEBUG_VAR("LoadBalancePattern<1>.local_block >", block_vs);
890  return block_vs;
891  }
892 
897  ViewSpec_t local_block_local(
898  index_type l_block_index) const
899  {
900  DASH_LOG_DEBUG_VAR("LoadBalancePattern<1>.local_block_local >",
901  l_block_index);
902  size_type block_size = _local_sizes[_team->myid()];
903  std::array<index_type, NumDimensions> offsets = {{ 0 }};
904  std::array<size_type, NumDimensions> extents = {{ block_size }};
905  ViewSpec_t block_vs(offsets, extents);
906  DASH_LOG_DEBUG_VAR("LoadBalancePattern<1>.local_block_local >", block_vs);
907  return block_vs;
908  }
909 
917  SizeType blocksize(
919  dim_t dimension) const
920  {
921  return _local_capacity;
922  }
923 
932  SizeType max_blocksize() const
933  {
934  return _local_capacity;
935  }
936 
942  inline SizeType local_capacity() const
943  {
944  return _local_capacity;
945  }
946 
957  inline SizeType local_size(
958  team_unit_t unit = UNDEFINED_TEAM_UNIT_ID) const
959  {
960  if (unit == UNDEFINED_TEAM_UNIT_ID) {
961  unit = _myid;
962  }
963  return _local_sizes[unit];
964  }
965 
971  inline IndexType num_units() const
972  {
973  return _nunits;
974  }
975 
981  inline IndexType capacity() const
982  {
983  return _size;
984  }
985 
991  inline IndexType size() const
992  {
993  return _size;
994  }
995 
1000  inline dash::Team & team() const
1001  {
1002  return *_team;
1003  }
1004 
1008  const DistributionSpec_t & distspec() const
1009  {
1010  return _distspec;
1011  }
1012 
1018  SizeSpec_t sizespec() const
1019  {
1020  return SizeSpec_t(std::array<SizeType, 1> {{ _size }});
1021  }
1022 
1028  const std::array<SizeType, NumDimensions> & extents() const
1029  {
1030  return std::array<SizeType, 1> {{ _size }};
1031  }
1032 
1039  const TeamSpec_t & teamspec() const
1040  {
1041  return _teamspec;
1042  }
1043 
1050  std::array<IndexType, NumDimensions> coords(
1051  IndexType index) const
1052  {
1053  return std::array<IndexType, 1> {{ index }};
1054  }
1055 
1062  std::array<IndexType, NumDimensions> coords(
1063  IndexType index,
1064  const ViewSpec_t & viewspec) const
1065  {
1066  return std::array<IndexType, 1> {{ index + viewspec.offset(0) }};
1067  }
1068 
1072  constexpr static MemArrange memory_order()
1073  {
1074  return Arrangement;
1075  }
1076 
1080  constexpr static dim_t ndim()
1081  {
1082  return 1;
1083  }
1084 
1085  const std::vector<double> & unit_cpu_weights() const
1086  {
1087  return _unit_cpu_weights;
1088  }
1089 
1090  const std::vector<double> & unit_membw_weights() const
1091  {
1092  return _unit_membw_weights;
1093  }
1094 
1095  const std::vector<double> & unit_load_weights() const
1096  {
1097  return _unit_load_weights;
1098  }
1099 
1100 private:
1101 
1102  std::vector<double> initialize_load_weights(
1103  const std::vector<double> & cpu_weights,
1104  const std::vector<double> & membw_weights) const
1105  {
1106  std::vector<double> load_weights;
1107  if (cpu_weights.size() != membw_weights.size()) {
1108  DASH_THROW(
1110  "Number of CPU weights and SHMEM weights differ");
1111  }
1112  // Trying to resolve the "inverse Roofline model" here:
1113  // We do not know if the operations on the data that is distributed
1114  // using this pattern is memory-bound or computation-bound.
1115  //
1116  // Most basic model:
1117  // weight[u] = cpu_weight[u] * membw_weight[u]
1118  load_weights.reserve(cpu_weights.size());
1119  std::transform(cpu_weights.begin(), cpu_weights.end(),
1120  membw_weights.begin(),
1121  std::back_inserter(load_weights),
1122  std::multiplies<double>());
1123  dash::math::div_mean(load_weights.begin(), load_weights.end());
1124  return load_weights;
1125  }
1126 
1131  std::vector<size_type> initialize_local_sizes(
1132  size_type total_size,
1133  const TeamLocality_t & locality) const
1134  {
1135  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_local_sizes()", total_size);
1136  std::vector<size_type> l_sizes;
1137  auto nunits = locality.team().size();
1138  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_local_sizes()", nunits);
1139  if (nunits == 1) {
1140  l_sizes.push_back(total_size);
1141  }
1142  if (nunits <= 1) {
1143  return l_sizes;
1144  }
1145 
1146  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_local_sizes",
1147  _unit_load_weights);
1148 
1149  double balanced_lsize = static_cast<double>(total_size) / nunits;
1150 
1151  size_t assigned_capacity = 0;
1152  // Unit with maximum CPU capacity in team:
1153  team_unit_t max_cpu_cap_unit{0};
1154 
1155  // Maximum CPU capacity found:
1156  size_t unit_max_cpu_cap = 0;
1157  for (team_unit_t u{0}; u < nunits; u++) {
1158  double weight = _unit_load_weights[u];
1159  size_t unit_capacity = weight > 1
1160  ? std::ceil(weight * balanced_lsize)
1161  : std::floor(weight * balanced_lsize);
1162  if (unit_capacity > unit_max_cpu_cap) {
1163  max_cpu_cap_unit = u;
1164  unit_max_cpu_cap = unit_capacity;
1165  }
1166  assigned_capacity += unit_capacity;
1167  l_sizes.push_back(unit_capacity);
1168  }
1169  // Some elements might be unassigned due to rounding.
1170  // Assign them to the unit with highest CPU capacity:
1171  l_sizes[max_cpu_cap_unit] += (total_size - assigned_capacity);
1172 
1173  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_local_sizes >", l_sizes);
1174  return l_sizes;
1175  }
1176 
1177  BlockSpec_t initialize_blockspec(
1178  const std::vector<size_type> & local_sizes) const
1179  {
1180  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_blockspec", local_sizes);
1181  BlockSpec_t blockspec(
1182  std::array<size_type, 1> {{
1183  static_cast<size_type>(local_sizes.size())
1184  }});
1185  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_blockspec >", blockspec);
1186  return blockspec;
1187  }
1188 
1193  std::vector<size_type> initialize_block_offsets(
1194  const std::vector<size_type> & local_sizes) const
1195  {
1196  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_block_offsets", local_sizes);
1197  std::vector<size_type> block_offsets;
1198  if (local_sizes.size() > 0) {
1199  // NOTE: Assuming 1 block for every unit.
1200  block_offsets.push_back(0);
1201  for (size_type unit_idx = 0;
1202  unit_idx < local_sizes.size()-1;
1203  ++unit_idx)
1204  {
1205  auto block_offset = block_offsets[unit_idx] +
1206  local_sizes[unit_idx];
1207  block_offsets.push_back(block_offset);
1208  }
1209  }
1210  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_block_offsets >",
1211  block_offsets);
1212  return block_offsets;
1213  }
1214 
1218  SizeType initialize_local_capacity(
1219  const std::vector<size_type> & local_sizes) const
1220  {
1221  SizeType l_capacity = 0;
1222  if (_nunits == 0) {
1223  return 0;
1224  }
1225  DASH_LOG_TRACE_VAR("LoadBalancePattern.init_lcapacity", _nunits);
1226  // Local capacity is maximum number of elements assigned to a single
1227  // unit, i.e. the maximum local size:
1228  l_capacity = *(std::max_element(local_sizes.begin(),
1229  local_sizes.end()));
1230  DASH_LOG_DEBUG_VAR("LoadBalancePattern.init_lcapacity >", l_capacity);
1231  return l_capacity;
1232  }
1233 
1238  void initialize_local_range()
1239  {
1240  auto l_size = _local_size;
1241  DASH_LOG_DEBUG_VAR("LoadBalancePattern.init_local_range()", l_size);
1242  if (l_size == 0) {
1243  _lbegin = 0;
1244  _lend = 0;
1245  } else {
1246  // First local index transformed to global index
1247  _lbegin = global(0);
1248  // Index past last local index transformed to global index.
1249  // global(l_size) would be out of range, so we use the global index
1250  // to the last element and increment by 1:
1251  _lend = global(l_size - 1) + 1;
1252  }
1253  DASH_LOG_DEBUG_VAR("LoadBalancePattern.init_local_range >", _lbegin);
1254  DASH_LOG_DEBUG_VAR("LoadBalancePattern.init_local_range >", _lend);
1255  }
1256 
1260  SizeType initialize_local_extent(
1261  team_unit_t unit,
1262  const std::vector<size_type> & local_sizes) const
1263  {
1264  DASH_LOG_DEBUG_VAR("LoadBalancePattern.init_local_extent()", unit);
1265  if (local_sizes.size() == 0) {
1266  return 0;
1267  }
1268  // Local size of given unit:
1269  SizeType l_extent = local_sizes[unit];
1270  DASH_LOG_DEBUG_VAR("LoadBalancePattern.init_local_extent >", l_extent);
1271  return l_extent;
1272  }
1273 
1274 private:
1276  SizeType _size;
1278  std::vector<double> _unit_cpu_weights;
1281  std::vector<double> _unit_membw_weights;
1283  std::vector<double> _unit_load_weights;
1285  std::vector<size_type> _local_sizes;
1287  std::vector<size_type> _block_offsets;
1289  MemoryLayout_t _memory_layout;
1291  BlockSpec_t _blockspec;
1293  DistributionSpec_t _distspec;
1295  dash::Team * _team = nullptr;
1297  team_unit_t _myid;
1299  TeamSpec_t _teamspec;
1301  SizeType _nunits = 0;
1303  SizeType _local_size;
1305  LocalMemoryLayout_t _local_memory_layout;
1307  SizeType _local_capacity;
1309  IndexType _lbegin;
1311  IndexType _lend;
1312 
1313 }; // class LoadBalancePattern
1314 
1315 } // namespace dash
1316 
1317 #endif // DASH__LOAD_BALANCE_PATTERN_H__INCLUDED
IndexType at(IndexType value, Values ... values) const
Global coordinates to local index.
constexpr team_unit_t UNDEFINED_TEAM_UNIT_ID
Invalid local unit ID.
Definition: Types.h:341
local_index_t local_index(const std::array< IndexType, NumDimensions > &g_coords) const
Converts global coordinates to their associated unit and their respective local index.
All blocks have identical size.
bool is_local(IndexType index) const
Whether the given global index is local to the unit that created this pattern instance.
std::array< IndexType, NumDimensions > coords(IndexType index) const
Convert given global linear offset (index) to global cartesian coordinates.
IndexType at(const std::array< IndexType, NumDimensions > &g_coords) const
at
SizeType local_size(team_unit_t unit=UNDEFINED_TEAM_UNIT_ID) const
The actual number of elements in this pattern that are local to the calling unit in total...
const TeamSpec_t & teamspec() const
Cartesian arrangement of the Team containing the units to which this pattern&#39;s elements are mapped...
constexpr std::enable_if< std::is_integral< IndexType >::value, IndexType >::type index(IndexType idx)
Definition: Iterator.h:60
size_t size()
Return the number of units in the global team.
IndexType local_at(const std::array< IndexType, NumDimensions > &local_coords, const ViewSpec_t &viewspec) const
local
index_type block_at(const std::array< index_type, NumDimensions > &g_coords) const
Index of block at given global coordinates.
constexpr auto local(ViewType &v) -> typename std::enable_if<(std::is_pointer< typename ViewType::iterator >::value||(dash::view_traits< ViewValueT >::is_local::value)), ViewType &>::type
Definition: Local.h:28
This class is a simple memory pool which holds allocates elements of size ValueType.
Definition: AllOf.h:8
Local element order corresponds to a logical linearization within single blocks (if blocked) or withi...
SizeSpec_t sizespec() const
Size specification of the index space mapped by this pattern.
Specifies cartesian extents in a specific number of dimensions.
Definition: Cartesian.h:197
std::array< IndexType, NumDimensions > global(const std::array< IndexType, NumDimensions > &l_coords) const
Converts local coordinates of active unit to global coordinates.
std::array< IndexType, NumDimensions > global(team_unit_t unit, const std::array< IndexType, NumDimensions > &local_coords) const
global
std::array< IndexType, NumDimensions > local_coords(const std::array< IndexType, NumDimensions > &g_coords) const
Converts global coordinates to their associated unit&#39;s respective local coordinates.
Specifies view parameters for implementing submat, rows and cols.
Definition: Dimensional.h:430
IndexType local_extent(dim_t dim) const
The actual number of elements in this pattern that are local to the calling unit in the given dimensi...
int dim_t
Scalar type for a dimension value, with 0 indicating the first dimension.
Definition: Types.h:39
bool operator==(const self_t &other) const
Equality comparison operator.
static constexpr MemArrange memory_order()
Memory order followed by the pattern.
local_coords_t local(const std::array< IndexType, NumDimensions > &g_coords) const
Converts global coordinates to their associated unit and its respective local coordinates.
team_unit_t unit_at(IndexType global_pos, const ViewSpec_t &viewspec) const
Convert given global linear index to its assigned unit id.
The number of blocks assigned to units may differ.
const DistributionSpec_t & distspec() const
Distribution specification of this pattern.
Minimal number of blocks in every dimension, typically at most one block per unit.
IndexType at(const std::array< IndexType, NumDimensions > &g_coords, const ViewSpec_t &viewspec) const
Global coordinates and viewspec to local index.
Block extents are constant for every dimension.
ViewSpec_t local_block(index_type l_block_index) const
View spec (offset and extents) of block at local linear block index in global cartesian element space...
SizeType max_blocksize() const
Maximum number of elements in a single block in all dimensions.
constexpr std::enable_if< dash::view_traits< ViewType >::is_view::value &&dash::view_traits< ViewType >::is_local::value, const typename ViewType::global_type & >::type global(const ViewType &v)
Definition: Global.h:19
size_t size() const
The number of units in this team.
Definition: Team.h:498
static constexpr dim_t ndim()
Number of dimensions of the cartesian space partitioned by the pattern.
Cartesian space defined by extents in n dimensions.
Definition: Cartesian.h:26
IndexType lbegin() const
Resolves the global index of the first local element in the pattern.
internal::default_signed_index default_index_t
Signed integer type used as default for index values.
Definition: Types.h:59
A Team instance specifies a subset of all available units.
Definition: Team.h:41
IndexType global(IndexType l_index) const
Resolve an element&#39;s linear global index from the calling unit&#39;s local index of that element...
Elements are contiguous in local memory within a single block and thus indexed blockwise.
IndexType size() const
The number of elements arranged in this pattern.
ViewSpec_t local_block_local(index_type l_block_index) const
View spec (offset and extents) of block at local linear block index in local cartesian element space...
Defines a cartesian, totally-ordered index space by mapping linear indices to cartesian coordinates d...
Definition: Cartesian.h:239
pattern_layout_properties< pattern_layout_tag::blocked, pattern_layout_tag::linear > layout_properties
Satisfiable properties in pattern property category Layout:
team_unit_t unit_at(const std::array< IndexType, NumDimensions > &coords, const ViewSpec_t &viewspec) const
unit_at
SizeType local_capacity() const
Maximum number of elements assigned to a single unit.
Data range is partitioned dynamically.
IndexType global(team_unit_t unit, IndexType l_index) const
Resolve an element&#39;s linear global index from the given unit&#39;s local index of that element...
IndexType capacity() const
The maximum number of elements arranged in this pattern.
team_unit_t unit_at(const std::array< IndexType, NumDimensions > &g_coords) const
Convert given coordinate in pattern to its assigned unit id.
LoadBalancePattern(const SizeSpec_t &sizespec, TeamLocality_t &team_loc)
Constructor.
IndexType lend() const
Resolves the global index past the last local element in the pattern.
OutputIt transform(InputIt in_first, InputIt in_last, OutputIt out_first, UnaryOperation unary_op)
Apply a given function to elements in a range and store the result in another range, beginning at out_first.
IndexType local_at(const std::array< IndexType, NumDimensions > &local_coords) const
Convert given local coordinates to linear local offset (index).
Irregular dynamic pattern.
Hierarchical locality domains of a specified team.
Definition: TeamLocality.h:61
SizeType blocksize(dim_t dimension) const
Maximum number of elements in a single block in the given dimension.
struct dash::unit_id< dash::local_unit, dart_team_unit_t > team_unit_t
Unit ID to use for team-local IDs.
Definition: Types.h:319
Wrapper of a single dart_domain_locality_t object.
std::array< IndexType, NumDimensions > coords(IndexType index, const ViewSpec_t &viewspec) const
Convert given global linear offset (index) to global cartesian coordinates using viewspec.
IndexType num_units() const
The number of units to which this pattern&#39;s elements are mapped.
GlobIter max_element(const GlobIter &first, const GlobIter &last, Compare compare=Compare())
Finds an iterator pointing to the element with the greatest value in the range [first,last).
Definition: MinMax.h:332
pattern_partitioning_properties< pattern_partitioning_tag::minimal, pattern_partitioning_tag::rectangular, pattern_partitioning_tag::balanced, pattern_partitioning_tag::unbalanced, pattern_partitioning_tag::dynamic > partitioning_properties
Satisfiable properties in pattern property category Partitioning:
ViewSpec_t block(index_type g_block_index) const
View spec (offset and extents) of block at global linear block index in cartesian element space...
IndexType global_index(team_unit_t unit, const std::array< IndexType, NumDimensions > &l_coords) const
Resolve an element&#39;s linear global index from a given unit&#39;s local coordinates of that element...
dash::Team & team() const
The Team containing the units to which this pattern&#39;s elements are mapped.
local_index_t local(IndexType g_index) const
Converts global index to its associated unit and respective local index.
std::array< SizeType, NumDimensions > local_extents(team_unit_t unit) const
The actual number of elements in this pattern that are local to the given unit, by dimension...
const std::array< SizeType, NumDimensions > & extents() const
Size specification of the index space mapped by this pattern.
LoadBalancePattern(self_t &other)
Copy constructor using non-const lvalue reference parameter.
static Team & All()
The invariant Team instance containing all available units.
Definition: Team.h:213
static std::vector< double > unit_weights(const TeamLocality_t &tloc)
Returns unit CPU capacities as percentage of the team&#39;s total CPU capacity average, e.g.
see https://en.cppreference.com/w/cpp/feature_test for recommended feature tests
Definition: cstddef.h:8
static std::vector< double > unit_weights(const TeamLocality_t &tloc)
Shared memory bandwidth capacities of every unit factored by the mean memory bandwidth capacity of al...
pattern_mapping_properties< pattern_mapping_tag::unbalanced > mapping_properties
Satisfiable properties in pattern property category Mapping:
DistributionSpec describes distribution patterns of all dimensions,.
Definition: Dimensional.h:222
bool operator!=(const self_t &other) const
Inquality comparison operator.
Generic type of mapping properties of a model satisfying the Pattern concept.
LoadBalancePattern(const SizeSpec_t &sizespec, dash::Team &team=dash::Team::All())
Constructor.
team_unit_t unit_at(IndexType g_index) const
Convert given global linear index to its assigned unit id.