1ea6e839346506459e5b128cdc09aace87ef84c7
[charm.git] / tests / charm++ / load_balancing / lb_test / Topo.C
1 #include <math.h>
2 #include <charm++.h>
3
4 #if defined(_WIN32)
5 #define strcasecmp stricmp
6 #endif
7
8 #include "Topo.h"
9 #include "Topo.def.h"
10 #include "lb_test.decl.h"
11
12 #define LINEARLY_GRADED                            0
13
14 /* readonly*/ extern CProxy_main mainProxy;
15
16 CkGroupID Topo::Create(const int _elem, const char* _topology, 
17                        const int min_us, const int max_us)
18 {
19   int topo = Select(_topology);
20   if (topo == -1)
21     //The user's topology name wasn't in the table-- also bad!
22     CkAbort("ERROR! Topology not found!  \n");
23
24   TopoInitMsg* tmsg = new TopoInitMsg;
25   tmsg->elements = _elem;
26   tmsg->topology = topo;
27   tmsg->seed = 12345;
28   tmsg->min_us = min_us;
29   tmsg->max_us = max_us;
30   CkGroupID topo_id = CProxy_Topo::ckNew(tmsg);
31   return topo_id;
32 }
33
34 Topo::Elem* Topo::elemlist = NULL;
35
36 int Topo::Select(const char* _topo)
37 {
38   int i=0;
39   while (TopoTable[i].name) {
40     if (strcasecmp(_topo,TopoTable[i].name) == 0) {
41       CkPrintf("Selecting Topology %s\n",TopoTable[i].name);
42       return TopoTable[i].id;
43     }
44     i++;
45   }
46   CkPrintf("Unknown topology %s\n",_topo);
47   return TopoError;
48 }
49
50 Topo::Topo(TopoInitMsg* _m)
51 {
52   elements = _m->elements;
53   topo = TopoType(_m->topology);
54   seed = _m->seed;
55   min_us = _m->min_us;
56   max_us = _m->max_us;
57
58   // Do this first, to make sure everyone gets the same seed
59   srand(seed);
60
61   if (CkMyPe()==0)
62     CkPrintf("Generating topology %d for %d elements\n",topo,elements);
63
64   if (elemlist) {
65     delete _m;
66     return; 
67   }
68
69   elemlist = new Elem[elements];
70
71   FindComputeTimes();
72
73   // Re-seed, so we can change the graph independent of computation
74   srand(seed);
75
76         switch (topo) {
77         case TopoRing:
78                 ConstructRing();
79                 break;
80         case  TopoMesh2D:
81                 ConstructMesh2D();
82                 break;
83         case TopoMesh3D:
84                 ConstructMesh3D();
85                 break;
86         case TopoRandGraph:
87                 ConstructRandGraph();
88                 break;
89         };
90
91   delete _m;
92 }
93
94 // Function to change loads in all the elements
95 void Topo::shuffleLoad(){
96
97         printf("[%d] At shuffleLoad\n",CkMyPe());
98         
99         // calling function to assign new loads
100         FindComputeTimes();
101
102         // reduction to continue execution
103         contribute(CkCallback(CkIndex_main::resume(),mainProxy));
104 }
105
106 void Topo::FindComputeTimes()
107 {
108   int i;
109   double total_work = 0;
110   const double em1 = exp(1.) - 1;
111   for(i=0; i < elements; i++) {
112     double work;
113     do {  
114 #if LINEARLY_GRADED
115       int mype = i/(elements/CkNumPes());
116       double max_on_pe = min_us + 1.0*(max_us - min_us)*(mype+1)/CkNumPes();
117       double min_on_pe = min_us + 1.0*(max_us - min_us)*(mype)/CkNumPes();
118       work = min_on_pe + (max_on_pe-min_on_pe)*pow((double)rand()/RAND_MAX,4.);
119 #else
120       // Gaussian doesn't give a bad enough distribution
121       // work = gasdev() * devms + meanms;
122       //work = (int)(((2.*devms*rand()) / RAND_MAX + meanms - devms) + 0.5);
123       // Randomly select 10% to do 4x more work
124 //      if ((10.*rand())/RAND_MAX < 1.)
125 //      work *= 4;
126 //      work = meanms-devms + 2*devms*(exp((double)rand()/RAND_MAX)-1) / em1;
127       work = min_us + (max_us-min_us)*pow((double)rand()/RAND_MAX,4.);
128 #endif
129     } while (work < 0);
130     elemlist[i].work = work;
131     // CkPrintf("%d work %f\n", i, work);
132     total_work += work;
133   }
134   if (CkMyPe() == 0)
135     CkPrintf("[%d] Total work/step = %f sec\n",CkMyPe(),total_work*1e-6);
136       
137 }
138
139 float Topo::gasdev()
140 {
141   // Based on Numerical Recipes, but throw away extra deviate.
142   float fac,r,v1,v2;
143
144   do {
145     v1 = (rand() * 2.)/RAND_MAX - 1.;
146     v2 = (rand() * 2.)/RAND_MAX - 1.;
147     r = v1*v1 + v2*v2;
148   } while (r >= 1.0);
149   fac = sqrt(-2.0*log(r)/r);
150   return v2 * fac;
151 }
152
153 void Topo::ConstructRing()
154 {
155   int i;
156   for(i=0;i<elements;i++) {
157     elemlist[i].receivefrom = new MsgInfo;
158     elemlist[i].sendto = new MsgInfo;
159  
160     int from = i-1;
161     if (from < 0) from = elements-1;
162     elemlist[i].receivefrom->obj = from;
163     elemlist[i].receivefrom->bytes = N_BYTES;
164     elemlist[i].receiving = 1;
165
166     int to = i+1;
167     if (to == elements) to = 0;
168     elemlist[i].sendto->obj = to;
169     elemlist[i].sendto->bytes = N_BYTES;
170     elemlist[i].sending = 1;
171   }
172 }
173
174 void Topo::ConstructMesh2D()
175 {
176   // How should I build a mesh?  I'll make it close to square, and not
177   // communicate with nonexistent elements
178
179   int nrows = (int)(sqrt(1.0*elements) + 0.5); // Round it
180   if (nrows < 1) nrows = 1;
181   int ncols = elements / nrows;
182   while (nrows * ncols < elements) ncols++;
183
184   if (CkMyPe() == 0)
185     CkPrintf("Building a %d x %d mesh, with %d missing elements\n",
186              nrows,ncols,nrows*ncols-elements);
187
188   int i;
189   for(i=0;i<elements;i++) {
190     elemlist[i].receivefrom = new MsgInfo[4];
191     elemlist[i].sendto = new MsgInfo[4];
192     elemlist[i].receiving = elemlist[i].sending = 0;
193   }
194
195   for(i=0;i<elements;i++) {
196     const int r = i / ncols;
197     const int c = i % ncols;
198
199     const int to_r[4] = { r+1, r,   r-1, r   };
200     const int to_c[4] = { c,   c+1, c,   c-1 };
201
202     for(int nbor = 0; nbor < 4; nbor++) {
203       int dest_r = to_r[nbor];
204       int dest_c = to_c[nbor];
205       if (   dest_r >= nrows || dest_r < 0
206           || dest_c >= ncols || dest_c < 0 )
207         continue;
208
209       int dest = dest_r * ncols + dest_c;
210       if (dest >= elements || dest < 0) 
211         continue;
212
213       // CkPrintf("[%d]Element %d (%d,%d) is sending to element %d(%d,%d)\n",
214       //           CkMyPe(),i,r,c,dest,dest_r,dest_c);
215
216       elemlist[i].sendto[elemlist[i].sending].obj = dest;
217       elemlist[i].sendto[elemlist[i].sending].bytes = N_BYTES;
218       elemlist[i].sending++;
219
220       elemlist[dest].receivefrom[elemlist[dest].receiving].obj = i;
221       elemlist[dest].receivefrom[elemlist[dest].receiving].bytes = N_BYTES;
222       elemlist[dest].receiving++;
223     }
224   }
225 }
226
227 /**
228  * Builds a 3D mesh by creating the smallest cube containing all the objects.
229  * The cube might have "holes" depending on the number of objects. We avoid
230  * communication with non-existent elements.
231  */
232 void Topo::ConstructMesh3D()
233 {
234         // variable to store the length of one side of the cube
235         int length, i;
236
237         // computing the size of one side of the cube
238         length = (int)ceil(pow((double)elements,(double)1/3));
239
240         if (CkMyPe() == 0)
241         CkPrintf("Building a %d x %d x %d mesh, with %d missing elements\n",
242                  length,length,length,length*length*length-elements);
243
244         // initializing elemlist array, each element will potentially 
245         // communicate with other 6 neighbors
246         for(i=0;i<elements;i++) {
247         elemlist[i].receivefrom = new MsgInfo[6];
248         elemlist[i].sendto = new MsgInfo[6];
249         elemlist[i].receiving = elemlist[i].sending = 0;
250         }
251
252         // filling up neihgbor list for each element
253         for(i=0; i<elements; i++) {
254                 
255                 // transforming linear index into (x,y,z) coordinates
256                 const int x = i % length;
257                 const int y = ((i - x) % (length*length)) / length;
258                 const int z = (i - y*length -x) / (length*length);
259                 const int to_x[6] = { x-1, x+1,   x,   x,   x,   x };
260                 const int to_y[6] = {   y,   y, y-1, y+1,   y,   y };
261                 const int to_z[6] = {   z,   z,   z,   z, z-1, z+1 };
262
263                 //DEBUG CkPrintf("[%d] Element %d -> (%d,%d,%d)\n",CkMyPe(),i,x,y,z);
264
265                 //  adding each neighbor to list
266                 for(int nbor = 0; nbor < 6; nbor++) {
267                         int dest_x = to_x[nbor];
268                         int dest_y = to_y[nbor];
269                         int dest_z = to_z[nbor];
270                         if (dest_x >= length || dest_x < 0 || dest_y >= length || dest_y < 0 || dest_z >= length || dest_z < 0 )
271                                 continue;
272
273                         int dest = dest_z * length*length + dest_y*length + dest_x;
274                         if (dest >= elements || dest < 0) 
275                                 continue;
276
277                         //DEBUG CkPrintf("[%d]Element %d (%d,%d,%d) is sending to element %d (%d,%d,%d)\n",
278                                 //DEBUG CkMyPe(),i,x,y,z,dest,dest_x,dest_y,dest_z);
279
280                         elemlist[i].sendto[elemlist[i].sending].obj = dest;
281                         elemlist[i].sendto[elemlist[i].sending].bytes = N_BYTES;
282                         elemlist[i].sending++;
283
284                         elemlist[dest].receivefrom[elemlist[dest].receiving].obj = i;
285                         elemlist[dest].receivefrom[elemlist[dest].receiving].bytes = N_BYTES;
286                         elemlist[dest].receiving++;
287                 }
288         }
289 }
290
291 void Topo::ConstructRandGraph()
292 {
293   // First, build a ring.  Then add more random links on top of those
294   // To build the links, we will make a big temporary array for connections
295   const int num_connections = elements * (elements - 1);
296   int connections_made = 0;
297   int connections_tried = 0;
298
299   const double ratio = .01;
300
301   int i;
302   for(i=0;i<elements;i++)
303     elemlist[i].receiving = elemlist[i].sending = 0;
304
305   // To save memory, I will use this slightly more complicated algorithm
306   // A) For each from element
307   //    1) Compute the from links for each processor
308   //    2) Allocate and store enough memory for that list
309   //    3) Keep track of how many each receiver will get
310   // B) For each to element
311   //    1) Allocate enough elements for the to list
312   // C) For each from element
313   //    1) Copy the from list to the to list
314
315   int* receivefrom = new int[elements];
316   for(i=0;i<elements;i++)
317     receivefrom[i] = 0;
318
319   int from;
320   for(from=0; from < elements; from++) {
321     int n_sends = 0;
322     MsgInfo* sendto = new MsgInfo[elements];
323
324     // First, build the ring link
325     int to = (from+1) % elements;
326     receivefrom[to]++;
327     sendto[n_sends].obj = to;
328     sendto[n_sends].bytes = N_BYTES;
329     n_sends++;
330     connections_made++;
331     connections_tried++;
332
333     // Now check out the rest of the links for this processor
334     // Examine each possible destination
335     for(int j=2; j < elements; j++) {
336       const int to = (from + j) % elements;
337       const int to_make = (int)(ratio * num_connections - connections_made);
338       const int to_try = num_connections - connections_tried;
339       const double myrand = ((double) rand() * to_try) / RAND_MAX;
340
341       if (myrand < to_make) {
342         int findx = n_sends++;
343         sendto[findx].obj = to;
344         sendto[findx].bytes = N_BYTES;
345         receivefrom[to]++;
346         connections_made++;
347       }
348       connections_tried++;
349     }
350     // Okay, now we have all of the outgoing links for this processor,
351     // so we just have to copy them into the elemlist
352     if (n_sends > elements)
353       CkPrintf("%s:%d Too many sends attempted %d %d\n",
354                __FILE__,__LINE__,n_sends,elements);
355     elemlist[from].sending = n_sends;
356     elemlist[from].sendto = new MsgInfo[n_sends];
357     int i;
358     for(i=0;i<n_sends;i++)
359       elemlist[from].sendto[i] = sendto[i];
360
361     delete [] sendto;
362   }
363
364   // Now that we've created all of the send lists, and we know how many
365   // elements we will receive, we can create the receivefrom lists
366   for(int to=0; to < elements; to++)
367     elemlist[to].receivefrom = new MsgInfo[receivefrom[to]];
368
369   for(from=0;from<elements;from++) {
370     for(int i=0; i < elemlist[from].sending; i++) {
371       int to = elemlist[from].sendto[i].obj;
372       if (elemlist[to].receiving < receivefrom[to]) {
373         int tindex = elemlist[to].receiving++;
374         elemlist[to].receivefrom[tindex].obj = from;
375         elemlist[to].receivefrom[tindex].bytes = N_BYTES;
376       } else {
377         CkPrintf("%s:%d Too many receives going to %d: %d\n",
378                  __FILE__,__LINE__,to,elemlist[to].receiving);
379       }
380     }
381   }
382
383   delete [] receivefrom;
384
385   if (CkMyPe() == 0) {
386     CkPrintf(
387       "Built random graph with %d of %d possible links (%f percent)\n",
388       connections_made,num_connections,
389       (100.0*connections_made)/num_connections);
390   }
391 }
392
393 int Topo::SendCount(int index)
394 {
395   return elemlist[index].sending;
396 }
397
398 void Topo::SendTo(int index, MsgInfo* who)
399 {
400   for(int i=0; i < elemlist[index].sending; i++)
401     who[i] = elemlist[index].sendto[i];
402 }
403
404 int Topo::RecvCount(int index)
405 {
406   return elemlist[index].receiving;
407 }
408
409 void Topo::RecvFrom(int index, MsgInfo* who)
410 {
411   for(int i=0; i < elemlist[index].receiving; i++)
412     who[i] = elemlist[index].receivefrom[i];
413 }