00001 // -*- C++ -*- 00002 /*************************************************************************** 00003 * 00004 * The IPPL Framework 00005 * 00006 * 00007 * Visit http://people.web.psi.ch/adelmann/ for more details 00008 * 00009 ***************************************************************************/ 00010 00011 #ifndef BINARY_BALANCER_H 00012 #define BINARY_BALANCER_H 00013 00015 /* 00016 00017 A fairly simple load balancer inspired by Dan Quinlan's MLB. 00018 00019 It does recursive binary subdivision of a FieldLayout domain, 00020 restricting the cuts to coordinate directions, so as to balance the 00021 workload. The "workload" is given by a Field of weights passed in. 00022 It decides on the cut axis by cutting the longest axis of a brick, 00023 and the location of that cut by balancing the weights on each side 00024 of the cut. The resulting distribution has one vnode per processor. 00025 00026 This is restricted to a processor number that is a power of two. 00027 00028 It performs log(P) parallel reductions. 00029 00030 It does nothing fancy when deciding on the splits to try to make the 00031 new paritioning close to the previous. The same set of weights will 00032 always give the same repartitioning, but similar sets of weights 00033 could result in quite different partitionings. 00034 00035 There are two functions defined here: 00036 00037 NDIndex<Dim> 00038 CalcBinaryRepartion(FieldLayout<Dim>&, BareField<double,Dim>&); 00039 00040 Given a FieldLayout and a Field of weights, find the domain for this 00041 processor. This does not repartition the FieldLayout, it just 00042 calculates the domain. If you want to further subdivide these 00043 domains, just cut up what this function returns. 00044 00045 void 00046 BinaryRepartition(FieldLayout<Dim>&, BareField<double,Dim>&); 00047 00048 Just call the above function and then repartition the FieldLayout 00049 (and all the Fields defined on it). 00050 00051 */ 00053 00054 // forward declarations 00055 template<unsigned Dim> class FieldLayout; 00056 template<class T, unsigned Dim> class BareField; 00057 00058 // Calculate the local domain for a binary repartition. 00059 template<unsigned Dim> 00060 NDIndex<Dim> 00061 CalcBinaryRepartition(FieldLayout<Dim>&, BareField<double,Dim>&); 00062 00063 // Calculate and apply a local domain for a binary repartition. 00064 template<unsigned Dim> 00065 void 00066 BinaryRepartition(FieldLayout<Dim>& layout, BareField<double,Dim>& weights) 00067 { 00068 layout.Repartition( CalcBinaryRepartition(layout,weights) ); 00069 } 00070 00072 00073 #include "FieldLayout/BinaryBalancer.cpp" 00074 00075 #endif // BINARY_BALANCER_H 00076 00077 /*************************************************************************** 00078 * $RCSfile: BinaryBalancer.h,v $ $Author: adelmann $ 00079 * $Revision: 1.1.1.1 $ $Date: 2003/01/23 07:40:27 $ 00080 * IPPL_VERSION_ID: $Id: BinaryBalancer.h,v 1.1.1.1 2003/01/23 07:40:27 adelmann Exp $ 00081 ***************************************************************************/