GraphBFTLB: stratgey which does breadth first traversal
authorAbhinav S Bhatele <bhatele@illinois.edu>
Thu, 11 Nov 2010 18:58:42 +0000 (12:58 -0600)
committerAbhinav S Bhatele <bhatele@illinois.edu>
Thu, 11 Nov 2010 18:58:42 +0000 (12:58 -0600)
Currently does not consider:
  1. non-migratable objects (tries to map them)
  2. non-available processors (maps to all of them)
  3. assumes a connected graph

src/ck-ldb/GraphBFTLB.C

index 3f5fb13dd5e718e3bc6d51e944f6f22b5f819fb8..9b5e81022c9fd733399f8caa1518690bfbfd8203 100644 (file)
@@ -13,6 +13,7 @@
 
 #include "GraphBFTLB.h"
 #include "ckgraph.h"
+#include <queue>
 
 CreateLBFunc_Def(GraphBFTLB, "Algorithm which does breadth first traversal for communication aware load balancing")
 
@@ -28,13 +29,46 @@ CmiBool GraphBFTLB::QueryBalanceNow(int _step) {
 
 void GraphBFTLB::work(LDStats *stats) {
   /** ========================== INITIALIZATION ============================= */
-  ProcArray *parr = new ProcArray(stats);
-  ObjGraph *ogr = new ObjGraph(stats);
+  ProcArray *parr = new ProcArray(stats);      // Processor Array
+  ObjGraph *ogr = new ObjGraph(stats);         // Object Graph
 
   /** ============================= STRATEGY ================================ */
+  double avgLoad = parr->getAverageLoad();
+  parr->resetTotalLoad();
+
+  int start = 0, nextPe = 0;
+  std::queue<int> vertexq;
+
+  // start at vertex with id 0
+  vertexq.push(start);
+  while(parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getObjLoad() > avgLoad)
+    nextPe++;
+  ogr->vertices[start].setNewPe(nextPe);
+  parr->procs[nextPe].setTotalLoad(parr->procs[nextPe].getTotalLoad() + ogr->vertices[start].getObjLoad());
+
+  int i, nbr;
+  // breadth first traversal
+  while(!vertexq.empty()) {
+    start = vertexq.front();
+    vertexq.pop();
+
+    for(i = 0; i < ogr->vertices[start].edgeList.size(); i++) {
+      // look at all neighbors of a node in the queue and map them while
+      // inserting them in the queue (so we can look at their neighbors next)
+      nbr = ogr->vertices[start].edgeList[i].getNeighborId();
+      if(ogr->vertices[nbr].getNewPe() == -1) {
+       vertexq.push(nbr);
+
+       while(parr->procs[nextPe].getTotalLoad() + ogr->vertices[nbr].getObjLoad() > avgLoad)
+         nextPe++;
+       ogr->vertices[nbr].setNewPe(nextPe);
+       parr->procs[nextPe].setTotalLoad(parr->procs[nextPe].getTotalLoad() + ogr->vertices[nbr].getObjLoad());
+      }
+    } // end of for loop
+  } // end of while loop
 
   /** ============================== CLEANUP ================================ */
-  ogr->convertDecisions(stats);
+  ogr->convertDecisions(stats);                // Send decisions back to LDStats
 }
 
 #include "GraphBFTLB.def.h"