33#ifndef MADNESS_MRA_IBDEUX_H__INCLUDED
34#define MADNESS_MRA_IBDEUX_H__INCLUDED
44#include <unordered_map>
58 template<
typename T, std::
size_t NDIM>
61 template<
typename T, std::
size_t NDIM>
64 template <std::
size_t NDIM>
67 typedef std::pair<keyT,ProcessID>
pairT;
70 typedef std::unordered_map<keyT,ProcessID,Hash<keyT>>
mapT;
82 map.reserve(
v.size());
83 for (
const pairT& entry :
v) {
85 const bool inserted =
map.insert(entry).second;
99 if (it !=
map.end())
return it->second;
100 if (
k.level() <= 0) {
115 template <std::
size_t NDIM>
141 for (
int i=0; i<
nchild; ++i)
149 for (
int i=0; i<
nchild; ++i)
154 for (
int i=0; i<
nchild; ++i)
179 void add(
double cost,
bool got_kids) {
190 if (child.
level() > 1) {
207 const keyT child = kit.key();
220 const keyT child = kit.key();
221 int ind =
index(child);
225 for (
int i=0; i<
nchild; ++i) {
226 for (
int j=i+1; j<
nchild; ++j) {
227 if (vals[i] < vals[j]) {
228 std::swap(vals[i],vals[j]);
229 std::swap(keys[i],keys[j]);
235 for (
int i=0; i<
nchild; ++i) {
247 template <
typename Archive>
254 template <std::
size_t NDIM>
265 template <
typename T,
typename costT>
271 if (
lb->tree.is_local(key))
283 const keyT& key = it->first;
284 const nodeT& node = it->second;
293 total =
tree.find(key0).get()->second.get_total_cost();
295 world.gop.broadcast(total,
tree.owner(key0));
302 static bool compare(
const std::pair<keyT,double>&
a,
const std::pair<keyT,double>&
b) {
303 return a.second <
b.second;
315 template <
typename T,
typename costT>
324 if (it !=
tree.end()) {
325 for (
int i=0; i<key.level(); ++i) std::cout <<
" ";
326 print(key, it->second.get_total_cost());
328 if (it->second.has_children()) {
350 std::ostream& os = std::cout) {
352 std::vector<double> cost(
nproc, 0.0);
356 if (it->second.is_deleted())
continue;
357 cost[
pmap->owner(it->first)] += it->second.get_total_cost();
361 if (
world.rank() != 0)
return;
365 double mn = std::numeric_limits<double>::max();
366 for (
double c : cost) {
371 const double avg = (
nproc > 0) ? total /
nproc : 0.0;
372 const int barwidth = 40;
374 std::ios::fmtflags saved_flags = os.flags();
375 std::streamsize saved_prec = os.precision();
377 os <<
"=== Load balance summary: " << label <<
" ===\n";
378 os << std::fixed << std::setprecision(2)
379 <<
" total=" << total
381 <<
" max/avg=" << (avg > 0.0 ? mx / avg : 0.0);
382 if (mn > 0.0) os <<
" max/min=" << mx / mn;
385 int n = (mx > 0.0) ?
static_cast<int>(std::lround(barwidth * cost[
p] / mx)) : 0;
387 if (n > barwidth) n = barwidth;
388 os <<
" rank " << std::setw(3) <<
p <<
" |"
389 << std::string(n,
'#')
390 << std::string(barwidth - n,
' ')
391 <<
"| " << std::setw(10) << cost[
p]
392 <<
" (" << (avg > 0.0 ? cost[
p] / avg : 0.0) <<
"x avg)\n";
394 os <<
"================================" << std::endl;
396 os.flags(saved_flags);
397 os.precision(saved_prec);
411 std::shared_ptr< WorldDCPmapInterface<keyT> >
load_balance(
double fac = 1.0,
bool printstuff=
false) {
414 const double total =
sum();
417 MADNESS_CHECK_THROW(std::isfinite(total),
"LoadBalanceDeux: the cost function returned a non-finite cost");
418 double avg = total/(
world.size()*fac);
430 std::vector< std::pair<keyT,double> > results;
433 if (!it->second.is_deleted()) {
434 results.push_back(std::make_pair(it->first,it->second.get_total_cost()));
437 results =
world.gop.concat0(results, 128*1024*1024);
440 std::vector< std::pair<keyT,ProcessID> >
map;
442 if (
world.rank() == 0) {
444 std::sort(results.begin(), results.end(),
compare);
446 print(
"THESE ARE THE INITIAL SUBTREES");
447 for (
unsigned int i=0; i<results.size(); ++i)
print(i,results[i]);
451 map.reserve(results.size());
455 std::priority_queue<CostPerProc> costs;
456 for (
unsigned int p=0;
p<
nproc && !results.empty(); ++
p) {
457 const std::pair<keyT,double>&
f = results.back();
459 map.push_back(std::make_pair(
f.first,
p));
464 while (!results.empty()) {
465 const std::pair<keyT,double>&
f = results.back();
468 top.
cost +=
f.second;
470 map.push_back(std::make_pair(
f.first,top.
proc));
474 print(
"THIS IS THE MAP");
476 print(
"THESE ARE THE COSTS PER PROCESSOR");
477 while (!costs.empty()) {
478 print(costs.top().proc,costs.top().cost);
485 world.gop.broadcast_serializable(
map, 0);
An integer with atomic set, get, read+increment, read+decrement, and decrement+test operations.
Definition atomicint.h:126
FunctionDefaults holds default paramaters as static class members.
Definition funcdefaults.h:101
FunctionNode holds the coefficients, etc., at each node of the 2^NDIM-tree.
Definition funcimpl.h:136
bool has_children() const
Returns true if this node has children.
Definition funcimpl.h:217
A multiresolution adaptive numerical function.
Definition mra.h:141
A future is a possibly yet unevaluated value.
Definition future.h:370
T & get(bool dowork=true) &
Gets the value, waiting if necessary.
Definition future.h:571
Iterates in lexical order thru all children of a key.
Definition key.h:624
Key is the index for a node of the 2^NDIM-tree.
Definition key.h:71
Level level() const
Definition key.h:170
Key parent(int generation=1) const
Returns the key of the parent.
Definition key.h:366
const Vector< Translation, NDIM > & translation() const
Definition key.h:175
ProcessID owner(const keyT &key) const
Definition lbdeux.h:94
void print() const
Definition lbdeux.h:108
Level max_level
Deepest level of any entry in map.
Definition lbdeux.h:72
Key< NDIM > keyT
Definition lbdeux.h:66
mapT map
Definition lbdeux.h:71
LBDeuxPmap(const std::vector< pairT > &v, const ProcessID nproc)
Definition lbdeux.h:80
mapT::const_iterator iteratorT
Definition lbdeux.h:73
std::unordered_map< keyT, ProcessID, Hash< keyT > > mapT
Definition lbdeux.h:70
std::pair< keyT, ProcessID > pairT
Definition lbdeux.h:67
void add(double cost, bool got_kids)
Accumulates cost into this node.
Definition lbdeux.h:179
double get_total_cost() const
Definition lbdeux.h:169
LBNodeDeux()
Definition lbdeux.h:138
void serialize(Archive &ar)
Definition lbdeux.h:248
Key< NDIM > keyT
Definition lbdeux.h:118
void partition(const treeT &tree, const keyT &key, double avg)
Descends tree deleting all except internal nodes and sub-tree parents.
Definition lbdeux.h:214
bool is_deleted() const
True if partitioning logically deleted this node, so it is not a subtree root.
Definition lbdeux.h:174
bool gotkids
Definition lbdeux.h:125
AtomicInt nsummed
Definition lbdeux.h:128
LBNodeDeux< NDIM > & operator=(const LBNodeDeux< NDIM > &other)
Definition lbdeux.h:153
double total_cost
Definition lbdeux.h:124
bool deleted
Set by deleter(). A retained node can have any cost, even a negative one.
Definition lbdeux.h:126
static const int nchild
Definition lbdeux.h:117
bool has_children() const
Definition lbdeux.h:165
WorldContainer< keyT, nodeT > treeT
Definition lbdeux.h:120
int index(const keyT &key)
Computes index of child key in this node using last bit of translations.
Definition lbdeux.h:131
LBNodeDeux(const LBNodeDeux< NDIM > &other)
Definition lbdeux.h:145
double my_cost
Definition lbdeux.h:123
double child_cost[nchild]
Definition lbdeux.h:122
LBNodeDeux< NDIM > nodeT
Definition lbdeux.h:119
void deleter(const treeT &tree, const keyT &key)
Logically deletes this node and its descendants.
Definition lbdeux.h:203
void sum(const treeT &tree, const keyT &child, double value)
Accumulates cost up the tree from children.
Definition lbdeux.h:185
Key< NDIM > keyT
Definition lbdeux.h:256
World & world
Definition lbdeux.h:261
treeT::iterator iteratorT
Definition lbdeux.h:259
treeT tree
Definition lbdeux.h:262
LBNodeDeux< NDIM > nodeT
Definition lbdeux.h:257
std::shared_ptr< WorldDCPmapInterface< keyT > > load_balance(double fac=1.0, bool printstuff=false)
Actually does the partitioning of the tree.
Definition lbdeux.h:411
void print_tree(const keyT &key=keyT(0))
Printing for the curious.
Definition lbdeux.h:321
treeT::const_iterator const_iteratorT
Definition lbdeux.h:260
double sum()
Sums costs up the tree returning to everyone the total cost.
Definition lbdeux.h:279
static bool compare(const std::pair< keyT, double > &a, const std::pair< keyT, double > &b)
Used to sort results into descending order.
Definition lbdeux.h:302
void add_tree(const Function< T, NDIM > &f, const costT &costfn, bool fence=false)
Accumulates cost from a function.
Definition lbdeux.h:316
WorldContainer< keyT, nodeT > treeT
Definition lbdeux.h:258
LoadBalanceDeux(World &world)
Definition lbdeux.h:308
void print_cost_per_rank(const std::string &label, const std::shared_ptr< WorldDCPmapInterface< keyT > > &pmap, std::ostream &os=std::cout)
Definition lbdeux.h:348
Makes a distributed container with specified attributes.
Definition worlddc.h:1302
implT::const_iterator const_iterator
Definition worlddc.h:1310
implT::iterator iterator
Definition worlddc.h:1309
Interface to be provided by any process map.
Definition worlddc.h:128
A parallel world class.
Definition world.h:134
char * p(char *buf, const char *name, int k, int initial_level, double thresh, int order)
Definition derivatives.cc:72
Provides FunctionDefaults and utilities for coordinate transformation.
archive_array< unsigned char > wrap_opaque(const T *, std::size_t)
Factory function to wrap a pointer to contiguous data as an opaque (uchar) archive_array.
Definition archive.h:926
static const double v
Definition hatom_sf_dirac.cc:20
Multidimension Key for MRA tree and associated iterators.
Macros and tools pertaining to the configuration of MADNESS.
#define MADNESS_EXCEPTION(msg, value)
Macro for throwing a MADNESS exception.
Definition madness_exception.h:119
#define MADNESS_CHECK_THROW(condition, msg)
Check a condition — even in a release build the condition is always evaluated so it can have side eff...
Definition madness_exception.h:207
Namespace for all elements and tools of MADNESS.
Definition DFConvergence.h:9
std::shared_ptr< WorldDCPmapInterface< Key< NDIM > > > FunctionDefaults< NDIM >::pmap
Definition mraimpl.h:3898
int FunctionDefaults< NDIM >::k
Definition mraimpl.h:3878
ConcurrentHashMap< hashT, std::shared_ptr< GaussianConvolution1D< double > > > GaussianConvolution1DCache< double >::map
Definition convolution1d.h:1073
int Level
Definition key.h:60
NDIM & f
Definition mra.h:2817
void print(const T &t, Ts &&... ts)
Print items to std::cout (items separated by spaces) and terminate with a new line.
Definition print.h:232
const Future< void > Future< void >::value
Definition future.cc:44
static const double b
Definition nonlinschro.cc:119
static const double d
Definition nonlinschro.cc:121
static const double a
Definition nonlinschro.cc:118
static const double c
Definition relops.cc:10
CostPerProc(double cost, int proc)
Definition lbdeux.h:404
int proc
Definition lbdeux.h:402
bool operator<(const CostPerProc &other) const
Definition lbdeux.h:405
double cost
Definition lbdeux.h:401
CostPerProc()
Definition lbdeux.h:403
void operator()(const keyT &key, const FunctionNode< T, NDIM > &node) const
Definition lbdeux.h:270
const costT & costfn
Definition lbdeux.h:268
LoadBalanceDeux * lb
Definition lbdeux.h:267
add_op(LoadBalanceDeux *lb, const costT &costfn)
Definition lbdeux.h:269
static constexpr ProcessID nproc
Rank bound for the hand-written maps, which use the ranks 0, 1 and 2.
Definition test_lbdeux.cc:24
int task(int i)
Definition test_runtime.cpp:4
constexpr std::size_t NDIM
Definition testgconv.cc:54
Implements WorldContainer.
int ProcessID
Used to clearly identify process number/rank.
Definition worldtypes.h:43