KDNode Class Reference

represents a node in the decomposition tree when using KDDecomposition More...

#include <KDNode.h>

Public Types
typedef MPIKDNodePacked	MPIKDNode

Public Member Functions
	KDNode (const KDNode &other)
	KDNode (int numP, const int low[KDDIM], const int high[KDDIM], int id, int owner, bool coversAll[KDDIM], int level)
bool	equals (KDNode &other)
	~KDNode ()
	The destructor deletes the childs (recursive call of destructors)
KDNode *	findAreaForProcess (int rank)
void	buildKDTree ()
	create an initial decomposition of the domain represented by this node. More...
bool	isResolvable ()
unsigned int	getNumMaxProcs ()
double	calculateAvgLoadPerProc () const
void	calculateDeviationLowerBound (std::vector< double > *accumulatedProcessorSpeeds=nullptr)
void	calculateDeviation (std::vector< double > *processorSpeeds=nullptr, const double &totalMeanProcessorSpeed=1.)
void	getOwningProcs (const int low[KDDIM], const int high[KDDIM], std::vector< int > &procIDs, std::vector< int > &neighbHaloAreas) const
void	split (int divDimension, int splitIndex, int numProcsLeft)
void	printTree (const std::string &prefix, std::ostream &ostream)
	prints this (sub-) tree to stdout More...
void	serialize (const std::string &fileName)
void	deserialize (const std::string &fileName)
void	plotNode (const std::string &vtkFile, const std::vector< double > *processorSpeeds=nullptr) const
MPIKDNode	getMPIKDNode ()

Static Public Member Functions
static void	initMPIDataType ()
static void	shutdownMPIDataType ()

Public Attributes
int	_numProcs
	number of procs which share this area
int	_lowCorner [3]
	in cells relative to global domain
int	_highCorner [3]
	in cells relative to global domain
bool	_coversWholeDomain [KDDIM]
	true if the domain in the given dimension is not divided into more than one process
int	_nodeID
	ID of this KDNode.
int	_owningProc
	process which owns this KDNode (only possible for leaf nodes)
KDNode *	_child1
	"left" child of this KDNode (only used if the child is no leaf)
KDNode *	_child2
	"left" child of this KDNode (only used if the child is no leaf)
double	_load
double	_optimalLoadPerProcess
double	_deviationLowerBound
double	_deviation
int	_level
	level of this node (at root node, level = 0)

Detailed Description

represents a node in the decomposition tree when using KDDecomposition

Author

Martin Buchholz, Wolfgang Eckhardt

The KDDecomposition decomposes the domain by recursively splitting the domain into smaller parts. This class is used to represent this decomposition. The root node of the decomposition covers the whole domain, in the first splitting step, this domain is divided into two parts, where each part then has to be divided into several smaller parts. How many parts/regions there depends on the number of processes, each process will get one region. So the KNNode also has to store how many process "share" the current region The leaf nodes of the tree represent the region of the single processes. The regions (the size of the regions) is not stored in some floating-point length unit but in cells. So it is assumed that the domain is discretised with cells and the decomposition is based on distributing those cells (blocks of cells) to the processes

Member Typedef Documentation

MPIKDNode

typedef MPIKDNodePacked KDNode::MPIKDNode

MPIKDNodes represent the data of a KDNode which has to be sent via MPI. MPIKDNodes can be used directly in MPI Send/Receive operations, with mpi_data_type as type.

Constructor & Destructor Documentation

KDNode()

KDNode::KDNode ( const KDNode &  other )

inline

Copy constructor copies everything except for the children (are set to nullptr!)

Member Function Documentation

buildKDTree()

void KDNode::buildKDTree

(

)

create an initial decomposition of the domain represented by this node.

Build a KDTree representing a simple initial domain decomposition by bipartitioning the area recursively, always in the dimension with the longest extend.

calculateDeviationLowerBound()

void KDNode::calculateDeviationLowerBound ( std::vector< double > *  accumulatedProcessorSpeeds = nullptr )

inline

Calculates a lower bound for the expected deviation.

Parameters

accumulatedProcessorSpeeds

deserialize()

void KDNode::deserialize

(

const std::string &

fileName

)

Read the tree represented by this (root-)node from a (binary) file.

equals()

bool KDNode::equals

(

KDNode &

other

)

compare the tree represented by this node to another tree.

findAreaForProcess()

KDNode * KDNode::findAreaForProcess

(

int

rank

)

Returns

the area for process rank, i.e. the leaf of this tree with (_owningProc == rank) and (_numProcs == 1).

If no corresponding node is found, this method returns nullptr!

getMPIKDNode()

KDNode::MPIKDNode KDNode::getMPIKDNode

(

)

Get a MPIDKNode object representing this KDNode.

getNumMaxProcs()

unsigned int KDNode::getNumMaxProcs

(

)

Returns

maximum number of processes, which could be assigned to this node.

getOwningProcs()

void KDNode::getOwningProcs	(	const int	low[KDDIM],
		const int	high[KDDIM],
		std::vector< int > &	procIDs,
		std::vector< int > &	neighbHaloAreas
	)		const

Parameters

low
high
procIDs
neighbHaloAreas

initMPIDataType()

static void KDNode::initMPIDataType ( )

inlinestatic

Initialize the mpi datatype. Has to be called once initially.

isResolvable()

bool KDNode::isResolvable

(

)

Returns

true, if the node can be resolved for its number of processes (_numProcs), i.e. each process can have a subdomain of at least 2 cells per dimension.

plotNode()

void KDNode::plotNode	(	const std::string &	vtkFile,
		const std::vector< double > *	processorSpeeds = nullptr
	)		const

plot the leafs of the KDTree with vtk.

printTree()

void KDNode::printTree	(	const std::string &	prefix,
		std::ostream &	ostream
	)

prints this (sub-) tree to stdout

For each node, it is printed whether it is a "LEAF" or a "INNER" node, The order of printing is a depth-first walk through the tree, children are always indented two spaces more than there parents

Parameters

prefix

A string which is printed in front of each line

serialize()

void KDNode::serialize

(

const std::string &

fileName

)

Write the tree represented by this (root-)node to a (binary) file, in order to be able to restore the decomposition from disk.

shutdownMPIDataType()

static void KDNode::shutdownMPIDataType ( )

inlinestatic

Free the mpi datatype

split()

void KDNode::split	(	int	divDimension,
		int	splitIndex,
		int	numProcsLeft
	)

Split this node, i.e. create two children (note, that its children must be nullptr before this call!).

Parameters

dimension	the dimension \in [0;KDDIM-1] along which this node is split
splitIndex	the index of the corner cell for the new left child (note: must be in bigger or equal to _lowCorner[divDimension] + (KDDStaticValues::minNumCellsPerDimension-1) and smaller than _highCorner[dimension].
numProcsLeft	the number of processors for the left child. The number of processors for the right child is calculated.

Member Data Documentation

_deviation

double KDNode::_deviation

Deviation of the actual assigned load from the optimal load.

_deviationLowerBound

double KDNode::_deviationLowerBound

This is a lower bound for the deviation of the load from the optimal load.

---

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

• src/parallel/KDNode.h
• src/parallel/KDNode.cpp