add phase change notification
[charm.git] / src / conv-ldb / topology.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 #include <math.h>
7
8 //#include "LBDatabase.h"
9 #include "cklists.h"
10 #include "topology.h"
11
12 extern "C" char *_lbtopo;                       /* topology name string */
13
14 int LBTopology::get_hop_count(int src,int dest)
15 {
16         int npe;
17         int *visited_srcs;
18
19         if(src==dest)
20                 return 0;
21         
22         npe = max_neighbors();
23         visited_srcs = new int[npes];
24         
25         int count = rec_hop_count(src,dest,npe,1,visited_srcs,999999);
26         delete [] visited_srcs;
27
28         return count;
29 }
30
31 int LBTopology::rec_hop_count(int src,int dest,int max_neigh,int count,int *visited_srcs,int min_hop_cnt)
32 {
33         int *pes = new int[max_neigh];
34         //int min_hop_cnt=999999;
35         int ret_val=0;
36         int skip_neigh=0;
37         int neigh_cnt=0;
38         int i;
39         
40         neighbors(src,pes,neigh_cnt);
41         
42         visited_srcs[count-1]=src;
43         
44         for(i=0;i<neigh_cnt;i++)
45         {
46                 if(pes[i]==dest)
47                         return count;
48         }
49         for(i=0;i<neigh_cnt;i++)
50         {
51                 for(int j=0;j<count;j++)
52                         if(visited_srcs[j]==pes[i])
53                         {
54                                 skip_neigh=1;
55                                 break;
56                         }
57                 if(!skip_neigh)
58                 {
59                         if(min_hop_cnt > count+1){
60                                 ret_val=rec_hop_count(pes[i],dest,max_neigh,count+1,visited_srcs,min_hop_cnt);
61                                 if(ret_val < min_hop_cnt)
62                                         min_hop_cnt = ret_val;
63                         }
64                 }
65                 else
66                         skip_neigh=0;
67         }
68         delete [] pes;
69         return min_hop_cnt;
70 }
71
72 double LBTopology::per_hop_delay(int last_hop)
73 {
74         if(!last_hop)
75                 return (HOP_LINK_DELAY + HOP_PROC_DELAY);
76         else
77                 return HOP_LINK_DELAY;
78 }
79
80 void LBTopology::get_pairwise_hop_count(double  **distance)
81 {
82   struct queueNode
83   {
84     int index;
85     int dist;
86     queueNode *next;
87     queueNode(int i,int d): index(i), dist(d), next(NULL) {}
88   };
89   
90   bool *visited=new bool[npes];
91   int *neigh=new int[max_neighbors()];
92   int num_neighbors;
93
94   for(int i=0;i<npes;i++)
95   {
96     //Init data structures for BFS from i-th proc
97     for(int j=0;j<npes;j++)
98       visited[j]=false;
99
100     queueNode *q=new queueNode(i,0);
101     queueNode *last=q;
102     distance[i][i]=0;
103     visited[i]=true;
104
105     // Perform BFS until queue is empty
106     while(q)
107     { 
108       neighbors(q->index,neigh,num_neighbors);
109       for(int j=0;j<num_neighbors;j++)
110       {
111         if(!visited[neigh[j]])
112         {
113           visited[neigh[j]]=true;
114           distance[i][neigh[j]]=q->dist+1;
115           queueNode *qnew=new queueNode(neigh[j],q->dist+1);
116           last->next=qnew;
117           last=last->next;
118         }
119       }
120       queueNode *qtemp=q;
121       q=q->next;
122       delete qtemp;
123     }
124   }
125   delete[] visited;
126   delete[] neigh;
127 }
128
129 //smp - assume 1,2,3 or 4 processors per node
130
131 template <int ppn>
132 class LBTopo_smp_n: public LBTopology {
133 public:
134   LBTopo_smp_n(int p): LBTopology(p) {}
135   virtual int max_neighbors() { return npes - 1; }
136
137   virtual void neighbors(int mype, int* _n, int &nb){
138       nb = 0;
139       for(int i=1; i<=ppn; i++)
140       {
141           _n[nb++] = (mype+i)%npes;
142       }
143   }
144         
145         int get_hop_count(int src,int dest){
146                 
147                 //CmiPrintf("in smp get_hop_count\n");
148                 int a = src/ppn;
149                 int b = dest/ppn;
150                 
151                 if(a!=b){
152                         //CmiPrintf("2 returned\n");
153                         return 2;
154                 }
155                 else{
156                         //CmiPrintf("1 returned\n");
157                         return 1;
158                 }
159         }
160 };
161
162 typedef LBTopo_smp_n<1> LBTopo_smp_n_1;
163 typedef LBTopo_smp_n<2> LBTopo_smp_n_2;
164 typedef LBTopo_smp_n<3> LBTopo_smp_n_3;
165 typedef LBTopo_smp_n<4> LBTopo_smp_n_4;
166 typedef LBTopo_smp_n<5> LBTopo_smp_n_5;
167 typedef LBTopo_smp_n<6> LBTopo_smp_n_6;
168 typedef LBTopo_smp_n<7> LBTopo_smp_n_7;
169 typedef LBTopo_smp_n<8> LBTopo_smp_n_8;
170 typedef LBTopo_smp_n<9> LBTopo_smp_n_9;
171 typedef LBTopo_smp_n<10> LBTopo_smp_n_10;
172
173 LBTOPO_MACRO(LBTopo_smp_n_1)
174 LBTOPO_MACRO(LBTopo_smp_n_2)
175 LBTOPO_MACRO(LBTopo_smp_n_3)
176 LBTOPO_MACRO(LBTopo_smp_n_4)
177 LBTOPO_MACRO(LBTopo_smp_n_5)
178 LBTOPO_MACRO(LBTopo_smp_n_6)
179 LBTOPO_MACRO(LBTopo_smp_n_7)
180 LBTOPO_MACRO(LBTopo_smp_n_8)
181 LBTOPO_MACRO(LBTopo_smp_n_9)
182 LBTOPO_MACRO(LBTopo_smp_n_10)
183
184
185 // ring
186
187 LBTOPO_MACRO(LBTopo_ring)
188
189 int LBTopo_ring::max_neighbors()
190 {
191   if (npes > 2) return 2;
192   else return (npes-1);
193 }
194
195 void LBTopo_ring::neighbors(int mype, int* _n, int &nb)
196 {
197   nb = 0;
198   if (npes>1) _n[nb++] = (mype + npes -1) % npes;
199   if (npes>2) _n[nb++] = (mype + 1) % npes;
200 }
201
202 int LBTopo_ring::get_hop_count(int src,int dest){
203         
204         int dist=src-dest;
205         if(dist<0) dist=-dist;
206         
207         if((npes-dist) < dist)
208                 return (npes-dist);
209         else
210                 return dist;
211 }
212
213 //  TORUS 2D
214
215 LBTOPO_MACRO(LBTopo_torus2d)
216
217 LBTopo_torus2d::LBTopo_torus2d(int p): LBTopology(p) 
218 {
219   width = (int)sqrt(p*1.0);
220   if (width * width < npes) width++;
221 }
222
223 int LBTopo_torus2d::max_neighbors()
224 {
225   return 4;
226 }
227
228 int LBTopo_torus2d::goodcoor(int x, int y)
229 {
230   if (x<0 || x>=width) return -1;
231   if (y<0 || y>=width) return -1;
232   int next = x*width + y;
233   if (next<npes && next>=0) return next;
234   return -1;
235 }
236
237 static int checkuniq(int *arr, int nb, int val) {
238   for (int i=0;i<nb;i++) if (arr[i]==val) return 0;
239   return 1;
240 }
241
242 void LBTopo_torus2d::neighbors(int mype, int* _n, int &nb)
243 {
244   int next;
245   int x = mype/width;
246   int y = mype%width;
247   nb=0;
248   for (int i=-1; i<=1; i+=2) {
249     int x1 = x+i;
250     if (x1 == -1) {
251       x1 = width-1;
252       while (goodcoor(x1, y)==-1) x1--;
253     }
254     else if (goodcoor(x1, y) == -1) x1=0;
255     next = goodcoor(x1, y);
256     CmiAssert(next != -1);
257     if (next != mype && checkuniq(_n, nb, next)) _n[nb++] = next;
258
259     int y1 = y+i;
260     if (y1 == -1) {
261       y1 = width-1;
262       while (goodcoor(x, y1)==-1) y1--;
263     }
264     else if (goodcoor(x, y1) == -1) y1=0;
265     next = goodcoor(x, y1);
266     CmiAssert(next != -1);
267     if (next != mype && checkuniq(_n, nb, next)) _n[nb++] = next;
268   }
269 }
270
271 int LBTopo_torus2d::get_hop_count(int src,int dest){
272         int xpos_src,xpos_dest;
273         int ypos_src,ypos_dest;
274         int xdist=0;
275         int ydist=0;
276         
277         int xchange;
278         if(src > dest){
279                 xchange = src;
280                 src = dest;
281                 dest = xchange;
282         }
283         
284         xpos_src=src%width;
285         ypos_src=src/width;
286
287         xpos_dest=dest%width;
288         ypos_dest=dest/width;
289
290         xdist = xpos_dest-xpos_src;
291         if(xdist<0) xdist=-xdist;
292         if((width-xdist) < xdist)
293                 xdist = width-xdist;
294         
295         ydist = ypos_dest-ypos_src;
296         if(ydist<0) ydist=-ydist;
297
298         int lastpos=(npes-1)%width;
299         int otherylen=0;
300
301         if(xpos_src<=lastpos && xpos_dest<=lastpos)
302                 otherylen=((npes-1)/width)+1-ydist;
303         else{
304                 if(ypos_dest==((npes-1)/width))
305                         otherylen=((npes-1)/width)+1-ydist;
306                 else    
307                         otherylen=((npes-1)/width)-ydist;
308         }
309         
310         if(otherylen < ydist)
311                 ydist=otherylen;
312         
313         //added later
314         int sdist=0,adist=0,bdist=0,cdist=0,ddist=0;
315         
316         if(xpos_src>lastpos && xpos_dest>lastpos){
317                 sdist = xpos_src;
318                 if((width-sdist) < sdist)
319                 sdist = width-sdist;
320
321                 adist = ((npes-1)/width)-ypos_src;
322                 if(adist<0) adist=-adist;
323                 if(ypos_src+1 < adist)
324                         adist = ypos_src+1;
325         
326                 bdist = 1;
327
328                 cdist = ((npes-1)/width)-ypos_dest;
329                 if(cdist<0) cdist=-cdist;
330                 if(ypos_dest+1 < cdist)
331                         cdist = ypos_dest+1;
332
333                 ddist = xpos_dest-lastpos;
334                 if(ddist<0) ddist=-ddist;
335                 if((width-ddist) < ddist)
336                         ddist = width-ddist;
337         }
338         else{
339                 if(xpos_src>lastpos){
340                         xchange = src;
341                         src = dest;
342                         dest = xchange;
343                         xpos_src=src%width;
344                         ypos_src=src/width;
345                         xpos_dest=dest%width;
346                         ypos_dest=dest/width;
347                 }
348                 adist = ((npes-1)/width)-ypos_src;
349                 if(adist<0) adist=-adist;
350                 if(ypos_src+1 < adist)
351                         adist = ypos_src+1;
352         
353                 if(xpos_dest<=lastpos){
354                         bdist = xpos_dest-xpos_src;
355                         if(bdist<0) bdist=-bdist;
356                         if((lastpos+1-bdist) < bdist)
357                                 bdist = lastpos+1-bdist;
358
359                         cdist = ((npes-1)/width)-ypos_dest;
360                         if(cdist<0) cdist=-cdist;
361                         if(ypos_dest+1 < cdist)
362                                 cdist = ypos_dest+1;
363                 
364                         ddist=0;
365                 }
366                 else{
367                         bdist = lastpos-xpos_src;
368                         if(bdist<0) bdist=-bdist;
369                         if((xpos_src+1) < bdist)
370                                 bdist = xpos_src+1;
371
372                         cdist = ((npes-1)/width)-ypos_dest;
373                         if(cdist<0) cdist=-cdist;
374                         if(ypos_dest+1 < cdist)
375                                 cdist = ypos_dest+1;
376
377                         ddist = xpos_dest-lastpos;
378                         if(ddist<0) ddist=-ddist;
379                         if((width-ddist) < ddist)
380                                 ddist = width-ddist;
381                 }
382         }
383         
384         if((sdist+adist+bdist+cdist+ddist) < (xdist+ydist))
385                 return (sdist+adist+bdist+cdist+ddist);
386         else
387                 return (xdist+ydist);
388
389 }
390
391 //  TORUS 3D
392
393 LBTOPO_MACRO(LBTopo_torus3d)
394
395 LBTopo_torus3d::LBTopo_torus3d(int p): LBTopology(p) 
396 {
397   width = 1;
398   while ( (width+1) * (width+1) * (width+1) <= npes) width++;
399   if (width * width * width < npes) width++;
400 }
401
402 int LBTopo_torus3d::max_neighbors()
403 {
404   return 6;
405 }
406
407 int LBTopo_torus3d::goodcoor(int x, int y, int z)
408 {
409   if (x<0 || x>=width) return -1;
410   if (y<0 || y>=width) return -1;
411   if (z<0 || z>=width) return -1;
412   int next = x*width*width + y*width + z;
413   if (next<npes && next>=0) return next;
414   return -1;
415 }
416
417 void LBTopo_torus3d::neighbors(int mype, int* _n, int &nb)
418 {
419
420   int x = mype/(width*width);
421   int k = mype%(width*width);
422   int y = k/width;
423   int z = k%width;
424   int next;
425   nb=0;
426   for (int i=-1; i<=1; i+=2) {
427     int x1 = x+i;
428     if (x1 == -1) {
429       x1 = width-1;
430       while (goodcoor(x1, y, z)==-1) x1--;
431     }
432     else if (goodcoor(x1, y, z) == -1) x1=0;
433     next = goodcoor(x1, y, z);
434     CmiAssert(next != -1);
435     if (next != mype && checkuniq(_n, nb, next)) _n[nb++] = next;
436
437     int y1 = y+i;
438     if (y1 == -1) {
439       y1 = width-1;
440       while (goodcoor(x, y1, z)==-1) y1--;
441     }
442     else if (goodcoor(x, y1, z) == -1) y1=0;
443     next = goodcoor(x, y1, z);
444     CmiAssert(next != -1);
445     if (next != mype && checkuniq(_n, nb, next)) _n[nb++] = next;
446
447     int z1 = z+i;
448     if (z1 == -1) {
449       z1 = width-1;
450       while (goodcoor(x, y, z1)==-1) z1--;
451     }
452     else if (goodcoor(x, y, z1) == -1) z1=0;
453     next = goodcoor(x, y, z1);
454     CmiAssert(next != -1);
455     if (next != mype && checkuniq(_n, nb, next)) _n[nb++] = next;
456   }
457 }
458
459 /*
460 // Works only for perfect cube number of processor topologies
461 int LBTopo_torus3d::get_hop_count(int src,int dest){
462         
463         int x_src = src/(width*width);
464   int k_src = src%(width*width);
465   int y_src = k_src/width;
466   int z_src = k_src%width;
467
468         int x_dest = dest/(width*width);
469   int k_dest = dest%(width*width);
470   int y_dest = k_dest/width;
471   int z_dest = k_dest%width;
472
473         int xdist=0,ydist=0,zdist=0;
474         
475         //CmiPrintf("just a chk........\n");
476         xdist = x_dest-x_src;
477         if(xdist<0) xdist=-xdist;
478         if((width-xdist) < xdist)
479                 xdist = width-xdist;
480
481         ydist = y_dest-y_src;
482         if(ydist<0) ydist=-ydist;
483         if((width-ydist) < ydist)
484                 ydist = width-ydist;
485
486         zdist = z_dest-z_src;
487         if(zdist<0) zdist=-zdist;
488         if((width-zdist) < zdist)
489                 zdist = width-zdist;
490
491         return (xdist+ydist+zdist);
492
493 }
494 */
495
496 //Mesh3D
497 LBTOPO_MACRO(LBTopo_mesh3d)
498
499 LBTopo_mesh3d::LBTopo_mesh3d(int p): LBTopology(p) 
500 {
501   width = 1;
502   while ( (width+1) * (width+1) * (width+1) <= npes) width++;
503   if (width * width * width < npes) width++;
504 }
505
506 int LBTopo_mesh3d::max_neighbors()
507 {
508   return 6;
509 }
510
511 int LBTopo_mesh3d::goodcoor(int x, int y, int z)
512 {
513   if (x<0 || x>=width) return -1;
514   if (y<0 || y>=width) return -1;
515   if (z<0 || z>=width) return -1;
516   int next = z*width*width + y*width + x;
517   if (next<npes && next>=0) return next;
518   return -1;
519 }
520
521 void LBTopo_mesh3d::neighbors(int mype, int* _n, int &nb)
522 {
523
524   int z = mype/(width*width);
525   int k = mype%(width*width);
526   int y = k/width;
527   int x = k%width;
528   int next;
529   int isNeigh=1;
530   nb=0;
531   for (int i=-1; i<=1; i+=2) {
532     isNeigh=1;
533     int x1 = x+i;
534     if (x1 == -1) {
535       //x1 = width-1;
536       x1=x;
537       //while (goodcoor(x1, y, z)==-1) x1--;
538       isNeigh=0;
539     }
540     else if (goodcoor(x1, y, z) == -1) { x1=0; isNeigh=0; }
541     next = goodcoor(x1, y, z);
542     CmiAssert(next != -1);
543     if (next != mype && isNeigh && checkuniq(_n, nb, next)) _n[nb++] = next;
544
545     isNeigh=1;
546     int y1 = y+i;
547     if (y1 == -1) {
548       //y1 = width-1;
549       //while (goodcoor(x, y1, z)==-1) y1--;
550       y1=y;
551       isNeigh=0;
552     }
553     else if (goodcoor(x, y1, z) == -1) { y1=0; isNeigh=0; }
554     next = goodcoor(x, y1, z);
555     CmiAssert(next != -1);
556     if (next != mype && isNeigh && checkuniq(_n, nb, next)) _n[nb++] = next;
557
558     isNeigh=1;
559     int z1 = z+i;
560     if (z1 == -1) {
561       //z1 = width-1;
562       //while (goodcoor(x, y, z1)==-1) z1--;
563       z1=z;
564       isNeigh=0;
565     }
566     else if (goodcoor(x, y, z1) == -1) { z1=0; isNeigh=0; }
567     next = goodcoor(x, y, z1);
568     CmiAssert(next != -1);
569     if (next != mype && isNeigh && checkuniq(_n, nb, next)) _n[nb++] = next;
570   }
571 }
572
573 //  TORUS ND 
574 //  added by zshao1
575
576 template <int dimension>
577 class LBTopo_torus_nd: public LBTopology {
578 private:
579   // inherited int npes;
580   int* Cardinality;
581   int VirtualProcessorCount;
582   int* TempCo;
583 private:
584   int GetNeighborID(int ProcessorID, int number) {
585     CmiAssert(number>=0 && number<max_neighbors());
586     CmiAssert(ProcessorID>=0 && ProcessorID<npes);
587     get_processor_coordinates(ProcessorID, TempCo);
588
589     int index = number/2;
590     int displacement = (number%2)? -1: 1;
591     do{
592       TempCo[index] = (TempCo[index] + displacement + Cardinality[index]) % Cardinality[index];
593       get_processor_id(TempCo, &ProcessorID);
594     } while (ProcessorID >= npes);
595     return ProcessorID;
596   }
597 public:
598   LBTopo_torus_nd(int p): LBTopology(p) /*inherited :npes(p) */ {
599     int i;
600     CmiAssert(dimension>=1 && dimension<=16);
601     CmiAssert(p>=1);
602
603     Cardinality = new int[dimension];
604     TempCo = new int[dimension];
605     double pp = p;
606     for(i=0;i<dimension;i++) {
607       Cardinality[i] = (int)ceil(pow(pp,1.0/(dimension-i))-1e-5);
608       pp = pp / Cardinality[i];
609     }
610     VirtualProcessorCount = 1;
611     for(i=0;i<dimension;i++) {
612       VirtualProcessorCount *= Cardinality[i];
613     }
614   }
615   ~LBTopo_torus_nd() {
616     delete[] Cardinality;
617     delete[] TempCo;
618   }
619   virtual int max_neighbors() {
620     return dimension*2;
621   }
622   virtual void neighbors(int mype, int* _n, int &nb) {
623     nb = 0;
624     for(int i=0;i<dimension*2;i++) {
625       _n[nb] = GetNeighborID(mype, i);
626       if (_n[nb]!=mype && (nb==0 || _n[nb-1]!=_n[nb]) ) nb++;
627     }
628   }
629   virtual int get_dimension() {
630     return dimension;
631   }
632   virtual bool get_processor_coordinates(int processor_id, int* processor_coordinates) {
633     CmiAssert(processor_id>=0 && processor_id<VirtualProcessorCount);
634     CmiAssert( processor_coordinates != NULL );
635     for(int i=0;i<dimension;i++) {
636       processor_coordinates[i] = processor_id % Cardinality[i];
637       processor_id = processor_id / Cardinality[i];
638     }
639     return true;
640   }
641   virtual bool get_processor_id(const int* processor_coordinates, int* processor_id) {
642     int i;
643     CmiAssert( processor_coordinates != NULL );
644     CmiAssert( processor_id != NULL );
645     for(i=dimension-1;i>=0;i--) 
646       CmiAssert( 0<=processor_coordinates[i] && processor_coordinates[i]<Cardinality[i]);
647     (*processor_id) = 0;
648     for(i=dimension-1;i>=0;i--) {
649       (*processor_id) = (*processor_id)* Cardinality[i] + processor_coordinates[i];
650     }
651     return true;
652   }
653   //Note: if abs(difference)*2 = cardinality, the difference is set to zero
654   virtual bool coordinate_difference(const int* my_coordinates, const int* target_coordinates, int* difference) { 
655 //    CmiPrintf("[%d] coordiate_difference begin\n", CkMyPe());
656     CmiAssert( my_coordinates != NULL);
657     CmiAssert( target_coordinates != NULL);
658     CmiAssert( difference != NULL);
659 //    CmiPrintf("[%d] after assert\n", CkMyPe());
660     for(int i=0;i<dimension;i++) {
661 //      CmiPrintf("[%d] coordiate_difference iteration %d\n", i);
662       difference[i] = target_coordinates[i] - my_coordinates[i];
663       if (abs(difference[i])*2 > Cardinality[i]) {
664         difference[i] += (difference[i]>0) ? -Cardinality[i] : Cardinality[i];
665       } else if (abs(difference[i])*2 == Cardinality[i]) {
666         difference[i] = 0;
667       }
668     }
669 //    CmiPrintf("[%d] coordiate_difference just before return\n");
670     return true;
671   }
672   //Note: if abs(difference)*2 = cardinality, the difference is set to zero
673   virtual bool coordinate_difference(int my_processor_id, int target_processor_id, int* difference) { 
674     CmiAssert( difference != NULL);
675     int my_coordinates[dimension];
676     int target_coordinates[dimension];
677     get_processor_coordinates(my_processor_id, my_coordinates);
678     get_processor_coordinates(target_processor_id, target_coordinates);
679     coordinate_difference(my_coordinates, target_coordinates, difference);
680     return true;
681   }
682 };
683
684 typedef LBTopo_torus_nd<1> LBTopo_torus_nd_1;
685 typedef LBTopo_torus_nd<2> LBTopo_torus_nd_2;
686 typedef LBTopo_torus_nd<3> LBTopo_torus_nd_3;
687 typedef LBTopo_torus_nd<4> LBTopo_torus_nd_4;
688 typedef LBTopo_torus_nd<5> LBTopo_torus_nd_5;
689 typedef LBTopo_torus_nd<6> LBTopo_torus_nd_6;
690 typedef LBTopo_torus_nd<7> LBTopo_torus_nd_7;
691 typedef LBTopo_torus_nd<8> LBTopo_torus_nd_8;
692 typedef LBTopo_torus_nd<9> LBTopo_torus_nd_9;
693 typedef LBTopo_torus_nd<10> LBTopo_torus_nd_10;
694
695 LBTOPO_MACRO(LBTopo_torus_nd_1)
696 LBTOPO_MACRO(LBTopo_torus_nd_2)
697 LBTOPO_MACRO(LBTopo_torus_nd_3)
698 LBTOPO_MACRO(LBTopo_torus_nd_4)
699 LBTOPO_MACRO(LBTopo_torus_nd_5)
700 LBTOPO_MACRO(LBTopo_torus_nd_6)
701 LBTOPO_MACRO(LBTopo_torus_nd_7)
702 LBTOPO_MACRO(LBTopo_torus_nd_8)
703 LBTOPO_MACRO(LBTopo_torus_nd_9)
704 LBTOPO_MACRO(LBTopo_torus_nd_10)
705
706 //  TORUS ND  and SMP Awareness
707 //  added by Yanhua Sun 
708
709 //#define YHDEBUG
710
711 template <int dimension>
712 class LBTopo_torus_nd_smp: public LBTopology {
713 private:
714   // inherited int npes;
715   int* Cardinality;
716   int  VirtualNodeCount;
717   int* TempCo;
718   int  ppn;
719   int  NumOfNodes;
720 private:
721   int GetNeighborID(int ProcessorID, int number) {
722     CmiAssert(number>=0 && number<max_neighbors());
723     CmiAssert(ProcessorID>=0 && ProcessorID<npes);
724     int neighborId; 
725     int nodeId = CmiPhysicalNodeID(ProcessorID);
726     
727     get_node_coordinates(nodeId, TempCo);
728
729     int index = number/2;
730     int displacement = (number%2)? -1: 1;
731     do{
732       TempCo[index] = (TempCo[index] + displacement + Cardinality[index]) % Cardinality[index];
733       get_node_id(TempCo, &nodeId);
734     } while (nodeId >= NumOfNodes);
735     neighborId = CmiGetFirstPeOnPhysicalNode(nodeId);
736     return neighborId;
737   }
738 public:
739   LBTopo_torus_nd_smp(int p): LBTopology(p) /*inherited :npes(p) */ {
740     int i;
741     CmiAssert(dimension>=1 && dimension<=32);
742     CmiAssert(p>=1);
743
744     ppn = CmiNumPesOnPhysicalNode(0);
745     NumOfNodes = CmiNumPhysicalNodes();
746
747     Cardinality = new int[dimension];
748     TempCo = new int[dimension];
749     double pp = NumOfNodes;
750     for(i=0;i<dimension;i++) {
751       Cardinality[i] = (int)ceil(pow(pp,1.0/(dimension-i))-1e-5);
752       pp = pp / Cardinality[i];
753     }
754     VirtualNodeCount = 1;
755     for(i=0;i<dimension;i++) {
756       VirtualNodeCount *= Cardinality[i];
757     }
758 #ifdef YHDEBUG
759     CmiPrintf(" ppn=%d, NumOfNodes=%d\n", ppn, NumOfNodes);
760 #endif
761   }
762   ~LBTopo_torus_nd_smp() {
763     delete[] Cardinality;
764     delete[] TempCo;
765   }
766   virtual int max_neighbors() {
767     return (dimension+ppn)*2;
768   }
769   virtual void neighbors(int mype, int* _n, int &nb) {
770     nb = 0;
771     int *nodePeList; 
772     int numpes;
773     int rank = CmiPhysicalRank(mype);
774     int node = CmiPhysicalNodeID(mype);
775     int _ppn_ = CmiNumPesOnPhysicalNode(node);
776     CmiGetPesOnPhysicalNode(node, &nodePeList, &numpes); 
777 #ifdef YHDEBUG
778     CmiPrintf(" PE[%d] ppn=%d, NumOfNodes=%d, rank=%d, node=%d, numpes=%d\n", mype, _ppn_, NumOfNodes, rank, node, numpes);
779 #endif   
780     for(int i=0; i<numpes; i++)
781     {
782         int _pid = nodePeList[i];
783         if(_pid != mype)
784         {
785              _n[nb] = _pid;
786              nb++;
787         }
788     }
789
790     /* for inter-node communication */
791     if(mype == CmiGetFirstPeOnPhysicalNode(node))
792     {
793         for(int j=0; j<dimension*2; j++)
794         {
795             //_n[nb] = (mype+1)%npes;//GetNeighborID(mype, j);
796             _n[nb] = GetNeighborID(mype, j);
797             /* the first processors in other nodes */
798             if (_n[nb]!=mype && (nb==0 || _n[nb-1]!=_n[nb]) ) nb++;
799         }
800     }
801
802 #ifdef YHDEBUG
803   CmiPrintf(" [%d] neighbor = %d ppn=%d, NumOfNodes=%d, rank=%d, node=%d, numpes=%d\n", mype, nb, _ppn_, NumOfNodes, rank, node, numpes);
804 #endif
805   }
806   virtual int get_dimension() {
807     return dimension;
808   }
809   virtual bool get_node_coordinates(int node_id, int* node_coordinates) {
810     CmiAssert(node_id>=0 && node_id<VirtualNodeCount);
811     CmiAssert( node_coordinates != NULL );
812     for(int i=0;i<dimension;i++) {
813       node_coordinates[i] = node_id % Cardinality[i];
814       node_id = node_id / Cardinality[i];
815     }
816     return true;
817   }
818   virtual bool get_node_id(const int* node_coordinates, int* node_id) {
819     int i;
820     CmiAssert( node_coordinates != NULL );
821     CmiAssert( node_id != NULL );
822     for(i=dimension-1;i>=0;i--) 
823       CmiAssert( 0<=node_coordinates[i] && node_coordinates[i]<Cardinality[i]);
824     (*node_id) = 0;
825     for(i=dimension-1;i>=0;i--) {
826       (*node_id) = (*node_id)* Cardinality[i] + node_coordinates[i];
827     }
828     return true;
829   }
830   //Note: if abs(difference)*2 = cardinality, the difference is set to zero
831   virtual bool coordinate_difference(const int* my_coordinates, const int* target_coordinates, int* difference) { 
832     CmiAssert( my_coordinates != NULL);
833     CmiAssert( target_coordinates != NULL);
834     CmiAssert( difference != NULL);
835     for(int i=0;i<dimension;i++) {
836       difference[i] = target_coordinates[i] - my_coordinates[i];
837       if (abs(difference[i])*2 > Cardinality[i]) {
838         difference[i] += (difference[i]>0) ? -Cardinality[i] : Cardinality[i];
839       } else if (abs(difference[i])*2 == Cardinality[i]) {
840         difference[i] = 0;
841       }
842     }
843     return true;
844   }
845   //Note: if abs(difference)*2 = cardinality, the difference is set to zero
846   virtual bool coordinate_difference(int my_processor_id, int target_processor_id, int* difference) { 
847     CmiAssert( difference != NULL);
848     int my_coordinates[dimension];
849     int target_coordinates[dimension];
850     get_processor_coordinates(my_processor_id, my_coordinates);
851     get_processor_coordinates(target_processor_id, target_coordinates);
852     coordinate_difference(my_coordinates, target_coordinates, difference);
853     return true;
854   }
855 };
856
857
858 typedef LBTopo_torus_nd_smp<1> LBTopo_torus_nd_smp_1;
859 typedef LBTopo_torus_nd_smp<2> LBTopo_torus_nd_smp_2;
860 typedef LBTopo_torus_nd_smp<3> LBTopo_torus_nd_smp_3;
861 typedef LBTopo_torus_nd_smp<4> LBTopo_torus_nd_smp_4;
862 typedef LBTopo_torus_nd_smp<5> LBTopo_torus_nd_smp_5;
863 typedef LBTopo_torus_nd_smp<6> LBTopo_torus_nd_smp_6;
864 typedef LBTopo_torus_nd_smp<7> LBTopo_torus_nd_smp_7;
865 typedef LBTopo_torus_nd_smp<8> LBTopo_torus_nd_smp_8;
866 typedef LBTopo_torus_nd_smp<9> LBTopo_torus_nd_smp_9;
867 typedef LBTopo_torus_nd_smp<10> LBTopo_torus_nd_smp_10;
868
869 LBTOPO_MACRO(LBTopo_torus_nd_smp_1)
870 LBTOPO_MACRO(LBTopo_torus_nd_smp_2)
871 LBTOPO_MACRO(LBTopo_torus_nd_smp_3)
872 LBTOPO_MACRO(LBTopo_torus_nd_smp_4)
873 LBTOPO_MACRO(LBTopo_torus_nd_smp_5)
874 LBTOPO_MACRO(LBTopo_torus_nd_smp_6)
875 LBTOPO_MACRO(LBTopo_torus_nd_smp_7)
876 LBTOPO_MACRO(LBTopo_torus_nd_smp_8)
877 LBTOPO_MACRO(LBTopo_torus_nd_smp_9)
878 LBTOPO_MACRO(LBTopo_torus_nd_smp_10)
879
880
881 //Torus ND with unequal number of processors in each dimension
882 /***************************************************************/
883 template <int dimension>
884 class LBTopo_itorus_nd: public LBTopology {
885 private:
886         int *dim;
887         int *tempCoor;
888         
889 public:
890         LBTopo_itorus_nd(int p): LBTopology(p) {
891         CmiPrintf("Irregular torus created\n");
892         dim = new int[dimension];
893                 tempCoor = new int[dimension];
894
895                 int i=0;
896         char *lbcopy = strdup(_lbtopo);
897         char *ptr = strchr(lbcopy, ':');
898         if (ptr==NULL) return;
899         ptr = strtok(ptr+1, ",");
900         while (ptr) {
901                         dim[i]=atoi(ptr);
902                         i++;
903                         ptr = strtok(NULL, ",");
904         }
905                 CmiAssert(dimension==i);
906                 
907                 int procs=1;
908                 for(i=0;i<dimension;i++)
909                         procs*=dim[i];
910     CmiAssert(dimension>=1 && dimension<=16);
911     CmiAssert(p>=1);
912                 CmiAssert(procs==p);
913   }
914         
915   ~LBTopo_itorus_nd() {
916         delete[] dim;
917                 delete[] tempCoor;
918         }
919         
920   virtual int max_neighbors() {
921     return dimension*2;
922   }
923         
924         virtual void neighbors(int mype, int* _n, int &nb) {
925     nb = 0;
926     for(int i=0;i<dimension*2;i++) {
927       _n[nb] = GetNeighborID(mype, i);
928       if (_n[nb]!=mype && (nb==0 || _n[nb-1]!=_n[nb]) ) nb++;
929     }
930   }
931
932         int GetNeighborID(int ProcessorID, int number) {
933     CmiAssert(number>=0 && number<max_neighbors());
934     CmiAssert(ProcessorID>=0 && ProcessorID<npes);
935     get_processor_coordinates(ProcessorID, tempCoor);
936
937     int index = number/2;
938     int displacement = (number%2)? -1: 1;
939    // do{
940                 tempCoor[index] = (tempCoor[index] + displacement + dim[index]) % dim[index];
941                 get_processor_id(tempCoor, &ProcessorID);
942     //} while (ProcessorID >= npes);
943     return ProcessorID;
944   }
945
946         virtual bool get_processor_coordinates(int processor_id, int* processor_coordinates) {
947     CmiAssert(processor_id>=0 && processor_id<npes);
948     CmiAssert(processor_coordinates != NULL );
949     for(int i=0;i<dimension;i++) {
950       processor_coordinates[i] = processor_id % dim[i];
951       processor_id = processor_id / dim[i];
952     }
953     return true;
954   }
955
956         virtual bool get_processor_id(const int* processor_coordinates, int* processor_id) {
957     int i;
958     CmiAssert( processor_coordinates != NULL );
959     CmiAssert( processor_id != NULL );
960     for(i=dimension-1;i>=0;i--) 
961       CmiAssert( 0<=processor_coordinates[i] && processor_coordinates[i]<dim[i]);
962     (*processor_id) = 0;
963     for(i=dimension-1;i>=0;i--) {
964       (*processor_id) = (*processor_id)* dim[i] + processor_coordinates[i];
965     }
966     return true;
967   }
968 };
969
970
971 typedef LBTopo_itorus_nd<1> LBTopo_itorus_nd_1;
972 typedef LBTopo_itorus_nd<2> LBTopo_itorus_nd_2;
973 typedef LBTopo_itorus_nd<3> LBTopo_itorus_nd_3;
974 typedef LBTopo_itorus_nd<4> LBTopo_itorus_nd_4;
975 typedef LBTopo_itorus_nd<5> LBTopo_itorus_nd_5;
976 typedef LBTopo_itorus_nd<6> LBTopo_itorus_nd_6;
977 typedef LBTopo_itorus_nd<7> LBTopo_itorus_nd_7;
978
979 LBTOPO_MACRO(LBTopo_itorus_nd_1)
980 LBTOPO_MACRO(LBTopo_itorus_nd_2)
981 LBTOPO_MACRO(LBTopo_itorus_nd_3)
982 LBTOPO_MACRO(LBTopo_itorus_nd_4)
983 LBTOPO_MACRO(LBTopo_itorus_nd_5)
984 LBTOPO_MACRO(LBTopo_itorus_nd_6)
985 LBTOPO_MACRO(LBTopo_itorus_nd_7)
986
987
988 /******************************************************************/
989 //Mesh ND with unequal number of processors in each dimension
990 /***************************************************************/
991 template <int dimension>
992 class LBTopo_imesh_nd: public LBTopology {
993 private:
994         int *dim;
995         int *tempCoor;
996         
997 public:
998         LBTopo_imesh_nd(int p): LBTopology(p) {
999         CmiPrintf("Irregular mesh created\n");
1000         dim = new int[dimension];
1001         tempCoor = new int[dimension];
1002
1003         int i=0;
1004         char *lbcopy = strdup(_lbtopo);
1005         char *ptr = strchr(lbcopy, ':');
1006         if (ptr==NULL) return;
1007         ptr = strtok(ptr+1, ",");
1008         while (ptr) {
1009           dim[i]=atoi(ptr);
1010           i++;
1011           ptr = strtok(NULL, ",");
1012         }
1013         CmiAssert(dimension==i);
1014         
1015         //char *ptr2=strchr(_lbtopo,':');
1016         //*ptr2='\0';
1017         int procs=1;
1018         for(i=0;i<dimension;i++)
1019           procs*=dim[i];
1020           CmiAssert(dimension>=1 && dimension<=16);
1021           CmiAssert(p>=1);
1022           CmiAssert(procs==p);
1023   }
1024         
1025   ~LBTopo_imesh_nd() {
1026         delete[] dim;
1027                 delete[] tempCoor;
1028         }
1029         
1030   virtual int max_neighbors() {
1031     return dimension*2;
1032   }
1033         
1034   virtual void neighbors(int mype, int* _n, int &nb) {
1035     nb = 0;
1036     for(int i=0;i<dimension*2;i++) {
1037       _n[nb] = GetNeighborID(mype, i);
1038       if (_n[nb]!=mype && (nb==0 || _n[nb-1]!=_n[nb]) ) nb++;
1039     }
1040     /*CmiPrintf("Nhs[%d]:",mype);
1041     for(int i=0;i<nb;i++)
1042       CmiPrintf("%d ",_n[i]);
1043     CmiPrintf("\n");*/
1044   }
1045
1046         int GetNeighborID(int ProcessorID, int number) {
1047         CmiAssert(number>=0 && number<max_neighbors());
1048         CmiAssert(ProcessorID>=0 && ProcessorID<npes);
1049         get_processor_coordinates(ProcessorID, tempCoor);
1050
1051         int index = number/2;
1052         int displacement = (number%2)? -1: 1;
1053    // do{
1054             if((tempCoor[index]==0 && displacement==-1) || (tempCoor[index]==dim[index]-1 && displacement==1)){
1055         }
1056         else{
1057              tempCoor[index] = (tempCoor[index] + displacement + dim[index]) % dim[index];
1058              get_processor_id(tempCoor, &ProcessorID);
1059             }
1060     //} while (ProcessorID >= npes);
1061     return ProcessorID;
1062   }
1063
1064         virtual bool get_processor_coordinates(int processor_id, int* processor_coordinates) {
1065     CmiAssert(processor_id>=0 && processor_id<npes);
1066     CmiAssert(processor_coordinates != NULL );
1067     for(int i=0;i<dimension;i++) {
1068       processor_coordinates[i] = processor_id % dim[i];
1069       processor_id = processor_id / dim[i];
1070     }
1071     return true;
1072   }
1073
1074         virtual bool get_processor_id(const int* processor_coordinates, int* processor_id) {
1075     int i;
1076     CmiAssert( processor_coordinates != NULL );
1077     CmiAssert( processor_id != NULL );
1078     for(i=dimension-1;i>=0;i--) 
1079       CmiAssert( 0<=processor_coordinates[i] && processor_coordinates[i]<dim[i]);
1080     (*processor_id) = 0;
1081     for(i=dimension-1;i>=0;i--) {
1082       (*processor_id) = (*processor_id)* dim[i] + processor_coordinates[i];
1083     }
1084     return true;
1085   }
1086 };
1087
1088
1089 typedef LBTopo_imesh_nd<1> LBTopo_imesh_nd_1;
1090 typedef LBTopo_imesh_nd<2> LBTopo_imesh_nd_2;
1091 typedef LBTopo_imesh_nd<3> LBTopo_imesh_nd_3;
1092 typedef LBTopo_imesh_nd<4> LBTopo_imesh_nd_4;
1093 typedef LBTopo_imesh_nd<5> LBTopo_imesh_nd_5;
1094 typedef LBTopo_imesh_nd<6> LBTopo_imesh_nd_6;
1095 typedef LBTopo_imesh_nd<7> LBTopo_imesh_nd_7;
1096
1097 LBTOPO_MACRO(LBTopo_imesh_nd_1)
1098 LBTOPO_MACRO(LBTopo_imesh_nd_2)
1099 LBTOPO_MACRO(LBTopo_imesh_nd_3)
1100 LBTOPO_MACRO(LBTopo_imesh_nd_4)
1101 LBTOPO_MACRO(LBTopo_imesh_nd_5)
1102 LBTOPO_MACRO(LBTopo_imesh_nd_6)
1103 LBTOPO_MACRO(LBTopo_imesh_nd_7)
1104
1105
1106 // dense graph with connectivity of square root processor number
1107
1108 LBTOPO_MACRO(LBTopo_graph)
1109
1110 int LBTopo_graph::max_neighbors()
1111 {
1112   return (int)(sqrt(1.0*CmiNumPes())+0.5);
1113 }
1114
1115 extern "C" void gengraph(int, int, int, int *, int *, int);
1116
1117 void LBTopo_graph::neighbors(int mype, int* na, int &nb)
1118 {
1119   gengraph(CmiNumPes(), (int)(sqrt(1.0*CmiNumPes())+0.5), 234, na, &nb, 0);
1120 }
1121
1122 /* add by Yanhua Aug-2010*/
1123 template <int dimension>
1124 class LBTopo_graph_nc: public LBTopology {
1125
1126 public:
1127     LBTopo_graph_nc(int p): LBTopology(p) {}
1128     int max_neighbors()
1129     {
1130         return dimension + 1; 
1131     }
1132
1133     void neighbors(int mype, int* na, int &nb)
1134     {
1135 #if CMK_NODE_QUEUE_AVAILABLE
1136         gengraph(CmiNumNodes(), dimension, 234, na, &nb, 0);
1137 #else
1138         gengraph(CmiNumPes(), dimension, 234, na, &nb, 0);
1139 #endif
1140     }
1141
1142 };
1143 typedef LBTopo_graph_nc<2> LBTopo_graph_nc_2;
1144 typedef LBTopo_graph_nc<3> LBTopo_graph_nc_3;
1145 typedef LBTopo_graph_nc<4> LBTopo_graph_nc_4;
1146 typedef LBTopo_graph_nc<5> LBTopo_graph_nc_5;
1147 typedef LBTopo_graph_nc<6> LBTopo_graph_nc_6;
1148 typedef LBTopo_graph_nc<7> LBTopo_graph_nc_7;
1149 typedef LBTopo_graph_nc<8> LBTopo_graph_nc_8;
1150 typedef LBTopo_graph_nc<9> LBTopo_graph_nc_9;
1151 typedef LBTopo_graph_nc<10> LBTopo_graph_nc_10;
1152 typedef LBTopo_graph_nc<20> LBTopo_graph_nc_20;
1153
1154 LBTOPO_MACRO(LBTopo_graph_nc_2)
1155 LBTOPO_MACRO(LBTopo_graph_nc_3)
1156 LBTOPO_MACRO(LBTopo_graph_nc_4)
1157 LBTOPO_MACRO(LBTopo_graph_nc_5)
1158 LBTOPO_MACRO(LBTopo_graph_nc_6)
1159 LBTOPO_MACRO(LBTopo_graph_nc_7)
1160 LBTOPO_MACRO(LBTopo_graph_nc_8)
1161 LBTOPO_MACRO(LBTopo_graph_nc_9)
1162 LBTOPO_MACRO(LBTopo_graph_nc_10)
1163 LBTOPO_MACRO(LBTopo_graph_nc_20)
1164
1165
1166 /* Centralized  balancer, one processor has the neighbors of all other processors, while the other ones only have one neighbor, the centralized processor */
1167
1168  
1169
1170 // complete graph
1171
1172 class LBTopo_complete: public LBTopology {
1173 public:
1174   LBTopo_complete(int p): LBTopology(p) {}
1175   int max_neighbors() {
1176     return npes - 1;
1177   }
1178   void neighbors(int mype, int* _n, int &nb) {
1179     nb = 0;
1180     for (int i=0; i<npes; i++)  if (mype != i) _n[nb++] = i;
1181   }
1182 };
1183
1184 LBTOPO_MACRO(LBTopo_complete)
1185
1186 //   k-ary tree
1187
1188 template <int k>
1189 class LBTopo_karytree: public LBTopology {
1190 public:
1191   LBTopo_karytree(int p): LBTopology(p) {}
1192   virtual int max_neighbors() {
1193     return k+1;     // parent + children
1194   }
1195   virtual void neighbors(int mype, int* _n, int &nb) {
1196     nb = 0;
1197     if (mype!=0) _n[nb++] = (mype-1)/k;
1198     int firstchild = mype*k+1;
1199     for (int i=0; i<k; i++)
1200       if (firstchild+i < npes) _n[nb++] = firstchild+i;
1201   }
1202 };
1203
1204 typedef LBTopo_karytree<2> LBTopo_2_arytree;
1205 typedef LBTopo_karytree<3> LBTopo_3_arytree;
1206 typedef LBTopo_karytree<4> LBTopo_4_arytree;
1207 typedef LBTopo_karytree<128> LBTopo_128_arytree;
1208 typedef LBTopo_karytree<512> LBTopo_512_arytree;
1209
1210 LBTOPO_MACRO(LBTopo_2_arytree)
1211 LBTOPO_MACRO(LBTopo_3_arytree)
1212 LBTOPO_MACRO(LBTopo_4_arytree)
1213 LBTOPO_MACRO(LBTopo_128_arytree)
1214 LBTOPO_MACRO(LBTopo_512_arytree)
1215
1216 //
1217
1218 class LBTopoMap {
1219 public:
1220   const char *name;
1221   LBtopoFn fn;
1222   LBTopoMap(const char *s, LBtopoFn f): name(s), fn(f) {}
1223   LBTopoMap(const LBTopoMap &p);                // You don't want to copy
1224   void operator=(const LBTopoMap &p);           // You don't want to copy
1225 };
1226
1227 class LBTopoVec {
1228   CkVec<LBTopoMap *> lbTopos;
1229 public:
1230   LBTopoVec() {
1231     // register all topos
1232     lbTopos.push_back(new LBTopoMap("ring", createLBTopo_ring));
1233     lbTopos.push_back(new LBTopoMap("torus2d", createLBTopo_torus2d));
1234     lbTopos.push_back(new LBTopoMap("torus3d", createLBTopo_torus3d));
1235     lbTopos.push_back(new LBTopoMap("mesh3d", createLBTopo_mesh3d));
1236     lbTopos.push_back(new LBTopoMap("torus_nd_1", createLBTopo_torus_nd_1));
1237     lbTopos.push_back(new LBTopoMap("torus_nd_2", createLBTopo_torus_nd_2));
1238     lbTopos.push_back(new LBTopoMap("torus_nd_3", createLBTopo_torus_nd_3));
1239     lbTopos.push_back(new LBTopoMap("torus_nd_4", createLBTopo_torus_nd_4));
1240     lbTopos.push_back(new LBTopoMap("torus_nd_5", createLBTopo_torus_nd_5));
1241     lbTopos.push_back(new LBTopoMap("torus_nd_6", createLBTopo_torus_nd_6));
1242     lbTopos.push_back(new LBTopoMap("torus_nd_7", createLBTopo_torus_nd_7));
1243     lbTopos.push_back(new LBTopoMap("torus_nd_8", createLBTopo_torus_nd_8));
1244     lbTopos.push_back(new LBTopoMap("torus_nd_9", createLBTopo_torus_nd_9));
1245     lbTopos.push_back(new LBTopoMap("torus_nd_10", createLBTopo_torus_nd_10));
1246     lbTopos.push_back(new LBTopoMap("torus_nd_smp_1", createLBTopo_torus_nd_smp_1));
1247     lbTopos.push_back(new LBTopoMap("torus_nd_smp_2", createLBTopo_torus_nd_smp_2));
1248     lbTopos.push_back(new LBTopoMap("torus_nd_smp_3", createLBTopo_torus_nd_smp_3));
1249     lbTopos.push_back(new LBTopoMap("torus_nd_smp_4", createLBTopo_torus_nd_smp_4));
1250     lbTopos.push_back(new LBTopoMap("torus_nd_smp_5", createLBTopo_torus_nd_smp_5));
1251     lbTopos.push_back(new LBTopoMap("torus_nd_smp_6", createLBTopo_torus_nd_smp_6));
1252     lbTopos.push_back(new LBTopoMap("torus_nd_smp_7", createLBTopo_torus_nd_smp_7));
1253     lbTopos.push_back(new LBTopoMap("torus_nd_smp_8", createLBTopo_torus_nd_smp_8));
1254     lbTopos.push_back(new LBTopoMap("torus_nd_smp_9", createLBTopo_torus_nd_smp_9));
1255     lbTopos.push_back(new LBTopoMap("torus_nd_smp_10", createLBTopo_torus_nd_smp_10));
1256     lbTopos.push_back(new LBTopoMap("itorus_nd_1", createLBTopo_itorus_nd_1));
1257     lbTopos.push_back(new LBTopoMap("itorus_nd_2", createLBTopo_itorus_nd_2));
1258     lbTopos.push_back(new LBTopoMap("itorus_nd_3", createLBTopo_itorus_nd_3));
1259     lbTopos.push_back(new LBTopoMap("itorus_nd_4", createLBTopo_itorus_nd_4));
1260     lbTopos.push_back(new LBTopoMap("itorus_nd_5", createLBTopo_itorus_nd_5));
1261     lbTopos.push_back(new LBTopoMap("itorus_nd_6", createLBTopo_itorus_nd_6));
1262     lbTopos.push_back(new LBTopoMap("itorus_nd_7", createLBTopo_itorus_nd_7));
1263     lbTopos.push_back(new LBTopoMap("imesh_nd_1", createLBTopo_imesh_nd_1));
1264     lbTopos.push_back(new LBTopoMap("imesh_nd_2", createLBTopo_imesh_nd_2));
1265     lbTopos.push_back(new LBTopoMap("imesh_nd_3", createLBTopo_imesh_nd_3));
1266     lbTopos.push_back(new LBTopoMap("imesh_nd_4", createLBTopo_imesh_nd_4));
1267     lbTopos.push_back(new LBTopoMap("imesh_nd_5", createLBTopo_imesh_nd_5));
1268     lbTopos.push_back(new LBTopoMap("imesh_nd_6", createLBTopo_imesh_nd_6));
1269     lbTopos.push_back(new LBTopoMap("imesh_nd_7", createLBTopo_imesh_nd_7));
1270     lbTopos.push_back(new LBTopoMap("graph", createLBTopo_graph));
1271     lbTopos.push_back(new LBTopoMap("graph_nc_2", createLBTopo_graph_nc_2));
1272     lbTopos.push_back(new LBTopoMap("graph_nc_3", createLBTopo_graph_nc_3));
1273     lbTopos.push_back(new LBTopoMap("graph_nc_4", createLBTopo_graph_nc_4));
1274     lbTopos.push_back(new LBTopoMap("graph_nc_5", createLBTopo_graph_nc_5));
1275     lbTopos.push_back(new LBTopoMap("graph_nc_6", createLBTopo_graph_nc_6));
1276     lbTopos.push_back(new LBTopoMap("graph_nc_7", createLBTopo_graph_nc_7));
1277     lbTopos.push_back(new LBTopoMap("graph_nc_8", createLBTopo_graph_nc_8));
1278     lbTopos.push_back(new LBTopoMap("graph_nc_9", createLBTopo_graph_nc_9));
1279     lbTopos.push_back(new LBTopoMap("graph_nc_10", createLBTopo_graph_nc_10));
1280     lbTopos.push_back(new LBTopoMap("graph_nc_20", createLBTopo_graph_nc_20));
1281     lbTopos.push_back(new LBTopoMap("complete", createLBTopo_complete));
1282     lbTopos.push_back(new LBTopoMap("2_arytree", createLBTopo_2_arytree));
1283     lbTopos.push_back(new LBTopoMap("3_arytree", createLBTopo_3_arytree));
1284     lbTopos.push_back(new LBTopoMap("4_arytree", createLBTopo_4_arytree));
1285     lbTopos.push_back(new LBTopoMap("128_arytree", createLBTopo_128_arytree));
1286     lbTopos.push_back(new LBTopoMap("512_arytree", createLBTopo_512_arytree));
1287     lbTopos.push_back(new LBTopoMap("smp_n_1", createLBTopo_smp_n_1));
1288     lbTopos.push_back(new LBTopoMap("smp_n_2", createLBTopo_smp_n_2));
1289     lbTopos.push_back(new LBTopoMap("smp_n_3", createLBTopo_smp_n_3));
1290     lbTopos.push_back(new LBTopoMap("smp_n_4", createLBTopo_smp_n_4));
1291     lbTopos.push_back(new LBTopoMap("smp_n_5", createLBTopo_smp_n_5));
1292     lbTopos.push_back(new LBTopoMap("smp_n_6", createLBTopo_smp_n_6));
1293     lbTopos.push_back(new LBTopoMap("smp_n_7", createLBTopo_smp_n_7));
1294     lbTopos.push_back(new LBTopoMap("smp_n_8", createLBTopo_smp_n_8));
1295     lbTopos.push_back(new LBTopoMap("smp_n_9", createLBTopo_smp_n_9));
1296     lbTopos.push_back(new LBTopoMap("smp_n_10", createLBTopo_smp_n_10));
1297   }
1298   ~LBTopoVec() {
1299     for (int i=0; i<lbTopos.length(); i++)
1300       delete lbTopos[i];
1301   }
1302   void push_back(LBTopoMap *map) { lbTopos.push_back(map); }
1303   int length() { return lbTopos.length(); }
1304   LBTopoMap * operator[](size_t n) { return lbTopos[n]; }
1305   void print() {
1306     for (int i=0; i<lbTopos.length(); i++) {
1307       CmiPrintf("  %s\n", lbTopos[i]->name);
1308     }
1309   }
1310 };
1311
1312 static LBTopoVec lbTopoMap;
1313
1314 extern "C"
1315 LBtopoFn LBTopoLookup(char *name)
1316 {
1317   for (int i=0; i<lbTopoMap.length(); i++) {
1318     if (strcmp(name, lbTopoMap[i]->name)==0) return lbTopoMap[i]->fn;
1319   }
1320   return NULL;
1321 }
1322
1323 // C wrapper functions
1324 extern "C" void getTopoNeighbors(void *topo, int myid, int* narray, int *n)
1325 {
1326   ((LBTopology*)topo)->neighbors(myid, narray, *n);
1327 }
1328
1329 extern "C" int getTopoMaxNeighbors(void *topo)
1330 {
1331   return ((LBTopology*)topo)->max_neighbors();
1332 }
1333
1334 extern "C" void printoutTopo()
1335 {
1336   lbTopoMap.print();
1337 }
1338