Home Research Papers Posters Manuals Talks Download People Help Internal

util/treeStrategy_nodeAware_minBytes.h

Go to the documentation of this file.

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

#ifndef TREE_STRATEGY_NODE_AWARE_MIN_BYTES
#define TREE_STRATEGY_NODE_AWARE_MIN_BYTES
namespace topo {

namespace impl {
    template <typename Iterator>
    SpanningTreeVertex* buildNextGen_nodeAware_minBytes(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
}

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



template <typename Iterator>
class SpanningTreeStrategy_nodeAware_minBytes<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_nodeAware_minBytes((*firstVtx).id,firstVtx,beyondLastVtx,maxBranches);
            *firstVtx = *parent;
            return parent;
        }
};


namespace impl {
    template <typename Iterator>
    SpanningTreeVertex* buildNextGen_nodeAware_minBytes(const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
    {
        CkAssert(parentPE < CkNumPes() );
        int numOnNode, *pesOnNode;
        CmiGetPesOnPhysicalNode(CmiPhysicalNodeID(parentPE),&pesOnNode,&numOnNode);

        int numLocalDestinations = 0, numLocalBranches = 0;
        SpanningTreeVertex *parent = 0;
        Iterator itr = firstVtx, lastLocal = firstVtx;

        while ( numLocalDestinations < numOnNode -1 && itr != beyondLastVtx)
        {
            itr = std::find_first_of(++itr,beyondLastVtx,pesOnNode,pesOnNode + numOnNode
#if CMK_FIND_FIRST_OF_PREDICATE
                     , vtxEqual()
#endif
                     );

            if (itr != beyondLastVtx)
            {
                numLocalDestinations++;
                if (itr != ++lastLocal)
                    std::iter_swap(itr,lastLocal);
            }
        }

        if (numLocalDestinations > 0)
        {
            int numRemoteDestinations = std::distance(firstVtx,beyondLastVtx) -1 - numLocalDestinations; 
            numLocalBranches = (numRemoteDestinations >= maxBranches)? 1 : (maxBranches - numRemoteDestinations);

            Iterator beyondLastLocal = lastLocal;
            parent = buildNextGen_topoUnaware(firstVtx,++beyondLastLocal,numLocalBranches);

            SpanningTreeVertex *remoteSubTrees = buildNextGen_topoUnaware(lastLocal,beyondLastVtx,maxBranches); 

            for (int i=0, n=remoteSubTrees->childIndex.size(); i< n; i++)
                parent->childIndex.push_back(remoteSubTrees->childIndex[i] + numLocalDestinations);
            delete remoteSubTrees;
        }
        else
            parent = buildNextGen_topoUnaware(firstVtx,beyondLastVtx,maxBranches);

        return parent;
    }
} // end namespace impl

} // end namespace topo
#endif // TREE_STRATEGY_NODE_AWARE_MIN_BYTES

---