topo::impl Namespace Reference

Nested namespace to prevent the implementation muck from polluting topo::. More...

Data Structures
class	TreeBoundingBoxOn3dTorus
	Utility class to partition the bounding box of a spanning (sub)tree on a 3D mesh machine and divide that into the necessary number of branches. More...
class	vtxEqual
	Hack for PGI and Fujitsu STLport-using compilers because of their incorrect implementation of an STL routine. More...
Functions
template<typename Iterator>
void	buildSpanningTree (SpanningTreeVertex *dispatchTag, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches, SpanningTreeStrategy< Iterator > *bldr)
	Tag dispatched function that does the actual work of building the complete spanning tree.
template<typename Iterator>
void	checkSection (const Iterator start, const Iterator end, const Iterator p1, const Iterator p2)
int	modulo (int k, int n)
template<typename Iterator>
SpanningTreeVertex *	buildNextGen_nodeAware_minBytes (const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
	Separates on-node PEs into separate sub-tree(s) and then builds a dumb spanning tree for the off-node PEs.
template<typename Iterator>
SpanningTreeVertex *	buildNextGen_nodeAware_minGens (const vtxType parentPE, const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)
	Common implementation for all value_types.
template<typename Iterator>
SpanningTreeVertex *	buildNextGen_topoUnaware (const Iterator firstVtx, const Iterator beyondLastVtx, const int maxBranches)

---

Detailed Description

Nested namespace to prevent the implementation muck from polluting topo::.

Implementation artifacts shouldnt pollute topo::.

---

Function Documentation

template<typename Iterator>

void topo::impl::buildSpanningTree	(	SpanningTreeVertex *	dispatchTag,
		const Iterator	firstVtx,
		const Iterator	beyondLastVtx,
		const int	maxBranches,
		SpanningTreeStrategy< Iterator > *	bldr
	)			[inline]

Tag dispatched function that does the actual work of building the complete spanning tree.

Validate input. Invalid inputs are not exceptions. They are just no-ops

Build the next generation of the tree rooted at *firstVtx

Delete the copy of firstVtx that gets returned from the call

For each direct child...

Identify the range of vertices that are part of this subtree

Build this subtree

Definition at line 232 of file spanningTreeStrategy.h.

References advance(), topo::buildSpanningTreeGeneration(), and topo::SpanningTreeVertex::childIndex.

Referenced by topo::buildSpanningTree().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

void topo::impl::checkSection	(	const Iterator	start,
		const Iterator	end,
		const Iterator	p1,
		const Iterator	p2
	)			[inline]

Definition at line 229 of file treeStrategy_3dTorus_minHops.h.

References PUP::d.

Referenced by topo::impl::TreeBoundingBoxOn3dTorus< Iterator >::bisect(), and topo::impl::TreeBoundingBoxOn3dTorus< Iterator >::trisect().

Here is the caller graph for this function:

int topo::impl::modulo	(	int	k,
		int	n
	)			[inline]

Definition at line 416 of file treeStrategy_3dTorus_minHops.h.

Referenced by topo::impl::TreeBoundingBoxOn3dTorus< Iterator >::translateCoordinates().

Here is the caller graph for this function:

template<typename Iterator>

SpanningTreeVertex * topo::impl::buildNextGen_nodeAware_minBytes	(	const vtxType	parentPE,
		const Iterator	firstVtx,
		const Iterator	beyondLastVtx,
		const int	maxBranches = 2
	)			[inline]

Separates on-node PEs into separate sub-tree(s) and then builds a dumb spanning tree for the off-node PEs.

------------- Obtain a list of all PEs on this physical machine node -------------

------------- Identify the PEs that are on the same node as the tree root ------------- The number of local destinations (same node PEs) and the number of branches that will span these destinations

The object that will hold the final results

Scan the tree members until we identify all possible same node PEs or run out of tree members

Try to find the next same-node PE

If such a PE was found...

------------- Construct a generation in the tree with local sub-tree(s) if necessary ------------- If there are any local vertices at all

Determine how many branches can be used to span the local destinations

<

Warning:

: This is O(treeSize) for Iterator != random iterator

Distribute the local destination vertices amongst numLocalBranches branches

Construct a topo-unaware tree for the rest (off-node PEs) of the vertices

< Abuse the interface by faking lastLocal as the tree root

Append the remote sub-tree info to the result object

Return the output structure

Definition at line 62 of file treeStrategy_nodeAware_minBytes.h.

References buildNextGen_topoUnaware(), topo::SpanningTreeVertex::childIndex, Converse::CkNumPes(), CmiGetPesOnPhysicalNode(), CmiPhysicalNodeID(), std::distance(), n, and parent().

Referenced by topo::topo::SpanningTreeStrategy_nodeAware_minBytes< Iterator, SpanningTreeVertex >::buildNextGen(), and topo::SpanningTreeStrategy_nodeAware_minBytes< Iterator, ValueType >::buildNextGen().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

SpanningTreeVertex * topo::impl::buildNextGen_nodeAware_minGens	(	const vtxType	parentPE,
		const Iterator	firstVtx,
		const Iterator	beyondLastVtx,
		const int	maxBranches
	)			[inline]

Common implementation for all value_types.

The differences (obtaining the parent PE) for different value_types are handled at the call location itself.

Simply generates a balanced tree in a topo unaware manner and then promotes any same node PEs as direct children

Construct the next generation in a blind, aware-of-nothing manner

Obtain a list of all PEs on this physical machine node

Find any (upto maxBranches) tree members that are on the same node and make them the direct children

Scan the tree members until we identify same node PEs for all direct children or run out of tree members

Search the tree members for a PE on this node that is not already a direct child

Check if this vertex is already a direct child

Search the child locations for the first slot that does not have a same-node PE

Check if this child is already on the same node

If a same-node PE is found and a child slot without a same-node PE exists

Return the output structure

Definition at line 92 of file treeStrategy_nodeAware_minGens.h.

References advance(), buildNextGen_topoUnaware(), topo::SpanningTreeVertex::childIndex, Converse::CkNumPes(), CmiGetPesOnPhysicalNode(), CmiPhysicalNodeID(), std::distance(), and parent().

Referenced by topo::topo::SpanningTreeStrategy_nodeAware_minGens< Iterator, SpanningTreeVertex >::buildNextGen(), and topo::SpanningTreeStrategy_nodeAware_minGens< Iterator, ValueType >::buildNextGen().

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Iterator>

SpanningTreeVertex * topo::impl::buildNextGen_topoUnaware	(	const Iterator	firstVtx,
		const Iterator	beyondLastVtx,
		const int	maxBranches
	)			[inline]

Invalid inputs are not exceptions. They are just no-ops

Return data holds the parent vertex info [and child info, if there are any]

Compute the number of vertices in each branch

Push the appropriate relative distances (from the tree root) into the container of child indices

Distribute any remainder vertices as evenly as possible amongst all the branches

Compute the number of vertices in each branch

Push the appropriate relative distances (from the tree root) into the container of child indices

Distribute any remainder vertices as evenly as possible amongst all the branches

Return the output structure

Definition at line 59 of file treeStrategy_topoUnaware.h.

References topo::SpanningTreeVertex::childIndex, CmiNodeOf(), std::distance(), topo::getProcID(), and parent().

Referenced by topo::topo::SpanningTreeStrategy_topoUnaware< Iterator, SpanningTreeVertex >::buildNextGen(), topo::SpanningTreeStrategy_topoUnaware< Iterator, ValueType >::buildNextGen(), topo::topo::SpanningTreeStrategy_3dTorus_minBytesHops< Iterator, SpanningTreeVertex >::buildNextGen(), buildNextGen_nodeAware_minBytes(), and buildNextGen_nodeAware_minGens().

Here is the call graph for this function:

Here is the caller graph for this function: