Fixing performance problems with OneTimeMulticast algorithms.
authorIsaac Dooley <idooley2@illinois.edu>
Wed, 26 Aug 2009 22:30:20 +0000 (22:30 +0000)
committerIsaac Dooley <idooley2@illinois.edu>
Wed, 26 Aug 2009 22:30:20 +0000 (22:30 +0000)
src/ck-com/ComlibManager.ci
src/ck-com/OneTimeMulticastStrategy.C
src/ck-com/OneTimeMulticastStrategy.h

index b6b34a78fafcf0832a7310ea57ac42301ffa7c9f..5035defec524901c8a103600d100b74ac38e0ee6 100644 (file)
@@ -49,6 +49,7 @@ module comlib {
   PUPable OneTimeRingMulticastStrategy;
   PUPable OneTimeNodeTreeMulticastStrategy;
   PUPable OneTimeNodeTreeRingMulticastStrategy;
+  PUPable OneTimeDimensionOrderedMulticastStrategy;
 
   //PUPable CharmStrategy;
   //PUPable MessageHolder;
index 7a46dac1c3e52b545f0600797b5d74313828027c..278ce7bb874f024d160fe7647785ad83065ec348 100644 (file)
 #include <string>
 #include <set>
 #include <vector>
+#include <list>
 
 //#define DEBUG 1
 
+using std::list;
+using std::set;
+using std::vector;
+
+
 CkpvExtern(CkGroupID, cmgrID);
 
 OneTimeMulticastStrategy::OneTimeMulticastStrategy()
@@ -86,7 +92,7 @@ void OneTimeMulticastStrategy::localMulticast(CharmMessageHolder *cmsg) {
 
 /** 
     Forward multicast message to our successor processors in the spanning tree. 
-    Uses CmiSyncListSendAndFree for delivery to this strategy's OneTimeMulticastStrategy::handleMessage method.
+    Uses CmiSyncListSend for delivery to this strategy's OneTimeMulticastStrategy::handleMessage method.
 */
 void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, bool rootPE) {
   double start = CmiWallTimer();
@@ -101,6 +107,7 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   
   // Find my index in the list of all destination PEs
   if(rootPE){
+    CkAssert(CkMyPe() == multMsg->_cookie.pe);
     myIndex = -1;
   } else {
     for (int i=0; i<totalDestPEs; ++i) {
@@ -118,7 +125,7 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   int *pelist = NULL;
 
   if(totalDestPEs > 0)
-    determineNextHopPEs(totalDestPEs, multMsg->indicesCount, myIndex, pelist, npes );
+    determineNextHopPEs(totalDestPEs, multMsg->indicesCount, myIndex, multMsg->_cookie.pe, pelist, npes );
   else {
     npes = 0;
   }
@@ -147,7 +154,7 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
 
 
   CkAssert(npes > 0);
-  CmiSyncListSendAndFree(npes, pelist, env->getTotalsize(), (char*)env);
+  CmiSyncListSend(npes, pelist, env->getTotalsize(), (char*)env);
   
   delete[] pelist;
 
@@ -168,14 +175,7 @@ void OneTimeMulticastStrategy::handleMessage(void *msg){
   //  CkPrintf("[%d] OneTimeMulticastStrategy::handleMessage\n", CkMyPe());
 #endif
   envelope *env = (envelope *)msg;
-  // CkPrintf("[%d] in OneTimeMulticastStrategy::handleMessage env->event=%d\n", CkMyPe(), (int)env->getEvent());
-  
   CkUnpackMessage(&env);
-  
-  // CkPrintf("[%d] in OneTimeMulticastStrategy::handleMessage after CkUnpackMessage env->event=%d\n", CkMyPe(), (int)env->getEvent());
-  
-
-
   ComlibMulticastMsg* multMsg = (ComlibMulticastMsg*)EnvToUsr(env);
   
   // Don't use msg after this point. Instead use the unpacked env
@@ -191,17 +191,21 @@ void OneTimeMulticastStrategy::handleMessage(void *msg){
 
   //  CkPrintf("[%d] in OneTimeMulticastStrategy::handleMessage before  deliverToIndices newenv->event=%d\n", CkMyPe(), (int)newenv->getEvent());
 
-  deliverToIndices(newmsg, localElems, local_idx_list );
-  
   // Forward on to other processors if necessary
   remoteMulticast(multMsg, false);
 
+  // Deliver locally
+  deliverToIndices(newmsg, localElems, local_idx_list );
+  
+  // Finally delete the reference counted message because remoteMulticast does not do this.
+  CmiFree(multMsg);
+  
 }
 
 
 
 
-void OneTimeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes) {
+void OneTimeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes) {
   if(myIndex==-1){
     // We are at a root node of the spanning tree. 
     // We will forward the message to all other PEs in the destination list.
@@ -219,7 +223,7 @@ void OneTimeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const
 }
 
 
-void OneTimeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes) {
+void OneTimeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes) {
   const int myPe = CkMyPe();
 
   if(myIndex == totalDestPEs-1){
@@ -236,7 +240,7 @@ void OneTimeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, c
 }
 
 
-void OneTimeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes){
+void OneTimeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
   const int myPe = CkMyPe();
   
   // 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
@@ -331,9 +335,9 @@ int getNthPeOnPhysicalNodeFromList(int n, int pe, const int totalDestPEs, const
 
 
 /** List all the PEs from the list that share the physical node */ 
-std::vector<int> getPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){ 
+vector<int> getPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){ 
    
-  std::vector<int> result; 
+  vector<int> result; 
  
   int num; 
   int *nodePeList; 
@@ -358,9 +362,9 @@ std::vector<int> getPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, co
 
 
 /** List all the other PEs from the list that share the physical node */
-std::vector<int> getOtherPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
+vector<int> getOtherPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
   
-  std::vector<int> result;
+  vector<int> result;
 
   int num;
   int *nodePeList;
@@ -384,10 +388,10 @@ std::vector<int> getOtherPesOnPhysicalNodeFromList(int pe, const int totalDestPE
 }
 
 
-void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes){
+void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
   const int myPe = CkMyPe();
 
-  std::set<int> nodePERepresentatives;
+  set<int> nodePERepresentatives;
   
   // create a list of PEs, with one for each node to which the message must be sent
   for(int i=0; i<totalDestPEs; i++){
@@ -396,6 +400,19 @@ void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPE
     nodePERepresentatives.insert(representative);    
   }
   
+  // Create an ordered list of PEs to send to, based upon the rootPE
+  // This should distribute load more evenly than the sorted list previously used
+  set<int>::iterator splitter = nodePERepresentatives.upper_bound(rootPE);
+  vector<int> nodePERepresentativesOrdered;
+  for(set<int>::iterator iter = splitter; iter!=nodePERepresentatives.end(); ++iter){
+    nodePERepresentativesOrdered.push_back(*iter);
+  }
+  for(set<int>::iterator iter = nodePERepresentatives.begin(); iter!=splitter; ++iter){
+    nodePERepresentativesOrdered.push_back(*iter);
+  }
+
+  CkAssert(nodePERepresentativesOrdered.size() == nodePERepresentatives.size());
+    
   int numRepresentativePEs = nodePERepresentatives.size();
   
   int repForMyPe=-1;
@@ -411,12 +428,11 @@ void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPE
   if(CkMyPe() == repForMyPe || myIndex == -1){
     // I am an internal node in the multicast tree
     
-    // flatten the data structure for nodePERepresentatives
+    // flatten the nodePERepresentativesOrdered data structure
     int *repPeList = new int[numRepresentativePEs];
     int myRepIndex = -1;
-    std::set<int>::iterator iter;
     int p=0;
-    for(iter=nodePERepresentatives.begin(); iter != nodePERepresentatives.end(); iter++){
+    for(vector<int>::iterator iter=nodePERepresentativesOrdered.begin(); iter != nodePERepresentativesOrdered.end(); iter++){
       repPeList[p] = *iter;
       if(*iter == repForMyPe)
        myRepIndex = p;
@@ -436,7 +452,7 @@ void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPE
     if(numSendTree < 0)
       numSendTree = 0;
     
-    std::vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+    vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
     int numSendLocal;
     if(myIndex == -1)
       numSendLocal = 0;
@@ -498,10 +514,10 @@ void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPE
 }
 
 
-void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes){
+void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
   const int myPe = CkMyPe();
 
-  std::set<int> nodePERepresentatives;
+  set<int> nodePERepresentatives;
   
   // create a list of PEs, with one for each node to which the message must be sent
   for(int i=0; i<totalDestPEs; i++){
@@ -509,7 +525,19 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
     int representative = getFirstPeOnPhysicalNodeFromList(pe, totalDestPEs, destPEs);
     nodePERepresentatives.insert(representative);    
   }
-  
+
+   // Create an ordered list of PEs to send to, based upon the rootPE
+  // This should distribute load more evenly than the sorted list previously used
+  set<int>::iterator splitter = nodePERepresentatives.upper_bound(rootPE);
+  vector<int> nodePERepresentativesOrdered;
+  for(set<int>::iterator iter = splitter; iter!=nodePERepresentatives.end(); ++iter){
+    nodePERepresentativesOrdered.push_back(*iter);
+  }
+  for(set<int>::iterator iter = nodePERepresentatives.begin(); iter!=splitter; ++iter){
+    nodePERepresentativesOrdered.push_back(*iter);
+  }
+
+  CkAssert(nodePERepresentativesOrdered.size() == nodePERepresentatives.size());
   int numRepresentativePEs = nodePERepresentatives.size();
   
   int repForMyPe=-1;
@@ -528,9 +556,8 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
     // flatten the data structure for nodePERepresentatives
     int *repPeList = new int[numRepresentativePEs];
     int myRepIndex = -1;
-    std::set<int>::iterator iter;
     int p=0;
-    for(iter=nodePERepresentatives.begin(); iter != nodePERepresentatives.end(); iter++){
+    for(vector<int>::iterator iter=nodePERepresentativesOrdered.begin(); iter != nodePERepresentativesOrdered.end(); iter++){
       repPeList[p] = *iter;
       if(*iter == repForMyPe)
        myRepIndex = p;
@@ -552,7 +579,7 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
 
 
     // Send in a ring to the PEs on this node
-    std::vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+    vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
     int numSendLocal = 0;
     if(myIndex == -1)
       numSendLocal = 0;
@@ -608,7 +635,7 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
         
   } else {
     // We are a leaf PE, so forward in a ring to the PEs on this node
-    const std::vector<int> otherLocalPes = getPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+    const vector<int> otherLocalPes = getPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
     
     npes = 0;
     pelist = new int[1];
@@ -644,4 +671,216 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
   
 }
 
+
+
+
+
+
+
+
+void OneTimeDimensionOrderedMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes){
+ //  const int myPe = CkMyPe();
+
+//   set<int> nodePERepresentatives;
+  
+//   // create a list of PEs, with one for each node to which the message must be sent
+//   for(int i=0; i<totalDestPEs; i++){
+//     int pe = destPEs[i].pe;
+//     int representative = getFirstPeOnPhysicalNodeFromList(pe, totalDestPEs, destPEs);
+//     nodePERepresentatives.insert(representative);    
+//   }
+  
+//   int numRepresentativePEs = nodePERepresentatives.size();
+  
+//   int repForMyPe=-1;
+//   if(myIndex != -1)
+//     repForMyPe = getFirstPeOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+  
+// #if DEBUG
+//   CkPrintf("[%d] Multicasting to %d PEs on %d physical nodes  repForMyPe=%d\n", CkMyPe(), totalDestPEs, numRepresentativePEs, repForMyPe);
+//   fflush(stdout);
+// #endif
+  
+//   // If this PE is part of the multicast tree, then it should forward the message along
+//   if(CkMyPe() == repForMyPe || myIndex == -1){
+//     // I am an internal node in the multicast tree
+
+//     TopoManager tmgr;
+    
+//     // flatten the data structure for nodePERepresentatives
+//     int *repPeList = new int[numRepresentativePEs];
+//     bool *inTreeYet = new bool[numRepresentativePEs];
+//     int *repPeTopoX = new int[numRepresentativePEs];
+//     int *repPeTopoY = new int[numRepresentativePEs];
+//     int *repPeTopoZ = new int[numRepresentativePEs];
+
+//     set<int> xcoords;
+
+//     int myX, myY, myZ, myT;
+//     int rootX, rootY, rootZ, rootT;
+//     tmgr->rankToCoordinates(CkMyPe(), myX, myY, myZ, myT);        
+//     tmgr->rankToCoordinates(CkMyPe(), rootX, rootY, rootZ, rootT);        
+
+//     int myRepIndex = -1;
+//     set<int>::iterator iter;
+//     int p=0;
+//     for(iter=nodePERepresentatives.begin(); iter != nodePERepresentatives.end(); iter++){
+//       int pe =  *iter;
+//       repPeList[p] = pe;
+//       inTreeYet[p] = false;
+//       int t; // ignore the 't' dimension (which PE on the node)
+//       tmgr->rankToCoordinates(pe, repPeTopoX[p], repPeTopoY[p], repPeTopoZ[p], t);     
+//       xcoords.insert(repPeTopoX[p]);
+//       if(*iter == repForMyPe)
+//     myRepIndex = p;
+//       p++;
+//     }
+//     CkAssert(myRepIndex >=0 || myIndex==-1);
+    
+
+//     // Holds the spanning tree as we build it. It maps from index in the repPeList to sets of indices for repPeList
+//     map<int, set<int> > spanningTreeChildren;
+
+//     //---------------------------------------------------------------------------------------------
+//     // Determine the children of the root of the multicast tree
+//     int nearestXp = 100000;
+//     int nearestXpidx = -1;
+//     int nearestXm = -100000;
+//     int nearestXmidx = -1;
+
+//     for(int i=0; i<numRepresentativePEs; i++){
+//       // Find the nearest +x neighbor
+//       if(repPeTopoX[i] > rootX && repPeTopoX[i] < nearestXp){
+//     nearestXp = repPeTopoX[i] ;
+//     nearestXpidx = i;
+//       }
+      
+//       // Find the nearest -x neighbor
+//       if(repPeTopoX[i] < rootX && repPeTopoX[i] > nearestXm){
+//     nearestXm = repPeTopoX[i] ;
+//     nearestXmidx = i;
+//       }    
+      
+//     //   // send to some destinations with same X coordinate (just one per Y coordinate)
+// //       if(repPeTopoX == rootX){
+// //  set<int>::iterator iter;
+// //  bool found = false;
+// //  for(iter = spanningTreeChildren[-1].begin(); iter != spanningTreeChildren[-1].end(); ++iter){
+// //    iterYcoord = repPeTopoY[*iter];
+// //    if(iterYcoord == repPeTopoY[i]){
+// //      found = true;
+// //      break;
+// //    } 
+// //  }
+// //  if(! found) {
+// //    // haven't seen this Y coordinate yet
+// //    spanningTreeChildren[-1].insert(i);
+// //    inTreeYet[i] = true;
+// //  }
+// //       }
+//     }
+    
+    
+//     // The root sends to nearest +x neighbor
+//     if(nearestXpidx != -1){
+//       spanningTreeChildren[-1].insert(nearestXpidx);
+//       inTreeYet[nearestXpidx] = true;
+//     }
+    
+    
+//     // The root sends to nearest -x neighbor
+//     if(nearestXpidx != -1){
+//       spanningTreeChildren[-1].insert(nearestXpidx);
+//       inTreeYet[nearestXpidx] = true;
+//     }
+    
+    
+//     //---------------------------------------------------------------------------------------------
+//     // Make sure we span all X coordinates 
+    
+    
+    
+    
+
+
+
+
+
+    
+    
+   
+//     int numSendTree = 1;
+//     if(numSendTree < 0)
+//       numSendTree = 0;
+    
+//     vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+//     int numSendLocal;
+//     if(myIndex == -1)
+//       numSendLocal = 0;
+//     else 
+//       numSendLocal = otherLocalPes.size();
+    
+//     int numSend = numSendTree + numSendLocal;
+//     if(numSend <= 0){
+//       npes = 0;
+//       return;
+//     }
+    
+//     npes = numSend;
+//     pelist = new int[npes];
+  
+//     for(int i=0;i<numSendTree;i++){
+//       CkAssert(sendLogicalIndexStart-1+i < numRepresentativePEs);
+//       pelist[i] = repPeList[sendLogicalIndexStart-1+i];
+//       CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
+//     }
+    
+//     delete[] repPeList;
+//     delete[] repPeTopoX;
+//     delete[] repPeTopoY;
+//     delete[] repPeTopoZ;
+//     repPeList = NULL;
+
+//     for(int i=0;i<numSendLocal;i++){
+//       pelist[i+numSendTree] = otherLocalPes[i];
+//       CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
+//     }
+    
+// #if 1
+//     char buf[1024];
+//     sprintf(buf, "PE %d is sending to Remote Node PEs: ", CkMyPe() );
+//     for(int i=0;i<numSend;i++){
+//       if(i==numSendTree)
+//     sprintf(buf+strlen(buf), " and Local To Node PEs: ", pelist[i]);
+
+//       sprintf(buf+strlen(buf), "%d ", pelist[i]);
+//     }    
+//     CkPrintf("%s\n", buf);
+//     fflush(stdout);
+// #endif
+        
+//   } else {
+//     // We are a leaf PE
+//     npes = 0;
+//     return;
+//   }
+
+  
+  
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
 /*@}*/
index 95c8056e10f3e9ce756b08a149d1a3ba1a0e6193..5931df63a86d27c7e5a38f50b7f0fa68d8ccf969 100644 (file)
@@ -54,12 +54,13 @@ class OneTimeMulticastStrategy: public Strategy, public CharmStrategy {
       @param [in] totalDestPEs The number of destination PEs to whom the message needs to be sent. This will always be > 0.
       @param [in] destPEs The list of PEs that eventually will be sent the message.
       @param [in] myIndex The index into destPEs for this PE.
-
+      @param [in] rootPE The PE that created the multicast (is not listed in destPEs).
+      
       @param [out] pelist A list of PEs to which the message will be sent after this function returns. This function allocates the array with new. The caller will free it with delete[] if npes>0.
       @param [out] npes The size of pelist
 
   */
-  virtual void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes );
+  virtual void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE , int * &pelist, int &npes);
 
     OneTimeMulticastStrategy(CkMigrateMessage *m): Strategy(m), CharmStrategy(m){}
   
@@ -88,7 +89,7 @@ class OneTimeMulticastStrategy: public Strategy, public CharmStrategy {
 class OneTimeRingMulticastStrategy: public OneTimeMulticastStrategy {
   
  public:
-  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes );
+  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE , int * &pelist, int &npes);
 
  OneTimeRingMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}
  OneTimeRingMulticastStrategy(): OneTimeMulticastStrategy() {}
@@ -111,7 +112,7 @@ class OneTimeTreeMulticastStrategy: public OneTimeMulticastStrategy {
   
  public:
   
-  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes );
+  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes);
   
  OneTimeTreeMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}
 
@@ -130,6 +131,28 @@ class OneTimeTreeMulticastStrategy: public OneTimeMulticastStrategy {
 
 
 
+/**
+   A strategy that does dimension ordered sending of messages. This may result in lower contention for torus networks than a topology oblivious tree.
+*/
+class OneTimeDimensionOrderedMulticastStrategy: public OneTimeMulticastStrategy {
+ public:
+  
+  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes);
+  
+ OneTimeDimensionOrderedMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}
+
+  /** Create a strategy with specified branching factor(which defaults to 4) */
+ OneTimeDimensionOrderedMulticastStrategy(): OneTimeMulticastStrategy() {}
+
+  ~OneTimeDimensionOrderedMulticastStrategy() {}
+  
+  void pup(PUP::er &p){ 
+    OneTimeMulticastStrategy::pup(p); 
+  }
+  
+  PUPable_decl(OneTimeDimensionOrderedMulticastStrategy);
+};
+
 
 
 
@@ -142,7 +165,7 @@ class OneTimeNodeTreeMulticastStrategy: public OneTimeMulticastStrategy {
   
  public:
   
-  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes );
+  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes);
   
  OneTimeNodeTreeMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}
   
@@ -170,7 +193,7 @@ class OneTimeNodeTreeRingMulticastStrategy: public OneTimeMulticastStrategy {
   
  public:
   
-  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes );
+  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes);
   
  OneTimeNodeTreeRingMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}