d7a0882e5948f357f37c707c38d5296de1dca59e
[charm.git] / src / ck-com / OneTimeMulticastStrategy.C
1 /**
2    @addtogroup ComlibCharmStrategy
3    @{
4    @file
5
6 */
7
8
9 #include "OneTimeMulticastStrategy.h"
10 #include "TopoManager.h"
11 #include <string>
12 #include <set>
13 #include <vector>
14 #include <list>
15 #include <map>
16
17 //#define DEBUG 1
18
19 using std::list;
20 using std::set;
21 using std::vector;
22 using std::map;
23
24 /// @note: There is some bug that is preventing us from using CmiSyncListSend. 
25 #define SYNCLISTSENDANDFREE 1
26
27
28 CkpvExtern(CkGroupID, cmgrID);
29
30 OneTimeMulticastStrategy::OneTimeMulticastStrategy()
31   : Strategy(), CharmStrategy() {
32   //  ComlibPrintf("OneTimeMulticastStrategy constructor\n");
33   setType(ARRAY_STRATEGY);
34 }
35
36 OneTimeMulticastStrategy::~OneTimeMulticastStrategy() {
37 }
38
39 void OneTimeMulticastStrategy::pup(PUP::er &p){
40   Strategy::pup(p);
41   CharmStrategy::pup(p);
42 }
43
44
45 /** Called when the user invokes the entry method on the delegated proxy. */
46 void OneTimeMulticastStrategy::insertMessage(CharmMessageHolder *cmsg){
47 #if DEBUG
48   CkPrintf("[%d] OneTimeMulticastStrategy::insertMessage\n", CkMyPe());
49   fflush(stdout);
50 #endif 
51
52   if(cmsg->dest_proc != IS_SECTION_MULTICAST && cmsg->sec_id == NULL) { 
53     CkAbort("OneTimeMulticastStrategy can only be used with an array section proxy");
54   }
55     
56
57   envelope *env = UsrToEnv(cmsg->getCharmMessage());
58   int npes = 1;
59   int pes[1] = {0};
60   _TRACE_CREATION_MULTICAST(env, npes, pes);
61
62 #if DEBUG
63   CkPrintf("[%d] after TRACE_CREATION_MULTICAST menv->event=%d\n", CkMyPe(), (int)env->getEvent());  
64 #endif
65   
66   // Create a multicast message containing all information about remote destination objects 
67   ComlibMulticastMsg * multMsg = sinfo.getNewMulticastMessage(cmsg, 0, getInstance());
68
69
70 #if DEBUG
71     CkPrintf("[%d] after TRACE_CREATION_MULTICAST multMsg->event=%d\n", CkMyPe(), (int)( UsrToEnv(multMsg)->getEvent() ) );  
72 #endif
73
74   // The remote multicast method will send the message to the remote PEs, as specified in multMsg
75   remoteMulticast(multMsg, true);
76
77   // local multicast will re-extract a list of local destination objects (FIXME to make this more efficient)
78   localMulticast(cmsg);
79
80   delete cmsg;    
81 }
82
83
84
85 /** Deliver the message to the local elements. */
86 void OneTimeMulticastStrategy::localMulticast(CharmMessageHolder *cmsg) {
87   double start = CmiWallTimer();
88   CkSectionID *sec_id = cmsg->sec_id;
89   CkVec< CkArrayIndex > localIndices;
90   CkArrayID aid(sec_id->_cookie.get_aid());
91   sinfo.getLocalIndices(sec_id->_nElems, sec_id->_elems, aid, localIndices);
92   deliverToIndices(cmsg->getCharmMessage(), localIndices );
93   traceUserBracketEvent(10000, start, CmiWallTimer());
94 }
95
96
97
98
99
100 /** 
101     Forward multicast message to our successor processors in the spanning tree. 
102     Uses CmiSyncListSend for delivery to this strategy's OneTimeMulticastStrategy::handleMessage method.
103 */
104 void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, bool rootPE) {
105   double start = CmiWallTimer();
106
107   envelope *env = UsrToEnv(multMsg);
108     
109   
110   /// The index into the PE list in the message
111   int myIndex = -10000; 
112   const int totalDestPEs = multMsg->nPes;
113   const int myPe = CkMyPe();
114   
115   // Find my index in the list of all destination PEs
116   if(rootPE){
117     CkAssert(CkMyPe() == multMsg->_cookie.get_pe());
118     myIndex = -1;
119   } else {
120     for (int i=0; i<totalDestPEs; ++i) {
121       if(multMsg->indicesCount[i].pe == myPe){
122         myIndex = i;
123         break;
124       }
125     }
126   }
127   
128   if(myIndex == -10000)
129     CkAbort("My PE was not found in the list of destination PEs in the ComlibMulticastMsg");
130   
131   int npes;
132   int *pelist = NULL;
133
134   if(totalDestPEs > 0) {
135     //CkPrintf("totalDestPEs = %d\n", totalDestPEs);
136     determineNextHopPEs(totalDestPEs, multMsg->indicesCount, myIndex, multMsg->_cookie.get_pe(), pelist, npes );
137   } else {
138     npes = 0;
139   }
140
141   if(npes == 0) {
142 #if DEBUG
143     CkPrintf("[%d] OneTimeMulticastStrategy::remoteMulticast is not forwarding to any other PEs\n", CkMyPe());
144 #endif
145     traceUserBracketEvent(10001, start, CmiWallTimer());
146     CmiFree(env);
147     return;
148   }
149   
150   //Collect Multicast Statistics
151   RECORD_SENDM_STATS(getInstance(), env->getTotalsize(), pelist, npes);
152   
153
154   CmiSetHandler(env, CkpvAccess(comlib_handler));
155   ((CmiMsgHeaderExt *) env)->stratid = getInstance();  
156   CkPackMessage(&env);
157
158   double middle = CmiWallTimer();
159
160   
161   // CkPrintf("[%d] before CmiSyncListSendAndFree env->event=%d\n", CkMyPe(), (int)env->getEvent());
162
163 #if SYNCLISTSENDANDFREE
164   CmiSyncListSendAndFree(npes, pelist, env->getTotalsize(), (char*)env);
165 #else
166
167   CkAssert(npes > 0);
168   CmiSyncListSend(npes, pelist, env->getTotalsize(), (char*)env);
169   
170   delete[] pelist;
171 #endif
172
173   double end = CmiWallTimer();
174   traceUserBracketEvent(10001, start, middle);
175   traceUserBracketEvent(10002, middle, end);
176   
177 }
178
179
180
181 /** 
182     Receive an incoming multicast message(sent from OneTimeMulticastStrategy::remoteMulticast).
183     Deliver the message to all local elements 
184 */
185 void OneTimeMulticastStrategy::handleMessage(void *msg){
186 #if DEBUG
187   //  CkPrintf("[%d] OneTimeMulticastStrategy::handleMessage\n", CkMyPe());
188 #endif
189   envelope *env = (envelope *)msg;
190   CkUnpackMessage(&env);
191   ComlibMulticastMsg* multMsg = (ComlibMulticastMsg*)EnvToUsr(env);
192   
193   // Don't use msg after this point. Instead use the unpacked env
194   
195   RECORD_RECV_STATS(getInstance(), env->getTotalsize(), env->getSrcPe()); // DOESN'T DO ANYTHING IN NEW COMLIB
196   
197   // Deliver to objects marked as local in the message
198   int localElems;
199   envelope *newenv;
200   CkArrayIndex *local_idx_list;  
201   sinfo.unpack(env, localElems, local_idx_list, newenv);
202   ComlibMulticastMsg *newmsg = (ComlibMulticastMsg *)EnvToUsr(newenv);  
203
204   //  CkPrintf("[%d] in OneTimeMulticastStrategy::handleMessage before  deliverToIndices newenv->event=%d\n", CkMyPe(), (int)newenv->getEvent());
205
206
207 #if SYNCLISTSENDANDFREE
208
209   // Deliver locally
210   deliverToIndices(newmsg, localElems, local_idx_list );
211   
212   // Forward on to other processors if necessary
213   remoteMulticast(multMsg, false);
214  
215 #else
216
217   // Forward on to other processors if necessary
218   remoteMulticast(multMsg, false);
219
220   // Deliver locally
221   deliverToIndices(newmsg, localElems, local_idx_list );
222   
223   // Finally delete the reference counted message because remoteMulticast does not do this.
224   CmiFree(multMsg);
225
226 #endif
227   
228 }
229
230
231
232
233 void OneTimeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes) {
234   if(myIndex==-1){
235     // We are at a root node of the spanning tree. 
236     // We will forward the message to all other PEs in the destination list.
237     npes = totalDestPEs;
238     
239     pelist = new int[npes];
240     for (int i=0; i<npes; ++i) {
241       pelist[i] = destPEs[i].pe;
242     }
243   } else {
244     // We are at a leaf node of the spanning tree. 
245     npes = 0;
246   }
247   
248 }
249
250
251 void OneTimeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes) {
252   const int myPe = CkMyPe();
253
254   if(myIndex == totalDestPEs-1){
255     // Final PE won't send to anyone
256     npes = 0;
257     return;
258   } else {
259     // All non-final PEs will send to next PE in list
260     npes = 1;
261     pelist = new int[1];
262     pelist[0] = destPEs[myIndex+1].pe;
263   }
264
265 }
266
267
268 void OneTimeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
269   const int myPe = CkMyPe();
270   
271   // The logical indices start at 0 = root node. Logical index i corresponds to the entry i+1 in the array of PEs in the message
272   
273   int sendLogicalIndexStart = degree*(myIndex+1) + 1;       // inclusive
274   int sendLogicalIndexEnd = sendLogicalIndexStart + degree - 1;   // inclusive
275   
276   if(sendLogicalIndexEnd-1 >= totalDestPEs){
277     sendLogicalIndexEnd = totalDestPEs;
278   }
279
280   int numSend = sendLogicalIndexEnd - sendLogicalIndexStart + 1;
281   if(numSend <= 0){
282     npes = 0;
283     return;
284   }
285  
286 #if DEBUG
287   if(numSend > 0)
288     CkPrintf("Tree logical index %d sending to logical %d to %d (totalDestPEs excluding root=%d)  numSend=%d\n",
289              myIndex+1, sendLogicalIndexStart, sendLogicalIndexEnd, totalDestPEs, numSend);
290 #endif
291
292   npes = numSend;
293   pelist = new int[npes];
294   
295   for(int i=0;i<numSend;i++){
296     CkAssert(sendLogicalIndexStart-1+i < totalDestPEs);
297     pelist[i] = destPEs[sendLogicalIndexStart-1+i].pe;
298 #if DEBUG
299     CkPrintf("Tree logical index %d sending to PE %d\n", myIndex+1, pelist[i]);
300 #endif
301     CkAssert(pelist[i] < CkNumPes());
302   }
303   
304 }
305
306
307 /** Find a unique representative PE for a node containing pe, with the restriction that the returned PE is in the list destPEs. */
308 int getFirstPeOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
309   int num;
310   int *nodePeList;
311   CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num);
312   
313   for(int i=0;i<num;i++){
314     // Scan destPEs for the pe
315     int p = nodePeList[i];
316     
317     for(int j=0;j<totalDestPEs;j++){
318       if(p == destPEs[j].pe){
319         // found the representative PE for the node that is in the destPEs list
320         return p;
321       }
322     }
323   }
324   
325   CkAbort("ERROR: Could not find an entry for pe in destPEs list.\n");
326   return -1;
327 }
328
329
330 /** Find a unique representative PE for a node containing pe, with the restriction that the returned PE is in the list destPEs. */
331 int getNthPeOnPhysicalNodeFromList(int n, int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
332   int num;
333   int *nodePeList;
334   CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num);
335   
336   int count = 0;
337   int lastFound = -1;
338   
339   // Foreach PE on this physical node
340   for(int i=0;i<num;i++){
341     int p = nodePeList[i];
342     
343     // Scan destPEs for the pe
344     for(int j=0;j<totalDestPEs;j++){
345       if(p == destPEs[j].pe){
346         lastFound = p;
347         if(count==n)
348           return p;
349         count++;
350       }
351     }
352   }
353   
354   if(lastFound != -1)
355     return lastFound;
356
357   CkAbort("ERROR: Could not find an entry for pe in destPEs list.\n");
358   return -1;
359 }
360
361
362 /** List all the PEs from the list that share the physical node */ 
363 vector<int> getPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){ 
364    
365   vector<int> result; 
366  
367   int num; 
368   int *nodePeList; 
369   CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num); 
370   
371   for(int i=0;i<num;i++){ 
372     // Scan destPEs for the pe 
373     int p = nodePeList[i]; 
374     for(int j=0;j<totalDestPEs;j++){ 
375       if(p == destPEs[j].pe){ 
376         // found the representative PE for the node that is in the
377         // destPEs list 
378         result.push_back(p); 
379         break; 
380       } 
381     } 
382   } 
383   
384   return result; 
385 }
386
387
388
389 /** List all the other PEs from the list that share the physical node */
390 vector<int> getOtherPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
391   
392   vector<int> result;
393
394   int num;
395   int *nodePeList;
396   CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num);
397   
398   for(int i=0;i<num;i++){
399     // Scan destPEs for the pe
400     int p = nodePeList[i];
401     if(p != pe){
402       for(int j=0;j<totalDestPEs;j++){
403         if(p == destPEs[j].pe){
404           // found the representative PE for the node that is in the destPEs list
405           result.push_back(p);
406           break;
407         }
408       }
409     }
410   }
411   
412   return result;
413 }
414
415
416 void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
417   const int myPe = CkMyPe();
418
419   set<int> nodePERepresentatives;
420   
421   // create a list of PEs, with one for each node to which the message must be sent
422   for(int i=0; i<totalDestPEs; i++){
423     int pe = destPEs[i].pe;
424     int representative = getFirstPeOnPhysicalNodeFromList(pe, totalDestPEs, destPEs);
425     nodePERepresentatives.insert(representative);    
426   }
427   
428   // Create an ordered list of PEs to send to, based upon the rootPE
429   // This should distribute load more evenly than the sorted list previously used
430   set<int>::iterator splitter = nodePERepresentatives.upper_bound(rootPE);
431   vector<int> nodePERepresentativesOrdered;
432   for(set<int>::iterator iter = splitter; iter!=nodePERepresentatives.end(); ++iter){
433     nodePERepresentativesOrdered.push_back(*iter);
434   }
435   for(set<int>::iterator iter = nodePERepresentatives.begin(); iter!=splitter; ++iter){
436     nodePERepresentativesOrdered.push_back(*iter);
437   }
438
439   CkAssert(nodePERepresentativesOrdered.size() == nodePERepresentatives.size());
440     
441   int numRepresentativePEs = nodePERepresentatives.size();
442   
443   int repForMyPe=-1;
444   if(myIndex != -1)
445     repForMyPe = getFirstPeOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
446   
447 #if DEBUG
448   CkPrintf("[%d] Multicasting to %d PEs on %d physical nodes  repForMyPe=%d\n", CkMyPe(), totalDestPEs, numRepresentativePEs, repForMyPe);
449   fflush(stdout);
450 #endif
451   
452   // If this PE is part of the multicast tree, then it should forward the message along
453   if(CkMyPe() == repForMyPe || myIndex == -1){
454     // I am an internal node in the multicast tree
455     
456     // flatten the nodePERepresentativesOrdered data structure
457     int *repPeList = new int[numRepresentativePEs];
458     int myRepIndex = -1;
459     int p=0;
460     for(vector<int>::iterator iter=nodePERepresentativesOrdered.begin(); iter != nodePERepresentativesOrdered.end(); iter++){
461       repPeList[p] = *iter;
462       if(*iter == repForMyPe)
463         myRepIndex = p;
464       p++;
465     }
466     CkAssert(myRepIndex >=0 || myIndex==-1);
467       
468     // The logical indices start at 0 = root node. Logical index i corresponds to the entry i+1 in the array of PEs in the message
469     int sendLogicalIndexStart = degree*(myRepIndex+1) + 1;       // inclusive
470     int sendLogicalIndexEnd = sendLogicalIndexStart + degree - 1;   // inclusive
471     
472     if(sendLogicalIndexEnd-1 >= numRepresentativePEs){
473       sendLogicalIndexEnd = numRepresentativePEs;
474     }
475     
476     int numSendTree = sendLogicalIndexEnd - sendLogicalIndexStart + 1;
477     if(numSendTree < 0)
478       numSendTree = 0;
479     
480     vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
481     int numSendLocal;
482     if(myIndex == -1)
483       numSendLocal = 0;
484     else 
485       numSendLocal = otherLocalPes.size();
486     
487     
488
489 #if DEBUG
490     CkPrintf("[%d] numSendTree=%d numSendLocal=%d sendLogicalIndexStart=%d sendLogicalIndexEnd=%d\n", CkMyPe(), numSendTree, numSendLocal,  sendLogicalIndexStart, sendLogicalIndexEnd);
491     fflush(stdout);
492 #endif
493
494     int numSend = numSendTree + numSendLocal;
495     if(numSend <= 0){
496       npes = 0;
497       return;
498     }
499     
500     npes = numSend;
501     pelist = new int[npes];
502   
503     for(int i=0;i<numSendTree;i++){
504       CkAssert(sendLogicalIndexStart-1+i < numRepresentativePEs);
505       pelist[i] = repPeList[sendLogicalIndexStart-1+i];
506       CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
507     }
508     
509     delete[] repPeList;
510     repPeList = NULL;
511
512     for(int i=0;i<numSendLocal;i++){
513       pelist[i+numSendTree] = otherLocalPes[i];
514       CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
515     }
516     
517     
518 #if DEBUG
519     char buf[1024];
520     sprintf(buf, "PE %d is sending to Remote Node PEs: ", CkMyPe() );
521     for(int i=0;i<numSend;i++){
522       if(i==numSendTree)
523         sprintf(buf+strlen(buf), " and Local To Node PEs: ", pelist[i]);
524
525       sprintf(buf+strlen(buf), "%d ", pelist[i]);
526     }    
527     CkPrintf("%s\n", buf);
528     fflush(stdout);
529 #endif
530         
531   } else {
532     // We are a leaf PE
533     npes = 0;
534     return;
535   }
536
537   
538   
539 }
540
541
542 void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
543   const int myPe = CkMyPe();
544
545   set<int> nodePERepresentatives;
546   
547   // create a list of PEs, with one for each node to which the message must be sent
548   for(int i=0; i<totalDestPEs; i++){
549     int pe = destPEs[i].pe;
550     int representative = getFirstPeOnPhysicalNodeFromList(pe, totalDestPEs, destPEs);
551     nodePERepresentatives.insert(representative);    
552   }
553
554    // Create an ordered list of PEs to send to, based upon the rootPE
555   // This should distribute load more evenly than the sorted list previously used
556   set<int>::iterator splitter = nodePERepresentatives.upper_bound(rootPE);
557   vector<int> nodePERepresentativesOrdered;
558   for(set<int>::iterator iter = splitter; iter!=nodePERepresentatives.end(); ++iter){
559     nodePERepresentativesOrdered.push_back(*iter);
560   }
561   for(set<int>::iterator iter = nodePERepresentatives.begin(); iter!=splitter; ++iter){
562     nodePERepresentativesOrdered.push_back(*iter);
563   }
564
565   CkAssert(nodePERepresentativesOrdered.size() == nodePERepresentatives.size());
566   int numRepresentativePEs = nodePERepresentatives.size();
567   
568   int repForMyPe=-1;
569   if(myIndex != -1)
570     repForMyPe = getFirstPeOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
571   
572 #if DEBUG
573   CkPrintf("[%d] Multicasting to %d PEs on %d physical nodes  repForMyPe=%d\n", CkMyPe(), totalDestPEs, numRepresentativePEs, repForMyPe);
574   fflush(stdout);
575 #endif
576   
577   // If this PE is part of the multicast tree, then it should forward the message along
578   if(CkMyPe() == repForMyPe || myIndex == -1){
579     // I am an internal node in the multicast tree
580     
581     // flatten the data structure for nodePERepresentatives
582     int *repPeList = new int[numRepresentativePEs];
583     int myRepIndex = -1;
584     int p=0;
585     for(vector<int>::iterator iter=nodePERepresentativesOrdered.begin(); iter != nodePERepresentativesOrdered.end(); iter++){
586       repPeList[p] = *iter;
587       if(*iter == repForMyPe)
588         myRepIndex = p;
589       p++;
590     }
591     CkAssert(myRepIndex >=0 || myIndex==-1);
592       
593     // The logical indices start at 0 = root node. Logical index i corresponds to the entry i+1 in the array of PEs in the message
594     int sendLogicalIndexStart = degree*(myRepIndex+1) + 1;       // inclusive
595     int sendLogicalIndexEnd = sendLogicalIndexStart + degree - 1;   // inclusive
596     
597     if(sendLogicalIndexEnd-1 >= numRepresentativePEs){
598       sendLogicalIndexEnd = numRepresentativePEs;
599     }
600     
601     int numSendTree = sendLogicalIndexEnd - sendLogicalIndexStart + 1;
602     if(numSendTree < 0)
603       numSendTree = 0;
604
605
606     // Send in a ring to the PEs on this node
607     vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
608     int numSendLocal = 0;
609     if(myIndex == -1)
610       numSendLocal = 0;
611     else {
612       if(otherLocalPes.size() > 0)
613         numSendLocal = 1;
614       else
615         numSendLocal = 0;
616     }
617     
618
619 #if DEBUG
620     CkPrintf("[%d] numSendTree=%d numSendLocal=%d sendLogicalIndexStart=%d sendLogicalIndexEnd=%d\n", CkMyPe(), numSendTree, numSendLocal,  sendLogicalIndexStart, sendLogicalIndexEnd);
621     fflush(stdout);
622 #endif
623
624     int numSend = numSendTree + numSendLocal;
625     if(numSend <= 0){
626       npes = 0;
627       return;
628     }
629     
630     npes = numSend;
631     pelist = new int[npes];
632   
633     for(int i=0;i<numSendTree;i++){
634       CkAssert(sendLogicalIndexStart-1+i < numRepresentativePEs);
635       pelist[i] = repPeList[sendLogicalIndexStart-1+i];
636       CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
637     }
638     
639     delete[] repPeList;
640     repPeList = NULL;
641
642     for(int i=0;i<numSendLocal;i++){
643       pelist[i+numSendTree] = otherLocalPes[i];
644       CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
645     }
646     
647     
648 #if DEBUG
649     char buf[1024];
650     sprintf(buf, "PE %d is sending to Remote Node PEs: ", CkMyPe() );
651     for(int i=0;i<numSend;i++){
652       if(i==numSendTree)
653         sprintf(buf+strlen(buf), " and Local To Node PEs: ", pelist[i]);
654
655       sprintf(buf+strlen(buf), "%d ", pelist[i]);
656     }    
657     CkPrintf("%s\n", buf);
658     fflush(stdout);
659 #endif
660         
661   } else {
662     // We are a leaf PE, so forward in a ring to the PEs on this node
663     const vector<int> otherLocalPes = getPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
664     
665     npes = 0;
666     pelist = new int[1];
667     
668     //    CkPrintf("[%d] otherLocalPes.size=%d\n", CkMyPe(), otherLocalPes.size() ); 
669     const int numOthers = otherLocalPes.size() ;
670     
671     for(int i=0;i<numOthers;i++){
672       if(otherLocalPes[i] == CkMyPe()){
673         // found me in the PE list for this node
674         if(i+1<otherLocalPes.size()){
675           // If we have a successor in the ring
676           pelist[0] = otherLocalPes[i+1];
677           npes = 1;
678         }
679       }
680     }
681     
682     
683 #if DEBUG
684     if(npes==0)
685       CkPrintf("[%d] At end of ring\n", CkMyPe() );
686     else
687       CkPrintf("[%d] sending along ring to %d\n", CkMyPe(), pelist[0] );
688     
689     fflush(stdout);
690 #endif
691     
692     
693   }
694   
695   
696   
697 }
698
699 // If min == 1 then this function finds the min else the max value in the array
700 // This function returns the index of the array that it found to be the max or the min
701 int OneTimeDimensionOrderedMulticastStrategy::findMinMaxArray(int min, int len, int *array, bool* notincluded, int value) {
702   int k = value;
703   int a = -1;
704   for (int j = 0; j < len; j++) {
705     if (notincluded[j]) continue;
706     if (min && array[j] < k) {
707       k = array[j];
708       a = j;
709     } else if (!min && array[j] > k) {
710       k = array[j];
711       a = j;
712     }
713   }
714   return a;
715 }
716
717 void OneTimeDimensionOrderedMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPe, int * &pelist, int &npes) {
718   const int myPe = CkMyPe();
719
720   set<int> nodePEReps;
721   
722   // create a list of PEs, with one for each node to which the message must be sent
723   for(int i=0; i<totalDestPEs; i++){
724     int pe = destPEs[i].pe;
725     CkAssert(pe != rootPe);
726     if (myPe == 0)
727       CkPrintf("destPE = %d\n", pe);
728     int rep = getFirstPeOnPhysicalNodeFromList(pe, totalDestPEs, destPEs);
729     nodePEReps.insert(rep);
730   }
731   
732   int numRepPEs = nodePEReps.size();
733   
734   int repForMyPe = -1;
735   if(myIndex != -1)
736     repForMyPe = getFirstPeOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
737   
738   map<int, set<int> > spanTree;
739
740   TopoManager tmgr;
741
742   int myX, myY, myZ, myT;
743   tmgr.rankToCoordinates(rootPe, myX, myY, myZ, myT);
744
745   map<int, int> peRef;
746   int *repPeRef = new int[numRepPEs+1];
747   int *repPeX = new int[numRepPEs+1];
748   int *repPeY = new int[numRepPEs+1];
749   int *repPeZ = new int[numRepPEs+1];
750
751   int i = 0, myRepIndex;
752
753   for (set<int>::iterator iter = nodePEReps.begin(); iter != nodePEReps.end(); ++iter) {
754       int pe = *iter;
755       repPeRef[i] = pe;
756       peRef[pe] = i;
757       int t; // ignore the 't' dimension (which PE on the node)
758       tmgr.rankToCoordinates(pe, repPeX[i], repPeY[i], repPeZ[i], t);
759       if (*iter == repForMyPe)
760           myRepIndex = i;
761       i++;
762   }
763
764   int t;
765   repPeRef[i] = rootPe;
766   peRef[rootPe] = i;
767   tmgr.rankToCoordinates(rootPe, repPeX[i], repPeY[i], repPeZ[i], t);
768
769   CkAssert(myRepIndex >= 0 || myIndex == -1);
770  
771   bool *destAdded = new bool[numRepPEs];
772
773   for (int i = 0; i < numRepPEs; i++)
774       destAdded[i] = false;
775
776   int mode = 0; // 0 = x-axis, 1 = y-axis, 2 = z-axis
777
778   spanTree[rootPe].insert(rootPe);
779
780   //CkPrintf("Starting to build the tree...\n");
781
782   while (spanTree.size() < numRepPEs+1) {
783       int k = 0;
784       for (int i = 0; i < numRepPEs; i++) {
785           if (destAdded[i])
786               k++;
787       }
788
789       //CkPrintf("size of destAdded = %d, numRepPEs = %d, spanTree.size() = %d\n", k, numRepPEs, spanTree.size());
790
791       for(map<int, set<int> >::iterator iter = spanTree.begin(); iter != spanTree.end(); ++iter) {
792           int pe = iter->first;
793           int iPe = peRef[pe];
794           if (mode % 4 == 0) {
795               // Move in the -x direction
796               int i1 = findMinMaxArray(1, numRepPEs, repPeX, destAdded, repPeX[iPe]);
797         
798               if (i1 != -1) {
799                   destAdded[i1] = true;
800                   spanTree[pe].insert(repPeRef[i1]);
801                   spanTree[repPeRef[i1]].insert(repPeRef[i1]);
802                   //CkPrintf("added to -x\n");
803               }
804
805               // Move in the +x direction
806               int i2 = findMinMaxArray(0, numRepPEs, repPeX, destAdded, repPeX[iPe]);
807                 
808               if (i2 != -1) {
809                   destAdded[i2] = true;
810                   spanTree[pe].insert(repPeRef[i2]);
811                   spanTree[repPeRef[i2]].insert(repPeRef[i2]);
812                   //CkPrintf("added to +x\n");
813               }
814           } else if (mode % 4 == 1) {
815               bool* notEqX = new bool[numRepPEs];
816               for (int i = 0; i < numRepPEs; i++) {
817                   notEqX[i] = destAdded[i];
818                   if (!destAdded[i] && repPeX[iPe] != repPeX[i])
819                       notEqX[i] = true;
820               }
821
822               // Move in the -y direction
823               int i1 = findMinMaxArray(1, numRepPEs, repPeY, notEqX, repPeY[iPe]);
824         
825               if (i1 != -1) {
826                   destAdded[i1] = true;
827                   spanTree[pe].insert(repPeRef[i1]);
828                   spanTree[repPeRef[i1]].insert(repPeRef[i1]);
829                   //CkPrintf("added to -y\n");
830               }
831
832               // Move in the +y direction
833               int i2 = findMinMaxArray(0, numRepPEs, repPeY, notEqX, repPeY[iPe]);
834                 
835               if (i2 != -1) {
836                   destAdded[i2] = true;
837                   spanTree[pe].insert(repPeRef[i2]);
838                   spanTree[repPeRef[i2]].insert(repPeRef[i2]);
839                   //CkPrintf("added to +y\n");
840               }
841
842               delete[] notEqX;
843           } else if (mode % 4 == 2) {
844               bool* notEqXY = new bool[numRepPEs];
845               for (int i = 0; i < numRepPEs; i++) {
846                   notEqXY[i] = destAdded[i];
847                   if (!destAdded[i] && (repPeX[iPe] != repPeX[i] || repPeY[iPe] != repPeY[i]))
848                       notEqXY[i] = true;
849               }
850
851               // Move in the -z direction
852               int i1 = findMinMaxArray(1, numRepPEs, repPeZ, notEqXY, repPeZ[iPe]);
853         
854               if (i1 != -1) {
855                   destAdded[i1] = true;
856                   spanTree[pe].insert(repPeRef[i1]);
857                   spanTree[repPeRef[i1]].insert(repPeRef[i1]);
858                   //CkPrintf("added to -z\n");
859               }
860
861               // Move in the +z direction
862               int i2 = findMinMaxArray(0, numRepPEs, repPeZ, notEqXY, repPeZ[iPe]);
863                 
864               if (i2 != -1) {
865                   destAdded[i2] = true;
866                   spanTree[pe].insert(repPeRef[i2]);
867                   spanTree[repPeRef[i2]].insert(repPeRef[i2]);
868                   //CkPrintf("added to +z\n");
869               }
870
871               delete[] notEqXY;
872           }
873       }
874       mode++;
875   }
876
877   /*CkPrintf("Finished creating spanning tree\n");*/
878
879   static bool firstTime = true;
880
881   if (myPe == 0 && firstTime) {
882       firstTime = false;
883       for(map<int, set<int> >::iterator iter = spanTree.begin(); iter != spanTree.end(); ++iter) {
884           CkPrintf("Map %d to: ", iter->first);
885           for(set<int>::iterator iter2 = iter->second.begin(); iter2 != iter->second.end(); ++iter2) {
886               CkPrintf("%d, ", *iter2);
887           }
888           CkPrintf("\n");
889       }
890   }
891
892   // Send to local PEs
893   vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
894   int numSendLocal = otherLocalPes.size();
895
896   int numSend = spanTree[myPe].size() > 0 ? spanTree[myPe].size()-1 + numSendLocal : numSendLocal;
897     
898   if(numSend <= 0) {
899       npes = 0;
900       return;
901   }
902     
903   //CkPrintf("Sending to %d processors based on tree + local nodes\n", numSend);
904
905   npes = numSend;
906   pelist = new int[npes];
907   
908   i = 0;
909
910   for (set<int>::iterator iter = spanTree[myPe].begin(); iter != spanTree[myPe].end(); ++iter) {
911       if (*iter != myPe) {
912           pelist[i] = *iter;
913           i++;
914       }
915   }
916
917   for(int j = 0; j < numSendLocal; j++){
918       pelist[i] = otherLocalPes[j];
919       i++;
920   }
921 }
922
923 #include "spanningTreeStrategy.h"
924
925 using namespace topo;
926
927 void OneTimeTopoTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes)
928 {
929     /// Initialize
930     npes = 0; 
931     int myPE = (myIndex<0)? rootPE : destPEs[myIndex].pe;
932
933     /// Create a container of SpanningTreeVertex-es from the input list of PEs (include the root PE too)
934     std::vector<topo::SpanningTreeVertex> tree;
935     tree.push_back( topo::SpanningTreeVertex(rootPE) );
936     for (int i=0; i< totalDestPEs; i++)
937         tree.push_back( topo::SpanningTreeVertex(destPEs[i].pe) );
938
939     /// Build the complete spanning tree
940     topo::buildSpanningTree(tree.begin(),tree.end(),degree);
941
942     /// Identify this PE in the tree and find immediate children
943     int peIdx = -1;
944     bool noMatchFound = true;
945     while ( (++peIdx < tree.size()) && noMatchFound)
946     {
947         if (myPE == tree[peIdx].id)
948         {
949             /// Add immediate children to pelist and set npes accordingly
950             npes   = tree[peIdx].childIndex.size();
951             pelist = new int[npes];
952             for (int i=0; i< npes; i++)
953                 pelist[i] = tree[ peIdx + tree[peIdx].childIndex[i] ].id; ///< child indices are relative distances from the parent in the container
954             noMatchFound = false;
955         }
956     }
957 }
958
959 /*@}*/