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