Home Research Papers Posters Manuals Talks Download People Help Internal

util/spanningTreeStrategy.h

Go to the documentation of this file.

#include <iostream>
#include <vector>
#include <iterator>
#include <cstdlib>

#include "conv-config.h"
#include "spanningTreeVertex.h"

#ifndef SPANNING_TREE_STRATEGY
#define SPANNING_TREE_STRATEGY

#if ! CMK_HAS_ITERATOR_TRAITS
namespace std {

template <class Iterator>
  struct iterator_traits {
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::difference_type   difference_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
  };

  template <class T>
  struct iterator_traits<T*> {
    typedef random_access_iterator_tag iterator_category;
    typedef T                          value_type;
    typedef ptrdiff_t                  difference_type;
    typedef T*                         pointer;
    typedef T&                         reference;
  };

}

#endif

#if ! CMK_HAS_STD_DISTANCE
namespace std {

template <class Iterator>
int distance(Iterator first, Iterator last)
{
  int n=0;
  while (first!=last)
  {
       ++first;
       ++n;
  }

  return n;
}
}
#endif

//-------------------------------- Declarations of the main entities in this file --------------------------------

namespace topo {

typedef int vtxType;

class SpanningTreeVertex;

template <typename Iterator,typename ValueType = typename std::iterator_traits<Iterator>::value_type>
class SpanningTreeStrategy;


// Use a default strategy
template <typename Iterator>
SpanningTreeVertex* buildSpanningTreeGeneration
(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
// Use the strategy provided by the caller
template <typename Iterator>
SpanningTreeVertex* buildSpanningTreeGeneration
(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches, SpanningTreeStrategy<Iterator> *bldr);


// Use a default strategy
template <typename Iterator>
void buildSpanningTree
(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches=2);
// Use the strategy provided by the caller
template <typename Iterator>
void buildSpanningTree
(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches, SpanningTreeStrategy<Iterator> *bldr);

template <typename Iterator>
SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy
(const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches);

} // end namespace topo



//--------------------------------  Class and function definitions --------------------------------
namespace topo {

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




template <typename Iterator>
inline SpanningTreeVertex* buildSpanningTreeGeneration(const Iterator firstVtx,
                                                       const Iterator beyondLastVtx,
                                                       const int maxBranches,
                                                       SpanningTreeStrategy<Iterator> *bldr
                                                      )
{
    CkAssert(NULL != bldr);

    if (maxBranches < 1 || firstVtx == beyondLastVtx)
        return new SpanningTreeVertex();
    else
    return bldr->buildNextGen(firstVtx,beyondLastVtx,maxBranches);
}


// Overload to automatically use the default strategy
template <typename Iterator>
inline SpanningTreeVertex* buildSpanningTreeGeneration(const Iterator firstVtx,
                                                       const Iterator beyondLastVtx,
                                                       const int maxBranches
                                                      )
{
    SpanningTreeStrategy<Iterator> *bldr =
    getSpanningTreeStrategy(firstVtx,beyondLastVtx,maxBranches);
    SpanningTreeVertex *result = buildSpanningTreeGeneration(firstVtx, beyondLastVtx, maxBranches, bldr);
    delete bldr;
    return result;
}



namespace impl {

template <typename Iterator>
void buildSpanningTree(SpanningTreeVertex* dispatchTag,
                       const Iterator firstVtx,
                       const Iterator beyondLastVtx,
                       const int maxBranches,
                       SpanningTreeStrategy<Iterator> *bldr
                      )
{
    if (maxBranches < 1 || firstVtx == beyondLastVtx)
        return;

    SpanningTreeVertex *tmp = buildSpanningTreeGeneration(firstVtx,beyondLastVtx,maxBranches,bldr);
    delete tmp;

    int numChildren = (*firstVtx).childIndex.size();
    for (int i=0; i< numChildren; i++)
    {
        Iterator start = firstVtx, end = firstVtx;
        std::advance(start, (*firstVtx).childIndex[i] );
        if (i < numChildren -1)
            std::advance(end, (*firstVtx).childIndex[i+1] );
        else
            end = beyondLastVtx;
        buildSpanningTree(dispatchTag,start,end,maxBranches,bldr);
    }
}

} // end namespace impl




template <typename Iterator>
inline void buildSpanningTree(const Iterator firstVtx,
                              const Iterator beyondLastVtx,
                              const int maxBranches,
                              SpanningTreeStrategy<Iterator> *bldr
                             )
{
    CkAssert(NULL != bldr);
    typename std::iterator_traits<Iterator>::value_type *tag = 0;
    impl::buildSpanningTree(tag,firstVtx,beyondLastVtx,maxBranches,bldr);
}


// Overload to automatically use the default strategy
template <typename Iterator>
inline void buildSpanningTree(const Iterator firstVtx,
                              const Iterator beyondLastVtx,
                              const int maxBranches
                             )
{
    SpanningTreeStrategy<Iterator> *bldr =
    getSpanningTreeStrategy(firstVtx,beyondLastVtx,maxBranches);
    buildSpanningTree(firstVtx, beyondLastVtx, maxBranches, bldr);
    delete bldr;
}

} // end namespace topo



#if XE6_TOPOLOGY
#define MAX_TORUS_DIM_SIZE 24
#endif
#include "treeStrategy_topoUnaware.h"
#include "treeStrategy_nodeAware_minGens.h"
#include "treeStrategy_nodeAware_minBytes.h"
#include "treeStrategy_3dTorus_minHops.h"
#include "treeStrategy_3dTorus_minBytesHops.h"

namespace topo {

template <typename Iterator>
inline SpanningTreeStrategy<Iterator>* getSpanningTreeStrategy(const Iterator firstVtx,
                                                               const Iterator beyondLastVtx,
                                                               const int maxBranches)
{
    #if XT3_TOPOLOGY || XT4_TOPOLOGY || XT5_TOPOLOGY || XE6_TOPOLOGY
        return ( new SpanningTreeStrategy_3dTorus_minBytesHops<Iterator>() );
    #else
        class NumOnNode
        {
            public:
                inline int operator() (const vtxType vtx)             { return CmiNumPesOnPhysicalNode( CmiPhysicalNodeID(vtx) ); }
                inline int operator() (const SpanningTreeVertex &vtx) { return CmiNumPesOnPhysicalNode( CmiPhysicalNodeID(vtx.id) ); }
        } findNumPEsOnNode;

        int numPEsOnNode = findNumPEsOnNode(*firstVtx);

        if (numPEsOnNode <= 4 && maxBranches < 4)
            return ( new SpanningTreeStrategy_nodeAware_minGens<Iterator>() );
        else
            return ( new SpanningTreeStrategy_nodeAware_minBytes<Iterator>() );
    #endif
}

} // end namespace topo

#endif // SPANNING_TREE_STRATEGY

---