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