src / oct

Balance.C File Reference

A set of functions for 2:1 balancing octrees. More...

#include "parUtils.h"
#include "seqUtils.h"
#include "TreeNode.h"
#include "TreeNodePointer.h"
#include "testUtils.h"
#include "dendro.h"

Go to the source code of this file.

Namespaces

namespace ot

Functions

int balanceBlocks (const std::vector< TreeNode > &inp, const std::vector< TreeNode > &blocks, std::vector< TreeNode > &nodes, std::vector< TreeNode > &allBoundaryLeaves, bool incCorner, std::vector< unsigned int > *maxBlockBndVec)

int balanceOctree (std::vector< TreeNode > &in, std::vector< TreeNode > &out, unsigned int dim, unsigned int maxDepth, bool incCorner, MPI_Comm comm, MPI_Comm *newCommPtr, bool *iAmActive)

Parallel 2:1 hybrid balance function. It uses a combination of search free and search based approaches to balancing. It does not use parallel searches. Instead, it uses a-priori communication and the concept of insulation layers to de-couple the problem of balancing.

int comboRipple (std::vector< TreeNode > &in, bool incCorner, const unsigned int maxNum)

int finalMergeInBal (std::vector< ot::TreeNode > &out, std::vector< ot::TreeNode > &allBoundaryLeaves)

int mergeComboBalAndPickBoundary (std::vector< ot::TreeNode > &out, std::vector< ot::TreeNode > &allBoundaryLeaves, const ot::TreeNode &firstBlock, const ot::TreeNode &lastBlock)

Merge the input of ConBal and intra-processor ripple bal and pick the inter-processor boundaries from the result.

int mergeRecvKeysInBal (const std::vector< ot::TreeNode > &recvK1, const int *recvOffsets1, const std::vector< ot::TreeNode > &recvK2, const int *recvOffsets2, int npes, std::vector< ot::TreeNode > &recvK)

int parallelRippleType1 (std::vector< TreeNode > &nodes, bool incCorners, bool checkBailOut, bool rePart, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)

An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.

int parallelRippleType2 (std::vector< TreeNode > &nodes, bool incCorners, bool checkBailOut, bool rePart, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)

An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.

int parallelRippleType3 (std::vector< TreeNode > &nodes, bool incCorners, bool checkBailOut, bool rePart, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)

An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.

int pointerBasedRipple (std::vector< ot::TreeNode > &nodes, bool incCorners)

Sequential ripple propagation algorithm using pointer based octree representation (internally). The input (linear) octree need not be complete. It can have holes.

int prepareBalComm1MessagesType1 (const std::vector< ot::TreeNode > &allBoundaryLeaves, const std::vector< ot::TreeNode > &myNhBlocks, int npes, unsigned int maxDepth, std::vector< TreeNode > *sendNodes, std::vector< unsigned int > *sentToPid, int *sendCnt)

int prepareBalComm1MessagesType2 (const std::vector< ot::TreeNode > &allBoundaryLeaves, const std::vector< ot::TreeNode > &minsAllBlocks, int rank, unsigned int dim, unsigned int maxDepth, std::vector< TreeNode > *sendNodes, std::vector< unsigned int > *sentToPid, int *sendCnt)

int prepareBalComm2Messages (const std::vector< ot::TreeNode > &allBoundaryLeaves, const std::vector< ot::TreeNode > &wList, const std::vector< std::vector< unsigned int > > &wListRanks, std::vector< TreeNode > *sendNodes, std::vector< unsigned int > *sentToPid, int *sendCnt)

int prepareWlistInBal (const std::vector< ot::TreeNode > &recvK1, const int *recvCnt, int npes, const ot::TreeNode &myFirstBlock, const ot::TreeNode &myLastBlock, std::vector< TreeNode > &wList, std::vector< std::vector< unsigned int > > &wListRanks)

int ripple (std::vector< TreeNode > &nodes, bool incCorners)

Sequential ripple propagation algorithm on linear octrees. The octree need not be complete. It can have holes.

int selectNeighboringBlocks (const std::vector< TreeNode > &allBlocks, const std::vector< TreeNode > &blocks, const std::vector< unsigned int > &maxBlockBndVec, int myRank, std::vector< TreeNode > &myNhBlocks)

Detailed Description

A set of functions for 2:1 balancing octrees.

Author:: Rahul S. Sampath, rahul.sampath@gmail.com
Hari Sundar, hsundar@gmail.com

Definition in file Balance.C.

Function Documentation

int ot::balanceBlocks ( const std::vector< TreeNode > & inp,

const std::vector< TreeNode > & blocks,

std::vector< TreeNode > & nodes,

std::vector< TreeNode > & allBoundaryLeaves,

bool incCorners,

std::vector< unsigned int > * maxBlockBndVec = NULL

)

Definition at line 912 of file Balance.C.
References ot::areComparable(), ot::TreeNode::balanceSubtree(), ot::TreeNode::getMaxDepth(), ot::TreeNode::pickInternalBoundaryCells(), PROF_CON_BAL_BEGIN, and PROF_CON_BAL_END.
Referenced by ot::balanceOctree(), and ot::comboRipple().

int ot::balanceOctree ( std::vector< TreeNode > & in,

std::vector< TreeNode > & out,

unsigned int dim,

unsigned int maxDepth,

bool incCorner,

MPI_Comm comm,

MPI_Comm * newCommPtr = NULL,

bool * iAmActive = NULL

)

Parallel 2:1 hybrid balance function. It uses a combination of search free and search based approaches to balancing. It does not use parallel searches. Instead, it uses a-priori communication and the concept of insulation layers to de-couple the problem of balancing.

Author:
Rahul Sampath
Hari Sundar

Parameters:

in a sorted, complete, linear octree

out a sorted, complete, linear, balanced octree

dim the dimension of the tree (1 for binary trees, 2 for quadtrees and 3 for octrees)

maxDepth the maximum depth of the octree must be <= _MAX_LEVEL_

incCorner 'true' to balance across corners as well and 'false' otherwise. in is cleared inside the function

See also:
_MAX_LEVEL_

Definition at line 31 of file Balance.C.
References ot::areComparable(), ot::balanceBlocks(), ot::blockPartStage1(), ot::blockPartStage2(), ot::comboRipple(), DendroIntL, ot::finalMergeInBal(), ot::TreeNode::getDLD(), ot::TreeNode::isAncestor(), ot::mergeComboBalAndPickBoundary(), ot::mergeRecvKeysInBal(), ot::prepareBalComm1MessagesType2(), ot::prepareBalComm2Messages(), ot::prepareWlistInBal(), PROF_BAL_BEGIN, PROF_BAL_BPART1_BEGIN, PROF_BAL_BPART1_END, PROF_BAL_BPART2_BEGIN, PROF_BAL_BPART2_END, PROF_BAL_COMM_BEGIN, PROF_BAL_COMM_END, PROF_BAL_END, PROF_BAL_SCATTER_BEGIN, PROF_BAL_SCATTER_END, PROF_BAL_SPLIT_COMM_BEGIN, PROF_BAL_SPLIT_COMM_END, ot::ripple(), ot::selectNeighboringBlocks(), and par::splitCommUsingSplittingRank().
Referenced by ot::DAMGCreateAndSetDA(), main(), solve_neumann(), and solve_neumann_oct().

int ot::comboRipple ( std::vector< TreeNode > & in,

bool incCorner,

const unsigned int maxNum = _COMBO_RIPPLE_FACTOR_

)

Definition at line 767 of file Balance.C.
References ot::TreeNode::addChildren(), ot::areComparable(), ot::balanceBlocks(), ot::getNCA(), ot::TreeNode::pickInternalBoundaryCells(), PROF_COMBO_RIPPLE_BEGIN, PROF_COMBO_RIPPLE_END, and ot::ripple().
Referenced by ot::balanceOctree().

int ot::finalMergeInBal ( std::vector< ot::TreeNode > & out,

std::vector< ot::TreeNode > & allBoundaryLeaves

)

Author:
Rahul Sampath

Definition at line 2672 of file Balance.C.
References ot::areComparable(), PROF_FINAL_MERGE_IN_BAL_BEGIN, and PROF_FINAL_MERGE_IN_BAL_END.
Referenced by ot::balanceOctree().

int ot::mergeComboBalAndPickBoundary ( std::vector< ot::TreeNode > & out,

std::vector< ot::TreeNode > & allBoundaryLeaves,

const ot::TreeNode & firstBlock,

const ot::TreeNode & lastBlock

)

Merge the input of ConBal and intra-processor ripple bal and pick the inter-processor boundaries from the result.

Author:
Rahul Sampath

Definition at line 2610 of file Balance.C.
References ot::areComparable(), ot::pickInterProcessorBoundaryNodes(), PROF_MERGE_COMBO_BAL_BEGIN, and PROF_MERGE_COMBO_BAL_END.
Referenced by ot::balanceOctree().

int ot::mergeRecvKeysInBal ( const std::vector< ot::TreeNode > & recvK1,

const int * recvOffsets1,

const std::vector< ot::TreeNode > & recvK2,

const int * recvOffsets2,

int npes,

std::vector< ot::TreeNode > & recvK

)

Author:
Rahul Sampath

Definition at line 2954 of file Balance.C.
References PROF_MERGE_RECV_KEYS_BAL_BEGIN, and PROF_MERGE_RECV_KEYS_BAL_END.
Referenced by ot::balanceOctree().

int ot::parallelRippleType1 ( std::vector< TreeNode > & nodes,

bool incCorners,

bool checkBailOut,

bool rePart,

unsigned int dim,

unsigned int maxDepth,

MPI_Comm comm

)

An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.

Author:
Rahul Sampath

See also:
balanceOctree()

Definition at line 2160 of file Balance.C.
References ot::areComparable(), ot::TreeNode::completeSubtree(), ot::TreeNode::getLevel(), ot::TreeNode::getSearchKeys(), PROF_PAR_RIPPLE_TYPE1_BEGIN, and PROF_PAR_RIPPLE_TYPE1_END.
Referenced by main().

int ot::parallelRippleType2 ( std::vector< TreeNode > & nodes,

bool incCorners,

bool checkBailOut,

bool rePart,

unsigned int dim,

unsigned int maxDepth,

MPI_Comm comm

)

An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.

Author:
Rahul Sampath

See also:
balanceOctree()

Definition at line 1766 of file Balance.C.
References ot::areComparable(), ot::TreeNode::completeSubtree(), ot::TreeNode::getLevel(), ot::TreeNode::getSearchKeys(), PROF_PAR_RIPPLE_TYPE2_BEGIN, and PROF_PAR_RIPPLE_TYPE2_END.
Referenced by main().

int ot::parallelRippleType3 ( std::vector< TreeNode > & nodes,

bool incCorners,

bool checkBailOut,

bool rePart,

unsigned int dim,

unsigned int maxDepth,

MPI_Comm comm

)

An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.

Author:
Rahul Sampath

See also:
balanceOctree()

Definition at line 1365 of file Balance.C.
References ot::areComparable(), ot::TreeNode::completeSubtree(), ot::TreeNode::getLevel(), ot::TreeNode::getSearchKeys(), PROF_PAR_RIPPLE_TYPE3_BEGIN, and PROF_PAR_RIPPLE_TYPE3_END.
Referenced by main().

int ot::pointerBasedRipple ( std::vector< ot::TreeNode > & nodes,

bool incCorners

)

Sequential ripple propagation algorithm using pointer based octree representation (internally). The input (linear) octree need not be complete. It can have holes.

Author:
Rahul Sampath

Parameters:

nodes a sorted, linear octree. The octree need not be complete. It can have holes.

incCorners 'true' if you want to balance across corners as well.

Definition at line 1269 of file Balance.C.
References ot::addOctantToTreeNodePointer(), ot::appendOctantsAtLevel(), ot::convertLinearToPointer(), ot::convertPointerToLinear(), ot::deleteTreeNodePointer(), ot::findOctantOrFinestAncestor(), ot::TreeNode::getDim(), ot::TreeNode::getLevel(), ot::TreeNode::getMaxDepth(), ot::TreeNode::getSearchKeys(), ot::TreeNodePointer::m_tnMe, ot::TreeNodePointer::m_tnpMyChildren, PROF_PTR_RIPPLE_BAL_BEGIN, and PROF_PTR_RIPPLE_BAL_END.
Referenced by main().

int ot::prepareBalComm1MessagesType1 ( const std::vector< ot::TreeNode > & allBoundaryLeaves,

const std::vector< ot::TreeNode > & myNhBlocks,

int npes,

unsigned int maxDepth,

std::vector< TreeNode > * sendNodes,

std::vector< unsigned int > * sentToPid,

int * sendCnt

)

Author:
Rahul Sampath

Definition at line 2718 of file Balance.C.
References ot::TreeNode::getWeight(), ot::TreeNode::maxX(), ot::TreeNode::maxY(), ot::TreeNode::maxZ(), ot::TreeNode::minX(), ot::TreeNode::minY(), ot::TreeNode::minZ(), PROF_PREP_BAL_COMM1_MSSG_BEGIN, and PROF_PREP_BAL_COMM1_MSSG_END.

int ot::prepareBalComm1MessagesType2 ( const std::vector< ot::TreeNode > & allBoundaryLeaves,

const std::vector< ot::TreeNode > & minsAllBlocks,

int rank,

unsigned int dim,

unsigned int maxDepth,

std::vector< TreeNode > * sendNodes,

std::vector< unsigned int > * sentToPid,

int * sendCnt

)

Author:
Rahul Sampath

Definition at line 3014 of file Balance.C.
References ot::TreeNode::getAllNeighbours(), PROF_PREP_BAL_COMM1_MSSG_BEGIN, and PROF_PREP_BAL_COMM1_MSSG_END.
Referenced by ot::balanceOctree().

int ot::prepareBalComm2Messages ( const std::vector< ot::TreeNode > & allBoundaryLeaves,

const std::vector< ot::TreeNode > & wList,

const std::vector< std::vector< unsigned int > > & wListRanks,

std::vector< TreeNode > * sendNodes,

std::vector< unsigned int > * sentToPid,

int * sendCnt

)

Author:
Rahul Sampath

Definition at line 2869 of file Balance.C.
References ot::areComparable(), PROF_PREP_BAL_COMM2_MSSG_BEGIN, and PROF_PREP_BAL_COMM2_MSSG_END.
Referenced by ot::balanceOctree().

int ot::prepareWlistInBal ( const std::vector< ot::TreeNode > & recvK1,

const int * recvCnt,

int npes,

const ot::TreeNode & myFirstBlock,

const ot::TreeNode & myLastBlock,

std::vector< TreeNode > & wList,

std::vector< std::vector< unsigned int > > & wListRanks

)

Author:
Rahul Sampath

Definition at line 2768 of file Balance.C.
References ot::areComparable(), ot::TreeNode::getAllNeighbours(), ot::TreeNode::getDLD(), PROF_PREP_BAL_WLIST_BEGIN, PROF_PREP_BAL_WLIST_END, ot::TreeNode::setWeight(), and sort().
Referenced by ot::balanceOctree().

int ot::ripple ( std::vector< TreeNode > & nodes,

bool incCorners

)

Sequential ripple propagation algorithm on linear octrees. The octree need not be complete. It can have holes.

Author:
Rahul Sampath

Parameters:

nodes a sorted, linear octree. The octree need not be complete. It can have holes.

incCorners 'true' if you want to balance across corners as well.

Definition at line 1162 of file Balance.C.
References ot::TreeNode::addBalancingDescendants(), ot::areComparable(), ot::TreeNode::completeSubtree(), ot::TreeNode::getDim(), ot::TreeNode::getLevel(), ot::TreeNode::getMaxDepth(), ot::TreeNode::getSearchKeys(), PROF_RIPPLE_BAL_BEGIN, and PROF_RIPPLE_BAL_END.
Referenced by ot::balanceOctree(), ot::comboRipple(), and main().

int ot::selectNeighboringBlocks ( const std::vector< TreeNode > & allBlocks,

const std::vector< TreeNode > & blocks,

const std::vector< unsigned int > & maxBlockBndVec,

int myRank,

std::vector< TreeNode > & myNhBlocks

)

Author:
Rahul Sampath

Definition at line 2564 of file Balance.C.
References ot::TreeNode::maxX(), ot::TreeNode::maxY(), ot::TreeNode::maxZ(), ot::TreeNode::minX(), ot::TreeNode::minY(), ot::TreeNode::minZ(), PROF_PICK_NH_BLOCKS_BEGIN, and PROF_PICK_NH_BLOCKS_END.
Referenced by ot::balanceOctree().

Generated on Tue Mar 24 16:14:14 2009 for DENDRO by

1.3.9.1


Namespaces
namespace	ot
Functions
int	balanceBlocks (const std::vector< TreeNode > &inp, const std::vector< TreeNode > &blocks, std::vector< TreeNode > &nodes, std::vector< TreeNode > &allBoundaryLeaves, bool incCorner, std::vector< unsigned int > *maxBlockBndVec)
int	balanceOctree (std::vector< TreeNode > &in, std::vector< TreeNode > &out, unsigned int dim, unsigned int maxDepth, bool incCorner, MPI_Comm comm, MPI_Comm newCommPtr, bool iAmActive)
	Parallel 2:1 hybrid balance function. It uses a combination of search free and search based approaches to balancing. It does not use parallel searches. Instead, it uses a-priori communication and the concept of insulation layers to de-couple the problem of balancing.
int	comboRipple (std::vector< TreeNode > &in, bool incCorner, const unsigned int maxNum)
int	finalMergeInBal (std::vector< ot::TreeNode > &out, std::vector< ot::TreeNode > &allBoundaryLeaves)
int	mergeComboBalAndPickBoundary (std::vector< ot::TreeNode > &out, std::vector< ot::TreeNode > &allBoundaryLeaves, const ot::TreeNode &firstBlock, const ot::TreeNode &lastBlock)
	Merge the input of ConBal and intra-processor ripple bal and pick the inter-processor boundaries from the result.
int	mergeRecvKeysInBal (const std::vector< ot::TreeNode > &recvK1, const int recvOffsets1, const std::vector< ot::TreeNode > &recvK2, const int recvOffsets2, int npes, std::vector< ot::TreeNode > &recvK)
int	parallelRippleType1 (std::vector< TreeNode > &nodes, bool incCorners, bool checkBailOut, bool rePart, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)
	An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.
int	parallelRippleType2 (std::vector< TreeNode > &nodes, bool incCorners, bool checkBailOut, bool rePart, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)
	An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.
int	parallelRippleType3 (std::vector< TreeNode > &nodes, bool incCorners, bool checkBailOut, bool rePart, unsigned int dim, unsigned int maxDepth, MPI_Comm comm)
	An implementation of 2:1 balancing using parallel prioritized ripple propagation algorithm.
int	pointerBasedRipple (std::vector< ot::TreeNode > &nodes, bool incCorners)
	Sequential ripple propagation algorithm using pointer based octree representation (internally). The input (linear) octree need not be complete. It can have holes.
int	prepareBalComm1MessagesType1 (const std::vector< ot::TreeNode > &allBoundaryLeaves, const std::vector< ot::TreeNode > &myNhBlocks, int npes, unsigned int maxDepth, std::vector< TreeNode > sendNodes, std::vector< unsigned int > sentToPid, int *sendCnt)
int	prepareBalComm1MessagesType2 (const std::vector< ot::TreeNode > &allBoundaryLeaves, const std::vector< ot::TreeNode > &minsAllBlocks, int rank, unsigned int dim, unsigned int maxDepth, std::vector< TreeNode > sendNodes, std::vector< unsigned int > sentToPid, int *sendCnt)
int	prepareBalComm2Messages (const std::vector< ot::TreeNode > &allBoundaryLeaves, const std::vector< ot::TreeNode > &wList, const std::vector< std::vector< unsigned int > > &wListRanks, std::vector< TreeNode > sendNodes, std::vector< unsigned int > sentToPid, int *sendCnt)
int	prepareWlistInBal (const std::vector< ot::TreeNode > &recvK1, const int *recvCnt, int npes, const ot::TreeNode &myFirstBlock, const ot::TreeNode &myLastBlock, std::vector< TreeNode > &wList, std::vector< std::vector< unsigned int > > &wListRanks)
int	ripple (std::vector< TreeNode > &nodes, bool incCorners)
	Sequential ripple propagation algorithm on linear octrees. The octree need not be complete. It can have holes.
int	selectNeighboringBlocks (const std::vector< TreeNode > &allBlocks, const std::vector< TreeNode > &blocks, const std::vector< unsigned int > &maxBlockBndVec, int myRank, std::vector< TreeNode > &myNhBlocks)