New load balancer, RecBisectBfLB
authorRobert Brunner <rbrunner@uiuc.edu>
Mon, 3 Jan 2000 20:55:03 +0000 (20:55 +0000)
committerRobert Brunner <rbrunner@uiuc.edu>
Mon, 3 Jan 2000 20:55:03 +0000 (20:55 +0000)
src/ck-ldb/RecBisectBfLB.C [new file with mode: 0644]
src/ck-ldb/RecBisectBfLB.ci [new file with mode: 0644]
src/ck-ldb/RecBisectBfLB.h [new file with mode: 0644]
src/ck-ldb/bitvecset.c [new file with mode: 0644]
src/ck-ldb/bitvecset.h [new file with mode: 0644]
src/ck-ldb/fifoInt.c [new file with mode: 0644]
src/ck-ldb/fifoInt.h [new file with mode: 0644]
src/ck-ldb/graph.c [new file with mode: 0644]
src/ck-ldb/graph.h [new file with mode: 0644]
src/scripts/Makefile

diff --git a/src/ck-ldb/RecBisectBfLB.C b/src/ck-ldb/RecBisectBfLB.C
new file mode 100644 (file)
index 0000000..cebddf4
--- /dev/null
@@ -0,0 +1,308 @@
+#include <charm++.h>
+
+#if CMK_LBDB_ON
+
+#include "CkLists.h"
+
+
+#include "RecBisectBfLB.h"
+#include "RecBisectBfLB.def.h"
+
+extern "C" {
+IntQueue * fifoInt_create(int size);
+int fifoInt_enqueue(IntQueue *q, int value);
+int fifoInt_empty(IntQueue *q);
+int fifoInt_dequeue(IntQueue *q);
+}
+
+extern "C" {
+  Graph * initGraph(int v, int e);
+  nextVertex(Graph *g, int v, float w);
+  finishVertex(Graph *g);
+  addEdge(Graph *g, int w, float w2);
+  graph_weightof(Graph *g, int vertex);
+  numNeighbors(Graph *g, int node);
+  getNeighbor(Graph *g, int d , int i);
+  printGraph(Graph *g);
+
+  int bvset_size(BV_Set *);
+  int bvset_find(BV_Set *, int i);
+  bvset_enumerate(BV_Set * s1, int **p1, int *numP1);
+  bvset_insert(BV_Set *ss1, int t1);
+  BV_Set *makeSet(int *nodes, int numNodes, int V);
+  BV_Set *makeEmptySet( int V);
+
+
+/*  IntQueue * fifoInt_create(int x);
+  int fifoInt_empty(IntQueue *q);
+  fifoInt_enqueue(IntQueue *q1, int r1);
+  fifoInt_dequeue(IntQueue *q);
+*/
+}
+
+
+
+void CreateRecBisectBfLB()
+{
+  //  CkPrintf("[%d] creating RecBisectBfLB %d\n",CkMyPe(),loadbalancer);
+  loadbalancer = CProxy_RecBisectBfLB::ckNew();
+  //  CkPrintf("[%d] created RecBisectBfLB %d\n",CkMyPe(),loadbalancer);
+}
+
+RecBisectBfLB::RecBisectBfLB()
+{
+  if (CkMyPe() == 0)
+    CkPrintf("[%d] RecBisectBfLB created\n",CkMyPe());
+}
+
+CmiBool RecBisectBfLB::QueryBalanceNow(int _step)
+{
+  //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
+  return CmiTrue;
+}
+
+CLBMigrateMsg* RecBisectBfLB::Strategy(CentralLB::LDStats* stats, int numPartitions)
+{
+  int i;
+  PartitionList *partitions;
+
+  
+  CkPrintf("[%d] RecBisectBfLB strategy\n",CkMyPe());
+  ObjGraph og(numPartitions, stats);
+
+  CkPrintf("[%d] RecBisectBfLB: og made. numPartitions: %d\n",
+          CkMyPe(), numPartitions);
+
+  Graph *g =  convertGraph( &og);
+  CkPrintf("[%d] RecBisectBfLB: graph converted\n",CkMyPe());
+    
+//    printGraph(g);
+    int  * nodes = (int *) malloc(sizeof(int)*g->V);
+
+
+    for (i=0; i<g->V; i++)
+      nodes[i] = i;
+
+    partitions = (PartitionList *) malloc(sizeof(PartitionList));
+    partitions->next = 0;
+    partitions->max = numPartitions;
+    partitions->partitions = (PartitionRecord *) malloc(sizeof(PartitionRecord)* numPartitions);
+    
+  recursivePartition(numPartitions, g, nodes, g->V,  partitions);
+  
+  CmiPrintf("\ngraph partitioned\n");
+  
+//  printPartitions(partitions);
+
+  CkVector migrateInfo;
+
+
+ for (i=0; i<partitions->max; i++) {
+   CmiPrintf("[%d] (%d) : \t", i, partitions->partitions[i].size);
+   int j;
+   for (j=0; j< partitions->partitions[i].size; j++) {
+     CmiPrintf("%d ", partitions->partitions[i].nodeArray[j]);
+     const int objref = partitions->partitions[i].nodeArray[j];
+     ObjGraph::Node n = og.GraphNode(objref);
+/*     CkPrintf("Moving %d(%d) from %d to %d\n",objref,
+               stats[n.proc].objData[n.index].handle.id.id[0],n.proc,i);
+  */
+   
+     if (n.proc != i) {
+       MigrateInfo *migrateMe = new MigrateInfo;
+       migrateMe->obj = stats[n.proc].objData[n.index].handle;
+       migrateMe->from_pe = n.proc;
+       migrateMe->to_pe = i;
+       migrateInfo.push_back((void*)migrateMe);
+     }
+   }
+ }
+
+  int migrate_count=migrateInfo.size();
+  CLBMigrateMsg* msg = new(&migrate_count,1) CLBMigrateMsg;
+  msg->n_moves = migrate_count;
+  for(int i=0; i < migrate_count; i++) {
+    MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
+    msg->moves[i] = *item;
+    delete item;
+    migrateInfo[i] = 0;
+  }
+
+  CmiPrintf("returning from partitioner strategy\n");
+  return msg;
+};
+
+Graph *
+RecBisectBfLB::convertGraph(ObjGraph *og) {
+
+  Graph *g;
+  
+  int V, E, i, j;
+
+
+  V = og->NodeCount();
+  E = og->EdgeCount();
+
+  g = initGraph(V, E);
+
+//  CkPrintf("[%d] RecBisectBfLB: convert (v=%d, e=%d, g=%d\n",
+//        CkMyPe(), V, E, (int) g);
+
+  for (i =0; i<V; i++) {
+    nextVertex(g, i, og->LoadOf(i));
+
+    ObjGraph::Node n = og->GraphNode(i);
+    ObjGraph::Edge *l;
+
+//  CkPrintf("[%d] RecBisectBfLB: convert before addEdge Loop\n");
+    
+    l = n.edges_from();
+    while (l) {
+      // CkPrintf("[%d] RecBisectBfLB: convert in addEdge Loop1\n");
+      addEdge(g, l->to_node, 1.0); /* get edgeweight */
+      l = l->next_from();
+    }
+
+    l = n.edges_to();
+    while (l) {
+      // CkPrintf("[%d] RecBisectBfLB: convert in addEdge Loop2\n");
+      addEdge(g, l->from_node, 1.0); /* get edgeweight */
+      l = l->next_to();
+    }
+    finishVertex(g);
+  }
+  return g;
+}
+
+void RecBisectBfLB::partitionInTwo(Graph *g, int nodes[], int numNodes, 
+              int ** pp1, int *numP1, int **pp2, int *numP2, 
+              int ratio1, int ratio2)
+{
+  int r1, r2, t1, t2, doneUpto, weight1, weight2;
+  BV_Set *all, *s1, *s2; //, *makeSet(int * nodes, int num, int max);
+  IntQueue * q1, *q2;
+  int * p1, *p2;
+
+  r1 = nodes[0];
+  r2 = nodes[numNodes-1];
+  /* Improvement: select r1 and r2 more carefully: e.g. farthest away from each other. */
+
+  all = makeSet(nodes, numNodes, g->V);
+  s1 = makeEmptySet(g->V);
+  s2 = makeEmptySet(g->V);
+  doneUpto = 0;
+
+  q1 = fifoInt_create(g->V);
+  q2 = fifoInt_create(g->V);
+
+  fifoInt_enqueue(q1, r1);
+  fifoInt_enqueue(q2, r2);
+  /*  printf("r1=%d, r2=%d\n", r1, r2);*/
+
+  weight1 = 0; weight2 = 0;
+  while (   (bvset_size(s1) + bvset_size(s2)) < numNodes ) {
+    if (weight1*ratio2 < weight2*ratio1) 
+      weight1 += addToQ(q1, g, all, s1,s2);      
+    else 
+      weight2 += addToQ(q2, g, all, s2,s1);
+  }
+
+  bvset_enumerate(s1, &p1, numP1);
+  bvset_enumerate(s2, &p2, numP2);
+  *pp1 = p1;
+  *pp2 = p2;
+}
+
+int 
+RecBisectBfLB::findNextUnassigned(int max, BV_Set * all, BV_Set * s1, BV_Set * s2) {
+  int i;
+  for (i=0; i<max; i++)
+    { 
+      if (bvset_find(all, i))
+       if ( (!bvset_find(s1,i)) && (!bvset_find(s2,i)) ) 
+         return i;
+    }
+  return (max + 1);
+}
+
+float RecBisectBfLB::addToQ(IntQueue * q, Graph *g, BV_Set * all, 
+           BV_Set * s1, BV_Set * s2) {
+  int t1, doneUpto;
+  float weightAdded;
+
+  weightAdded = 0.0;
+
+  if (fifoInt_empty(q)) {
+    doneUpto = findNextUnassigned(g->V, all, s1, s2);
+    if (doneUpto < g->V) fifoInt_enqueue(q,doneUpto); 
+  }
+  if (!fifoInt_empty(q) ) {
+    t1 = fifoInt_dequeue(q);
+    if (bvset_find(all, t1)) /* t1 is a vertex of the given partition */
+      if ( (!bvset_find(s1, t1)) && ( !bvset_find(s2, t1)) ) {
+       bvset_insert(s1, t1);
+       weightAdded = graph_weightof(g, t1); 
+       /*       printf("adding %d to s\n", t1); */
+       enqChildren(q, g, all, s1, s2, t1);
+      }
+  }
+  return weightAdded;
+}
+
+void RecBisectBfLB::enqChildren(IntQueue * q, Graph *g, BV_Set * all, 
+           BV_Set * s1, BV_Set * s2, int node) {
+
+  int nbrs, i, j;
+
+  nbrs = numNeighbors(g, node);
+  for (i=0; i<nbrs; i++) {
+    j = getNeighbor(g, node, i);
+    if (  (bvset_find(all,j)) && (!bvset_find(s1,j)) && (!bvset_find(s2,j)) ) {
+      fifoInt_enqueue(q, j);
+    }
+  } 
+}
+
+
+void RecBisectBfLB::addPartition(PartitionList * partitions, int * nodes, int num) {
+  int i;
+  i =  partitions->next++;
+  partitions->partitions[i].size = num;
+  partitions->partitions[i].nodeArray = nodes ;
+}
+
+void RecBisectBfLB::printPartitions(PartitionList * partitions) {
+ int i,j;
+
+ CmiPrintf("\n**************************\n The Partitions are: \n");
+ for (i=0; i<partitions->max; i++) {
+   CmiPrintf("[%d] (%d) : \t", i, partitions->partitions[i].size);
+   for (j=0; j< partitions->partitions[i].size; j++)
+     CmiPrintf("%d ", partitions->partitions[i].nodeArray[j]);
+   CmiPrintf("\n");
+ }
+}
+
+void RecBisectBfLB::recursivePartition(int numParts, Graph *g, int nodes[], int numNodes, 
+                  PartitionList *partitions) {
+  
+  int *p1, *p2;
+  int first, second,i ;
+  int numP1, numP2;
+  
+  if (numParts < 2) {
+    addPartition(partitions, nodes, numNodes);
+  }
+  else {
+    first = numParts/2;
+    second = numParts - first;
+    partitionInTwo(g, nodes, numNodes, &p1, &numP1, &p2, &numP2, first,second);
+    recursivePartition(first, g, p1, numP1, partitions);
+    recursivePartition(second, g, p2, numP2,  partitions);
+    free( nodes);
+  }  
+}
+
+#endif
+
diff --git a/src/ck-ldb/RecBisectBfLB.ci b/src/ck-ldb/RecBisectBfLB.ci
new file mode 100644 (file)
index 0000000..00bf2e9
--- /dev/null
@@ -0,0 +1,9 @@
+module RecBisectBfLB {
+
+extern module CentralLB;
+
+group RecBisectBfLB : CentralLB {
+  entry void RecBisectBfLB(void);  
+};
+
+};
diff --git a/src/ck-ldb/RecBisectBfLB.h b/src/ck-ldb/RecBisectBfLB.h
new file mode 100644 (file)
index 0000000..73ecba1
--- /dev/null
@@ -0,0 +1,55 @@
+
+#ifndef _RECBISECTBFLB_H_
+#define _RECBISECTBFLB_H_
+
+#include "CentralLB.h"
+#include "RecBisectBfLB.decl.h"
+
+#include "ObjGraph.h"
+#include "graph.h"
+#include "bitvecset.h"
+#include "fifoInt.h"
+
+void CreateRecBisectBfLB();
+
+typedef struct {
+  int size;
+  int * nodeArray;
+} PartitionRecord;
+
+
+typedef struct {
+  int next;
+  int max;
+  PartitionRecord * partitions;
+} PartitionList;
+
+
+class RecBisectBfLB : public CentralLB {
+public:
+  RecBisectBfLB();
+private:
+  CmiBool QueryBalanceNow(int step);
+  CLBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
+
+  Graph * convertGraph(ObjGraph *og);
+  
+  void  partitionInTwo(Graph *g, int nodes[], int numNodes, 
+                int ** pp1, int *numP1, int **pp2, int *numP2, 
+                int ratio1, int ratio2);  
+  int findNextUnassigned(int max, BV_Set * all, BV_Set * s1, BV_Set * s2);
+  float addToQ(IntQueue * q, Graph *g, BV_Set * all, BV_Set * s1, BV_Set * s2);
+  
+  void  enqChildren(IntQueue * q, Graph *g, BV_Set * all, 
+             BV_Set * s1, BV_Set * s2, int node) ;
+  
+  void addPartition(PartitionList * partitions, int * nodes, int num) ;
+  void printPartitions(PartitionList * partitions) ;
+  void recursivePartition(int numParts, Graph *g, int nodes[], int numNodes, 
+                    PartitionList *partitions);
+
+};
+
+
+
+#endif /* _RECBISECTBFLB_H_ */
diff --git a/src/ck-ldb/bitvecset.c b/src/ck-ldb/bitvecset.c
new file mode 100644 (file)
index 0000000..bf40e99
--- /dev/null
@@ -0,0 +1,84 @@
+#include "bitvecset.h"
+
+BV_Set * makeSet(int *list, int size, int max);
+
+BV_Set * makeEmptySet(int max)
+{
+ int x;
+
+ return ( makeSet(&x, 0, max));
+  
+}
+
+
+BV_Set * makeSet(int *list, int size, int max)
+{
+  BV_Set * s;
+  int i;
+
+  s = (BV_Set *) malloc(sizeof(BV_Set));
+  s->max = max;
+  s->size = size;
+  s->vector = (short *) malloc(sizeof(short)*(1+max));
+
+  for (i = 0; i< max; i++)
+      s->vector[i] = 0;
+  for (i = 0; i< size; i++)
+    if (list[i] <= max)
+      s->vector[ list[i]] = 1;
+    else printf("***ERROR: makeSet received %d, when max was supposed to be %d",
+               list[i], max);
+
+  return s;
+}
+
+
+bvset_insert(BV_Set * s, int value)
+  {
+    if (value > s->max) 
+      printf("BV_Set error. inserting value %d in a set where max is %d\n",
+            value, s->max);
+    else {
+      if (s->vector[value]) return;
+      else { 
+       s->vector[value] = 1;
+       s->size++;
+      }
+      
+    }
+  }
+
+
+int bvset_find(BV_Set * s, int value)
+  {
+    if (value > s->max)  
+      printf("BV_Set error.  *find* on a value %d in a set where max is %d\n",
+            value, s->max);
+    else 
+      return (s->vector[value]);
+  }
+
+int bvset_size(BV_Set * s) {
+  return s->size;
+}
+
+bvset_enumerate(BV_Set * s, int **list, int *size)
+{
+  int i, j;
+
+  /*
+  printf("set is: ");
+  for (i=0; i<=s->max; i++)
+    printf("%d ", s->vector[i]);
+  printf("\n returning list: "); */
+
+  *list = (int *) malloc(sizeof(int)*s->size);
+  *size = s->size;
+  j = 0;
+  for (i=0; i<=s->max; i++)
+    if (s->vector[i]) (*list)[j++] = i;
+
+  /*  for (i=0; i< *size; i++)
+    printf("%d ", (*list)[i]); */
+}
+
diff --git a/src/ck-ldb/bitvecset.h b/src/ck-ldb/bitvecset.h
new file mode 100644 (file)
index 0000000..980443a
--- /dev/null
@@ -0,0 +1,13 @@
+#ifndef _BITVECSET_H
+
+#define  _BITVECSET_H
+
+typedef struct {
+  int max;
+  int size;
+  short *vector;
+} BV_Set ;
+
+
+
+#endif
diff --git a/src/ck-ldb/fifoInt.c b/src/ck-ldb/fifoInt.c
new file mode 100644 (file)
index 0000000..12c1f23
--- /dev/null
@@ -0,0 +1,39 @@
+#include "fifoInt.h"
+
+IntQueue * fifoInt_create(int size) {
+
+  IntQueue *q;
+  q = (IntQueue *) malloc(sizeof(IntQueue));
+
+  q->max = size;
+  q->size = 0;
+  q->vector = (int *) malloc(sizeof(int)* (size + 1));
+  q->head = 0;
+  q->tail = -1;
+  return q;
+    
+}
+
+int fifoInt_empty(IntQueue *q) {
+  return (q->size == 0);
+}
+
+fifoInt_enqueue(IntQueue *q, int value) {
+  if (q->size >= q->max) {
+    printf("queue overflow\n");
+    return;
+  }
+  q->size++;
+  q->tail = (q->tail +1) % q->max;
+  q->vector[q->tail] = value;
+}
+
+
+int fifoInt_dequeue(IntQueue *q) {
+  int v;
+  if (q->size <= 0) { printf("queue underflow\n"); return; }
+  q->size--;
+  v = q->vector[q->head];
+  q->head = (q->head+1) % q->max;
+  return v;
+}
diff --git a/src/ck-ldb/fifoInt.h b/src/ck-ldb/fifoInt.h
new file mode 100644 (file)
index 0000000..bd783c6
--- /dev/null
@@ -0,0 +1,13 @@
+#ifndef _FIFOINT_H
+#define  _FIFOINT_H
+
+typedef struct {
+  int size;
+  int max;
+  int head;
+  int tail;
+  int *vector;
+} IntQueue;
+
+
+#endif
diff --git a/src/ck-ldb/graph.c b/src/ck-ldb/graph.c
new file mode 100644 (file)
index 0000000..98a0120
--- /dev/null
@@ -0,0 +1,149 @@
+#include "graph.h"
+
+#define printf CmiPrintf
+printPartition(Graph * g, int nodes[], int numNodes)
+{
+  int i;
+  for (i=0; i<numNodes; i++)
+    printf("\t%d", nodes[i]);
+  printf("\n");
+
+}
+
+intSqrt(int x)
+{ 
+  int y;
+  y = 4; /* change later */
+  return y; 
+}
+
+Graph * initGraph(int V, int E) {
+  Graph *g;
+
+  int i, j, stride, n;
+
+  g = (Graph *) malloc(sizeof(Graph));
+
+  g->V = V;
+  g->E = E ;
+  g->vertices = (VertexRecord *) malloc(V*sizeof(VertexRecord));
+  g->edges = (int *) malloc( 2* (1 + g->E) * sizeof(int));
+  g->currentVertex = -1;
+  g->currentEdge = 0;
+  return g;
+}
+
+nextVertex(Graph *g, int v, float weight)
+{
+  int current;
+
+  g->currentVertex++;
+  current = g->currentVertex; 
+  g->vertices[current].index = v;
+  g->vertices[current].weight = weight;
+  g->vertices[current].firstEdge = g->currentEdge;
+  g->vertices[current].numEdges = 0;
+/*  printf("next vertex is: %d \n", current);*/
+
+}
+
+
+addEdge(Graph *g, int w, float weight)
+{
+  /* for now , ignore weight */
+  int v, i;
+  v = g->currentVertex;
+
+/*
+  CmiPrintf("addEdge: graph: %d, v=%d, w=%d, wt=%f, currentEdge=%d\n", 
+          (int) g, v, w, weight, g->currentEdge, i);
+  CmiPrintf("addEdge: firstedge = %d, numEdges = %d\n",
+           g->vertices[v].firstEdge, g->vertices[v].numEdges);
+*/
+   i = g->vertices[v].firstEdge;
+   while (i < g->currentEdge) {
+     if (g->edges[i] == w) { 
+       return; /* was duplicate edge */ }
+     i++;
+   }
+
+/*  printf("adding (%d,%d) at %d \n", v, w, g->currentEdge);*/
+
+  g->vertices[v].numEdges++;
+  g->edges[g->currentEdge++] = w;
+
+}
+
+finishVertex(Graph *g) {
+
+if (g->vertices[g->currentVertex].numEdges != g->currentEdge - g->vertices[g->currentVertex].firstEdge)
+ printf("Error in finishVertex\n");
+  /* finish up the previous vertex's record. 
+     Nothing needs to be done here in the current scheme.*/
+}
+
+
+Graph *generateRandomGraph(int numNodes) {
+  
+ Graph *g;
+
+ int i, j, stride, n;
+
+ g = (Graph *) malloc(sizeof(Graph));
+ g->vertices = (VertexRecord *) malloc(numNodes*sizeof(VertexRecord));
+ g->V = numNodes;
+ g->E = 4* g->V ;
+ g->edges = (int *) malloc( (1 + g->E) * sizeof(int));
+ stride = intSqrt(g->V);
+
+ n = 0;
+ for (i = 0; i<g->V; i++) {
+   g->vertices[i].index = i;
+   g->vertices[i].firstEdge = n;
+   g->vertices[i].numEdges = 4;
+   g->vertices[i].weight = 1.0;
+
+   g->edges[n++] = (i + numNodes - 1) % numNodes;
+   g->edges[n++] = (i + 1) % numNodes;
+   
+   g->edges[n++] = (i +numNodes - stride) % numNodes;
+   g->edges[n++] = (i + stride) % numNodes;
+ }
+return g;
+}
+
+
+
+
+printGraph(Graph *g) {
+  int i, j;
+
+   CmiPrintf("%d vertices, %d edges \n", g->V, g->E); 
+  for (i=0; i< g->V; i++)
+    { printf("\n %d: (%d)\t", i, g->vertices[i].numEdges ); 
+      for (j=0; j<g->vertices[i].numEdges; j++) 
+       printf(" %d,", g->edges[g->vertices[i].firstEdge + j ]); }
+
+ }
+
+int numNeighbors(Graph *g, int node) {
+
+  return g->vertices[node].numEdges;
+}
+
+int getNeighbor(Graph *g, int node, int i) {
+  
+  if (i >= g->vertices[node].numEdges) {
+    printf("error: node %d has only %d neighbors. You asked for %d'th nbr\n",
+          node, g->vertices[node].numEdges, i);
+    return 0; 
+  }
+  return   g->edges [ g->vertices[node].firstEdge + i];
+  
+}
+
+float graph_weightof(Graph *g, int vertex) {
+ return 1.0;
+}
diff --git a/src/ck-ldb/graph.h b/src/ck-ldb/graph.h
new file mode 100644 (file)
index 0000000..23a60f9
--- /dev/null
@@ -0,0 +1,24 @@
+#ifndef _GRAPH_H
+
+#define _GRAPH_H
+
+typedef struct {
+  int index;
+  float weight;
+  int firstEdge;
+  int numEdges;
+} VertexRecord;
+
+
+typedef struct {
+  int V, E;
+  VertexRecord * vertices;
+  int * edges;
+  int currentVertex; /* needed during construction of graph */
+  int currentEdge; /* needed during construction of graph */
+} Graph;
+
+
+Graph * generateRandomGraph(int numNodex);
+
+#endif
index 66d1c66c0a95ef1400958b194bd48f9199b7180f..507946a53cf1b497f3ed65fc03a2de82656ad6bf 100644 (file)
@@ -64,7 +64,9 @@ ALLHEADERS=charm++.h ckstream.h charm.h cpthreads.h converse.h \
        pvm3.h sdag.h CDep.h CCounter.h CMsgBuffer.h CWhenTrigger.h \
        TList.h idl.h ckarray.h tempo.h waitqd.h LBDatabase.h \
        lbdb.h LBDBManager.h LBComm.h LBOM.h LBObj.h LBMachineUtil.h \
-       Refiner.h ObjGraph.h CentralLB.h RandCentLB.h RefineLB.h MetisLB.h \
+       Refiner.h ObjGraph.h CentralLB.h RandCentLB.h \
+       RecBisectBfLB.h graph.h fifoInt.h bitvecset.h \
+       RefineLB.h MetisLB.h \
        HeapCentLB.h Set.h elements.h heap.h conv-ccs.h NeighborLB.h \
        WSLB.h CkLists.h GreedyRefLB.h RandRefLB.h CommLB.h CommLBHeap.h
 
@@ -136,6 +138,7 @@ CVHEADERS=converse.h conv-mach.h conv-mach.sh \
           ../include/LBDatabase.decl.h LBDatabase.def.h \
           ../include/CentralLB.decl.h CentralLB.def.h \
           ../include/RandCentLB.decl.h RandCentLB.def.h \
+          ../include/RecBisectBfLB.decl.h RecBisectBfLB.def.h \
           ../include/MetisLB.decl.h MetisLB.def.h \
           ../include/RefineLB.decl.h RefineLB.def.h \
           ../include/HeapCentLB.decl.h HeapCentLB.def.h \
@@ -253,7 +256,8 @@ CKHEADERS=ck.h ckstream.h envelope.h init.h qd.h charm.h charm++.h trace.h \
           ckfutures.h ckarray.h tempo.h waitqd.h LBDatabase.h lbdb.h \
          LBDBManager.h LBComm.h LBOM.h LBObj.h LBMachineUtil.h \
          Refiner.h ObjGraph.h heap.h elements.h CommLBHeap.h\
-         CentralLB.h RandCentLB.h RefineLB.h HeapCentLB.h CommLB.h\
+         CentralLB.h RandCentLB.h RecBisectBfLB.h \
+         RefineLB.h HeapCentLB.h CommLB.h\
          MetisLB.h NeighborLB.h WSLB.h GreedyRefLB.h RandRefLB.h CkLists.h \
          $(CVHEADERS)
 
@@ -263,7 +267,8 @@ LIBCK_CORE=init.o register.o qd.o ck.o main.o msgalloc.o ckfutures.o \
            ckarray.o tempo.o waitqd.o LBDatabase.o lbdb.o \
           LBDBManager.o LBComm.o LBObj.o LBMachineUtil.o Refiner.o \
           ObjGraph.o \
-          CentralLB.o RandCentLB.o MetisLB.o RefineLB.o Set.o CommLB.o\
+          CentralLB.o RandCentLB.o RecBisectBfLB.o graph.o bitvecset.o fifoInt.o \
+          MetisLB.o RefineLB.o Set.o CommLB.o\
            HeapCentLB.o heap.o NeighborLB.o WSLB.o GreedyRefLB.o \
           RandRefLB.o CommLBHeap.o
 
@@ -297,6 +302,9 @@ libtrace-summary.a: $(LIBTRACE_SUMM)
 ../include/RandCentLB.decl.h : RandCentLB.decl.h
        /bin/cp RandCentLB.decl.h ../include
 
+../include/RecBisectBfLB.decl.h : RecBisectBfLB.decl.h
+       /bin/cp RecBisectBfLB.decl.h ../include
+
 ../include/MetisLB.decl.h : MetisLB.decl.h
        /bin/cp MetisLB.decl.h ../include
 
@@ -351,6 +359,9 @@ CentralLB.decl.h Central.def.h : CentralLB.ci charmxi
 RandCentLB.decl.h RandCent.def.h : RandCentLB.ci charmxi
        $(CHARMC) RandCentLB.ci
 
+RecBisectBfLB.decl.h RandCent.def.h : RecBisectBfLB.ci charmxi
+       $(CHARMC) RecBisectBfLB.ci
+
 MetisLB.decl.h MetisLB.def.h : MetisLB.ci charmxi
        $(CHARMC) MetisLB.ci
 
@@ -426,6 +437,18 @@ CentralLB.o: CentralLB.C $(CKHEADERS)
 RandCentLB.o: RandCentLB.C $(CKHEADERS)
        $(CHARMC) -o RandCentLB.o RandCentLB.C
 
+RecBisectBfLB.o: RecBisectBfLB.C $(CKHEADERS) graph.h fifoInt.h bitvecset.h
+       $(CHARMC) -o RecBisectBfLB.o RecBisectBfLB.C
+
+graph.o: graph.c 
+       $(CHARMC) -o graph.o graph.c
+
+fifoInt.o: fifoInt.c fifoInt.h
+       $(CHARMC) -o fifoInt.o fifoInt.c
+
+bitvecset.o: bitvecset.c bitvecset.h
+       $(CHARMC) -o bitvecset.o bitvecset.c
+
 MetisLB.o: MetisLB.C $(CKHEADERS)
        $(CHARMC) -o MetisLB.o MetisLB.C