Block-Structured AMR Software Framework
AMReX_DistributionMapping.H
Go to the documentation of this file.
1 #ifndef BL_DISTRIBUTIONMAPPING_H
2 #define BL_DISTRIBUTIONMAPPING_H
3 #include <AMReX_Config.H>
4 
5 #include <AMReX.H>
6 #include <AMReX_Array.H>
7 #include <AMReX_Vector.H>
8 #include <AMReX_Box.H>
9 #include <AMReX_REAL.H>
11 
12 #include <map>
13 #include <limits>
14 #include <memory>
15 #include <cstddef>
16 #include <iosfwd>
17 
18 namespace amrex {
19 
20 class BoxArray;
21 class MultiFab;
22 template <typename T> class FabArray;
23 template <typename T> class LayoutData;
24 class FabArrayBase;
25 
41 {
42  public:
43 
44  template <typename T> friend class FabArray;
45  friend class FabArrayBase;
46 
49 
51  DistributionMapping () noexcept;
52 
54  DistributionMapping (const DistributionMapping& rhs) = default;
55 
57  DistributionMapping& operator= (const DistributionMapping& rhs) = default;
58 
60  DistributionMapping (DistributionMapping&& rhs) noexcept = default;
61 
63  DistributionMapping& operator= (DistributionMapping&& rhs) noexcept = default;
64 
66  ~DistributionMapping() noexcept = default;
67 
71  explicit DistributionMapping (const Vector<int>& pmap);
72  explicit DistributionMapping (Vector<int>&& pmap) noexcept;
74  explicit DistributionMapping (const BoxArray& boxes,
75  int nprocs = ParallelDescriptor::NProcs());
81  const DistributionMapping& d2);
82 
88  void define (const BoxArray& boxes, int nprocs = ParallelDescriptor::NProcs());
93  void define (const Vector<int>& pmap);
94  void define (Vector<int>&& pmap) noexcept;
101  [[nodiscard]] const Vector<int>& ProcessorMap () const noexcept;
102 
104  [[nodiscard]] Long size () const noexcept { return Long(m_ref->m_pmap.size()); }
105  [[nodiscard]] Long capacity () const noexcept { return Long(m_ref->m_pmap.capacity()); }
106  [[nodiscard]] bool empty () const noexcept { return m_ref->m_pmap.empty(); }
107 
109  [[nodiscard]] Long linkCount () const noexcept { return m_ref.use_count(); }
110 
112  [[nodiscard]] int operator[] (int index) const noexcept { return m_ref->m_pmap[index]; }
113 
114  std::istream& readFrom (std::istream& is);
115 
116  std::ostream& writeOn (std::ostream& os) const;
117 
119  static void strategy (Strategy how);
120 
121  static Strategy strategy ();
122 
124  static void SFC_Threshold (int n);
125 
126  static int SFC_Threshold ();
127 
129  bool operator== (const DistributionMapping& rhs) const noexcept;
130 
132  bool operator!= (const DistributionMapping& rhs) const noexcept;
133 
134  void SFCProcessorMap (const BoxArray& boxes, const std::vector<Long>& wgts, int nprocs,
135  bool sort=true);
136  void SFCProcessorMap (const BoxArray& boxes, const std::vector<Long>& wgts, int nprocs,
137  Real& efficiency, bool sort=true);
138  void KnapSackProcessorMap (const std::vector<Long>& wgts, int nprocs,
139  Real* efficiency=nullptr,
140  bool do_full_knapsack=true,
142  bool sort=true);
143  void KnapSackProcessorMap (const DistributionMapping& olddm,
144  const std::vector<Long>& wgts, Real keep_ratio,
145  Real& old_efficiency, Real& new_efficiency,
146  int nmax=std::numeric_limits<int>::max());
147  void RoundRobinProcessorMap (int nboxes, int nprocs, bool sort=true);
148  void RoundRobinProcessorMap (const std::vector<Long>& wgts, int nprocs, bool sort=true);
149 
160  static void Initialize ();
161 
162  static void Finalize ();
163 
164  static bool SameRefs (const DistributionMapping& lhs,
165  const DistributionMapping& rhs)
166  { return lhs.m_ref == rhs.m_ref; }
167 
168  static DistributionMapping makeKnapSack (const MultiFab& weight,
169  int nmax=std::numeric_limits<int>::max());
170  static DistributionMapping makeKnapSack (const MultiFab& weight, Real& eff,
171  int nmax=std::numeric_limits<int>::max());
172  static DistributionMapping makeKnapSack (const Vector<Real>& rcost,
173  int nmax=std::numeric_limits<int>::max());
174  static DistributionMapping makeKnapSack (const Vector<Real>& rcost, Real& eff,
176  bool sort=true);
177 
202  static DistributionMapping makeKnapSack (const LayoutData<Real>& rcost_local,
203  Real& currentEfficiency, Real& proposedEfficiency,
205  bool broadcastToAll=true,
207  Real keep_ratio = Real(0.0));
208 
209  static DistributionMapping makeRoundRobin (const MultiFab& weight);
210  static DistributionMapping makeSFC (const MultiFab& weight, bool sort=true);
211  static DistributionMapping makeSFC (const MultiFab& weight, Real& eff, bool sort=true);
212  static DistributionMapping makeSFC (const Vector<Real>& rcost,
213  const BoxArray& ba, bool sort=true);
214  static DistributionMapping makeSFC (const Vector<Real>& rcost,
215  const BoxArray& ba, Real& eff, bool sort=true);
216 
237  static DistributionMapping makeSFC (const LayoutData<Real>& rcost_local,
238  Real& currentEfficiency, Real& proposedEfficiency,
239  bool broadcastToAll=true,
241 
246  static std::vector<std::vector<int> > makeSFC (const BoxArray& ba,
247  bool use_box_vol=true,
248  int nprocs=ParallelContext::NProcsSub() );
249 
257  template <typename T>
259  const std::vector<T>& cost,
260  Real* efficiency);
261 
262 private:
263 
264  const Vector<int>& getIndexArray ();
265  const std::vector<bool>& getOwnerShip ();
266 
268  void RoundRobinProcessorMap (const BoxArray& boxes, int nprocs);
269  void KnapSackProcessorMap (const BoxArray& boxes, int nprocs);
270  void SFCProcessorMap (const BoxArray& boxes, int nprocs);
271  void RRSFCProcessorMap (const BoxArray& boxes, int nprocs);
272 
273  using LIpair = std::pair<Long,int>;
274 
275  struct LIpairLT
276  {
277  bool operator () (const LIpair& lhs,
278  const LIpair& rhs) const noexcept
279  {
280  return lhs.first < rhs.first;
281  }
282  };
283 
284  struct LIpairGT
285  {
286  bool operator () (const LIpair& lhs,
287  const LIpair& rhs) const noexcept
288  {
289  return lhs.first > rhs.first;
290  }
291  };
292 
293  static void Sort (std::vector<LIpair>& vec, bool reverse);
294 
295  void RoundRobinDoIt (int nboxes,
296  int nprocs,
297  std::vector<LIpair>* LIpairV = nullptr,
298  bool sort = true);
299 
300  void KnapSackDoIt (const std::vector<Long>& wgts,
301  int nprocs,
302  Real& efficiency,
303  bool do_full_knapsack,
305  bool sort=true);
306 
307  void SFCProcessorMapDoIt (const BoxArray& boxes,
308  const std::vector<Long>& wgts,
309  int nprocs,
310  bool sort=true,
311  Real* efficiency=nullptr);
312 
313  void RRSFCDoIt (const BoxArray& boxes,
314  int nprocs);
315 
317  static void LeastUsedCPUs (int nprocs, Vector<int>& result);
322  static void LeastUsedTeams (Vector<int>& rteam, Vector<Vector<int> >& rworker, int nteams, int nworkers);
323 
325  using PVMF = void (DistributionMapping::*)(const BoxArray &, int);
326 
333  static PVMF m_BuildMap;
334 
335  struct Ref
336  {
337  friend class DistributionMapping;
338 
340  Ref () = default;
341 
342  explicit Ref (int len) : m_pmap(len) {}
343 
344  explicit Ref (const Vector<int>& pmap) : m_pmap(pmap) {}
345 
346  explicit Ref (Vector<int>&& pmap) noexcept : m_pmap(std::move(pmap)) {}
347 
349 
350  void clear () { m_pmap.clear(); m_index_array.clear(); m_ownership.clear(); }
351 
354  std::vector<bool> m_ownership;
355  };
356  //
358  std::shared_ptr<Ref> m_ref;
359 
360 public:
361  struct RefID {
362  constexpr RefID () noexcept {} // =default does not work due to a clang bug // NOLINT
363  explicit RefID (Ref* data_) noexcept : data(data_) {}
364  bool operator< (const RefID& rhs) const noexcept { return std::less<>{}(data,rhs.data); }
365  bool operator== (const RefID& rhs) const noexcept { return data == rhs.data; }
366  bool operator!= (const RefID& rhs) const noexcept { return data != rhs.data; }
367  [[nodiscard]] const Ref *dataPtr() const noexcept { return data; }
368  void PrintPtr(std::ostream &os) const { os << data << '\n'; }
369  friend std::ostream& operator<< (std::ostream& os, const RefID& id);
370  private:
371  Ref* data = nullptr;
372  };
373 
375  [[nodiscard]] RefID getRefID () const noexcept { return RefID { m_ref.get() }; }
376 };
377 
379 std::ostream& operator<< (std::ostream& os, const DistributionMapping& pmap);
380 
381 std::ostream& operator<< (std::ostream& os, const DistributionMapping::RefID& id);
382 
396 DistributionMapping MakeSimilarDM (const BoxArray& ba, const MultiFab& mf, const IntVect& ng);
397 
412 DistributionMapping MakeSimilarDM (const BoxArray& ba, const BoxArray& src_ba,
413  const DistributionMapping& src_dm, const IntVect& ng);
414 
415 template <typename T>
417  const DistributionMapping& dm, const std::vector<T>& cost, Real* efficiency)
418 {
419  const int nprocs = ParallelDescriptor::NProcs();
420  Vector<T> wgts(nprocs, T(0));
421 
422  const auto nboxes = int(dm.size());
423  for (int ibox = 0; ibox < nboxes; ++ibox) {
424  wgts[dm[ibox]] += cost[ibox];
425  }
426 
427  T max_weight = 0;
428  T sum_weight = 0;
429  for (auto const& w : wgts) {
430  max_weight = std::max(w, max_weight);
431  sum_weight += w;
432  }
433 
434  *efficiency = static_cast<Real>(sum_weight) /
435  (static_cast<Real>(nprocs) * static_cast<Real>(max_weight));
436 }
437 
438 }
439 
440 #endif /*BL_DISTRIBUTIONMAPPING_H*/
A collection of Boxes stored in an Array.
Definition: AMReX_BoxArray.H:549
Calculates the distribution of FABs to MPI processes.
Definition: AMReX_DistributionMapping.H:41
static void Initialize()
Initializes distribution strategy from ParmParse.
Definition: AMReX_DistributionMapping.cpp:107
int operator[](int index) const noexcept
Equivalent to ProcessorMap()[index].
Definition: AMReX_DistributionMapping.H:112
static DistributionMapping makeKnapSack(const MultiFab &weight, int nmax=std::numeric_limits< int >::max())
Definition: AMReX_DistributionMapping.cpp:1723
Long linkCount() const noexcept
Number of references to this DistributionMapping.
Definition: AMReX_DistributionMapping.H:109
void RRSFCProcessorMap(const BoxArray &boxes, int nprocs)
Definition: AMReX_DistributionMapping.cpp:1566
Long size() const noexcept
Length of the underlying processor map.
Definition: AMReX_DistributionMapping.H:104
void SFCProcessorMapDoIt(const BoxArray &boxes, const std::vector< Long > &wgts, int nprocs, bool sort=true, Real *efficiency=nullptr)
Definition: AMReX_DistributionMapping.cpp:1262
void define(const BoxArray &boxes, int nprocs=ParallelDescriptor::NProcs())
Build mapping out of BoxArray over nprocs processors. You need to call this if you built your Distrib...
Definition: AMReX_DistributionMapping.cpp:340
static bool SameRefs(const DistributionMapping &lhs, const DistributionMapping &rhs)
Definition: AMReX_DistributionMapping.H:164
void KnapSackDoIt(const std::vector< Long > &wgts, int nprocs, Real &efficiency, bool do_full_knapsack, int nmax=std::numeric_limits< int >::max(), bool sort=true)
Definition: AMReX_DistributionMapping.cpp:719
void RRSFCDoIt(const BoxArray &boxes, int nprocs)
Definition: AMReX_DistributionMapping.cpp:1533
static int SFC_Threshold()
Definition: AMReX_DistributionMapping.cpp:89
bool empty() const noexcept
Definition: AMReX_DistributionMapping.H:106
bool operator!=(const DistributionMapping &rhs) const noexcept
Are the distributions different?
Definition: AMReX_DistributionMapping.cpp:101
std::ostream & writeOn(std::ostream &os) const
Definition: AMReX_DistributionMapping.cpp:2010
static void LeastUsedTeams(Vector< int > &rteam, Vector< Vector< int > > &rworker, int nteams, int nworkers)
rteam: Least used ordering of Teams rworker[i]: Least used ordering of team workers for Team i
Definition: AMReX_DistributionMapping.cpp:239
static Strategy m_Strategy
Everyone uses the same Strategy – defaults to SFC.
Definition: AMReX_DistributionMapping.H:328
DistributionMapping() noexcept
The default constructor.
Definition: AMReX_DistributionMapping.cpp:303
static void Sort(std::vector< LIpair > &vec, bool reverse)
Definition: AMReX_DistributionMapping.cpp:177
std::shared_ptr< Ref > m_ref
The data – a reference-counted pointer to a Ref.
Definition: AMReX_DistributionMapping.H:358
static DistributionMapping makeRoundRobin(const MultiFab &weight)
Definition: AMReX_DistributionMapping.cpp:1746
void KnapSackProcessorMap(const std::vector< Long > &wgts, int nprocs, Real *efficiency=nullptr, bool do_full_knapsack=true, int nmax=std::numeric_limits< int >::max(), bool sort=true)
Definition: AMReX_DistributionMapping.cpp:845
std::pair< Long, int > LIpair
Definition: AMReX_DistributionMapping.H:273
const std::vector< bool > & getOwnerShip()
Definition: AMReX_DistributionMapping.cpp:1943
bool operator==(const DistributionMapping &rhs) const noexcept
Are the distributions equal?
Definition: AMReX_DistributionMapping.cpp:95
static DistributionMapping makeSFC(const MultiFab &weight, bool sort=true)
Definition: AMReX_DistributionMapping.cpp:1757
void RoundRobinProcessorMap(int nboxes, int nprocs, bool sort=true)
Definition: AMReX_DistributionMapping.cpp:450
const Vector< int > & getIndexArray()
Definition: AMReX_DistributionMapping.cpp:1924
void SFCProcessorMap(const BoxArray &boxes, const std::vector< Long > &wgts, int nprocs, bool sort=true)
Definition: AMReX_DistributionMapping.cpp:1488
const Vector< int > & ProcessorMap() const noexcept
Returns a constant reference to the mapping of boxes in the underlying BoxArray to the CPU that holds...
Definition: AMReX_DistributionMapping.cpp:47
RefID getRefID() const noexcept
This gives a unique ID of the reference, which is different from dmID above.
Definition: AMReX_DistributionMapping.H:375
static Strategy strategy()
Definition: AMReX_DistributionMapping.cpp:53
void RoundRobinDoIt(int nboxes, int nprocs, std::vector< LIpair > *LIpairV=nullptr, bool sort=true)
Definition: AMReX_DistributionMapping.cpp:366
static void Finalize()
Definition: AMReX_DistributionMapping.cpp:167
static void LeastUsedCPUs(int nprocs, Vector< int > &result)
Least used ordering of CPUs (by # of bytes of FAB data).
Definition: AMReX_DistributionMapping.cpp:192
Strategy
The distribution strategies.
Definition: AMReX_DistributionMapping.H:48
@ UNDEFINED
Definition: AMReX_DistributionMapping.H:48
@ KNAPSACK
Definition: AMReX_DistributionMapping.H:48
@ RRSFC
Definition: AMReX_DistributionMapping.H:48
@ ROUNDROBIN
Definition: AMReX_DistributionMapping.H:48
@ SFC
Definition: AMReX_DistributionMapping.H:48
void(DistributionMapping::*)(const BoxArray &, int) PVMF
A useful typedef.
Definition: AMReX_DistributionMapping.H:325
Long capacity() const noexcept
Definition: AMReX_DistributionMapping.H:105
static PVMF m_BuildMap
Pointer to one of the CreateProcessorMap() functions. Corresponds to the one specified by m_Strategy.
Definition: AMReX_DistributionMapping.H:333
std::istream & readFrom(std::istream &is)
Definition: AMReX_DistributionMapping.cpp:1989
static void ComputeDistributionMappingEfficiency(const DistributionMapping &dm, const std::vector< T > &cost, Real *efficiency)
Computes the average cost per MPI rank given a distribution mapping global cost vector.
Definition: AMReX_DistributionMapping.H:416
Base class for FabArray.
Definition: AMReX_FabArrayBase.H:41
An Array of FortranArrayBox(FAB)-like Objects.
Definition: AMReX_FabArray.H:344
a one-thingy-per-box distributed object
Definition: AMReX_LayoutData.H:13
A collection (stored as an array) of FArrayBox objects.
Definition: AMReX_MultiFab.H:38
This class is a thin wrapper around std::vector. Unlike vector, Vector::operator[] provides bound che...
Definition: AMReX_Vector.H:27
int NProcs()
Process ID in MPI_COMM_WORLD.
Definition: AMReX_MPMD.cpp:122
int NProcsSub() noexcept
number of ranks in current frame
Definition: AMReX_ParallelContext.H:74
int NProcs() noexcept
return the number of MPI ranks local to the current Parallel Context
Definition: AMReX_ParallelDescriptor.H:243
int IOProcessorNumber() noexcept
Definition: AMReX_ParallelDescriptor.H:266
@ max
Definition: AMReX_ParallelReduce.H:17
Definition: AMReX_Amr.cpp:49
IntVectND< AMREX_SPACEDIM > IntVect
Definition: AMReX_BaseFwd.H:30
DistributionMapping MakeSimilarDM(const BoxArray &ba, const MultiFab &mf, const IntVect &ng)
Function that creates a DistributionMapping "similar" to that of a MultiFab.
Definition: AMReX_DistributionMapping.cpp:2023
const int[]
Definition: AMReX_BLProfiler.cpp:1664
std::ostream & operator<<(std::ostream &os, AmrMesh const &amr_mesh)
Definition: AMReX_AmrMesh.cpp:1236
Definition: AMReX_DistributionMapping.H:285
bool operator()(const LIpair &lhs, const LIpair &rhs) const noexcept
Definition: AMReX_DistributionMapping.H:286
Definition: AMReX_DistributionMapping.H:276
bool operator()(const LIpair &lhs, const LIpair &rhs) const noexcept
Definition: AMReX_DistributionMapping.H:277
Definition: AMReX_DistributionMapping.H:361
constexpr RefID() noexcept
Definition: AMReX_DistributionMapping.H:362
friend std::ostream & operator<<(std::ostream &os, const RefID &id)
Definition: AMReX_DistributionMapping.cpp:1982
bool operator==(const RefID &rhs) const noexcept
Definition: AMReX_DistributionMapping.H:365
void PrintPtr(std::ostream &os) const
Definition: AMReX_DistributionMapping.H:368
Ref * data
Definition: AMReX_DistributionMapping.H:371
const Ref * dataPtr() const noexcept
Definition: AMReX_DistributionMapping.H:367
bool operator!=(const RefID &rhs) const noexcept
Definition: AMReX_DistributionMapping.H:366
bool operator<(const RefID &rhs) const noexcept
Definition: AMReX_DistributionMapping.H:364
RefID(Ref *data_) noexcept
Definition: AMReX_DistributionMapping.H:363
Definition: AMReX_DistributionMapping.H:336
Ref()=default
Constructors to match those in DistributionMapping ....
std::vector< bool > m_ownership
true ownership
Definition: AMReX_DistributionMapping.H:354
Ref(const Vector< int > &pmap)
Definition: AMReX_DistributionMapping.H:344
Vector< int > m_pmap
index array for all boxes
Definition: AMReX_DistributionMapping.H:352
Vector< int > m_index_array
index array for local boxes owned by the team
Definition: AMReX_DistributionMapping.H:353
Ref(int len)
Definition: AMReX_DistributionMapping.H:342
void clear()
dtor, copy-ctor, copy-op=, move-ctor, and move-op= are compiler generated.
Definition: AMReX_DistributionMapping.H:350
Ref(Vector< int > &&pmap) noexcept
Definition: AMReX_DistributionMapping.H:346