doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / RecBisectBfLB.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 /**
7  Status:
8   * does not support processor avail bitvector
9   * does not support nonmigratable attrib
10
11   FIXME:  need to remove outlier object load. Outlier object can cause
12   failure of partitioning and often causes: "too few objects to paritition"
13   error.
14 */
15
16 #include <charm++.h>
17
18 #include "RecBisectBfLB.h"
19
20 extern "C" {
21   Graph * g_initGraph(int v, int e);
22   void g_freeGraph(Graph* g);
23   void g_nextVertex(Graph *g, int v, float w);
24   void g_finishVertex(Graph *g);
25   void g_addEdge(Graph *g, int w, float w2);
26   float graph_weightof(Graph *g, int vertex);
27   int g_numNeighbors(Graph *g, int node);
28   int g_getNeighbor(Graph *g, int d , int i);
29   void g_printGraph(Graph *g);
30
31   int bvset_size(BV_Set *);
32   int bvset_find(BV_Set *, int i);
33   void bvset_enumerate(BV_Set * s1, int **p1, int *numP1);
34   void bvset_insert(BV_Set *ss1, int t1);
35   BV_Set *makeSet(int *nodes, int numNodes, int V);
36   BV_Set *makeEmptySet( int V);
37   void destroySet(BV_Set* s);
38 }
39
40
41
42 CreateLBFunc_Def(RecBisectBfLB, "Recursive partitioning with Breadth first enumeration")
43
44 RecBisectBfLB::RecBisectBfLB(const CkLBOptions &opt): CentralLB(opt)
45 {
46   lbname = (char*)"RecBisectBfLB";
47   if (CkMyPe() == 0)
48     CkPrintf("[%d] RecBisectBfLB created\n",CkMyPe());
49 }
50
51 CmiBool RecBisectBfLB::QueryBalanceNow(int _step)
52 {
53   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
54   return CmiTrue;
55 }
56
57 void RecBisectBfLB::work(LDStats* stats)
58 {
59   int i;
60   int numPartitions = stats->n_pes;
61
62   PartitionList *partitions;
63
64   CkPrintf("[%d] RecBisectBfLB strategy\n",CkMyPe());
65   ObjGraph og(numPartitions, stats);
66
67   Graph *g =  convertGraph( &og);
68   CkPrintf("[%d] RecBisectBfLB: graph converted\n",CkMyPe());
69     
70   //  g_printGraph(g);
71   int* nodes = (int *) malloc(sizeof(int)*g->V);
72
73   for (i=0; i<g->V; i++) 
74     nodes[i] = i;
75
76 /*  for (i=0; i<g->V; i++) 
77     CkPrintf("%d: %f\n", i, graph_weightof(g, i)); */
78
79   partitions = (PartitionList *) malloc(sizeof(PartitionList));
80   partitions->next = 0;
81   partitions->max = numPartitions;
82   partitions->partitions = (PartitionRecord *)
83     malloc(sizeof(PartitionRecord)* numPartitions);
84     
85   recursivePartition(numPartitions, g, nodes, g->V,  partitions);
86   
87   //  CmiPrintf("\ngraph partitioned\n");
88
89   g_freeGraph(g);
90   
91   //  printPartitions(partitions);
92
93   for (i=0; i<partitions->max; i++) {
94     //    CmiPrintf("[%d] (%d) : \t", i, partitions->partitions[i].size);
95     for (int j=0; j< partitions->partitions[i].size; j++) {
96       //      CmiPrintf("%d ", partitions->partitions[i].nodeArray[j]);
97       const int objref = partitions->partitions[i].nodeArray[j];
98       ObjGraph::Node n = og.GraphNode(objref);
99       //     CkPrintf("Moving %d(%d) from %d to %d\n",objref,
100       //             stats[n.proc].objData[n.index].handle.id.id[0],n.proc,i);
101       if (n.proc != i) {
102         CmiAssert(stats->from_proc[n.index] == n.proc);
103         stats->to_proc[n.index] = i;
104       }
105     }
106     free(partitions->partitions[i].nodeArray);
107   }
108   free(partitions->partitions);
109   free(partitions);
110
111   CmiPrintf("returning from partitioner strategy\n");
112 }
113
114
115 Graph *
116 RecBisectBfLB::convertGraph(ObjGraph *og) {
117
118   Graph *g;
119   
120   int V, E, i;
121
122   V = og->NodeCount();
123   E = og->EdgeCount();
124
125   g = g_initGraph(V, E);
126
127   //  CkPrintf("[%d] RecBisectBfLB: convert (v=%d, e=%d, g=%p\n",
128   //       CkMyPe(), V, E, g);
129
130   for (i =0; i<V; i++) {
131     g_nextVertex(g, i, og->LoadOf(i));
132
133     ObjGraph::Node n = og->GraphNode(i);
134     ObjGraph::Edge *l;
135
136     //  CkPrintf("[%d] RecBisectBfLB: convert before addEdge Loop\n");
137     
138     l = n.edges_from();
139     while (l) {
140       // CkPrintf("[%d] RecBisectBfLB: convert in addEdge Loop1\n");
141       g_addEdge(g, l->to_node, 1.0); /* get edgeweight */
142       l = l->next_from();
143     }
144
145     l = n.edges_to();
146     while (l) {
147       // CkPrintf("[%d] RecBisectBfLB: convert in addEdge Loop2\n");
148       g_addEdge(g, l->from_node, 1.0); /* get edgeweight */
149       l = l->next_to();
150     }
151     g_finishVertex(g);
152   }
153   return g;
154 }
155
156 void RecBisectBfLB::partitionInTwo(Graph *g, int nodes[], int numNodes, 
157                int ** pp1, int *numP1, int **pp2, int *numP2, 
158                int ratio1, int ratio2)
159 {
160   int r1, r2;
161   int i;
162   float w, weight1, weight2;
163   BV_Set *all, *s1, *s2; 
164   IntQueue * q1, *q2;
165   int * p1, *p2;
166
167   /*
168   CkPrintf("partitionInTwo:\n");
169   for (i=0; i<numNodes; i++) 
170     CkPrintf("%d: %f\n", i, graph_weightof(g, nodes[i])); 
171   */
172
173   if (numNodes <2) CkAbort("error: too few objects to paritition\n");
174   r1 = nodes[0];
175 /*  r2 = nodes[numNodes-1];*/
176   r2 = nodes[1]; 
177   weight1 = graph_weightof(g, r1);
178   weight2 = graph_weightof(g, r2);
179
180   /* Improvement:
181      select r1 and r2 more carefully: 
182      e.g. farthest away from each other. */
183
184   for (i=2; i<numNodes; i++) {
185     w = graph_weightof(g, nodes[i]);
186     if (w > weight1) { weight1 = w; r1 = nodes[i]; }
187     else if (w > weight2) { weight2 = w; r2 = nodes[i]; }
188   }
189 //  CkPrintf("starting weights: %f, %f\n", weight1, weight2);
190   
191   all = makeSet(nodes, numNodes, g->V);
192   s1 = makeEmptySet(g->V);
193   s2 = makeEmptySet(g->V);
194
195   q1 = new IntQueue(g->V);
196   q2 = new IntQueue(g->V);
197
198   q1->enq(r1);
199   q2->enq(r2);
200   /*  printf("r1=%d, r2=%d\n", r1, r2);*/
201
202   weight1 = 0; weight2 = 0;
203   while (   (bvset_size(s1) + bvset_size(s2)) < numNodes ) {
204     //    CkPrintf("weights: %f, %f\n", weight1, weight2);
205     if (weight1*ratio2 < weight2*ratio1) 
206       weight1 += addToQ(q1, g, all, s1,s2);      
207     else 
208       weight2 += addToQ(q2, g, all, s2,s1);
209   }
210
211   bvset_enumerate(s1, &p1, numP1);
212   bvset_enumerate(s2, &p2, numP2);
213   *pp1 = p1;
214   *pp2 = p2;
215   destroySet(s1);
216   destroySet(s2);
217   delete q1;
218   delete q2;
219 /*  CmiPrintf("==exiting partitionInTwo, ratios: (%d, %d); weights: %f %f \n",
220             ratio1, ratio2, weight1, weight2); */
221 }
222
223 int 
224 RecBisectBfLB::findNextUnassigned(int max, BV_Set * all, 
225                                   BV_Set * s1, BV_Set * s2)
226 {
227   int i;
228   for (i=0; i<max; i++) { 
229     if (bvset_find(all, i))
230       if ( (!bvset_find(s1,i)) && (!bvset_find(s2,i)) ) 
231         return i;
232   }
233   return (max + 1);
234 }
235
236 float RecBisectBfLB::addToQ(IntQueue * q, Graph *g, BV_Set * all, 
237                             BV_Set * s1, BV_Set * s2)
238 {
239   int t1, doneUpto;
240   float weightAdded;
241
242   weightAdded = 0.0;
243
244   if (q->isEmpty()) {
245     doneUpto = findNextUnassigned(g->V, all, s1, s2);
246     if (doneUpto < g->V) q->enq(doneUpto); 
247   }
248   if (!q->isEmpty() ) {
249     t1 = q->deq();
250     if (bvset_find(all, t1)) /* t1 is a vertex of the given partition */
251       if ( (!bvset_find(s1, t1)) && ( !bvset_find(s2, t1)) ) {
252         bvset_insert(s1, t1);
253         weightAdded = graph_weightof(g, t1); 
254         /*       printf("adding %d to s\n", t1); */
255         enqChildren(q, g, all, s1, s2, t1);
256       }
257   }
258   return weightAdded;
259 }
260
261 void RecBisectBfLB::enqChildren(IntQueue * q, Graph *g, BV_Set * all, 
262                                 BV_Set * s1, BV_Set * s2, int node)
263 {
264   int nbrs, i, j;
265
266   nbrs = g_numNeighbors(g, node);
267   for (i=0; i<nbrs; i++) {
268     j = g_getNeighbor(g, node, i);
269     if (  (bvset_find(all,j)) && (!bvset_find(s1,j)) 
270           && (!bvset_find(s2,j)) ) {
271       q->enq(j);
272     }
273   } 
274 }
275
276
277 void RecBisectBfLB::addPartition(PartitionList * partitions, 
278                                  int * nodes, int num) 
279 {
280   int i;
281
282   i =  partitions->next++;
283   partitions->partitions[i].size = num;
284   partitions->partitions[i].nodeArray = nodes ;
285 }
286
287 void RecBisectBfLB::printPartitions(PartitionList * partitions)
288 {
289   int i,j;
290  
291
292   CmiPrintf("\n**************************\n The Partitions are: \n");
293   for (i=0; i<partitions->max; i++) {
294     CmiPrintf("[%d] (%d) : \t", i, partitions->partitions[i].size);
295     for (j=0; j< partitions->partitions[i].size; j++)
296       CmiPrintf("%d ", partitions->partitions[i].nodeArray[j]);
297     CmiPrintf("\n");
298   }
299 }
300
301 void RecBisectBfLB::recursivePartition(int numParts, Graph *g, 
302                                        int nodes[], int numNodes, 
303                                        PartitionList *partitions) 
304 {
305   int *p1, *p2;
306   int first, second;
307   int numP1, numP2;
308   
309   if (numParts < 2) {
310     addPartition(partitions, nodes, numNodes);
311   } else {
312     first = numParts/2;
313     second = numParts - first;
314     partitionInTwo(g, nodes, numNodes, &p1, &numP1, &p2, &numP2, first,second);
315     recursivePartition(first, g, p1, numP1, partitions);
316     recursivePartition(second, g, p2, numP2,  partitions);
317     free(nodes);
318   }  
319 }
320
321 #include "RecBisectBfLB.def.h"
322
323 /*@}*/