doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-com / OneTimeMulticastStrategy.C
index 278ce7bb874f024d160fe7647785ad83065ec348..d7a0882e5948f357f37c707c38d5296de1dca59e 100644 (file)
@@ -7,16 +7,22 @@
 
 
 #include "OneTimeMulticastStrategy.h"
+#include "TopoManager.h"
 #include <string>
 #include <set>
 #include <vector>
 #include <list>
+#include <map>
 
 //#define DEBUG 1
 
 using std::list;
 using std::set;
 using std::vector;
+using std::map;
+
+/// @note: There is some bug that is preventing us from using CmiSyncListSend. 
+#define SYNCLISTSENDANDFREE 1
 
 
 CkpvExtern(CkGroupID, cmgrID);
@@ -80,8 +86,9 @@ void OneTimeMulticastStrategy::insertMessage(CharmMessageHolder *cmsg){
 void OneTimeMulticastStrategy::localMulticast(CharmMessageHolder *cmsg) {
   double start = CmiWallTimer();
   CkSectionID *sec_id = cmsg->sec_id;
-  CkVec< CkArrayIndexMax > localIndices;
-  sinfo.getLocalIndices(sec_id->_nElems, sec_id->_elems, sec_id->_cookie.aid, localIndices);
+  CkVec< CkArrayIndex > localIndices;
+  CkArrayID aid(sec_id->_cookie.get_aid());
+  sinfo.getLocalIndices(sec_id->_nElems, sec_id->_elems, aid, localIndices);
   deliverToIndices(cmsg->getCharmMessage(), localIndices );
   traceUserBracketEvent(10000, start, CmiWallTimer());
 }
@@ -107,7 +114,7 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   
   // Find my index in the list of all destination PEs
   if(rootPE){
-    CkAssert(CkMyPe() == multMsg->_cookie.pe);
+    CkAssert(CkMyPe() == multMsg->_cookie.get_pe());
     myIndex = -1;
   } else {
     for (int i=0; i<totalDestPEs; ++i) {
@@ -124,9 +131,10 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   int npes;
   int *pelist = NULL;
 
-  if(totalDestPEs > 0)
-    determineNextHopPEs(totalDestPEs, multMsg->indicesCount, myIndex, multMsg->_cookie.pe, pelist, npes );
-  else {
+  if(totalDestPEs > 0) {
+    //CkPrintf("totalDestPEs = %d\n", totalDestPEs);
+    determineNextHopPEs(totalDestPEs, multMsg->indicesCount, myIndex, multMsg->_cookie.get_pe(), pelist, npes );
+  } else {
     npes = 0;
   }
 
@@ -144,7 +152,7 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   
 
   CmiSetHandler(env, CkpvAccess(comlib_handler));
-  ((CmiMsgHeaderBasic *) env)->stratid = getInstance();  
+  ((CmiMsgHeaderExt *) env)->stratid = getInstance();  
   CkPackMessage(&env);
 
   double middle = CmiWallTimer();
@@ -152,11 +160,15 @@ void OneTimeMulticastStrategy::remoteMulticast(ComlibMulticastMsg * multMsg, boo
   
   // CkPrintf("[%d] before CmiSyncListSendAndFree env->event=%d\n", CkMyPe(), (int)env->getEvent());
 
+#if SYNCLISTSENDANDFREE
+  CmiSyncListSendAndFree(npes, pelist, env->getTotalsize(), (char*)env);
+#else
 
   CkAssert(npes > 0);
   CmiSyncListSend(npes, pelist, env->getTotalsize(), (char*)env);
   
   delete[] pelist;
+#endif
 
   double end = CmiWallTimer();
   traceUserBracketEvent(10001, start, middle);
@@ -185,12 +197,23 @@ void OneTimeMulticastStrategy::handleMessage(void *msg){
   // Deliver to objects marked as local in the message
   int localElems;
   envelope *newenv;
-  CkArrayIndexMax *local_idx_list;  
+  CkArrayIndex *local_idx_list;  
   sinfo.unpack(env, localElems, local_idx_list, newenv);
   ComlibMulticastMsg *newmsg = (ComlibMulticastMsg *)EnvToUsr(newenv);  
 
   //  CkPrintf("[%d] in OneTimeMulticastStrategy::handleMessage before  deliverToIndices newenv->event=%d\n", CkMyPe(), (int)newenv->getEvent());
 
+
+#if SYNCLISTSENDANDFREE
+
+  // Deliver locally
+  deliverToIndices(newmsg, localElems, local_idx_list );
+  
+  // Forward on to other processors if necessary
+  remoteMulticast(multMsg, false);
+#else
+
   // Forward on to other processors if necessary
   remoteMulticast(multMsg, false);
 
@@ -199,6 +222,8 @@ void OneTimeMulticastStrategy::handleMessage(void *msg){
   
   // Finally delete the reference counted message because remoteMulticast does not do this.
   CmiFree(multMsg);
+
+#endif
   
 }
 
@@ -283,7 +308,7 @@ void OneTimeTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, c
 int getFirstPeOnPhysicalNodeFromList(int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
   int num;
   int *nodePeList;
-  CmiGetPesOnPhysicalNode(pe, &nodePeList, &num);
+  CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num);
   
   for(int i=0;i<num;i++){
     // Scan destPEs for the pe
@@ -306,7 +331,7 @@ int getFirstPeOnPhysicalNodeFromList(int pe, const int totalDestPEs, const Comli
 int getNthPeOnPhysicalNodeFromList(int n, int pe, const int totalDestPEs, const ComlibMulticastIndexCount* destPEs){
   int num;
   int *nodePeList;
-  CmiGetPesOnPhysicalNode(pe, &nodePeList, &num);
+  CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num);
   
   int count = 0;
   int lastFound = -1;
@@ -341,7 +366,7 @@ vector<int> getPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, const C
  
   int num; 
   int *nodePeList; 
-  CmiGetPesOnPhysicalNode(pe, &nodePeList, &num); 
+  CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num); 
   
   for(int i=0;i<num;i++){ 
     // Scan destPEs for the pe 
@@ -368,7 +393,7 @@ vector<int> getOtherPesOnPhysicalNodeFromList(int pe, const int totalDestPEs, co
 
   int num;
   int *nodePeList;
-  CmiGetPesOnPhysicalNode(pe, &nodePeList, &num);
+  CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(pe), &nodePeList, &num);
   
   for(int i=0;i<num;i++){
     // Scan destPEs for the pe
@@ -671,216 +696,264 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
   
 }
 
+// If min == 1 then this function finds the min else the max value in the array
+// This function returns the index of the array that it found to be the max or the min
+int OneTimeDimensionOrderedMulticastStrategy::findMinMaxArray(int min, int len, int *array, bool* notincluded, int value) {
+  int k = value;
+  int a = -1;
+  for (int j = 0; j < len; j++) {
+    if (notincluded[j]) continue;
+    if (min && array[j] < k) {
+      k = array[j];
+      a = j;
+    } else if (!min && array[j] > k) {
+      k = array[j];
+      a = j;
+    }
+  }
+  return a;
+}
 
+void OneTimeDimensionOrderedMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPe, int * &pelist, int &npes) {
+  const int myPe = CkMyPe();
 
-
-
-
-
-
-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);    
-//   }
+  set<int> nodePEReps;
   
-//   int numRepresentativePEs = nodePERepresentatives.size();
+  // 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;
+    CkAssert(pe != rootPe);
+    if (myPe == 0)
+      CkPrintf("destPE = %d\n", pe);
+    int rep = getFirstPeOnPhysicalNodeFromList(pe, totalDestPEs, destPEs);
+    nodePEReps.insert(rep);
+  }
   
-//   int repForMyPe=-1;
-//   if(myIndex != -1)
-//     repForMyPe = getFirstPeOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+  int numRepPEs = nodePEReps.size();
   
-// #if DEBUG
-//   CkPrintf("[%d] Multicasting to %d PEs on %d physical nodes  repForMyPe=%d\n", CkMyPe(), totalDestPEs, numRepresentativePEs, repForMyPe);
-//   fflush(stdout);
-// #endif
+  int repForMyPe = -1;
+  if(myIndex != -1)
+    repForMyPe = getFirstPeOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
   
-//   // 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
+  map<int, set<int> > spanTree;
 
-//     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];
+  TopoManager tmgr;
 
-//     set<int> xcoords;
+  int myX, myY, myZ, myT;
+  tmgr.rankToCoordinates(rootPe, myX, myY, myZ, myT);
 
-//     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 
-    
-    
-    
-    
+  map<int, int> peRef;
+  int *repPeRef = new int[numRepPEs+1];
+  int *repPeX = new int[numRepPEs+1];
+  int *repPeY = new int[numRepPEs+1];
+  int *repPeZ = new int[numRepPEs+1];
 
+  int i = 0, myRepIndex;
 
+  for (set<int>::iterator iter = nodePEReps.begin(); iter != nodePEReps.end(); ++iter) {
+      int pe = *iter;
+      repPeRef[i] = pe;
+      peRef[pe] = i;
+      int t; // ignore the 't' dimension (which PE on the node)
+      tmgr.rankToCoordinates(pe, repPeX[i], repPeY[i], repPeZ[i], t);
+      if (*iter == repForMyPe)
+         myRepIndex = i;
+      i++;
+  }
 
+  int t;
+  repPeRef[i] = rootPe;
+  peRef[rootPe] = i;
+  tmgr.rankToCoordinates(rootPe, repPeX[i], repPeY[i], repPeZ[i], t);
 
+  CkAssert(myRepIndex >= 0 || myIndex == -1);
+  bool *destAdded = new bool[numRepPEs];
 
-    
-    
-   
-//     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;
-//   }
+  for (int i = 0; i < numRepPEs; i++)
+      destAdded[i] = false;
 
-  
-  
-}
+  int mode = 0; // 0 = x-axis, 1 = y-axis, 2 = z-axis
 
+  spanTree[rootPe].insert(rootPe);
 
+  //CkPrintf("Starting to build the tree...\n");
 
+  while (spanTree.size() < numRepPEs+1) {
+      int k = 0;
+      for (int i = 0; i < numRepPEs; i++) {
+         if (destAdded[i])
+             k++;
+      }
 
+      //CkPrintf("size of destAdded = %d, numRepPEs = %d, spanTree.size() = %d\n", k, numRepPEs, spanTree.size());
+
+      for(map<int, set<int> >::iterator iter = spanTree.begin(); iter != spanTree.end(); ++iter) {
+         int pe = iter->first;
+         int iPe = peRef[pe];
+         if (mode % 4 == 0) {
+             // Move in the -x direction
+             int i1 = findMinMaxArray(1, numRepPEs, repPeX, destAdded, repPeX[iPe]);
+       
+             if (i1 != -1) {
+                 destAdded[i1] = true;
+                 spanTree[pe].insert(repPeRef[i1]);
+                 spanTree[repPeRef[i1]].insert(repPeRef[i1]);
+                 //CkPrintf("added to -x\n");
+             }
+
+             // Move in the +x direction
+             int i2 = findMinMaxArray(0, numRepPEs, repPeX, destAdded, repPeX[iPe]);
+               
+             if (i2 != -1) {
+                 destAdded[i2] = true;
+                 spanTree[pe].insert(repPeRef[i2]);
+                 spanTree[repPeRef[i2]].insert(repPeRef[i2]);
+                 //CkPrintf("added to +x\n");
+             }
+         } else if (mode % 4 == 1) {
+             bool* notEqX = new bool[numRepPEs];
+             for (int i = 0; i < numRepPEs; i++) {
+                 notEqX[i] = destAdded[i];
+                 if (!destAdded[i] && repPeX[iPe] != repPeX[i])
+                     notEqX[i] = true;
+             }
+
+             // Move in the -y direction
+             int i1 = findMinMaxArray(1, numRepPEs, repPeY, notEqX, repPeY[iPe]);
+       
+             if (i1 != -1) {
+                 destAdded[i1] = true;
+                 spanTree[pe].insert(repPeRef[i1]);
+                 spanTree[repPeRef[i1]].insert(repPeRef[i1]);
+                 //CkPrintf("added to -y\n");
+             }
+
+             // Move in the +y direction
+             int i2 = findMinMaxArray(0, numRepPEs, repPeY, notEqX, repPeY[iPe]);
+               
+             if (i2 != -1) {
+                 destAdded[i2] = true;
+                 spanTree[pe].insert(repPeRef[i2]);
+                 spanTree[repPeRef[i2]].insert(repPeRef[i2]);
+                 //CkPrintf("added to +y\n");
+             }
+
+             delete[] notEqX;
+         } else if (mode % 4 == 2) {
+             bool* notEqXY = new bool[numRepPEs];
+             for (int i = 0; i < numRepPEs; i++) {
+                 notEqXY[i] = destAdded[i];
+                 if (!destAdded[i] && (repPeX[iPe] != repPeX[i] || repPeY[iPe] != repPeY[i]))
+                     notEqXY[i] = true;
+             }
+
+             // Move in the -z direction
+             int i1 = findMinMaxArray(1, numRepPEs, repPeZ, notEqXY, repPeZ[iPe]);
+       
+             if (i1 != -1) {
+                 destAdded[i1] = true;
+                 spanTree[pe].insert(repPeRef[i1]);
+                 spanTree[repPeRef[i1]].insert(repPeRef[i1]);
+                 //CkPrintf("added to -z\n");
+             }
+
+             // Move in the +z direction
+             int i2 = findMinMaxArray(0, numRepPEs, repPeZ, notEqXY, repPeZ[iPe]);
+               
+             if (i2 != -1) {
+                 destAdded[i2] = true;
+                 spanTree[pe].insert(repPeRef[i2]);
+                 spanTree[repPeRef[i2]].insert(repPeRef[i2]);
+                 //CkPrintf("added to +z\n");
+             }
+
+             delete[] notEqXY;
+         }
+      }
+      mode++;
+  }
 
+  /*CkPrintf("Finished creating spanning tree\n");*/
 
+  static bool firstTime = true;
 
+  if (myPe == 0 && firstTime) {
+      firstTime = false;
+      for(map<int, set<int> >::iterator iter = spanTree.begin(); iter != spanTree.end(); ++iter) {
+         CkPrintf("Map %d to: ", iter->first);
+         for(set<int>::iterator iter2 = iter->second.begin(); iter2 != iter->second.end(); ++iter2) {
+             CkPrintf("%d, ", *iter2);
+         }
+         CkPrintf("\n");
+      }
+  }
 
+  // Send to local PEs
+  vector<int> otherLocalPes = getOtherPesOnPhysicalNodeFromList(CkMyPe(), totalDestPEs, destPEs);
+  int numSendLocal = otherLocalPes.size();
 
+  int numSend = spanTree[myPe].size() > 0 ? spanTree[myPe].size()-1 + numSendLocal : numSendLocal;
+    
+  if(numSend <= 0) {
+      npes = 0;
+      return;
+  }
+    
+  //CkPrintf("Sending to %d processors based on tree + local nodes\n", numSend);
 
+  npes = numSend;
+  pelist = new int[npes];
+  
+  i = 0;
 
+  for (set<int>::iterator iter = spanTree[myPe].begin(); iter != spanTree[myPe].end(); ++iter) {
+      if (*iter != myPe) {
+         pelist[i] = *iter;
+         i++;
+      }
+  }
 
+  for(int j = 0; j < numSendLocal; j++){
+      pelist[i] = otherLocalPes[j];
+      i++;
+  }
+}
 
+#include "spanningTreeStrategy.h"
+
+using namespace topo;
+
+void OneTimeTopoTreeMulticastStrategy::determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes)
+{
+    /// Initialize
+    npes = 0; 
+    int myPE = (myIndex<0)? rootPE : destPEs[myIndex].pe;
+
+    /// Create a container of SpanningTreeVertex-es from the input list of PEs (include the root PE too)
+    std::vector<topo::SpanningTreeVertex> tree;
+    tree.push_back( topo::SpanningTreeVertex(rootPE) );
+    for (int i=0; i< totalDestPEs; i++)
+        tree.push_back( topo::SpanningTreeVertex(destPEs[i].pe) );
+
+    /// Build the complete spanning tree
+    topo::buildSpanningTree(tree.begin(),tree.end(),degree);
+
+    /// Identify this PE in the tree and find immediate children
+    int peIdx = -1;
+    bool noMatchFound = true;
+    while ( (++peIdx < tree.size()) && noMatchFound)
+    {
+        if (myPE == tree[peIdx].id)
+        {
+            /// Add immediate children to pelist and set npes accordingly
+            npes   = tree[peIdx].childIndex.size();
+            pelist = new int[npes];
+            for (int i=0; i< npes; i++)
+                pelist[i] = tree[ peIdx + tree[peIdx].childIndex[i] ].id; ///< child indices are relative distances from the parent in the container
+            noMatchFound = false;
+        }
+    }
+}
 
 /*@}*/