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