Added a new topology conscious LB called TopoCentLB
authorAmit Sharma <asharma6@uiuc.edu>
Fri, 6 May 2005 01:10:08 +0000 (01:10 +0000)
committerAmit Sharma <asharma6@uiuc.edu>
Fri, 6 May 2005 01:10:08 +0000 (01:10 +0000)
src/ck-ldb/EveryLB.ci
src/ck-ldb/Make.lb
src/ck-ldb/Makefile_lb.sh
src/ck-ldb/TopoCentLB.C [new file with mode: 0644]
src/ck-ldb/TopoCentLB.ci [new file with mode: 0644]
src/ck-ldb/TopoCentLB.h [new file with mode: 0644]
src/scripts/Make.depends
src/scripts/Makefile

index e7af4e5504d60ed56844f1b369d76ba74fdcf577..9e8ce59ef4a5880cdc1fef63dc1220bda0193432 100644 (file)
@@ -22,5 +22,6 @@ module EveryLB {
    extern module HybridLB;
    extern module TopoLB;
    extern module RefineTopoLB;
+   extern module TopoCentLB;
    initnode void initEveryLB(void);
 };
index 841a93665a28c4caf5c48656b8cd2f167b588ef1..de1422a1dd9e78946d36a387c566b04ec6934326 100644 (file)
@@ -1,7 +1,7 @@
 # Automatically generated by script Makefile_lb.sh
-#  by uid=21499(tarun) gid=80(kale) groups=80(kale)
+#  by uid=21529(amits) gid=80(kale) groups=80(kale)
 #  at finesse
-#  on Thu Apr 28 22:19:17 CDT 2005
+#  on Thu May 5 20:05:46 CDT 2005
 LOADBALANCERS=\
    $(L)/libmoduleDummyLB.a \
    $(L)/libmoduleComboCentLB.a \
@@ -25,6 +25,7 @@ LOADBALANCERS=\
    $(L)/libmoduleHybridLB.a \
    $(L)/libmoduleTopoLB.a \
    $(L)/libmoduleRefineTopoLB.a \
+   $(L)/libmoduleTopoCentLB.a \
    manager.o
 
 DummyLB.def.h: DummyLB.decl.h
@@ -225,6 +226,15 @@ $(L)/libmoduleRefineTopoLB.a: RefineTopoLB.o
        $(CHARMC) -o $(L)/libmoduleRefineTopoLB.a RefineTopoLB.o 
        
 
+TopoCentLB.def.h: TopoCentLB.decl.h
+
+TopoCentLB.decl.h: TopoCentLB.ci charmxi
+       $(CHARMXI) TopoCentLB.ci
+
+$(L)/libmoduleTopoCentLB.a: TopoCentLB.o 
+       $(CHARMC) -o $(L)/libmoduleTopoCentLB.a TopoCentLB.o 
+       
+
 # used for make dependes
 LB_OBJ=EveryLB.o \
     DummyLB.o \
@@ -249,6 +259,7 @@ LB_OBJ=EveryLB.o \
     HybridLB.o \
     TopoLB.o \
     RefineTopoLB.o \
+    TopoCentLB.o \
     manager.o
 
 EveryLB.def.h: EveryLB.decl.h
index 98b8ce235d2fd0241729d2f1267825471771b941..f12e75c2a91be3bc6064680a8f3f4acf225e4920 100755 (executable)
@@ -1,5 +1,5 @@
 #!/bin/sh
-LOADBALANCERS="DummyLB ComboCentLB RandCentLB RefineLB RefineKLB  RefineCommLB GreedyLB GreedyCommLB GreedyAgentLB GridCommLB Comm1LB OrbLB RecBisectBfLB MetisLB PhasebyArrayLB RotateLB NeighborLB NeighborCommLB WSLB HybridLB TopoLB RefineTopoLB"
+LOADBALANCERS="DummyLB ComboCentLB RandCentLB RefineLB RefineKLB  RefineCommLB GreedyLB GreedyCommLB GreedyAgentLB GridCommLB Comm1LB OrbLB RecBisectBfLB MetisLB PhasebyArrayLB RotateLB NeighborLB NeighborCommLB WSLB HybridLB TopoLB RefineTopoLB TopoCentLB"
 
 out="Make.lb"
 
diff --git a/src/ck-ldb/TopoCentLB.C b/src/ck-ldb/TopoCentLB.C
new file mode 100644 (file)
index 0000000..9bf3195
--- /dev/null
@@ -0,0 +1,835 @@
+/**************************************************************************
+** Amit Sharma (asharma6@uiuc.edu)
+** November 23, 2004
+**
+** This is a topology conscious load balancer.
+** It migrates objects to new processors based on the topology in which the processors are connected.
+****************************************************************************/
+
+#include <math.h>
+#include <stdlib.h>
+#include "charm++.h"
+#include "cklists.h"
+#include "CentralLB.h"
+
+#include "TopoCentLB.decl.h"
+
+#include "TopoCentLB.h"
+
+#define alpha PER_MESSAGE_SEND_OVERHEAD_DEFAULT  /*Startup time per message, seconds*/
+#define beta PER_BYTE_SEND_OVERHEAD_DEFAULT     /*Long-message time per byte, seconds*/
+#define DEG_THRES 0.50
+
+//#define MAX_EDGE
+
+CreateLBFunc_Def(TopoCentLB,"Balance objects based on the network topology");
+
+
+/*static void lbinit (void)
+{
+  LBRegisterBalancer ("TopoCentLB",
+                     CreateTopoCentLB,
+                     AllocateTopoCentLB,
+                     "Balance objects based on the network topology");
+}*/
+
+
+TopoCentLB::TopoCentLB(const CkLBOptions &opt) : CentralLB (opt)
+{
+  lbname = "TopoCentLB";
+  if (CkMyPe () == 0) {
+    CkPrintf ("[%d] TopoCentLB created\n",CkMyPe());
+  }
+}
+
+
+CmiBool TopoCentLB::QueryBalanceNow (int _step)
+{
+  return CmiTrue;
+}
+
+
+void TopoCentLB::computePartitions(CentralLB::LDStats *stats,int count,int *newmap)
+{
+       
+  int numobjs = stats->n_objs;
+       int i, j, m;
+
+  // allocate space for the computing data
+  double *objtime = new double[numobjs];
+  int *objwt = new int[numobjs];
+  int *origmap = new int[numobjs];
+  LDObjHandle *handles = new LDObjHandle[numobjs];
+  
+       for(i=0;i<numobjs;i++) {
+    objtime[i] = 0.0;
+    objwt[i] = 0;
+    origmap[i] = 0;
+  }
+
+  for (i=0; i<stats->n_objs; i++) {
+    LDObjData &odata = stats->objData[i];
+    if (!odata.migratable) 
+      CmiAbort("MetisLB doesnot dupport nonmigratable object.\n");
+    int frompe = stats->from_proc[i];
+    origmap[i] = frompe;
+    objtime[i] = odata.wallTime*stats->procs[frompe].pe_speed;
+    handles[i] = odata.handle;
+  }
+
+  // to convert the weights on vertices to integers
+  double max_objtime = objtime[0];
+  for(i=0; i<numobjs; i++) {
+    if(max_objtime < objtime[i])
+      max_objtime = objtime[i];
+  }
+       int maxobj=0;
+       int totalwt=0;
+  double ratio = 1000.0/max_objtime;
+  for(i=0; i<numobjs; i++) {
+      objwt[i] = (int)(objtime[i]*ratio);
+                       if(maxobj<objwt[i])
+                               maxobj=objwt[i];
+                       totalwt+=objwt[i];
+  }
+       
+       //CkPrintf("\nmax obj wt :%d \n totalwt before :%d \n\n",maxobj,totalwt);
+       
+  int **comm = new int*[numobjs];
+  for (i=0; i<numobjs; i++) {
+    comm[i] = new int[numobjs];
+    for (j=0; j<numobjs; j++)  {
+      comm[i][j] = 0;
+    }
+  }
+
+  const int csz = stats->n_comm;
+  for(i=0; i<csz; i++) {
+      LDCommData &cdata = stats->commData[i];
+      //if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
+        //continue;
+                       if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
+       int senderID = stats->getHash(cdata.sender);
+       int recverID = stats->getHash(cdata.receiver.get_destObj());
+       CmiAssert(senderID < numobjs);
+       CmiAssert(recverID < numobjs);
+       //comm[senderID][recverID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
+       //comm[recverID][senderID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
+               //CkPrintf("in compute partitions...%d\n",comm[senderID][recverID]);
+                               comm[senderID][recverID] += cdata.messages;
+       comm[recverID][senderID] += cdata.messages;
+
+                               //Use bytes or messages -- do i include messages for objlist too...??
+                       }
+                       else if (cdata.receiver.get_type() == LD_OBJLIST_MSG) {
+                               //CkPrintf("in objlist..\n");
+        int nobjs;
+        LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
+        int senderID = stats->getHash(cdata.sender);
+        for (j=0; j<nobjs; j++) {
+           int recverID = stats->getHash(objs[j]);
+           if((senderID == -1)||(recverID == -1))
+              if (_lb_args.migObjOnly()) continue;
+              else CkAbort("Error in search\n");
+           comm[senderID][recverID] += cdata.messages;
+           comm[recverID][senderID] += cdata.messages;
+        }
+                       }
+               }
+
+// ignore messages sent from an object to itself
+  for (i=0; i<numobjs; i++)
+    comm[i][i] = 0;
+
+  // construct the graph in CSR format
+  int *xadj = new int[numobjs+1];
+  int numedges = 0;
+  for(i=0;i<numobjs;i++) {
+    for(j=0;j<numobjs;j++) {
+      if(comm[i][j] != 0)
+        numedges++;
+    }
+  }
+  int *adjncy = new int[numedges];
+  int *edgewt = new int[numedges];
+       int factor = 10;
+  xadj[0] = 0;
+  int count4all = 0;
+  for (i=0; i<numobjs; i++) {
+    for (j=0; j<numobjs; j++) { 
+      if (comm[i][j] != 0) { 
+        adjncy[count4all] = j;
+        edgewt[count4all++] = comm[i][j]/factor;
+      }
+    }
+    xadj[i+1] = count4all;
+  }
+
+  /*if (_lb_args.debug() >= 2) {
+  CkPrintf("Pre-LDB Statistics step %d\n", step());
+  printStats(count, numobjs, objtime, comm, origmap);
+  }*/
+
+  int wgtflag = 3; // Weights both on vertices and edges
+  int numflag = 0; // C Style numbering
+  int options[5];
+  int edgecut;
+  int sameMapFlag = 1;
+
+       options[0] = 0;
+
+  if (count < 1) {
+    CkPrintf("error: Number of Pe less than 1!");
+  }
+  else if (count == 1) {
+       for(m=0;m<numobjs;m++) 
+                       newmap[i] = origmap[i];
+       sameMapFlag = 1;
+  }
+  else {
+       sameMapFlag = 0;
+               /*
+       if (count > 8)
+                       METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
+                           &wgtflag, &numflag, &count, options, 
+                           &edgecut, newmap);
+         else
+                       METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
+                                &wgtflag, &numflag, &count, options, 
+                                &edgecut, newmap);
+               */
+   //CkPrintf("before calling metis.\n");
+               METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt,
+                                 &wgtflag, &numflag, &count, options,
+                                 &edgecut, newmap);
+        //CkPrintf("after calling Metis function.\n");
+  }
+        
+  /*if (_lb_args.debug() >= 2) {
+       CkPrintf("Post-LDB Statistics step %d\n", step());
+       printStats(count, numobjs, objtime, comm, newmap);
+  }*/
+
+  for(i=0;i<numobjs;i++)
+    delete[] comm[i];
+  delete[] comm;
+  delete[] objtime;
+  delete[] xadj;
+  delete[] adjncy;
+  delete[] objwt;
+  delete[] edgewt;
+
+       //CkPrintf("chking wts on each partition...\n");
+
+       /*int avg=0;
+       int *chkwt = new int[count];
+       for(i=0;i<count;i++)
+               chkwt[i]=0;
+       //totalwt=0;
+       for(i=0;i<numobjs;i++){
+               chkwt[newmap[i]] += objwt[i];
+               avg += objwt[i];
+               
+       }
+       
+       
+       for(i=0;i<count;i++)
+               CkPrintf("%d -- %d\n",i,chkwt[i]);
+       
+       //CkPrintf("totalwt after:%d avg is %d\n",avg,avg/count);
+*/
+  /*if(!sameMapFlag) {
+    for(i=0; i<numobjs; i++) {
+      if(origmap[i] != newmap[i]) {
+                               CmiAssert(stats->from_proc[i] == origmap[i]);
+                               ///Dont assign....wait........
+                               stats->to_proc[i] =  newmap[i];
+                               if (_lb_args.debug() >= 3)
+          CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),i,stats->from_proc[i],stats->to_proc[i]);
+      }
+    }
+  }*/
+
+  delete[] origmap;
+
+}
+
+int TopoCentLB::findMaxObjs(int *map,int totalobjs,int count)
+{
+       int *max_num = new int[count];
+       int i;
+       int maxobjs=0;
+       
+       for(i=0;i<count;i++)
+               max_num[i]=0;
+               
+       for(i=0;i<totalobjs;i++)
+               max_num[map[i]]++;
+       
+       for(i=0;i<count;i++)
+               if(max_num[i]>maxobjs)
+                       maxobjs = max_num[i];
+       
+       delete[] max_num;
+
+       return maxobjs;
+}
+
+void TopoCentLB::Heapify(HeapNode *heap, int node, int heapSize)
+{
+  int left = 2*node+1;
+  int right = 2*node+2;
+  int xchange;
+       
+  //heap[left].load > heap[node].load)
+  if (left < heapSize && (heap[left].key > heap[node].key))
+    xchange = left;
+  else 
+               xchange = node;
+  //heap[right].load > heap[xchange].load) 
+  if (right < heapSize && (heap[right].key > heap[xchange].key))
+    xchange = right;
+
+  if (xchange != node) {
+    HeapNode tmp;
+    tmp = heap[node];
+    heap[node] = heap[xchange];
+    heap[xchange] = tmp;
+    Heapify(heap,xchange,heapSize);
+  }    
+}
+
+
+TopoCentLB::HeapNode TopoCentLB::extractMax(HeapNode *heap,int *heapSize){
+
+       if(*heapSize < 1)
+               CmiAbort("Empty Heap passed to extractMin!\n");
+
+       HeapNode max = heap[0];
+       heap[0] = heap[*heapSize-1];
+       *heapSize = *heapSize - 1;
+       Heapify(heap,0,*heapSize);
+       return max;
+}
+
+void TopoCentLB::BuildHeap(HeapNode *heap,int heapSize){
+       for(int i=heapSize/2; i >= 0; i--)
+               Heapify(heap,i,heapSize);
+}
+
+void TopoCentLB :: increaseKey(HeapNode *heap,int i,double wt){
+       
+       if(wt != -1.00){
+               #ifdef MAX_EDGE
+                       //CkPrintf("me here...\n");
+                       if(wt>heap[i].key)
+                               heap[i].key = wt;
+               #else
+                       heap[i].key += wt;
+               #endif
+       }
+       int parent = (i-1)/2;
+       
+       if(heap[parent].key >= heap[i].key)
+               return;
+       else {
+               HeapNode tmp = heap[parent];
+               heap[parent] = heap[i];
+               heap[i] = tmp;
+               increaseKey(heap,parent,-1.00);
+       }
+       
+}
+
+void TopoCentLB :: calculateMST(PartGraph *partgraph,LBTopology *topo,int *proc_mapping,int max_comm_part){
+
+       //Edge **markedEdges;
+       //int *parent;
+       int *inHeap;
+       double *keys;
+       int count = partgraph->n_nodes;
+       int i=0,j=0;
+       
+       //parent = new int[partgraph->n_nodes];
+       inHeap = new int[partgraph->n_nodes];
+       keys = new double[partgraph->n_nodes];
+
+       int **hopCount;
+       int **topoGraph;
+       //int *topoDegree;
+       int *assigned_procs = new int[count];
+
+       hopCount = new int*[count];
+       for(i=0;i<count;i++){
+               proc_mapping[i]=-1;
+               assigned_procs[i]=0;
+               hopCount[i] = new int[count];
+               for(j=0;j<count;j++)
+                       hopCount[i][j] = 0;
+       }
+
+       int max_neighbors = topo->max_neighbors();
+       
+       //topoDegree = new int[count];
+       topoGraph = new int*[count];
+       for(i=0;i<count;i++){
+               //topoDegree[i] = 0;
+               topoGraph[i] = new int[max_neighbors+1];
+               for(j=0;j<=max_neighbors;j++)
+                       topoGraph[i][j]=0;
+       }
+       
+       int *neigh = new int[max_neighbors];
+       int max_degree=0;
+       int num_neigh=0;
+       for(i=0;i<count;i++){
+               topo->neighbors(i,neigh,num_neigh);
+               //topoDegree[i] = num_neigh;
+               if(num_neigh > max_degree)
+                       max_degree = num_neigh;
+               for(j=0;j<num_neigh;j++)
+                       topoGraph[i][j]=neigh[j];
+               topoGraph[i][j]=-1;
+       }
+       //Topology graph constructed
+       delete [] neigh;
+
+       //markedEdges = new Edge*[partmst->n_nodes];
+       /*for(int i=0;i<partmst->n_nodes;i++){
+               parent[i] = -1;
+               inHeap[i] = 1;
+       markedEdges[i] = new Edge[partmst->n_nodes];
+    for(int j=0;j<partmst->n_nodes;j++)
+       markedEdges[i][j] = 0;
+  }*/
+       
+       HeapNode *heap = new HeapNode[partgraph->n_nodes];
+       int heapSize = 0;
+
+       for(i=0;i<partgraph->n_nodes;i++){
+               heap[i].key = 0.00;
+               heap[i].node = i;
+               keys[i] = 0.00;
+               //parent[i] = -1;
+               inHeap[i] = 1;
+               
+               /*if(i==0){ //Take 0 as root
+                       heap[0].key = 1.00;
+                       keys[0] = 0;
+               }*/
+       }
+
+       //Assign the max comm partition first
+       heap[max_comm_part].key = 1.00;
+       
+       //CkPrintf("in calculate MST..\n");
+       heapSize = partgraph->n_nodes;
+       BuildHeap(heap,heapSize);
+
+       int k=0,comm_cnt=0,m=0,n=0;
+       int *commParts = new int[partgraph->n_nodes];
+       
+       srand(count);
+
+       while(heapSize > 0){
+               HeapNode max = extractMax(heap,&heapSize);
+               //CkPrintf("in the extracting loop..\n");
+               inHeap[max.node] = 0;
+
+               //CkPrintf("extracted part..%d with weight :%.1f\n",max.node,max.key);
+               
+               for(i=0;i<partgraph->n_nodes;i++){
+                       commParts[i]=-1;
+                       PartGraph::Edge wt = partgraph->edges[max.node][i];
+                       if(wt == 0)
+                               continue;
+                       if(inHeap[i]){
+                               //parent[i] = max.node;
+                       #ifdef MAX_EDGE
+                               if(wt>keys[i])
+                                       keys[i]=wt;
+                       #else
+                               keys[i] += wt;
+                       #endif
+                               //Update in the heap too
+                               //First, find where this node is..in the heap
+                               for(j=0;j<heapSize;j++)
+                                       if(heap[j].node == i)
+                                               break;
+                               if(j==heapSize)
+                                       CmiAbort("Some error in heap...\n");
+                               increaseKey(heap,j,wt);
+                       }
+               }
+               
+               if(max.node==0){ //For now, assign max comm partition to 0th proc in the topology
+                       proc_mapping[max.node]=0;
+                       assigned_procs[0]=1;
+                       continue;
+               }
+               
+               m=0;
+               n=0;
+               comm_cnt=0;
+               for(k=0;k<partgraph->n_nodes;k++){
+                       if(!inHeap[k] && partgraph->edges[k][max.node]){
+                               commParts[comm_cnt]=k;
+                               comm_cnt++;
+                       }
+               }
+               int pot_proc=-1;
+               double min_cost=-1;
+               int min_cost_index=-1;
+               double cost=0;
+               int p=0;
+               int q=0;
+               int sec_pot_proc=-1;
+               
+               for(m=0;m<comm_cnt;m++){
+                       int pe=proc_mapping[commParts[m]];
+                       n=0;    
+                       //cost=0;
+                       //CkPrintf("\nnhs of %d ie. part %d are ",pe,commParts[m]);
+                       while(topoGraph[pe][n]!=-1){
+                               pot_proc=topoGraph[pe][n];
+                               //CkPrintf(" %d ",pot_proc);
+                               if(assigned_procs[pot_proc]){
+                                       n++;
+                                       continue;
+                               }
+                               cost=0;
+                               cost+=partgraph->edges[commParts[m]][max.node];
+                               for(p=0;p<comm_cnt;p++){
+                                       if(p!=m){
+                                               if(!hopCount[proc_mapping[commParts[p]]][pot_proc])
+                                                       hopCount[proc_mapping[commParts[p]]][pot_proc]=topo->get_hop_count(proc_mapping[commParts[p]],pot_proc);
+                                               cost += hopCount[proc_mapping[commParts[p]]][pot_proc]*partgraph->edges[commParts[p]][max.node];
+                                               //CkPrintf("hop count:%d\n",hopCount[proc_mapping[commParts[p]]][pot_proc]);
+                                       }
+                               }
+                               //CkPrintf("-cost=%.1f- ",cost);
+                               if(min_cost==-1 || cost<min_cost){
+                                       min_cost=cost;
+                                       min_cost_index=pot_proc;
+                               }
+
+                               // look at 2-away neighbors too...
+                               q=0;
+                               while(topoGraph[pot_proc][q]!=-1){
+                                       sec_pot_proc=topoGraph[pot_proc][q];
+                                       //CkPrintf(" %d ",pot_proc);
+                                       if(assigned_procs[sec_pot_proc]){
+                                               q++;
+                                               continue;
+                                       }
+                                       cost=0;
+                                       cost+=2*partgraph->edges[commParts[m]][max.node];
+                                       for(p=0;p<comm_cnt;p++){
+                                               if(p!=m){
+                                                       if(!hopCount[proc_mapping[commParts[p]]][sec_pot_proc])
+                                                               hopCount[proc_mapping[commParts[p]]][sec_pot_proc]=topo->get_hop_count(proc_mapping[commParts[p]],sec_pot_proc);
+                                                       cost += hopCount[proc_mapping[commParts[p]]][sec_pot_proc]*partgraph->edges[commParts[p]][max.node];
+                                                       //CkPrintf("hop count:%d\n",hopCount[proc_mapping[commParts[p]]][pot_proc]);
+                                               }
+                                       }
+                                       //CkPrintf("-cost=%.1f- ",cost);
+                                       if(min_cost==-1 || cost<min_cost){
+                                               min_cost=cost;
+                                               min_cost_index=sec_pot_proc;
+                                       }
+                                       q++;
+                               }
+                               n++;
+                       }
+               }
+               if(min_cost==-1){
+                       min_cost_index=-1;
+                       while(min_cost_index==-1){
+                               min_cost_index = rand()%count;
+                               if(assigned_procs[min_cost_index])
+                                       min_cost_index=-1;
+                       }
+                       //CmiAbort("No potential processor found\n");
+                       //CkPrintf("random proc:%d\n",min_cost_index);
+               }
+               //CkPrintf("\npart %d assigned to proc %d\n",max.node,min_cost_index);
+               proc_mapping[max.node]=min_cost_index;
+               assigned_procs[min_cost_index]=1;
+       }
+
+}
+
+       //CkPrintf("just before end..\n");
+       //Retain only those edges which are in the MST
+       /*PartGraph::Edge **newEdges;
+       
+       newEdges = new PartGraph::Edge*[partmst->n_nodes];
+       for(int i=0;i<partmst->n_nodes;i++){
+               newEdges[i] = new PartGraph::Edge[partmst->n_nodes];
+               for(int j=0;j<partmst->n_nodes;j++)
+                       newEdges[i][j]=0;
+       }
+       
+       for(int i=0;i<partmst->n_nodes;i++){
+               if(parent[i] != -1){
+                       newEdges[parent[i]][i] = partmst->edges[parent[i]][i];
+                       newEdges[i][parent[i]] = partmst->edges[i][parent[i]];
+               }
+       }
+
+       //Convert the minimum spanning tree back to maximum spanning tree       
+       for(int i=0;i<partmst->n_nodes;i++)
+               for(int j=0;j<partmst->n_nodes;j++)
+                       if(newEdges[i][j] != 0)
+                               partmst->edges[i][j] = max_weight - newEdges[i][j];
+                       else
+                               partmst->edges[i][j] = 0;
+       */
+
+
+/*int TopoCentLB :: compare(const void *p,const void *q){
+       return (((PotList*)p)->size - ((PotList*)q)->size);
+}
+*/
+void TopoCentLB :: work(CentralLB::LDStats *stats,int count)
+{
+  int proc;
+  int obj;
+  int dest;
+  int i,j;
+       LDObjData *odata;
+       
+       if (_lb_args.debug() >= 2) {
+    CkPrintf("In TopoCentLB Strategy...\n");
+  }
+       
+  // Make sure that there is at least one available processor.
+  for (proc = 0; proc < count; proc++) {
+    if (stats->procs[proc].available) {
+      break;
+    }
+  }
+       if (proc == count) {
+    CmiAbort ("TopoCentLB: no available processors!");
+  }
+  removeNonMigratable(stats,count);
+
+       int *newmap = new int[stats->n_objs];
+
+       //CkPrintf("before computing partitions...\n");
+       
+       computePartitions(stats,count,newmap);
+       
+       /*CkPrintf("obj-proc mapping\n");
+       for(i=0;i<stats->n_objs;i++)
+               CkPrintf(" %d,%d ",i,newmap[i]);
+       */
+       int max_objs = findMaxObjs(newmap,stats->n_objs,count);
+       
+       //Check to see if edgecut contains the reqd. no. of edges
+       
+       partgraph = new PartGraph(count,max_objs);
+
+       //Fill up the partition graph - first fill the nodes and then, the edges
+       //CkPrintf("after computing partitions...\n");
+
+
+       for(i=0;i<stats->n_objs;i++)
+       {
+               PartGraph::Node* n = &partgraph->nodes[newmap[i]];
+               //CkPrintf("num:%d\n",n->num_objs);
+               n->obj_list[n->num_objs]=i;
+               n->num_objs++;
+       }
+
+       int **bytesComm;
+       bytesComm = new int*[count];
+       for(i=0;i<count;i++){
+               bytesComm[i] = new int[count];
+               for(j=0;j<count;j++)
+                       bytesComm[i][j]=0;
+       }
+
+       //CkPrintf("num comm:%d\n",stats->n_comm);
+       int *addedComm=new int[count];
+
+       int max_comm_part=-1;
+       double max_comm=0;
+       
+       for(i=0;i<stats->n_comm;i++)
+       {
+               //DO I consider other comm too....i.e. to or from a processor
+
+               LDCommData &cdata = stats->commData[i];
+               //if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
+       //continue;
+               if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
+       int senderID = stats->getHash(cdata.sender);
+       int recverID = stats->getHash(cdata.receiver.get_destObj());
+                       CmiAssert(senderID < stats->n_objs);
+               CmiAssert(recverID < stats->n_objs);
+               
+                       if(newmap[senderID]==newmap[recverID])
+                               continue;
+       
+                       //CkPrintf("from %d to %d\n",newmap[senderID],newmap[recverID]);
+                       if(partgraph->edges[newmap[senderID]][newmap[recverID]] == 0){
+                               partgraph->nodes[newmap[senderID]].degree++;
+                               partgraph->nodes[newmap[recverID]].degree++;
+                       }
+               
+                       partgraph->edges[newmap[senderID]][newmap[recverID]] += cdata.bytes;
+                       partgraph->edges[newmap[recverID]][newmap[senderID]] += cdata.bytes;
+                       
+                       partgraph->nodes[newmap[senderID]].comm += cdata.bytes;
+                       partgraph->nodes[newmap[recverID]].comm += cdata.bytes;
+                       
+                       if(partgraph->nodes[newmap[senderID]].comm > max_comm){
+                               max_comm = partgraph->nodes[newmap[senderID]].comm;
+                               max_comm_part = newmap[senderID];
+                       }
+                       if(partgraph->nodes[newmap[recverID]].comm > max_comm){
+                               max_comm = partgraph->nodes[newmap[recverID]].comm;
+                               max_comm_part = newmap[recverID];
+                       }
+
+                       //partgraph->edges[newmap[recverID]][newmap[senderID]] += 1000*(cdata.messages*alpha + cdata.bytes*beta);
+                       //bytesComm[newmap[senderID]][newmap[recverID]] += cdata.bytes;
+                       //bytesComm[newmap[recverID]][newmap[senderID]] += cdata.bytes;
+
+               }
+               else if(cdata.receiver.get_type() == LD_OBJLIST_MSG) {
+       //CkPrintf("\nin obj list cal...\n\n");
+                       int nobjs;
+       LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
+      int senderID = stats->getHash(cdata.sender);
+      //addedComm = new int[count];
+                       for(j=0;j<count;j++)
+                               addedComm[j]=0;
+                       //CkPrintf("in obj list loop...\n");
+                       for (j=0; j<nobjs; j++) {
+       int recverID = stats->getHash(objs[j]);
+        if((senderID == -1)||(recverID == -1))
+               if (_lb_args.migObjOnly()) continue;
+               else CkAbort("Error in search\n");
+                                       
+                               if(newmap[senderID]==newmap[recverID])
+                                       continue;
+       
+                               //CkPrintf("from %d to %d\n",newmap[senderID],newmap[recverID]);
+                               if(partgraph->edges[newmap[senderID]][newmap[recverID]] == 0){
+                                       //CkPrintf("sender:%d recver:%d\n",newmap[senderID],newmap[recverID]);
+                                       partgraph->nodes[newmap[senderID]].degree++;
+                                       partgraph->nodes[newmap[recverID]].degree++;
+                               }
+               
+                               if(!addedComm[newmap[recverID]]){
+                                       partgraph->edges[newmap[senderID]][newmap[recverID]] += cdata.bytes;
+                                       partgraph->edges[newmap[recverID]][newmap[senderID]] += cdata.bytes;
+       
+                                       partgraph->nodes[newmap[senderID]].comm += cdata.bytes;
+                                       partgraph->nodes[newmap[recverID]].comm += cdata.bytes;
+
+                                       if(partgraph->nodes[newmap[senderID]].comm > max_comm){
+                                               max_comm = partgraph->nodes[newmap[senderID]].comm;
+                                               max_comm_part = newmap[senderID];
+                                       }
+                                       if(partgraph->nodes[newmap[recverID]].comm > max_comm){
+                                               max_comm = partgraph->nodes[newmap[recverID]].comm;
+                                               max_comm_part = newmap[recverID];
+                                       }
+
+                                       //bytesComm[newmap[senderID]][newmap[recverID]] += cdata.bytes;
+                                       //bytesComm[newmap[recverID]][newmap[senderID]] += cdata.bytes;
+                                       addedComm[newmap[recverID]]=1;
+                               }
+      }
+                       //CkPrintf("outside loop..\n");
+       //delete [] addedComm;
+               }
+
+       }
+       
+       int *proc_mapping = new int[count];
+       
+       delete [] addedComm;
+               
+       LBtopoFn topofn;
+       int max_neighbors=0;
+       int *neigh;
+       int num_neigh=0;
+       
+       topofn = LBTopoLookup(_lbtopo);
+  if (topofn == NULL) {
+       char str[1024];
+    CmiPrintf("TopoCentLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
+    printoutTopo();
+    sprintf(str, "TopoCentLB> Fatal error: Unknown topology: %s", _lbtopo);
+    CmiAbort(str);
+  }
+  
+       topo = topofn(count);
+       
+       /*max_neighbors = topo->max_neighbors();
+       
+       topoDegree = new int[count];
+       for(i=0;i<count;i++){
+               topoDegree[i] = 0;
+               topoGraph[i] = new int[count];
+               for(j=0;j<count;j++)
+                       topoGraph[i][j]=0;
+       }
+       
+       neigh = new int[max_neighbors];
+       int max_degree=0;
+       for(i=0;i<count;i++){
+               topo->neighbors(i,neigh,num_neigh);
+               topoDegree[i] = num_neigh;
+               if(num_neigh > max_degree)
+                       max_degree = num_neigh;
+               for(j=0;j<num_neigh;j++)
+                       topoGraph[i][neigh[j]]=1;
+       }
+       //Topology graph constructed
+       delete [] neigh;
+*/
+
+       calculateMST(partgraph,topo,proc_mapping,max_comm_part);
+       CkPrintf("after calculating MST...\n");
+       //Returned partition graph is a Maximum Spanning Tree -- converted in above function itself
+
+       /*for(i=0;i<count;i++)
+               for(j=0;j<count;j++)
+                       if(partmst->edges[i][j]==0)
+                               bytesComm[i][j]=0;*/
+       
+       //Construct the Topology Graph
+       
+       /*int max_part_degree = 0;
+       for(i=0;i<count;i++)
+               if(partmst->nodes[i].degree > max_part_degree)
+                       max_part_degree = partmst->nodes[i].degree;
+       */
+       
+       /*CkPrintf("part,proc mapping..\n");
+       for(i=0;i<count;i++)
+               CkPrintf("%d,%d len:%d\n",i,proc_mapping[i],(partgraph->nodes[i]).num_objs);
+               */
+       int pe;
+       PartGraph::Node* n;
+       for(i=0;i<count;i++){
+               pe = proc_mapping[i];
+               //pe=i;
+               n = &partgraph->nodes[i];
+               //CkPrintf("here..%d,first object:%d\n",n->num_objs,n->obj_list[0]);
+               for(j=0;j<n->num_objs;j++){
+                       stats->to_proc[n->obj_list[j]] = pe;
+                       //if(pe==507)
+                               //CkPrintf(" %d,%d ",n->obj_list[j],pe);
+                       if (_lb_args.debug()>1) 
+        CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),n->obj_list[j],stats->from_proc[n->obj_list[j]],pe);
+               }
+       }
+}
+#include "TopoCentLB.def.h"
diff --git a/src/ck-ldb/TopoCentLB.ci b/src/ck-ldb/TopoCentLB.ci
new file mode 100644 (file)
index 0000000..e0608c9
--- /dev/null
@@ -0,0 +1,11 @@
+module TopoCentLB
+{
+  extern module CentralLB;
+
+  initnode void lbinit (void);
+
+  group [migratable] TopoCentLB : CentralLB
+  {
+    entry void TopoCentLB (const CkLBOptions &);
+  };
+};
diff --git a/src/ck-ldb/TopoCentLB.h b/src/ck-ldb/TopoCentLB.h
new file mode 100644 (file)
index 0000000..fab2ed7
--- /dev/null
@@ -0,0 +1,111 @@
+#ifndef _TOPOCENTLB_H_
+#define _TOPOCENTLB_H_
+
+#include "CentralLB.h"
+#include "topology.h"
+
+void CreateTopoCentLB ();
+
+class TopoCentLB : public CentralLB
+{
+  public:
+    TopoCentLB (const CkLBOptions &opt);
+    TopoCentLB (CkMigrateMessage *m) : CentralLB (m) { };
+
+    void work (CentralLB::LDStats *stats, int count);
+
+    void pup (PUP::er &p) { CentralLB::pup(p); }
+
+               typedef struct{
+                       double key;
+                       int node;
+               } HeapNode;
+
+               class PartGraph {
+               public:
+                       typedef struct{
+                               int degree;
+                               int *obj_list;
+                               int num_objs;
+                               double comm;    //Amount of communication done by this partition -- num of bytes
+                       } Node;
+                       
+                       typedef double Edge;
+
+                       PartGraph(int num_parts,int init_num_objs){
+                               
+                               n_nodes = num_parts;
+                               nodes = new Node[num_parts];
+                               for(int i=0;i<num_parts;i++)
+                               {
+                                       nodes[i].obj_list = new int[init_num_objs];
+                                       nodes[i].num_objs=0;
+                                       nodes[i].degree=0;
+                                       nodes[i].comm=0;
+                               }
+                               
+                               n_edges = num_parts*num_parts;
+                               edges = new Edge*[num_parts];
+                               for(int i=0;i<num_parts;i++)
+                               {
+                                       edges[i] = new Edge[num_parts];
+                                       for(int j=0;j<num_parts;j++)
+                                               edges[i][j] = 0;
+                               }
+                       }
+
+                       PartGraph(PartGraph *pg,int init_num_objs){
+
+                               n_nodes = pg->n_nodes;
+                               n_edges = pg->n_edges;
+                               nodes = new Node[n_nodes];
+                               for(int i=0;i<n_nodes;i++){
+                                       nodes[i].obj_list=new int[init_num_objs];
+                                       nodes[i].num_objs = pg->nodes[i].num_objs;
+                                       nodes[i].degree = pg->nodes[i].degree;
+                                       nodes[i].comm = pg->nodes[i].comm;
+                                       for(int j=0;j<pg->nodes[i].num_objs;j++)
+                                               nodes[i].obj_list[j] = pg->nodes[i].obj_list[j];
+                               }
+                               
+                               edges = new Edge*[n_nodes];
+                               for(int i=0;i<n_nodes;i++){
+                                       edges[i] = new Edge[n_nodes];
+                                       for(int j=0;j<n_nodes;j++)
+                                               edges[i][j] = pg->edges[i][j];
+                               }
+                       }
+
+                       ~PartGraph(){
+                               for(int i=0;i<n_nodes;i++)
+                                       delete[] nodes[i].obj_list;
+                               delete[] nodes;
+                               delete[] edges;
+                       }
+               //private:
+                       Node *nodes;
+                       Edge **edges;
+                       int n_nodes;
+                       int n_edges;
+               };
+               
+               PartGraph *partgraph;
+               LBTopology                      *topo;
+
+               //int **topoGraph;
+               //int *topoDegree;
+               
+               void calculateMST(PartGraph *partgraph,LBTopology *topo,int *proc_mapping,int max_comm_part);
+               void increaseKey(HeapNode *heap,int i,double wt);
+               HeapNode extractMax(HeapNode *heap,int *heapSize);
+               void BuildHeap(HeapNode *heap,int heapSize);
+               void Heapify(HeapNode *heap, int node, int heapSize);
+               int findMaxObjs(int *map,int totalobjs,int count);
+               void computePartitions(CentralLB::LDStats *stats,int count,int *newmap);
+               //static int compare(const void *p,const void *q);
+  private:
+    
+               CmiBool QueryBalanceNow (int step);
+};
+
+#endif /* _TOPOCENTLB_H_ */
index ece3e89925bee9e7bdccd3e6afdf518ce8d5b4c3..96f7af87ac498a63185aaff15b7e309ec530cb57 100644 (file)
@@ -899,9 +899,9 @@ HybridBaseLB.o: HybridBaseLB.C charm++.h charm.h converse.h conv-config.h \
   trace-bluegene.h BaseLB.h HybridBaseLB.h CentralLB.h CentralLB.decl.h \
   CentralLBMsg.h HybridBaseLB.decl.h NeighborLBMsg.h HybridLBMsg.h \
   topology.h GreedyLB.h GreedyLB.decl.h GreedyCommLB.h \
-  GreedyCommLB.decl.h CommLBHeap.h RefineCommLB.h RefinerComm.h \
-  elements.h Set.h heap.h Refiner.h RefineLB.h RefineLB.decl.h \
-  RefineCommLB.decl.h HybridBaseLB.def.h
+  GreedyCommLB.decl.h elements.h Set.h heap.h CommLBHeap.h RefineCommLB.h \
+  RefinerComm.h Refiner.h RefineLB.h RefineLB.decl.h RefineCommLB.decl.h \
+  HybridBaseLB.def.h
        $(CHARMC) -c -I. HybridBaseLB.C
 
 NborBaseLB.o: NborBaseLB.C charm++.h charm.h converse.h conv-config.h \
@@ -1192,7 +1192,7 @@ EveryLB.o: EveryLB.C charm++.h charm.h converse.h conv-config.h \
   PhasebyArrayLB.decl.h RotateLB.decl.h NeighborLB.decl.h \
   NborBaseLB.decl.h NeighborLBMsg.h NeighborCommLB.decl.h WSLB.decl.h \
   HybridLB.decl.h HybridBaseLB.decl.h HybridLBMsg.h TopoLB.decl.h \
-  RefineTopoLB.decl.h EveryLB.def.h
+  RefineTopoLB.decl.h TopoCentLB.decl.h EveryLB.def.h
        $(CHARMC) -c -I. EveryLB.C
 
 DummyLB.o: DummyLB.C charm++.h charm.h converse.h conv-config.h \
@@ -1347,8 +1347,8 @@ GreedyCommLB.o: GreedyCommLB.C charm++.h charm.h converse.h conv-config.h \
   charisma.h charisma.decl.h tempo.h tempo.decl.h waitqd.h waitqd.decl.h \
   sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
   trace-bluegene.h GreedyCommLB.h CentralLB.h BaseLB.h CentralLB.decl.h \
-  CentralLBMsg.h GreedyCommLB.decl.h CommLBHeap.h manager.h \
-  GreedyCommLB.def.h
+  CentralLBMsg.h GreedyCommLB.decl.h elements.h Set.h heap.h CommLBHeap.h \
+  manager.h GreedyCommLB.def.h
        $(CHARMC) -c -I. GreedyCommLB.C
 
 GreedyAgentLB.o: GreedyAgentLB.C charm++.h charm.h converse.h \
@@ -1407,7 +1407,7 @@ Comm1LB.o: Comm1LB.C charm++.h charm.h converse.h conv-config.h \
   sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
   trace-bluegene.h Comm1LB.h CentralLB.h BaseLB.h CentralLB.decl.h \
   CentralLBMsg.h Comm1LB.decl.h CommLBHeap.h GreedyCommLB.h \
-  GreedyCommLB.decl.h Comm1LB.def.h
+  GreedyCommLB.decl.h elements.h Set.h heap.h Comm1LB.def.h
        $(CHARMC) -c -I. Comm1LB.C
 
 OrbLB.o: OrbLB.C charm++.h charm.h converse.h conv-config.h conv-common.h \
@@ -1564,9 +1564,9 @@ HybridLB.o: HybridLB.C charm++.h charm.h converse.h conv-config.h \
   trace-bluegene.h HybridLB.h BaseLB.h CentralLB.h CentralLB.decl.h \
   CentralLBMsg.h HybridBaseLB.h HybridBaseLB.decl.h NeighborLBMsg.h \
   HybridLBMsg.h topology.h HybridLB.decl.h GreedyLB.h GreedyLB.decl.h \
-  GreedyCommLB.h GreedyCommLB.decl.h CommLBHeap.h RefineCommLB.h \
-  RefinerComm.h elements.h Set.h heap.h Refiner.h RefineLB.h \
-  RefineLB.decl.h RefineCommLB.decl.h HybridLB.def.h
+  GreedyCommLB.h GreedyCommLB.decl.h elements.h Set.h heap.h CommLBHeap.h \
+  RefineCommLB.h RefinerComm.h Refiner.h RefineLB.h RefineLB.decl.h \
+  RefineCommLB.decl.h HybridLB.def.h
        $(CHARMC) -c -I. HybridLB.C
 
 TopoLB.o: TopoLB.C charm++.h charm.h converse.h conv-config.h \
@@ -1608,6 +1608,25 @@ RefineTopoLB.o: RefineTopoLB.C charm++.h charm.h converse.h conv-config.h \
   RefineTopoLB.def.h
        $(CHARMC) -c -I. RefineTopoLB.C
 
+TopoCentLB.o: TopoCentLB.C charm++.h charm.h converse.h conv-config.h \
+  conv-common.h conv-mach.h conv-autoconfig.h conv-mach-opt.h pup_c.h \
+  conv-cpm.h conv-cpath.h conv-qd.h conv-random.h conv-lists.h \
+  conv-trace.h persistent.h debug-conv.h pup.h middle.h middle-conv.h \
+  cklists.h ckbitvector.h ckstream.h init.h ckhashtable.h debug-charm.h \
+  CkMarshall.decl.h cksection.h ckcallback.h conv-ccs.h sockRoutines.h \
+  ccs-server.h ckobjQ.h ckreduction.h CkReduction.decl.h \
+  cknodegroupreduction.h CkArrayReductionMgr.decl.h ckmemcheckpoint.h \
+  CkMemCheckpoint.decl.h readonly.h ckarray.h cklocation.h LBDatabase.h \
+  lbdb.h LBDBManager.h LBObj.h LBOM.h LBComm.h LBMachineUtil.h \
+  LBDatabase.decl.h NullLB.decl.h BaseLB.decl.h CkLocation.decl.h \
+  CkArray.decl.h ComlibArrayListener.h ComlibStrategy.h \
+  convcomlibstrategy.h ComlibLearner.h envelope.h CkFutures.decl.h \
+  charisma.h charisma.decl.h tempo.h tempo.decl.h waitqd.h waitqd.decl.h \
+  sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
+  trace-bluegene.h CentralLB.h BaseLB.h CentralLB.decl.h CentralLBMsg.h \
+  TopoCentLB.decl.h TopoCentLB.h topology.h TopoCentLB.def.h
+       $(CHARMC) -c -I. TopoCentLB.C
+
 manager.o: manager.C manager.h CentralLB.h BaseLB.h LBDatabase.h lbdb.h \
   converse.h conv-config.h conv-common.h conv-mach.h conv-autoconfig.h \
   conv-mach-opt.h pup_c.h conv-cpm.h conv-cpath.h conv-qd.h conv-random.h \
@@ -1734,14 +1753,14 @@ ComlibManager.o: ComlibManager.C ComlibManager.h charm++.h charm.h \
   charisma.h charisma.decl.h tempo.h tempo.decl.h waitqd.h waitqd.decl.h \
   sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
   trace-bluegene.h comlib.h router.h convcomlibmanager.h ComlibStats.h \
-  comlib.decl.h EachToManyMulticastStrategy.h routerstrategy.h prefixrouter.h \
+  comlib.decl.h EachToManyMulticastStrategy.h routerstrategy.h \
   gridrouter.h petable.h graphrouter.h de.h treerouter.h 3dgridrouter.h \
-  DirectMulticastStrategy.h ComlibSectionInfo.h StreamingStrategy.h \
-  DummyStrategy.h MPIStrategy.h NodeMulticast.h MsgPacker.h register.h \
-  pup_cmialloc.h RingMulticastStrategy.h MultiRingMulticast.h \
-  PipeBroadcastStrategy.h pipebroadcastconverse.h BroadcastStrategy.h \
-  MeshStreamingStrategy.h PrioStreaming.h qd.h CentralLB.h BaseLB.h \
-  CentralLB.decl.h CentralLBMsg.h comlib.def.h
+  prefixrouter.h DirectMulticastStrategy.h ComlibSectionInfo.h \
+  StreamingStrategy.h DummyStrategy.h MPIStrategy.h NodeMulticast.h \
+  MsgPacker.h register.h pup_cmialloc.h RingMulticastStrategy.h \
+  MultiRingMulticast.h PipeBroadcastStrategy.h pipebroadcastconverse.h \
+  BroadcastStrategy.h MeshStreamingStrategy.h PrioStreaming.h qd.h \
+  CentralLB.h BaseLB.h CentralLB.decl.h CentralLBMsg.h comlib.def.h
        $(CHARMC) -c -I. ComlibManager.C
 
 MPIStrategy.o: MPIStrategy.C MPIStrategy.h ComlibManager.h charm++.h \
@@ -1839,7 +1858,8 @@ EachToManyMulticastStrategy.o: EachToManyMulticastStrategy.C \
   sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
   trace-bluegene.h comlib.h router.h convcomlibmanager.h ComlibStats.h \
   comlib.decl.h routerstrategy.h gridrouter.h petable.h graphrouter.h \
-  de.h treerouter.h 3dgridrouter.h AAPLearner.h AAMLearner.h prefixrouter.h 
+  de.h treerouter.h 3dgridrouter.h prefixrouter.h AAPLearner.h \
+  AAMLearner.h
        $(CHARMC) -c -I. EachToManyMulticastStrategy.C
 
 ComlibSectionInfo.o: ComlibSectionInfo.C ComlibManager.h charm++.h \
@@ -1879,7 +1899,7 @@ AAPLearner.o: AAPLearner.C AAPLearner.h comlib.h converse.h conv-config.h \
   trace-bluegene.h router.h ComlibManager.h convcomlibmanager.h \
   ComlibStats.h comlib.decl.h EachToManyMulticastStrategy.h \
   routerstrategy.h gridrouter.h petable.h graphrouter.h de.h treerouter.h \
-  3dgridrouter.h prefixrouter.h 
+  3dgridrouter.h prefixrouter.h
        $(CHARMC) -c -I. AAPLearner.C
 
 ComlibStats.o: ComlibStats.C ComlibStats.h charm++.h charm.h converse.h \
@@ -2189,24 +2209,6 @@ graphrouter.o: graphrouter.C graphrouter.h converse.h conv-config.h \
   trace-bluegene.h router.h petable.h hypercubetopology.h
        $(CHARMC) -c -I. graphrouter.C
 
-prefixrouter.o: prefixrouter.C prefixrouter.h converse.h conv-config.h \
-  conv-common.h conv-mach.h conv-autoconfig.h conv-mach-opt.h pup_c.h \
-  conv-cpm.h conv-cpath.h conv-qd.h conv-random.h conv-lists.h \
-  conv-trace.h persistent.h debug-conv.h comlib.h charm++.h charm.h pup.h \
-  middle.h middle-conv.h cklists.h ckbitvector.h ckstream.h init.h \
-  ckhashtable.h debug-charm.h CkMarshall.decl.h cksection.h ckcallback.h \
-  conv-ccs.h sockRoutines.h ccs-server.h ckobjQ.h ckreduction.h \
-  CkReduction.decl.h cknodegroupreduction.h CkArrayReductionMgr.decl.h \
-  ckmemcheckpoint.h CkMemCheckpoint.decl.h readonly.h ckarray.h \
-  cklocation.h LBDatabase.h lbdb.h LBDBManager.h LBObj.h LBOM.h LBComm.h \
-  LBMachineUtil.h LBDatabase.decl.h NullLB.decl.h BaseLB.decl.h \
-  CkLocation.decl.h CkArray.decl.h ComlibArrayListener.h ComlibStrategy.h \
-  convcomlibstrategy.h ComlibLearner.h envelope.h CkFutures.decl.h \
-  charisma.h charisma.decl.h tempo.h tempo.decl.h waitqd.h waitqd.decl.h \
-  sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
-  trace-bluegene.h router.h 
-       $(CHARMC) -c -I. prefixrouter.C
-
 hypercubetopology.o: hypercubetopology.C hypercubetopology.h \
   graphrouter.h converse.h conv-config.h conv-common.h conv-mach.h \
   conv-autoconfig.h conv-mach-opt.h pup_c.h conv-cpm.h conv-cpath.h \
@@ -2303,3 +2305,21 @@ pipelinestrategy.o: pipelinestrategy.C pipelinestrategy.h ckhashtable.h \
   comlib.h router.h
        $(CHARMC) -c -I. pipelinestrategy.C
 
+prefixrouter.o: prefixrouter.C prefixrouter.h converse.h conv-config.h \
+  conv-common.h conv-mach.h conv-autoconfig.h conv-mach-opt.h pup_c.h \
+  conv-cpm.h conv-cpath.h conv-qd.h conv-random.h conv-lists.h \
+  conv-trace.h persistent.h debug-conv.h comlib.h charm++.h charm.h pup.h \
+  middle.h middle-conv.h cklists.h ckbitvector.h ckstream.h init.h \
+  ckhashtable.h debug-charm.h CkMarshall.decl.h cksection.h ckcallback.h \
+  conv-ccs.h sockRoutines.h ccs-server.h ckobjQ.h ckreduction.h \
+  CkReduction.decl.h cknodegroupreduction.h CkArrayReductionMgr.decl.h \
+  ckmemcheckpoint.h CkMemCheckpoint.decl.h readonly.h ckarray.h \
+  cklocation.h LBDatabase.h lbdb.h LBDBManager.h LBObj.h LBOM.h LBComm.h \
+  LBMachineUtil.h LBDatabase.decl.h NullLB.decl.h BaseLB.decl.h \
+  CkLocation.decl.h CkArray.decl.h ComlibArrayListener.h ComlibStrategy.h \
+  convcomlibstrategy.h ComlibLearner.h envelope.h CkFutures.decl.h \
+  charisma.h charisma.decl.h tempo.h tempo.decl.h waitqd.h waitqd.decl.h \
+  sdag.h ckcheckpoint.h CkCheckpoint.decl.h ckarrayreductionmgr.h trace.h \
+  trace-bluegene.h router.h
+       $(CHARMC) -c -I. prefixrouter.C
+
index f97f23258cbfea905b2811bff9c595dc2a7f202c..f1127e4ed2058e9f0b66f6a847d378a2b855aede 100644 (file)
@@ -184,7 +184,7 @@ CKHEADERS=ck.h ckstream.h envelope.h init.h qd.h charm.h charm++.h \
          BaseLB.h CentralLB.h CentralLBMsg.h RandCentLB.h RecBisectBfLB.h \
          RefineLB.h RefineKLB.h RefineCommLB.h OrbLB.h \
          GreedyLB.h GreedyCommLB.h GreedyAgentLB.h Comm1LB.h MetisLB.h \
-      TopoLB.h RefineTopoLB.h   PhasebyArrayLB.h RotateLB.h GridCommLB.h DummyLB.h  \
+      TopoLB.h RefineTopoLB.h  TopoCentLB.h  PhasebyArrayLB.h RotateLB.h GridCommLB.h DummyLB.h  \
          NborBaseLB.h HybridBaseLB.h HybridLB.h HybridLBMsg.h \
          NeighborLB.h NeighborCommLB.h NeighborLBMsg.h WSLB.h \
          BlueGene.h middle.h middle-conv.h middle-blue.h \
@@ -197,7 +197,7 @@ CKHEADERS=ck.h ckstream.h envelope.h init.h qd.h charm.h charm++.h \
           DummyLB.decl.h RotateLB.decl.h RefineLB.decl.h RefineKLB.decl.h  \
           RefineCommLB.decl.h OrbLB.decl.h GreedyLB.decl.h GreedyCommLB.decl.h \
           Comm1LB.decl.h GreedyAgentLB.decl.h GridCommLB.decl.h \
-         PhasebyArrayLB.decl.h TopoLB.decl.h RefineTopoLB.decl.h\
+         PhasebyArrayLB.decl.h TopoLB.decl.h RefineTopoLB.decl.h TopoCentLB.decl.h \
           NborBaseLB.decl.h NeighborLB.decl.h NeighborCommLB.decl.h \
           HybridBaseLB.decl.h HybridLB.decl.h WSLB.decl.h EveryLB.decl.h \
           charisma.decl.h TraceSummary.decl.h BlueGene.decl.h \