Upscaler< T > Class Template Reference

Transforms SBD-structures over q parts into an SBD structure over p parts, with q>p, and q,p both powers of two. More...

#include <Upscaler.hpp>

Inheritance diagram for Upscaler< T >:

Collaboration diagram for Upscaler< T >:

Classes
class	treeInOrderIterator
	Same as treeIterator, but does in-order traversal instead of pre-order. More...
class	treeIterator
	Pre-order tree iterator. More...
class	treePostOrderIterator
	Same as treeIterator, but does post-order traversal instead of pre-order. More...

Public Member Functions
	Upscaler (const std::vector< Triplet< T > > &nonzeroes, const unsigned long int P, std::vector< unsigned long int > &r_hierarchy, std::vector< unsigned long int > &c_hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds, unsigned long int *row_perm=NULL, unsigned long int *col_perm=NULL, unsigned long int *proc2proc=NULL)
	Base constructor. More...
	~Upscaler ()
	Base deconstructor. More...
void	getSubTree (const unsigned long int s, std::vector< Triplet< T > > &local_nonzeroes, std::vector< Triplet< T > > &remote_nonzeroes, std::vector< unsigned long int > &upscaled_hierarchy, std::vector< unsigned long int > &upscaled_row_bounds, std::vector< unsigned long int > &upscaled_column_bounds, std::vector< unsigned long int > &rowLocalToGlobal, std::vector< unsigned long int > &columnLocalToGlobal, std::map< unsigned long int, unsigned long int > &rowGlobalToLocal, std::map< unsigned long int, unsigned long int > &colGlobalToLocal, const unsigned long int P, const unsigned long int Pref)
	Reads out a subtree corresponding to only the nonzeroes owned by processor s, and returns the upscaled version. More...
void	readout ()
	Reads out SBD data and prints to std::cout. More...
Public Member Functions inherited from SBDTree
	SBDTree (std::vector< unsigned long int > &r_hierarchy, std::vector< unsigned long int > &c_hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds)
	Base constructor.
	SBDTree (std::vector< unsigned long int > &hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds)
	Base constructor. More...
	~SBDTree ()
	Base deconstructor. More...
void	getSeparatorBB (const unsigned long int index, unsigned long int &r_lo, unsigned long int &r_hi, unsigned long int &c_lo, unsigned long int &c_hi)
	Gets, from a separator node, the bounding box of the nonzeroes contained in the separator. More...
unsigned long int	up (const unsigned long int index)
	Returns the parent of a given node. More...
unsigned long int	left (const unsigned long int index)
	Returns the left child of a given node. More...
unsigned long int	right (const unsigned long int index)
	Returns the right child of a given node. More...
void	rowBounds (const unsigned long int index, unsigned long int &r_lo, unsigned long int &r_hi)
	Returns the row bounds corresponding to a given node. More...
void	columnBounds (const unsigned long int index, unsigned long int &c_lo, unsigned long int &c_hi)
	Returns the column bounds corresponding to a given node. More...
char	isLeaf (const unsigned long int index)
	Whether the given node is a leaf node.
unsigned long int	size ()
	Gets the number of nodes.
unsigned long int	getRoot ()
	Gets the root index.

Protected Member Functions
void	determineEmpty (const std::vector< Triplet< T > > &nonzeroes, const unsigned long int s, const unsigned long int min_i, const unsigned long int min_j, std::vector< bool > &emptyRows, std::vector< bool > &emptyCols, bool &empty)
	Determines, given a collection of nonzeroes, which rows and columns nonzeroes owned by s reside on, and flags these rows and columns used in the appropriate vectors. More...
void	updateMinMax (const unsigned long int walk, const unsigned long int s, unsigned long int &min_i, unsigned long int &max_i, unsigned long int &min_j, unsigned long int &max_j)
	Determine min/max of nonzeroes owned by processor s inside node walk. More...
void	determineMinMax (const unsigned long int ID, const unsigned long int s, unsigned long int &min_i, unsigned long int &max_i, unsigned long int &min_j, unsigned long int &max_j)
	Determine min/max of nonzeroes owned by processor s, contained in the subtree with root ID, as well as all separators on the path from ID to the true root.
void	addNonzeroes (std::vector< Triplet< T > > &into, const unsigned long int from, const unsigned long int s, const std::map< unsigned long int, unsigned long int > &rowGlobalToLocal, const std::map< unsigned long int, unsigned long int > &colGlobalToLocal)
	adds nonzeroes from a given node into a given vector
void	getSubTree (const unsigned long int ID, const unsigned long int s, std::vector< Triplet< T > > &local_nonzeroes, std::vector< Triplet< T > > &remote_nonzeroes, std::vector< unsigned long int > &upscaled_hierarchy, std::vector< unsigned long int > &upscaled_row_bounds, std::vector< unsigned long int > &upscaled_column_bounds, std::vector< unsigned long int > &rowLocalToGlobal, std::vector< unsigned long int > &columnLocalToGlobal, std::map< unsigned long int, unsigned long int > &rowGlobalToLocal, std::map< unsigned long int, unsigned long int > &colGlobalToLocal)
	Reads out a subtree and returns the upscaled version. More...
Protected Member Functions inherited from SBDTree
void	build (std::vector< unsigned long int > &hierarchy, std::vector< unsigned long int > &r_bounds, std::vector< unsigned long int > &c_bounds)
	Builds the SBD tree using three input vectors. More...

Protected Attributes
std::vector< std::vector < Triplet< T > > >	nonzeroes
	All nonzeroes, stored block-by-block. More...
std::vector< std::vector< bool > >	containsPID
	Keeps track which processes are represented in which blocks. More...
Protected Attributes inherited from SBDTree
unsigned long int *	parent
	Array s.t. More...
unsigned long int *	left_child
	Array s.t. More...
unsigned long int *	right_child
	Array s.t. More...
unsigned long int *	r_lo
	Array s.t. More...
unsigned long int *	r_hi
	Array s.t. More...
unsigned long int *	c_lo
	Array s.t. More...
unsigned long int *	c_hi
	Array s.t. More...
unsigned long int	root
	Which node ID corresponds to the root. More...
unsigned long int	nodes
	The total number of tree nodes. More...
char	root_is_set
	Whether the root node is set. More...

Additional Inherited Members
Static Protected Attributes inherited from SBDTree
static const unsigned long int	NO_SUCH_NODE = ULONG_MAX
	Integer corresponding to non-existing nodes. More...

Detailed Description

template<typename T>
class Upscaler< T >

Transforms SBD-structures over q parts into an SBD structure over p parts, with q>p, and q,p both powers of two.

Constructor & Destructor Documentation

template<typename T>

Upscaler< T >::Upscaler ( const std::vector< Triplet< T > > &  nonzeroes, const unsigned long int  P, std::vector< unsigned long int > &  r_hierarchy, std::vector< unsigned long int > &  c_hierarchy, std::vector< unsigned long int > &  r_bounds, std::vector< unsigned long int > &  c_bounds, unsigned long int *  row_perm = NULL, unsigned long int *  col_perm = NULL, unsigned long int *  proc2proc = NULL  )

inline

Base constructor.

References SBDTree::c_hi, SBDTree::c_lo, Upscaler< T >::containsPID, Upscaler< T >::nonzeroes, SBDTree::parent, SBDTree::r_hi, SBDTree::r_lo, SBDTree::root, and SBDTree::size().

template<typename T>

Upscaler< T >::~Upscaler ( )

inline

Base deconstructor.

Member Function Documentation

template<typename T>

void Upscaler< T >::determineEmpty ( const std::vector< Triplet< T > > &  nonzeroes, const unsigned long int  s, const unsigned long int  min_i, const unsigned long int  min_j, std::vector< bool > &  emptyRows, std::vector< bool > &  emptyCols, bool &  empty  )

inlineprotected

Determines, given a collection of nonzeroes, which rows and columns nonzeroes owned by s reside on, and flags these rows and columns used in the appropriate vectors.

Parameters

nonzeroes	The collection of nonzeroes.
s	The process ID.
min_i	Minimum row index to consider (other nonzeroes are ignored).
min_j	Minimum column index to consider (other nonzeroes are ignored).
emptyRows	emptyRows[i] is true when no nonzeroes on row i are encountered.
emptyCols	emptyCols[j] is true when no nonzeroes on column j exist.
empty	Will be true when process s has no nonzeroes in this collection.

References Upscaler< T >::nonzeroes.

Referenced by Upscaler< T >::getSubTree().

template<typename T>

void Upscaler< T >::getSubTree ( const unsigned long int  ID, const unsigned long int  s, std::vector< Triplet< T > > &  local_nonzeroes, std::vector< Triplet< T > > &  remote_nonzeroes, std::vector< unsigned long int > &  upscaled_hierarchy, std::vector< unsigned long int > &  upscaled_row_bounds, std::vector< unsigned long int > &  upscaled_column_bounds, std::vector< unsigned long int > &  rowLocalToGlobal, std::vector< unsigned long int > &  columnLocalToGlobal, std::map< unsigned long int, unsigned long int > &  rowGlobalToLocal, std::map< unsigned long int, unsigned long int > &  colGlobalToLocal  )

inlineprotected

Reads out a subtree and returns the upscaled version.

Does global to local index translation. The non-binary part of the tree is returned in remote_nonzeroes and are not part of the upscaled_hierarchy structures.

Parameters

ID	root of the subtree to read out.
s	only output nonzeroes distributed to processor s.
local_nonzeroes	nonzeroes corresponding to this new tree (flat vector).
remote_nonzeroes	nonzeroes belonging to s contained in the path from ID to the root.
upscaled_hierarchy	hierarchy corresponding to the upscaled nonzeroes.
upscaled_row_bounds	row-wise boundaries corresponding to the upscaled nonzeroes.
upscaled_column_bounds	column-wise boundaries corresponding to the upscaled nonzeroes.
rowLocalToGlobal	maps local row indices to global indices.
columnLocalToGlobal	maps local column indices to global indices.
rowGlobalToLocal	maps global row indices to local indices.
colGlobalToLocal	maps global column indices to local indices.

References Upscaler< T >::addNonzeroes(), SBDTree::c_hi, SBDTree::c_lo, Upscaler< T >::determineEmpty(), Upscaler< T >::determineMinMax(), Upscaler< T >::treeIterator::next(), Upscaler< T >::treeInOrderIterator::next(), SBDTree::NO_SUCH_NODE, Upscaler< T >::nonzeroes, SBDTree::parent, Upscaler< T >::treeIterator::position(), SBDTree::r_hi, SBDTree::r_lo, SBDTree::root, and SBDTree::size().

Referenced by Upscaler< T >::getSubTree().

template<typename T>

void Upscaler< T >::getSubTree ( const unsigned long int  s, std::vector< Triplet< T > > &  local_nonzeroes, std::vector< Triplet< T > > &  remote_nonzeroes, std::vector< unsigned long int > &  upscaled_hierarchy, std::vector< unsigned long int > &  upscaled_row_bounds, std::vector< unsigned long int > &  upscaled_column_bounds, std::vector< unsigned long int > &  rowLocalToGlobal, std::vector< unsigned long int > &  columnLocalToGlobal, std::map< unsigned long int, unsigned long int > &  rowGlobalToLocal, std::map< unsigned long int, unsigned long int > &  colGlobalToLocal, const unsigned long int  P, const unsigned long int  Pref  )

inline

Reads out a subtree corresponding to only the nonzeroes owned by processor s, and returns the upscaled version.

Does global to local index translation. The non-binary part of the tree is returned in remote_nonzeroes and are not part of the upscaled_hierarchy structures.

Parameters

s	only output nonzeroes distributed to processor s.
local_nonzeroes	nonzeroes corresponding to this new tree (flat vector).
remote_nonzeroes	nonzeroes belonging to s contained in the path from ID to the root.
upscaled_hierarchy	hierarchy corresponding to the upscaled nonzeroes.
upscaled_row_bounds	row-wise boundaries corresponding to the upscaled nonzeroes.
upscaled_column_bounds	column-wise boundaries corresponding to the upscaled nonzeroes.
rowLocalToGlobal	maps local row indices to global indices.
columnLocalToGlobal	maps local column indices to global indices.
rowGlobalToLocal	maps global row indices to local indices.
colGlobalToLocal	maps global column indices to local indices.
P	The total number of parts to reduce the SBD tree to.
Pref	The total number of parts (blocks) in this SBD tree.

References Upscaler< T >::getSubTree(), SBDTree::left_child, Upscaler< T >::treeIterator::next(), Upscaler< T >::treePostOrderIterator::next(), SBDTree::NO_SUCH_NODE, Upscaler< T >::nonzeroes, Upscaler< T >::treeIterator::position(), SBDTree::right_child, SBDTree::root, and SBDTree::size().

template<typename T>

void Upscaler< T >::readout ( )

inline

Reads out SBD data and prints to std::cout.

Useful for debugging purposes.

References SBDTree::left_child, SBDTree::NO_SUCH_NODE, SBDTree::parent, SBDTree::right_child, and SBDTree::size().

template<typename T>

void Upscaler< T >::updateMinMax ( const unsigned long int  walk, const unsigned long int  s, unsigned long int &  min_i, unsigned long int &  max_i, unsigned long int &  min_j, unsigned long int &  max_j  )

inlineprotected

Determine min/max of nonzeroes owned by processor s inside node walk.

References Upscaler< T >::nonzeroes.

Referenced by Upscaler< T >::determineMinMax().

Member Data Documentation

template<typename T>

std::vector< std::vector< bool > > Upscaler< T >::containsPID

protected

Keeps track which processes are represented in which blocks.

Referenced by Upscaler< T >::Upscaler().

template<typename T>

std::vector< std::vector< Triplet< T > > > Upscaler< T >::nonzeroes

protected

All nonzeroes, stored block-by-block.

Referenced by Upscaler< T >::addNonzeroes(), Upscaler< T >::determineEmpty(), Upscaler< T >::getSubTree(), Upscaler< T >::updateMinMax(), and Upscaler< T >::Upscaler().

---

The documentation for this class was generated from the following file:

• Upscaler.hpp