Adding a new node aware multicast strategy that sends to PEs within a node along...
authorIsaac Dooley <idooley2@illinois.edu>
Thu, 2 Jul 2009 21:08:25 +0000 (21:08 +0000)
committerIsaac Dooley <idooley2@illinois.edu>
Thu, 2 Jul 2009 21:08:25 +0000 (21:08 +0000)
src/ck-com/ComlibManager.ci
src/ck-com/OneTimeMulticastStrategy.C
src/ck-com/OneTimeMulticastStrategy.h

index 2e9aacbcb3645f6222d1c78289c9b0721322cc64..e33d9bbd87a2cd1ec33b5b2b8018a2e1742fdf83 100644 (file)
@@ -48,6 +48,7 @@ module comlib {
   PUPable OneTimeTreeMulticastStrategy;
   PUPable OneTimeRingMulticastStrategy;
   PUPable OneTimeNodeTreeMulticastStrategy;
+  PUPable OneTimeNodeTreeRingMulticastStrategy;
 
   //PUPable CharmStrategy;
   //PUPable MessageHolder;
index 761b7ec75e1bdcf9bab915d97f23e42a2c9116ea..ff6cd5a8c52cb7cd75b676d4d2541e12f9284b60 100644 (file)
@@ -44,7 +44,7 @@ void OneTimeMulticastStrategy::insertMessage(CharmMessageHolder *cmsg){
   // Create a multicast message containing all information about remote destination objects 
   int needSort = 0;
   ComlibMulticastMsg * multMsg = sinfo.getNewMulticastMessage(cmsg, needSort, getInstance());
-  
+    
   // local multicast will re-extract a list of local destination objects (FIXME to make this more efficient)
   localMulticast(cmsg);
   
@@ -122,6 +122,9 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   ((CmiMsgHeaderBasic *) env)->stratid = getInstance();  
   CkPackMessage(&env);
 
+  double middle = CmiWallTimer();
+
+
   //Collect Multicast Statistics
   RECORD_SENDM_STATS(getInstance(), env->getTotalsize(), pelist, npes);
   
@@ -129,8 +132,11 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   CmiSyncListSendAndFree(npes, pelist, env->getTotalsize(), (char*)env);
   
   delete[] pelist;
-  traceUserBracketEvent(10001, start, CmiWallTimer());
 
+  double end = CmiWallTimer();
+  traceUserBracketEvent(10001, start, middle);
+  traceUserBracketEvent(10002, middle, end);
+  
 }
 
 
@@ -265,6 +271,38 @@ int getFirstPeOnPhysicalNodeFromList(int pe, const int totalDestPEs, const Comli
 }
 
 
+/** Find a unique representative PE for a node containing pe, with the restriction that the returned PE is in the list destPEs. */
+int getNthPeOnPhysicalNodeFromList(int n, int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
+  int num;
+  int *nodePeList;
+  CmiGetPesOnPhysicalNode(pe, &nodePeList, &num);
+  
+  int count = 0;
+  int lastFound = -1;
+  
+  // Foreach PE on this physical node
+  for(int i=0;i<num;i++){
+    int p = nodePeList[i];
+    
+    // Scan destPEs for the pe
+    for(int j=0;j<totalDestPEs;j++){
+      if(p == destPEs[j].pe){
+       lastFound = p;
+       if(count==n)
+         return p;
+       count++;
+      }
+    }
+  }
+  
+  if(lastFound != -1)
+    return lastFound;
+
+  CkAbort("ERROR: Could not find an entry for pe in destPEs list.\n");
+  return -1;
+}
+
+
 
 /** 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){
@@ -407,5 +445,147 @@ void OneTimeNodeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPE
 }
 
 
+void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes){
+  const int myPe = CkMyPe();
+
+  std::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
+    
+    // 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++){
+      repPeList[p] = *iter;
+      if(*iter == repForMyPe)
+       myRepIndex = p;
+      p++;
+    }
+    CkAssert(myRepIndex >=0 || myIndex==-1);
+      
+    // 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
+    int sendLogicalIndexStart = degree*(myRepIndex+1) + 1;       // inclusive
+    int sendLogicalIndexEnd = sendLogicalIndexStart + degree - 1;   // inclusive
+    
+    if(sendLogicalIndexEnd-1 >= numRepresentativePEs){
+      sendLogicalIndexEnd = numRepresentativePEs;
+    }
+    
+    int numSendTree = sendLogicalIndexEnd - sendLogicalIndexStart + 1;
+    if(numSendTree < 0)
+      numSendTree = 0;
+
+
+    // Send in a ring to the PEs on this node
+    std::vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+    int numSendLocal = 0;
+    if(myIndex == -1)
+      numSendLocal = 0;
+    else {
+      if(otherLocalPes.size() > 0)
+       numSendLocal = 1;
+      else
+       numSendLocal = 0;
+    }
+    
+
+#if DEBUG
+    CkPrintf("[%d] numSendTree=%d numSendLocal=%d sendLogicalIndexStart=%d sendLogicalIndexEnd=%d\n", CkMyPe(), numSendTree, numSendLocal,  sendLogicalIndexStart, sendLogicalIndexEnd);
+    fflush(stdout);
+#endif
+
+    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;
+    repPeList = NULL;
+
+    for(int i=0;i<numSendLocal;i++){
+      pelist[i+numSendTree] = otherLocalPes[i];
+      CkAssert(pelist[i] < CkNumPes() && pelist[i] >= 0);
+    }
+    
+    
+#if DEBUG
+    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, so forward in a ring to the PEs on this node
+    const std::vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+    
+    npes = 0;
+    pelist = new int[1];
+    
+    for(int i=0;i<otherLocalPes.size();i++){
+      if(otherLocalPes[i] == CkMyPe()){
+       // found me in the PE list for this node
+       if(i+1<otherLocalPes.size()){
+         // If we have a successor in the ring
+         pelist[0] = otherLocalPes[i+1];
+         npes = 1;
+       }
+      }
+    }
+     
+
+#if 1
+    if(npes==0)
+      CkPrintf("[%d] At end of ring", CkMyPe() );
+    else
+      CkPrintf("[%d] sending along ring to %d\n", CkMyPe(), pelist[0] );
+    
+    fflush(stdout);
+#endif
+
+
+  }
+
+  
+  
+}
 
 /*@}*/
index 90782a2ca04c32410871ad257413a89c7ebf11b1..8cbf6a344d447a33c3887320e563842197270f4c 100644 (file)
@@ -130,7 +130,7 @@ class OneTimeTreeMulticastStrategy: public OneTimeMulticastStrategy {
 
 
 /**
-   A node-aware strategy that sends along a node-based tree with user specified branching factor.
+   A node-aware strategy that sends along a node-based tree with user specified branching factor. Once the message reaches the PE representative for each node, it is forwarded from the PE to all other destination PEs on the node. This strategy can result in imbalanced loads. The PEs along the tree have higher load than the other PEs.
 */
 class OneTimeNodeTreeMulticastStrategy: public OneTimeMulticastStrategy {
  private:
@@ -157,6 +157,35 @@ class OneTimeNodeTreeMulticastStrategy: public OneTimeMulticastStrategy {
 
 
 
+/**
+   A node-aware strategy that sends along a node-based tree with user specified branching factor. Once the message arrives at the first PE on the node, it is forwarded to the other PEs on the node through a ring.
+*/
+class OneTimeNodeTreeRingMulticastStrategy: public OneTimeMulticastStrategy {
+ private:
+  int degree;
+  
+ public:
+  
+  void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, int * &pelist, int &npes );
+  
+ OneTimeNodeTreeRingMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}
+  
+  /** Create a strategy with specified branching factor(which defaults to 4) */
+ OneTimeNodeTreeRingMulticastStrategy(int treeDegree=4): OneTimeMulticastStrategy(), degree(treeDegree) {}
+  
+  ~OneTimeNodeTreeRingMulticastStrategy() {}
+  
+  void pup(PUP::er &p){ 
+    OneTimeMulticastStrategy::pup(p); 
+    p | degree;
+  }
+  
+  PUPable_decl(OneTimeNodeTreeRingMulticastStrategy);
+};
+
+
+
+
 
 #endif