#include <tree.hpp>

Inheritance diagram for hmlp::tree::Tree< SETUP, NODEDATA >:

Public Types
typedef SETUP::T	T

typedef Node< SETUP, NODEDATA >	NODE

Public Member Functions
	Tree ()

	~Tree ()

void	Offset (NODE *node, size_t offset)

void	RecursiveMorton (NODE *node, MortonHelper::Recursor r)

void	AllocateNodes (NODE *root)
	Allocate the local tree using the local root with n points and depth l. More...

void	TreePartition ()
	Shared-memory tree partition. More...

vector< size_t >	GetPermutation ()

template<typename KNNTASK >
Data< pair< T, size_t > >	AllNearestNeighbor (size_t n_tree, size_t k, size_t max_depth, pair< T, size_t > initNN, KNNTASK &dummy)

Data< int >	CheckAllInteractions ()

template<typename TASK , typename... Args>
void	TraverseLeafs (TASK &dummy, Args &...args)

template<typename TASK , typename... Args>
void	TraverseUp (TASK &dummy, Args &...args)

template<typename TASK , typename... Args>
void	TraverseDown (TASK &dummy, Args &...args)

template<typename TASK , typename... Args>
void	TraverseUnOrdered (TASK &dummy, Args &...args)
	For unordered traversal, we just call local downward traversal. More...

void	DependencyCleanUp ()

void	ExecuteAllTasks ()

bool	DoOutOfOrder ()

template<typename SUMMARY >
void	Summary (SUMMARY &summary)
	Summarize all events in each level.

Public Attributes
SETUP	setup

size_t	n = 0

size_t	m = 0

size_t	depth = 0

Lock	lock

vector< NODE * >	treelist

unordered_map< size_t, NODE * >	morton2node

Static Public Attributes
static const int	N_CHILDREN = 2

Protected Attributes
vector< size_t >	global_indices

Detailed Description

template<class SETUP, class NODEDATA>
class hmlp::tree::Tree< SETUP, NODEDATA >

end class Setup

Member Typedef Documentation

template<class SETUP, class NODEDATA>

typedef Node<SETUP, NODEDATA> hmlp::tree::Tree< SETUP, NODEDATA >::NODE

Define our tree node type as NODE.

Constructor & Destructor Documentation

template<class SETUP, class NODEDATA>

hmlp::tree::Tree< SETUP, NODEDATA >::Tree ( )

inline

(Default) Tree constructor.

template<class SETUP, class NODEDATA>

hmlp::tree::Tree< SETUP, NODEDATA >::~Tree ( )

inline

(Default) Tree destructor.

Member Function Documentation

template<class SETUP, class NODEDATA>

template<typename KNNTASK >

Data<pair<T, size_t> > hmlp::tree::Tree< SETUP, NODEDATA >::AllNearestNeighbor	(	size_t	n_tree,
		size_t	k,
		size_t	max_depth,
		pair< T, size_t >	initNN,
		KNNTASK &	dummy
	)

inline

end GetTreePermutation()

k-by-N, neighbor pairs.

Use leaf_size = 4 * k.

This loop has to be sequential to avoid race condiditon on NN.

Report accuracy

Randomize metric tree and exhausted search for each leaf node.

Increase leaf_size with less than 80% accuracy.

end for each tree.

Sort neighbor pairs in ascending order.

Check for illegle values.

Return a matrix of neighbor pairs.

template<class SETUP, class NODEDATA>

void hmlp::tree::Tree< SETUP, NODEDATA >::AllocateNodes ( NODE * root )

inline

Allocate the local tree using the local root with n points and depth l.

This routine will be called in two situations: 1) called by Tree::TreePartition(), or 2) called by MPITree::TreePartition().

Compute the global tree depth using std::log2().

Compute the local tree depth.

Clean up and reserve space for local tree nodes.

Push root into the treelist.

Allocate children with BFS (queue solution).

Assign local treenode_id.

Account for the depth of the distributed tree.

Leaf nodes are annotated with this flag

template<class SETUP, class NODEDATA>

Data<int> hmlp::tree::Tree< SETUP, NODEDATA >::CheckAllInteractions ( )

inline

end AllNearestNeighbor()

Get the total depth of the tree.

Number of total leaf nodes.

Create a 2^l-by-2^l table to check all interactions.

Now traverse all tree nodes (excluding the root).

Loop over all near interactions.

Loop over all far interactions.

template<class SETUP, class NODEDATA>

void hmlp::tree::Tree< SETUP, NODEDATA >::DependencyCleanUp ( )

inline

end TraverseUnOrdered()

template<class SETUP, class NODEDATA>

bool hmlp::tree::Tree< SETUP, NODEDATA >::DoOutOfOrder ( )

inline

end ExecuteAllTasks()

template<class SETUP, class NODEDATA>

void hmlp::tree::Tree< SETUP, NODEDATA >::ExecuteAllTasks ( )

inline

end DependencyCleanUp()

template<class SETUP, class NODEDATA>

vector<size_t> hmlp::tree::Tree< SETUP, NODEDATA >::GetPermutation ( )

inline

end TreePartition()

template<class SETUP, class NODEDATA>

void hmlp::tree::Tree< SETUP, NODEDATA >::Offset	(	NODE *	node,
		size_t	offset
	)

inline

Currently only used in DrawInteraction()

template<class SETUP, class NODEDATA>

void hmlp::tree::Tree< SETUP, NODEDATA >::RecursiveMorton	(	NODE *	node,
		MortonHelper::Recursor	r
	)

inline

end Offset()

Return dirctly while no children exist.

Set my MortonID.

Recur to children.

Fill the

template<class SETUP, class NODEDATA>

template<typename TASK , typename... Args>

void hmlp::tree::Tree< SETUP, NODEDATA >::TraverseDown	(	TASK &	dummy,
		Args &...	args
	)

inline

end TraverseUp()

contain at lesat one tree node

traverse the local tree without the root

IMPORTANT: local root alias of the distributed leaf node IMPORTANT: here l must be int, size_t will wrap over

loop over each node at level-l

do not parallelize if there is less nodes than threads

template<class SETUP, class NODEDATA>

template<typename TASK , typename... Args>

void hmlp::tree::Tree< SETUP, NODEDATA >::TraverseLeafs	(	TASK &	dummy,
		Args &...	args
	)

inline

end CheckAllInteractions()

Contain at lesat one tree node.

do not parallelize if there is less nodes than threads

template<class SETUP, class NODEDATA>

template<typename TASK , typename... Args>

void hmlp::tree::Tree< SETUP, NODEDATA >::TraverseUnOrdered	(	TASK &	dummy,
		Args &...	args
	)

inline

For unordered traversal, we just call local downward traversal.

end TraverseDown()

template<class SETUP, class NODEDATA>

template<typename TASK , typename... Args>

void hmlp::tree::Tree< SETUP, NODEDATA >::TraverseUp	(	TASK &	dummy,
		Args &...	args
	)

inline

end TraverseLeafs()

contain at lesat one tree node

traverse the local tree without the root

IMPORTANT: local root alias of the distributed leaf node IMPORTANT: here l must be int, size_t will wrap over

traverse level-by-level in sequential

loop over each node at level-l

do not parallelize if there is less nodes than threads

template<class SETUP, class NODEDATA>

void hmlp::tree::Tree< SETUP, NODEDATA >::TreePartition ( )

inline

Shared-memory tree partition.

end AllocateNodes()

Reset and initialize global indices with lexicographical order.

Reset the warning flag and clean up the treelist

Allocate all tree nodes in advance.

Recursive spliting (topdown).

Compute node and point MortonID.

Compute MortonID recursively.

Construct morton2node map for the local tree.

Adgust gids to the appropriate order.

Member Data Documentation

template<class SETUP, class NODEDATA>

size_t hmlp::tree::Tree< SETUP, NODEDATA >::depth = 0

depth of local tree

template<class SETUP, class NODEDATA>

Lock hmlp::tree::Tree< SETUP, NODEDATA >::lock

Mutex for exclusive right to modify treelist and morton2node.

template<class SETUP, class NODEDATA>

size_t hmlp::tree::Tree< SETUP, NODEDATA >::m = 0

maximum leaf node size

template<class SETUP, class NODEDATA>

unordered_map<size_t, NODE*> hmlp::tree::Tree< SETUP, NODEDATA >::morton2node

Map MortonID to tree nodes. When distributed tree inherits Tree, morton2node will also contain distributed and LET node.

template<class SETUP, class NODEDATA>

size_t hmlp::tree::Tree< SETUP, NODEDATA >::n = 0

number of points

template<class SETUP, class NODEDATA>

SETUP hmlp::tree::Tree< SETUP, NODEDATA >::setup

data shared by all tree nodes

template<class SETUP, class NODEDATA>

vector<NODE*> hmlp::tree::Tree< SETUP, NODEDATA >::treelist

Local tree nodes in the top-down order.

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

/home/chenhany/Projects/hmlp/gofmm/tree.hpp

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Protected Attributes

Detailed Description

template<class SETUP, class NODEDATA> class hmlp::tree::Tree< SETUP, NODEDATA >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class SETUP, class NODEDATA>
class hmlp::tree::Tree< SETUP, NODEDATA >