doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / GraphBFTLB.C
1 /** \file GraphBFTLB.C
2  *  Author: Abhinav S Bhatele
3  *  Date Created: November 10th, 2010
4  *  E-mail: bhatele@illinois.edu
5  *
6  */
7
8 /**
9  *  \addtogroup CkLdb
10  */
11
12 /*@{*/
13
14 #include "GraphBFTLB.h"
15 #include "ckgraph.h"
16 #include <queue>
17
18 CreateLBFunc_Def(GraphBFTLB, "Algorithm which does breadth first traversal for communication aware load balancing")
19
20 GraphBFTLB::GraphBFTLB(const CkLBOptions &opt) : CentralLB(opt) {
21   lbname = "GraphBFTLB";
22   if(CkMyPe() == 0)
23     CkPrintf("GraphBFTLB created\n");
24 }
25
26 CmiBool GraphBFTLB::QueryBalanceNow(int _step) {
27   return CmiTrue;
28 }
29
30 void GraphBFTLB::work(LDStats *stats) {
31   /** ========================== INITIALIZATION ============================= */
32   ProcArray *parr = new ProcArray(stats);       // Processor Array
33   ObjGraph *ogr = new ObjGraph(stats);          // Object Graph
34
35   /** ============================= STRATEGY ================================ */
36   double avgLoad = parr->getAverageLoad();
37   int numPes = parr->procs.size();
38
39   // CkPrintf("Average Load %g\n\n", avgLoad);
40   // for(int i=0; i<numPes; i++)
41   //  CkPrintf("PE [%d] %g %g\n", i, parr->procs[i].getTotalLoad(), parr->procs[i].getOverhead());
42   parr->resetTotalLoad();
43
44   int start = 0, nextPe = 0;
45   std::queue<int> vertexq;
46
47   // start at vertex with id 0
48   vertexq.push(start);
49   if(parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getVertexLoad() > avgLoad) {
50     nextPe++;
51     avgLoad += (avgLoad - parr->procs[nextPe].getTotalLoad())/(numPes-nextPe);
52   }
53   ogr->vertices[start].setNewPe(nextPe);
54   // CkPrintf("[%d] %d %d %g %g %g\n", start, ogr->vertices[start].getCurrentPe(), ogr->vertices[start].getNewPe(), parr->procs[nextPe].getTotalLoad(), ogr->vertices[start].getVertexLoad(), parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getVertexLoad());
55   parr->procs[nextPe].totalLoad() += ogr->vertices[start].getVertexLoad();
56
57   int i, nbr;
58   // breadth first traversal
59   while(!vertexq.empty()) {
60     start = vertexq.front();
61     vertexq.pop();
62
63     for(i = 0; i < ogr->vertices[start].sendToList.size(); i++) {
64       // look at all neighbors of a node in the queue and map them while
65       // inserting them in the queue (so we can look at their neighbors next)
66       nbr = ogr->vertices[start].sendToList[i].getNeighborId();
67       if(ogr->vertices[nbr].getNewPe() == -1) {
68         vertexq.push(nbr);
69
70         if(parr->procs[nextPe].getTotalLoad() + ogr->vertices[nbr].getVertexLoad() > avgLoad) {
71           nextPe++;
72           avgLoad += (avgLoad - parr->procs[nextPe].getTotalLoad())/(numPes-nextPe);
73         }
74         ogr->vertices[nbr].setNewPe(nextPe);
75         // CkPrintf("[%d] %d %d %g %g %g\n", nbr, ogr->vertices[nbr].getCurrentPe(), ogr->vertices[nbr].getNewPe(), parr->procs[nextPe].getTotalLoad(), ogr->vertices[start].getVertexLoad(), parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getVertexLoad());
76         parr->procs[nextPe].totalLoad() += ogr->vertices[nbr].getVertexLoad();
77       }
78     } // end of for loop
79   } // end of while loop
80
81   /** ============================== CLEANUP ================================ */
82   ogr->convertDecisions(stats);         // Send decisions back to LDStats
83 }
84
85 #include "GraphBFTLB.def.h"
86
87 /*@}*/