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