ST_RecursivePartition< Iterator > Class Template Reference

This strategy is phynode aware, and can form a tree of pes or logical nodes. More...

#include <spanningTree.h>

Inheritance diagram for ST_RecursivePartition< Iterator >:

Collaboration diagram for ST_RecursivePartition< Iterator >:


Public Member Functions
	ST_RecursivePartition (bool nodeTree=true, bool preSorted=false)
virtual int	buildSpanningTree (Iterator start, Iterator end, unsigned int maxBranches)
	Will reorder node range so that nodes are grouped by subtree, and by phynode.
virtual int	subtreeSize (int subtree)
	return number of nodes in generated subtree (includes root of subtree)
virtual Iterator	begin (int subtree)
	return Iterator to first node in generated subtree (i.e. root of subtree)
virtual Iterator	end (int subtree)
	return Iterator to end of generated subtree
Private Member Functions
void	initPhyNodes (Iterator start, Iterator end, std::vector< PhyNode > &phynodes) const
void	build (std::vector< PhyNode * > &phyNodes, Iterator start, unsigned int maxBranches)
void	partition (std::vector< PhyNode * > &nodes, int start, int end, int numPartitions, std::vector< int > &children) const
	recursive partitioning of phynodes into numPartitions
void	chooseSubtreeRoots (std::vector< PhyNode * > &phyNodes, std::vector< int > &children) const
	phyNodes is list of phyNodes, grouped by subtrees (rootPhyNode in position 0) phyNodeChildren contains the indices (in phyNodes) of first node of each subtree
void	bisect (std::vector< PhyNode * > &nodes, int start, int end, int numPartitions, std::vector< int > &children) const
void	trisect (std::vector< PhyNode * > &nodes, int start, int end, int numPartitions, std::vector< int > &children) const
int	maxSpreadDimension (std::vector< PhyNode * > &nodes, int start, int end) const
void	translateCoordinates (std::vector< PhyNode > &nodes) const
	Translate coordinates of phynodes such that the max spread in each dimension is equal (or closer) to the number of coordinates actually used in that dimension.
void	withinPhyNodeTree (PhyNode &rootPhyNode, int bfactor, Iterator &pos)
Private Attributes
std::vector< Iterator >	children
bool	nodeTree
bool	preSorted
TopoManager *	tmgr
Data Structures
class	PhyNode
class	PhyNodeCompare

Detailed Description

template<typename Iterator>
class ST_RecursivePartition< Iterator >

This strategy is phynode aware, and can form a tree of pes or logical nodes.

Will benefit from topology information (coordinates of hosts in the machine, and distance between hosts), but can be used without topology information (and will still be phynode aware).

Works for any N-d mesh/torus, including non-contiguous allocations and holes in allocation (e.g. Blue Waters).

Algorithm complexity is O(n) where n is number of nodes.

Inside a phynode, there will only be one root node, and currently every other node in that phynode is a direct descendant of it (this can be easily changed). Edges between phynodes are only between their corresponding root nodes (as a result there will only be one edge between phynodes).

Definition at line 107 of file spanningTree.h.

Constructor & Destructor Documentation

template<typename Iterator>

ST_RecursivePartition< Iterator >::ST_RecursivePartition	(	bool	nodeTree = `true`,
		bool	preSorted = `false`
	)			`[inline]`

Parameters:

	nodeTree	true if forming tree of nodes, false if tree of pes.
	preSorted	true if nodes will be provided grouped by phynode. Allows using slightly more efficient implementation.

Definition at line 72 of file spanningTree.C.

References BGConverse::CkMyNode(), TopoManager::getDimSize(), TopoManager::getNumDims(), TopoManager::getTopoManager(), TopoManager::haveTopologyInfo(), and ST_RecursivePartition< Iterator >::tmgr.

Here is the call graph for this function:

Member Function Documentation

template<typename Iterator>

int ST_RecursivePartition< Iterator >::buildSpanningTree	(	Iterator	start,
		Iterator	end,
		unsigned int	maxBranches
	)			`[inline, virtual]`

Will reorder node range so that nodes are grouped by subtree, *and* by phynode.

Parameters:

maxBranches

Max number of children in different phynode as root

Implements SpanningTreeGenerator< Iterator >.

Definition at line 92 of file spanningTree.C.

References ST_RecursivePartition< Iterator >::build(), ST_RecursivePartition< Iterator >::children, BGConverse::CkMyNode(), std::distance(), and ST_RecursivePartition< Iterator >::initPhyNodes().

Referenced by getNeighborsTopoTree_R(), and CkMulticastMgr::setup().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

virtual int ST_RecursivePartition< Iterator >::subtreeSize ( int subtree ) [inline, virtual]

return number of nodes in generated subtree (includes root of subtree)

Implements SpanningTreeGenerator< Iterator >.

Definition at line 125 of file spanningTree.h.

References ST_RecursivePartition< Iterator >::children, and std::distance().

Referenced by CkMulticastMgr::setup().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

virtual Iterator ST_RecursivePartition< Iterator >::begin ( int subtree ) [inline, virtual]

return Iterator to first node in generated subtree (i.e. root of subtree)

Implements SpanningTreeGenerator< Iterator >.

Definition at line 133 of file spanningTree.h.

References ST_RecursivePartition< Iterator >::children.

Referenced by getNeighborsTopoTree_R(), and CkMulticastMgr::setup().

Here is the caller graph for this function:

template<typename Iterator>

virtual Iterator ST_RecursivePartition< Iterator >::end ( int subtree ) [inline, virtual]

return Iterator to end of generated subtree

Implements SpanningTreeGenerator< Iterator >.

Definition at line 141 of file spanningTree.h.

References ST_RecursivePartition< Iterator >::children.

Referenced by getNeighborsTopoTree_R(), CkMulticastMgr::setup(), and ST_RecursivePartition< Iterator >::withinPhyNodeTree().

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::initPhyNodes	(	Iterator	start,
		Iterator	end,
		std::vector< PhyNode > &	phynodes
	)			const `[inline, private]`

Definition at line 129 of file spanningTree.C.

References ST_RecursivePartition< Iterator >::PhyNode< Iterator >::addNode(), BGConverse::CkMyNode(), CmiNodeFirst(), CmiNumPhysicalNodes(), CmiPhysicalNodeID(), std::distance(), int, min(), n, ST_RecursivePartition< Iterator >::nodeTree, ST_RecursivePartition< Iterator >::preSorted, print(), ST_RecursivePartition< Iterator >::tmgr, and ST_RecursivePartition< Iterator >::translateCoordinates().

Referenced by ST_RecursivePartition< Iterator >::buildSpanningTree().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::build	(	std::vector< PhyNode * > &	phyNodes,
		Iterator	start,
		unsigned int	maxBranches
	)			`[inline, private]`

Definition at line 228 of file spanningTree.C.

References ST_RecursivePartition< Iterator >::children, ST_RecursivePartition< Iterator >::chooseSubtreeRoots(), TopoManager::haveTopologyInfo(), ST_RecursivePartition< Iterator >::partition(), ST_RecursivePartition< Iterator >::tmgr, and ST_RecursivePartition< Iterator >::withinPhyNodeTree().

Referenced by ST_RecursivePartition< Iterator >::buildSpanningTree().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::partition	(	std::vector< PhyNode * > &	nodes,
		int	start,
		int	end,
		int	numPartitions,
		std::vector< int > &	children
	)			const `[inline, private]`

recursive partitioning of phynodes into numPartitions

Definition at line 300 of file spanningTree.C.

References ST_RecursivePartition< Iterator >::bisect(), and ST_RecursivePartition< Iterator >::trisect().

Referenced by ST_RecursivePartition< Iterator >::bisect(), ST_RecursivePartition< Iterator >::build(), and ST_RecursivePartition< Iterator >::trisect().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::chooseSubtreeRoots	(	std::vector< PhyNode * > &	phyNodes,
		std::vector< int > &	children
	)			const `[inline, private]`

phyNodes is list of phyNodes, grouped by subtrees (rootPhyNode in position 0) phyNodeChildren contains the indices (in phyNodes) of first node of each subtree

Definition at line 276 of file spanningTree.C.

References BGConverse::CkMyNode(), PUP::d, stats::swap(), and ST_RecursivePartition< Iterator >::tmgr.

Referenced by ST_RecursivePartition< Iterator >::build().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::bisect	(	std::vector< PhyNode * > &	nodes,
		int	start,
		int	end,
		int	numPartitions,
		std::vector< int > &	children
	)			const `[inline, private]`

Definition at line 329 of file spanningTree.C.

References TopoManager::haveTopologyInfo(), ST_RecursivePartition< Iterator >::maxSpreadDimension(), ST_RecursivePartition< Iterator >::partition(), and ST_RecursivePartition< Iterator >::tmgr.

Referenced by ST_RecursivePartition< Iterator >::partition().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::trisect	(	std::vector< PhyNode * > &	nodes,
		int	start,
		int	end,
		int	numPartitions,
		std::vector< int > &	children
	)			const `[inline, private]`

Pin the location of the 1/3 and 2/3 elements

Partition the three pieces further

Definition at line 352 of file spanningTree.C.

References TopoManager::haveTopologyInfo(), ST_RecursivePartition< Iterator >::maxSpreadDimension(), ST_RecursivePartition< Iterator >::partition(), and ST_RecursivePartition< Iterator >::tmgr.

Referenced by ST_RecursivePartition< Iterator >::partition().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

int ST_RecursivePartition< Iterator >::maxSpreadDimension	(	std::vector< PhyNode * > &	nodes,
		int	start,
		int	end
	)			const `[inline, private]`

Definition at line 377 of file spanningTree.C.

References c, ST_RecursivePartition< Iterator >::PhyNode< Iterator >::coords, count, TopoManager::getNumDims(), TopoManager::haveTopologyInfo(), n, ST_RecursivePartition< Iterator >::tmgr, and used.

Referenced by ST_RecursivePartition< Iterator >::bisect(), and ST_RecursivePartition< Iterator >::trisect().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void ST_RecursivePartition< Iterator >::translateCoordinates ( std::vector< PhyNode > & nodes ) const [inline, private]

Translate coordinates of phynodes such that the max spread in each dimension is equal (or closer) to the number of coordinates actually used in that dimension.

In other words, "moves" all phynodes by some translation offset so that their bounding box includes minimum number of coordinates, which implies that adjacent nodes won't go through torus edges. Works for any number of dimensions (N-d torus)

Definition at line 412 of file spanningTree.C.

References c, BGConverse::CkMyNode(), ST_RecursivePartition< Iterator >::PhyNode< Iterator >::coords, count, direction, TopoManager::getDimSize(), TopoManager::getNumDims(), PUP::m, modulo(), n, ST_RecursivePartition< Iterator >::tmgr, and x.