Home Research Papers Posters Manuals Talks Download People Help Internal

util/treeStrategy_topoUnaware.h

Go to the documentation of this file.

#include "charm++.h"

#include <map>

#ifndef TREE_STRATEGY_TOPO_UNAWARE
#define TREE_STRATEGY_TOPO_UNAWARE
namespace topo {

namespace impl {
    template <typename Iterator>
    SpanningTreeVertex* buildNextGen_topoUnaware(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches);
}

template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
class SpanningTreeStrategy_topoUnaware: public SpanningTreeStrategy<Iterator>
{
    public:
        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
        { return impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches); }
};



template <typename Iterator>
class SpanningTreeStrategy_topoUnaware<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator> 
{
    public:
        inline virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
        {
            (*firstVtx).childIndex.clear();
            SpanningTreeVertex *parent = impl::buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);
            *firstVtx = *parent;
            return parent;
        }
};


namespace impl {
    template <typename Iterator>
    SpanningTreeVertex* buildNextGen_topoUnaware(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
    {
        if (maxBranches < 1 || firstVtx == beyondLastVtx) return new SpanningTreeVertex();

        SpanningTreeVertex *parent = new SpanningTreeVertex(*firstVtx);

    //Containing no actual nodes to be built
    if(firstVtx+1 == beyondLastVtx) return parent;
    
    //store the sequence of local indices for each different node ids
    std::vector<int> nodesSeq; 
    #if CMK_SMP 
        //key is the node id, and the mapped value is the local index
        std::map<int, int> nodesMap;
        int localIndex = 1; //relative to the root
        for(Iterator vtx=firstVtx+1; vtx!=beyondLastVtx; vtx++, localIndex++){
            int nid = CmiNodeOf(topo::getProcID(*vtx));
            if(nodesMap.find(nid) == nodesMap.end()){
                //encounter a new node id
                nodesMap[nid] = localIndex;
                nodesSeq.push_back(localIndex);
            }
        }
        nodesMap.clear();
        int totalNodes = nodesSeq.size();
        //check whether the building of this tree is for procs on remote SMP nodes.
        //NOW: just use the condition whether the "parent" nid is same with (firstVtx+1)
        int pnid = CmiNodeOf(topo::getProcID(*firstVtx));
        int fnid = CmiNodeOf(topo::getProcID(*(firstVtx+1)));
        int forRemoteNodes = (pnid != fnid);
    #else
        //in non-SMP case, just to fake there's no SMP nodes so the work flow of spanning tree 
        //creation is correct
        int totalNodes = 0;
        int forRemoteNodes=0;
    #endif
        
        if(totalNodes <= 1 && !forRemoteNodes){
            const int numDescendants = std::distance(firstVtx,beyondLastVtx) - 1;
            int numInSubTree = numDescendants / maxBranches;
            int remainder    = numDescendants % maxBranches;

            for (int i=0, indx=1; (i<maxBranches && indx<=numDescendants); i++, indx += numInSubTree)
            {
                parent->childIndex.push_back(indx);
                if (remainder-- > 0) indx++;
            }   
        }else{
            const int numDescendants = totalNodes;
            int numInSubTree = numDescendants / maxBranches;
            int remainder    = numDescendants % maxBranches;

            for (int i=0, indx=0; (i<maxBranches && indx<numDescendants); i++, indx += numInSubTree)
            {
                parent->childIndex.push_back(nodesSeq[indx]);
                if (remainder-- > 0) indx++;
            }
        }
    nodesSeq.clear();
        return parent;
    }   
}

} // end namespace topo
#endif // TREE_STRATEGY_TOPO_UNAWARE

---