8 #include "tm_mapping.h"
9 #include "TreeMatchLB.h"
15 CreateLBFunc_Def(TreeMatchLB, "TreeMatch load balancer, like a normal one but with empty strategy")
17 #include "TreeMatchLB.def.h"
19 TreeMatchLB::TreeMatchLB(const CkLBOptions &opt): CBase_TreeMatchLB(opt)
21 lbname = (char*)"TreeMatchLB";
23 CkPrintf("[%d] TreeMatchLB created\n",CkMyPe());
26 bool TreeMatchLB::QueryBalanceNow(int _step)
32 double *get_comm_speed(int *depth){
38 res=(double*)malloc(sizeof(double)*(*depth));
41 for(i=1;i<*depth;i++){
47 tm_topology_t *build_abe_topology(int nb_procs){
48 int arity[4]={nb_procs,2,2,2}; /*abe memory hierarchy. Should be given by HWLOC*/
49 int nbring[8]={0,2,4,6,1,3,5,7}; /*abe cores numbering. Should be given by HWLOC*/
50 return build_synthetic_topology(arity,5,nbring,8);
53 class ProcLoadGreater {
55 bool operator()(ProcInfo p1, ProcInfo p2) {
56 return (p1.totalLoad() > p2.totalLoad());
60 class ObjLoadGreater {
62 bool operator()(Vertex v1, Vertex v2) {
63 return (v1.getVertexLoad() > v2.getVertexLoad());
67 void TreeMatchLB::work(BaseLB::LDStats* stats)
69 /** ========================= 1st Do Load Balancing =======================*/
71 /** ========================== INITIALIZATION ============================= */
72 ProcArray *parr = new ProcArray(stats); // Processor Array
73 ObjGraph *ogr = new ObjGraph(stats); // Object Graph
75 /** ============================= STRATEGY ================================ */
76 parr->resetTotalLoad();
78 if (_lb_args.debug()>1)
79 CkPrintf("[%d] In GreedyLB strategy\n",CkMyPe());
83 // max heap of objects
84 std::sort(ogr->vertices.begin(), ogr->vertices.end(), ObjLoadGreater());
85 // min heap of processors
86 std::make_heap(parr->procs.begin(), parr->procs.end(), ProcLoadGreater());
88 for(vert = 0; vert < ogr->vertices.size(); vert++) {
89 // Pop the least loaded processor
90 ProcInfo p = parr->procs.front();
91 std::pop_heap(parr->procs.begin(), parr->procs.end(), ProcLoadGreater());
92 parr->procs.pop_back();
94 // Increment the load of the least loaded processor by the load of the
95 // 'heaviest' unmapped object
96 p.totalLoad() += ogr->vertices[vert].getVertexLoad();
97 ogr->vertices[vert].setNewPe(p.getProcId());
99 // Insert the least loaded processor with load updated back into the heap
100 parr->procs.push_back(p);
101 std::push_heap(parr->procs.begin(), parr->procs.end(), ProcLoadGreater());
104 /** ============================== CLEANUP ================================ */
105 ogr->convertDecisions(stats); // Send decisions back to LDStats
108 /** ====================== 2nd do Topology aware mapping ====================*/
115 int *object_mapping, *permutation;
118 /* get number of processors and teh greedy load balancing*/
119 nb_procs = stats->nprocs();
120 object_mapping=stats->to_proc.getVec();
123 stats->makeCommHash();
124 // allocate communication matrix
125 comm_mat=(double**)malloc(sizeof(double*)*nb_procs);
126 for(i=0;i<nb_procs;i++){
127 comm_mat[i]=(double*)calloc(nb_procs,sizeof(double));
130 /* Build the communicartion matrix*/
131 for(i=0;i<stats->n_comm;i++){
132 LDCommData &commData = stats->commData[i];
133 if((!commData.from_proc())&&(commData.recv_type()==LD_OBJ_MSG)){
134 /* object_mapping[i] is the processors of object i*/
135 int from = object_mapping[stats->getHash(commData.sender)];
136 int to = object_mapping[stats->getHash(commData.receiver.get_destObj())];
138 comm_mat[from][to]+=commData.bytes;
139 comm_mat[to][from]+=commData.bytes;
144 /* build the topology of the hardware (abe machine here)*/
145 tm_topology_t *topology=build_abe_topology(nb_procs);
146 display_topology(topology);
147 /* compute the affinity tree */
148 tree_t *comm_tree=build_tree_from_topology(topology,comm_mat,nb_procs,NULL,NULL);
150 /* Compute the processor permutation*/
151 permutation=(int*)malloc(sizeof(int)*nb_procs);
152 map_topology_simple(topology,comm_tree,permutation,NULL);
156 Apply this perutation to all objects
157 Side effect: object_mapping points to the stats->to_proc.getVec()
158 So, these lines change also stats->to_proc.getVec()
160 for(i=0;i<nb_procs;i++)
161 object_mapping[i]=permutation[object_mapping[i]];
163 // free communication matrix;
164 for(i=0;i<nb_procs;i++){
168 free_topology(topology);