change Ckpv to Cpv in conv-com
[charm.git] / src / conv-com / hypercuberouter.C
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 /**
9    @addtogroup ConvComlibRouter
10    @{
11   
12    @file 
13     
14     @brief Dimensional Exchange (Hypercube) Router 
15
16     Modified to send last k stages directly for all to all multicast by
17     Sameer Kumar 9/07/03.
18
19     Adapted to the new communication library 05/14/04.
20  
21 */
22
23 #include "hypercuberouter.h"
24
25 #define gmap(pe) {if (gpes) pe=gpes[pe];}
26
27 //#define gmap(pe) (gpes ? gpes[pe] : pe)
28
29 /**The only communication op used. Modify this to use
30  ** vector send */
31
32 #if CMK_COMLIB_USE_VECTORIZE
33 #define HCUBESENDFN(kid, u1, u2, knpe, kpelist, khndl, knextpe, pehcube)  \
34         {int len;\
35         PTvectorlist newmsg;\
36         newmsg=pehcube->ExtractAndVectorize(kid, u1, knpe, kpelist);\
37         if (newmsg) {\
38           CmiSetHandler(newmsg->msgs[0], khndl);\
39           CmiSyncVectorSendAndFree(knextpe, -newmsg->count, newmsg->sizes, newmsg->msgs);\
40         }\
41         else {\
42           SendDummyMsg(kid, knextpe, u2);\
43         }\
44 }
45 #else
46 #define HCUBESENDFN(kid, u1, u2, knpe, kpelist, khndl, knextpe, pehcube)  \
47         {int len;\
48         char *newmsg;\
49         newmsg=pehcube->ExtractAndPack(kid, u1, knpe, kpelist, &len);\
50         if (newmsg) {\
51           CmiSetHandler(newmsg, khndl);\
52           CmiSyncSendAndFree(knextpe, len, newmsg);\
53         }\
54         else {\
55           SendDummyMsg(kid, knextpe, u2);\
56         }\
57 }
58 #endif
59
60 inline int maxdim(int n)
61 {
62   int maxpes=1, dim=0;
63
64   while (maxpes< n) {
65         maxpes *=2;
66         dim++;
67   }
68   if (maxpes==n) return(dim);
69   else return(dim-1);
70 }
71
72 inline int neighbor(int pe, int dim)
73 {
74   return(pe ^ (1<<dim));
75 }
76
77 inline int adjust(int dim, int pe)
78 {
79   int mymax=1<<dim;
80   if (pe >= mymax) return(neighbor(pe, dim));
81   else return(pe);
82 }
83
84 inline int setIC(int dim, int pe, int N)
85 {
86   int mymax= 1<< dim;
87   int initCounter=1, myneighb;
88   if (mymax < N) {
89         myneighb= neighbor(pe, dim);
90         if (myneighb < N && myneighb >= mymax) {
91               initCounter=0;
92         }
93   }
94   if (pe >= mymax) initCounter = -1;
95   return(initCounter);
96 }
97
98 /*********************************************************************
99  * Total preallocated memory=(P+Dim+Dim*P)ints + MAXNUMMSGS msgstruct
100  **********************************************************************/
101 HypercubeRouter::HypercubeRouter(int n, int me, Strategy *parent, int ndirect) : Router(parent)
102 {
103   int i;
104  
105   //last ndirect steps will be sent directly
106   numDirectSteps = ndirect;
107   //2 raised to the power of ndirect
108   two_pow_ndirect = 1;
109   for(int count = 0; count < ndirect; count ++)
110       two_pow_ndirect *= 2;
111
112   //Initialize the no: of pes and my Pe number
113   NumPes=n;
114   MyPe=me;
115   gpes=NULL;
116
117   //Initialize Dimension and no: of stages
118   Dim=maxdim(NumPes);
119
120   PeHcube=new PeTable(NumPes);
121   PeHcube1 = new PeTable(NumPes);
122
123   InitVars();
124
125   //Create the message array, buffer and the next stage table
126   buffer=new int[Dim+1];
127   next= new int* [Dim];
128   for (i=0;i<Dim;i++) {
129         next[i]=new int[NumPes];
130         buffer[i]=0;
131         for (int j=0;j<NumPes;j++) next[i][j]=-1;
132   }
133   buffer[Dim]=0;
134
135   //Create and initialize the indexes to the above table
136   penum=new int[NumPes];
137   int *dp=new int[NumPes];
138   for (i=0;i<NumPes;i++) {
139         penum[i]=0;
140         dp[i]=i;
141   }
142
143   CreateStageTable(NumPes, dp);
144   delete [] dp;
145
146   //CmiPrintf("%d DE constructor done dim=%d, mymax=%d IC=%d\n", MyPe, Dim, 1<<Dim, InitCounter);
147
148   if(numDirectSteps > Dim - 1)
149       numDirectSteps = Dim - 1;
150 }
151  
152 HypercubeRouter :: ~HypercubeRouter()
153 {
154   int i;
155   delete PeHcube;
156   delete PeHcube1;
157   delete buffer;
158   for (i=0;i<Dim;i++) {
159         delete next[i];
160   }
161   delete next;
162   delete penum;
163 }
164
165 void HypercubeRouter :: SetMap(int *pes)
166 {
167   gpes=pes;
168 }
169
170 void HypercubeRouter :: InitVars()
171 {
172   stage=Dim-1;
173   InitCounter=setIC(Dim, MyPe, NumPes);
174   procMsgCount = 0;
175 }
176
177 void HypercubeRouter::EachToAllMulticast(comID id, int size, void *msg, int more)
178 {
179   int npe=NumPes;
180   int * destpes=(int *)CmiAlloc(sizeof(int)*npe);
181   for (int i=0;i<npe;i++) destpes[i]=i;
182   EachToManyMulticast(id, size, msg, npe, destpes, more);
183   CmiFree(destpes);
184 }
185
186 void HypercubeRouter::NumDeposits(comID, int num)
187 {
188   //CmiPrintf("Deposit=%d\n", num);
189 }
190
191 void HypercubeRouter::EachToManyMulticast(comID id, int size, void *msg, int numpes, int *destpes, int more)
192 {
193
194     SetID(id);
195
196     //Create the message
197     if (msg && size) {
198         PeHcube->InsertMsgs(numpes, destpes, size, msg);
199     }
200     
201     if (more) return;
202     start_hcube(id);
203 }
204
205 void HypercubeRouter::EachToManyMulticastQ(comID id, CkQ<MessageHolder *> &msgq) {
206     SetID(id);
207
208     int count = 0;
209     int length = msgq.length();
210
211     for(count = 0; count < length; count ++) {
212         MessageHolder *mhdl = msgq.deq();
213         PeHcube->InsertMsgs(mhdl->npes, mhdl->pelist, mhdl->size, 
214                             mhdl->getMessage());
215         delete mhdl;
216     }
217     
218     start_hcube(id);
219 }
220
221 void HypercubeRouter::start_hcube(comID id) {
222
223     if (InitCounter <0) {
224         ComlibPrintf("%d Sending to the lower hypercube\n", MyPe);
225         int nextpe=neighbor(MyPe, Dim);
226         int * pelist=(int *)CmiAlloc(NumPes*sizeof(int));
227         for (int i=0;i<NumPes;i++) {
228             pelist[i]=i;
229         }
230         
231         ComlibPrintf("Before Gmap %d\n", nextpe);
232         gmap(nextpe);
233         ComlibPrintf("%d: EachToMany Sending to %d\n", MyPe, nextpe);
234         HCUBESENDFN(id, Dim, Dim, NumPes, pelist, CkpvAccess(RouterRecvHandle), nextpe, PeHcube);
235         CmiFree(pelist);
236         return;
237     }
238     
239     //Done: no more stages.
240     if (stage <0) {
241         //CmiPrintf("calling lp in multicast call %d\n", stage);
242         LocalProcMsg(id);
243         return;
244     }
245     
246     InitCounter++;
247     RecvManyMsg(id,NULL);
248 }
249
250 //Send the messages for the next stage to the next dimension neighbor
251 //If only numDirectStage's are left send messages directly using prefix send
252 void HypercubeRouter::RecvManyMsg(comID id, char *msg)
253 {
254     ComlibPrintf("%d recvmanymsg called\n", MyPe);
255     int msgstage;
256     if (msg) {
257         msgstage=PeHcube->UnpackAndInsert(msg);
258         //CmiPrintf("%d recvd msg for stage=%d\n", MyPe, msgstage);
259         if (msgstage == Dim) InitCounter++;
260         else buffer[msgstage]=1;
261     }
262   
263     //Check the buffers 
264     while ((InitCounter==2) || (stage >=numDirectSteps && buffer[stage+1])) {
265         InitCounter=setIC(Dim, MyPe, NumPes);
266         if (InitCounter != 2) { 
267             buffer[stage+1]=0;
268         }
269
270         //Send the data to the neighbor in this stage
271         int nextpe=neighbor(MyPe, stage);
272         
273         ComlibPrintf("Before Gmap %d\n", nextpe);
274         gmap(nextpe);
275         ComlibPrintf("%d RecvManyMsg Sending to %d\n", MyPe, nextpe);
276         HCUBESENDFN(id, stage, stage, penum[stage], next[stage], CkpvAccess(RouterRecvHandle), nextpe, PeHcube);
277
278         //Go to the next stage
279         stage--; 
280     }        
281
282     if (stage < numDirectSteps && buffer[numDirectSteps]) {
283                 
284         InitCounter=setIC(Dim, MyPe, NumPes);
285         
286         //I am a processor in the smaller hypercube and there are some
287         //processors to send directly
288         if(InitCounter >= 0 && numDirectSteps > 0) {
289             //Sending through prefix send to save on copying overhead   
290             //of the hypercube algorithm            
291             
292 #if CMK_COMLIB_USE_VECTORIZE
293             PTvectorlist newmsg;
294             newmsg=PeHcube->ExtractAndVectorizeAll(id, stage);
295             if (newmsg) {
296                 CmiSetHandler(newmsg->msgs[0], CkpvAccess(RouterProcHandle));
297                 for (int count=0; count<two_pow_ndirect; ++count) {
298                   int nextpe = count ^ MyPe;
299                   gmap(nextpe);
300                   ComlibPrintf("%d Sending to %d\n", MyPe, nextpe);
301                   CmiSyncVectorSend(nextpe, -newmsg->count, newmsg->sizes, newmsg->msgs);
302                 }
303                 for(int i=0;i<newmsg->count;i++) CmiFree(newmsg->msgs[i]);
304                 CmiFree(newmsg->sizes);
305                 CmiFree(newmsg->msgs);
306             }
307 #else
308             int *pelist = (int *)CmiAlloc(two_pow_ndirect * sizeof(int));
309             for(int count = 0; count < two_pow_ndirect; count ++){
310                 int nextpe = count ^ MyPe;
311                 gmap(nextpe);
312
313                 ComlibPrintf("%d Sending to %d\n", MyPe, nextpe);
314                 pelist[count] = nextpe;
315             }
316             
317             int len;
318             char *newmsg;
319             newmsg=PeHcube->ExtractAndPackAll(id, stage, &len);
320             if (newmsg) {
321                 CmiSetHandler(newmsg, CkpvAccess(RouterProcHandle));
322                 CmiSyncListSendAndFree(two_pow_ndirect, pelist, len, newmsg);
323             }
324             CmiFree(pelist);
325 #endif
326
327             stage -= numDirectSteps;
328
329             //if(procMsgCount == two_pow_ndirect)
330             //  LocalProcMsg();
331         }
332         else if(numDirectSteps == 0) {
333             LocalProcMsg(id);
334             ComlibPrintf("Calling local proc msg %d\n", 
335                          buffer[numDirectSteps]);
336         }
337         
338         buffer[numDirectSteps]=0;
339     }
340 }
341
342 void HypercubeRouter :: ProcManyMsg(comID id, char *m)
343 {
344     ComlibPrintf("%d: In procmanymsg\n", MyPe);
345     InitCounter=setIC(Dim, MyPe, NumPes);
346     if(id.isAllToAll) {
347         int pe_list[2];
348         int npes = 2;
349
350         if(InitCounter > 0)
351             npes = 1;
352         
353         pe_list[0] = MyPe;
354         pe_list[1] = neighbor(MyPe, Dim);
355         
356         PeHcube1->UnpackAndInsertAll(m, npes, pe_list);
357     }
358     else
359         PeHcube->UnpackAndInsert(m);
360     
361     procMsgCount ++;
362
363     if(InitCounter >= 0){
364         if((procMsgCount == two_pow_ndirect) && stage < 0) {
365             ComlibPrintf("%d Calling lp %d %d\n", MyPe, 
366                          procMsgCount, stage);
367             LocalProcMsg(id);
368         }
369     }
370     else
371         //CmiPrintf("calling lp in procmsg call\n");
372         LocalProcMsg(id);
373 }
374
375 void HypercubeRouter:: LocalProcMsg(comID id)
376 {
377     //CmiPrintf("%d local procmsg called\n", MyPe);
378
379     int mynext=neighbor(MyPe, Dim);
380     int mymax=1<<Dim;
381     
382     if (mynext >=mymax && mynext < NumPes) {
383         ComlibPrintf("Before Gmap %d\n", mynext);
384         int pelist[1];
385         pelist[0] = mynext;
386         ComlibPrintf("%d Sending to upper hypercube  %d\n", MyPe, mynext);
387         
388         if(id.isAllToAll){
389             gmap(mynext);
390             HCUBESENDFN(id, Dim, -1, 1, pelist, CkpvAccess(RouterProcHandle), mynext, PeHcube1);
391         }
392         else {
393             gmap(mynext);
394             HCUBESENDFN(id, Dim, -1, 1, pelist, CkpvAccess(RouterProcHandle), mynext, PeHcube);
395         }
396     }
397   
398     if(id.isAllToAll)
399         PeHcube1->ExtractAndDeliverLocalMsgs(MyPe, container);
400     else
401         PeHcube->ExtractAndDeliverLocalMsgs(MyPe, container);
402
403     PeHcube->Purge();
404     PeHcube1->Purge();
405     InitVars();
406     Done(id);
407 }
408
409 void HypercubeRouter::DummyEP(comID id, int msgstage)
410 {
411   if (msgstage >= 0) {
412         buffer[msgstage]=1;
413         RecvManyMsg(id, NULL);
414   }
415   else {
416         //CmiPrintf("%d Dummy calling lp\n", MyPe);
417         LocalProcMsg(id);
418   }
419 }
420
421 void HypercubeRouter::CreateStageTable(int numpes, int *destpes)
422 {
423   int *dir=new int[numpes];
424   int nextdim, j, i;
425   for (i=0;i<numpes;i++) {
426         dir[i]=MyPe ^ adjust(Dim, destpes[i]);
427   }
428   for (nextdim=Dim-1; nextdim>=0; nextdim--) {
429     int mask=1<<nextdim;
430     for (i=0;i<numpes;i++) {
431         if (dir[i] & mask) {
432                 dir[i]=0;
433                 for (j=0;(j<penum[nextdim]) && (destpes[i]!=next[nextdim][j]);j++);
434                 if (destpes[i]==next[nextdim][j]) { 
435                         //CmiPrintf("EQUAL %d\n", destpes[i]);
436                         continue;
437                 }
438                 next[nextdim][penum[nextdim]]=destpes[i];
439                 penum[nextdim]+=1;
440                 //CmiPrintf("%d next[%d][%d]=%d\n",MyPe, nextdim, penum[nextdim],destpes[i]);
441         }
442     }
443   }
444   delete [] dir;
445   return;
446 }
447
448 Router * newhcubeobject(int n, int me, Strategy *strat)
449 {
450     Router *obj=new HypercubeRouter(n, me, strat);
451     return(obj);
452 }
453
454 //MOVE this CODE else where, this method has been depricated!!!
455 void HypercubeRouter::SetID(comID id) { 
456
457     if(id.isAllToAll) {
458         numDirectSteps = 2;
459         two_pow_ndirect = 1;
460           for(int count = 0; count < numDirectSteps; count ++)
461               two_pow_ndirect *= 2;
462     }
463 }
464
465 /*@}*/