Adding a new comlib strategy: OneTimeTopoTreeMulticastStrategy
authorRamprasad Venkataraman <ramv@illinois.edu>
Thu, 3 Sep 2009 00:36:33 +0000 (00:36 +0000)
committerRamprasad Venkataraman <ramv@illinois.edu>
Thu, 3 Sep 2009 00:36:33 +0000 (00:36 +0000)
Topo-aware multicast spanning trees are constructed using the spanning tree builder. The process currently does a good bit of avoidable work at each generation of the multicast, but is a quick implementation to enable other experiments.

src/ck-com/ComlibManager.ci
src/ck-com/OneTimeMulticastStrategy.C
src/ck-com/OneTimeMulticastStrategy.h

index 5035defec524901c8a103600d100b74ac38e0ee6..54c2b41de1d80525f139e51cb2d923d8f05a6f7d 100644 (file)
@@ -46,6 +46,7 @@ module comlib {
  
   PUPable OneTimeMulticastStrategy;    
   PUPable OneTimeTreeMulticastStrategy;
+  PUPable OneTimeTopoTreeMulticastStrategy;
   PUPable OneTimeRingMulticastStrategy;
   PUPable OneTimeNodeTreeMulticastStrategy;
   PUPable OneTimeNodeTreeRingMulticastStrategy;
index 6bf16900957b2d7814d95e43d808cc1678308b8c..1c92bea333b6f18f5cd45c1308dbfe776e8bff6c 100644 (file)
@@ -696,6 +696,39 @@ void OneTimeNodeTreeRingMulticastStrategy::determineNextHopPEs(const int totalDe
 
 
 
+#include "spanningTreeStrategy.h"
+
+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;
+        }
+    }
+}
 
 
 
index 5931df63a86d27c7e5a38f50b7f0fa68d8ccf969..acf8fd197610141b718fae37a4bea87178fe1bbc 100644 (file)
@@ -131,6 +131,33 @@ class OneTimeTreeMulticastStrategy: public OneTimeMulticastStrategy {
 
 
 
+/**
+ * A strategy that uses the topo-aware spanning tree builder to send msgs down a spanning tree 
+ * that is constructed in a network-topology aware manner if such info is available. Users 
+ * can specify the branching factor for the spanning tree
+ */
+class OneTimeTopoTreeMulticastStrategy: public OneTimeMulticastStrategy 
+{
+    private:
+        int degree;
+        
+    public:
+        OneTimeTopoTreeMulticastStrategy(CkMigrateMessage *m): OneTimeMulticastStrategy(m) {}
+        /** Create a strategy with specified branching factor(which defaults to 4) */
+        OneTimeTopoTreeMulticastStrategy(int treeDegree=4): OneTimeMulticastStrategy(), degree(treeDegree) { }
+        ~OneTimeTopoTreeMulticastStrategy() {}
+        /// Determine the direct children of this PE in the spanning tree
+        void determineNextHopPEs(const int totalDestPEs, const ComlibMulticastIndexCount* destPEs, const int myIndex, const int rootPE, int * &pelist, int &npes);
+        void pup(PUP::er &p)
+        { 
+            OneTimeMulticastStrategy::pup(p);
+            p | degree;
+        }
+        PUPable_decl(OneTimeTopoTreeMulticastStrategy);
+};
+
+
+
 /**
    A strategy that does dimension ordered sending of messages. This may result in lower contention for torus networks than a topology oblivious tree.
 */
@@ -210,10 +237,6 @@ class OneTimeNodeTreeRingMulticastStrategy: public OneTimeMulticastStrategy {
   PUPable_decl(OneTimeNodeTreeRingMulticastStrategy);
 };
 
-
-
-
-
 #endif
 
 /*@}*/