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