Home Research Papers Posters Manuals Talks Download People Help Internal

util/treeStrategy_3dTorus_minHops.h

Go to the documentation of this file.

#include <algorithm>
#include "charm++.h"

#ifndef TREE_STRATEGY_3D_TORUS_MIN_HOPS
#define TREE_STRATEGY_3D_TORUS_MIN_HOPS
namespace topo {

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



template <typename Iterator>
class SpanningTreeStrategy_3dTorus_minHops<Iterator,SpanningTreeVertex>: public SpanningTreeStrategy<Iterator>
{
    public:
        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
};



template <typename Iterator>
class SpanningTreeStrategy_3dTorus_minHops<Iterator,vtxType>: public SpanningTreeStrategy<Iterator>
{
    public:
        virtual SpanningTreeVertex* buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2)
        {
            std::vector<SpanningTreeVertex> tree;
            for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
                tree.push_back( SpanningTreeVertex(*itr) );
            SpanningTreeStrategy_3dTorus_minHops< std::vector<SpanningTreeVertex>::iterator > theRealBuilder;
            SpanningTreeVertex *result = theRealBuilder.buildNextGen(tree.begin(),tree.end(),maxBranches);
            int indx=0;
            for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
            {
                *itr = tree[indx].id;
                indx++;
            }
            return result;
        }
};



namespace impl {
template <typename Iterator>
class TreeBoundingBoxOn3dTorus
{
    public:
        void partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);

    protected:
        void bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
        void trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions);
        int findMaxSpreadDimension(const Iterator start, const Iterator end);
        class lessThan
        {
            public:
                lessThan(const int _dim): dim(_dim) {}
                inline bool operator() (const SpanningTreeVertex &a, const SpanningTreeVertex &b)
                {
                    return (a.X[dim] < b.X[dim]);
                }
            private:
                const int dim;
        };
};
} // end namespace impl

} // end namespace topo


#include "TopoManager.h"

namespace topo {

template <typename Iterator>
SpanningTreeVertex* SpanningTreeStrategy_3dTorus_minHops<Iterator,SpanningTreeVertex>::buildNextGen(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
{
    (*firstVtx).childIndex.clear();
    (*firstVtx).childIndex.reserve(maxBranches);

    TopoManager aTopoMgr;
    for (Iterator itr = firstVtx; itr != beyondLastVtx; itr++)
    {
        (*itr).X.reserve(3);
        (*itr).X.assign(3,0);
        int coreNum; 
        aTopoMgr.rankToCoordinates( (*itr).id, (*itr).X[0], (*itr).X[1], (*itr).X[2], coreNum );
    }

    Iterator firstDescendant = firstVtx;
    impl::TreeBoundingBoxOn3dTorus<Iterator> treePart;
    treePart.partition(firstVtx,++firstDescendant,beyondLastVtx,maxBranches);

    for (int i=0, numChildren=(*firstVtx).childIndex.size(); i<numChildren; i++)
    {
        Iterator rangeStart = firstVtx;
        std::advance(rangeStart,(*firstVtx).childIndex[i]);
        Iterator rangeEnd   = firstVtx;
        if (i+1 == numChildren)
            rangeEnd = beyondLastVtx;
        else
            std::advance(rangeEnd, (*firstVtx).childIndex[i+1] );
        Iterator closestItr = pickClosest(*firstVtx,rangeStart,rangeEnd);
        std::iter_swap(rangeStart,closestItr);
    }
    return (new SpanningTreeVertex(*firstVtx) );
}



namespace impl {

template <typename Iterator>
inline void TreeBoundingBoxOn3dTorus<Iterator>::partition(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
{
    int numVertices = std::distance(start,end);
    if ( (numPartitions > 1) && (numVertices > 1) )
    {
        if (numPartitions % 3 == 0)
            trisect(parent,start,end,numPartitions);
        else
            bisect (parent,start,end,numPartitions);
    }
    else if ( (numPartitions >= 1) && (numVertices >= 1) )
    {
        int indx = std::distance(parent,start);
        (*parent).childIndex.push_back(indx);
    }
    else if (numVertices == 0)
    {
    }
    else if ( (numVertices >= 0) && (numPartitions == 0) )
        CkAbort("\nThere are vertices left but no remaining partitions to put them in.");
    else
        CkAbort("\nPartitioning fell through to the default case (which it never should). Check the logic in this routine.");
}



template <typename Iterator>
void TreeBoundingBoxOn3dTorus<Iterator>::bisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
{
    int numVertices = std::distance(start,end);
    int maxSpreadDim = findMaxSpreadDimension(start,end);
    Iterator median = start;
    std::advance(median,numVertices/2);
    std::nth_element( start, median, end, lessThan(maxSpreadDim) );
    int numLeft = numPartitions/2;
    partition(parent, start, median, numLeft);
    partition(parent, median, end, numPartitions - numLeft);
}



template <typename Iterator>
void TreeBoundingBoxOn3dTorus<Iterator>::trisect(const Iterator parent, const Iterator start, const Iterator end, const int numPartitions)
{
    if (numPartitions % 3 == 0)
    {
        int numVertices = std::distance(start,end);
        int maxSpreadDim = findMaxSpreadDimension(start,end);
        Iterator oneThird = start;
        std::advance(oneThird,numVertices/3);
        Iterator twoThird = oneThird;
        std::advance(twoThird,numVertices/3);
        std::nth_element( start,    oneThird, end, lessThan(maxSpreadDim) );
        std::nth_element( oneThird, twoThird, end, lessThan(maxSpreadDim) );
        int numLeft = numPartitions/3;
        partition(parent, start,    oneThird, numLeft);
        partition(parent, oneThird, twoThird, numLeft);
        partition(parent, twoThird, end,      numLeft);
    }
    else
        partition(parent, start, end, numPartitions);
}



template <typename Iterator>
int TreeBoundingBoxOn3dTorus<Iterator>::findMaxSpreadDimension(const Iterator start, const Iterator end)
{
    int nDims = (*start).X.size();
    std::vector<int> min, max, spread;
    min.reserve(nDims);
    max.reserve(nDims);
    spread.reserve(nDims);
    min = max = (*start).X;
    for (Iterator itr = start; itr != end; itr++)
    {
        for (int i=0; i<nDims; i++)
        {
            if ( (*itr).X[i] < min[i] )
                min[i] = (*itr).X[i];
            if ( (*itr).X[i] > max[i] )
                max[i] = (*itr).X[i];
        }
    }
    int maxSpread = abs(max[0] - min[0]);
    int maxSpreadDimension = 0;
    for (int i=1; i<nDims; i++)
    {
        int spread = abs(max[i] - min[i]);
        if (maxSpread < spread )
        {
            maxSpread = spread;
            maxSpreadDimension = i;
        }
    }
    return maxSpreadDimension;
}

} // end namespace impl

} // end namespace topo
#endif // TREE_STRATEGY_3D_TORUS_MIN_HOPS

---