Trees for collectives

Common primitives to manipulate trees (binary, binomial, flat, chain) used in collectives. More...

Files
file	nm_coll_trees.h
	trees description for collective operations
enum	nm_coll_tree_kind_e {   NM_COLL_TREE_NONE = 0 , NM_COLL_TREE_FLAT , NM_COLL_TREE_CHAIN , NM_COLL_TREE_CHAIN_MODIFIED ,   NM_COLL_TREE_2CHAINS_MODIFIED , NM_COLL_TREE_LADDER , NM_COLL_TREE_BINOMIAL , NM_COLL_TREE_3NOMIAL ,   NM_COLL_TREE_4NOMIAL , NM_COLL_TREE_8NOMIAL , NM_COLL_TREE_16NOMIAL , NM_COLL_TREE_BINARY ,   NM_COLL_TREE_3ARY , NM_COLL_TREE_4ARY , NM_COLL_TREE_8ARY , NM_COLL_TREE_HBINARY ,   NM_COLL_TREE_H4ARY , NM_COLL_TREE_HBINOMIAL , NM_COLL_TREE_H4NOMIAL , NM_COLL_TREE_DEFAULT ,   _NM_COLL_TREE_MAX }
	kind of tree More...
typedef enum nm_coll_tree_kind_e	nm_coll_tree_kind_t
void	nm_coll_tree_init (struct nm_coll_tree_info_s *p_tree, nm_coll_tree_kind_t kind, int n, int self, const struct nm_coll_topology_s *p_topology, int root)
void	nm_coll_tree_step (const struct nm_coll_tree_info_s *p_tree, int step, int *p_parent, int *p_children, int *n_children)
	get the parent & children for the local node at the given step.
void	nm_coll_tree_destroy (struct nm_coll_tree_info_s *p_tree)
int	nm_coll_tree_weight (const struct nm_coll_tree_info_s *p_tree, int step, int self)
const char *	nm_coll_tree_kind_name (nm_coll_tree_kind_t kind)
nm_coll_tree_kind_t	nm_coll_tree_kind_by_name (const char *s_kind)
int	nm_coll_tree_has_weight (nm_coll_tree_kind_t k)
void	nm_coll_tree_descendants (const struct nm_coll_tree_info_s *p_tree, int step, int self, int *p_descendants)
	get all the leaves below the 'self' vertex, including self
int	nm_coll_tree_has_descendants (nm_coll_tree_kind_t k)
	whether this coll_tree kind implements 'descendants' method for scatter/gather
nm_coll_tree_kind_t	nm_coll_tree_heuristic (int comm_size, nm_len_t data_size, const struct nm_coll_topology_s *p_topology)
	heuristic to select a coll_tree kind for a generic tree-based collective
nm_coll_tree_kind_t	nm_coll_tree_weight_heuristic (int comm_size, nm_len_t data_size, const struct nm_coll_topology_s *p_topology)
	heuristic to select a coll_tree kind for a tree-based collective that needs weights (scatter/gather)
int	nm_coll_binary_nb_nodes_in_left_subtree (const struct nm_coll_tree_info_s *const p_tree)
static int	nm_coll_tree_max_weight (const struct nm_coll_tree_info_s *p_tree)
	find the weight for the local process, without knowing at wich step we have a parent
static int	nm_coll_ispow2 (int x)
static int	nm_coll_log2_floor (int x)
	floor(log2(x))
static int	nm_coll_log2_ceil (int x)
	ceil(log2(x))
static int	nm_coll_log4_floor (int x)
	floor(log4(x))
static int	nm_coll_ipow (int base, int exp)
	fast integer power() = base ^ exp
static int	nm_coll_log_n_ceil (int x, const int n)
	ceil(log_n(x))
static int	nm_coll_log_n_floor (int x, const int n)
	floor(log_n(x)
static int	nm_coll_r2v (int i, const struct nm_coll_tree_info_s *p_tree)
	translate real ranks to virtual ranks (with root=0)
static int	nm_coll_v2r (int i, const struct nm_coll_tree_info_s *p_tree)
	translate virtual ranks (with root=0) to real ranks
static void	nm_coll_tree_status_init (struct nm_coll_tree_status_s *p_status, nm_session_t p_session, nm_coll_tree_kind_t kind, nm_group_t p_group, int root, int self, nm_tag_t tag)
	initialize a common status for non-blocking collective
static void	nm_coll_tree_status_destroy (struct nm_coll_tree_status_s *p_status)
static void	nm_coll_tree_send (struct nm_coll_tree_status_s *p_coll_tree, int dest, struct nm_data_s *p_data, nm_sr_request_t *p_req)
static void	nm_coll_tree_issend (struct nm_coll_tree_status_s *p_coll_tree, int dest, struct nm_data_s *p_data, nm_sr_request_t *p_req)
static void	nm_coll_tree_recv (struct nm_coll_tree_status_s *p_coll_tree, int from, struct nm_data_s *p_data, nm_sr_request_t *p_req)
static void	nm_coll_tree_set_notifier (struct nm_coll_tree_status_s *p_coll_tree, nm_sr_request_t *p_req, void(*p_notifier)(nm_sr_event_t, const nm_sr_event_info_t *, void *))
static int	nm_coll_tree_req_index (struct nm_coll_tree_status_s *p_coll_tree, nm_sr_request_t *p_request)

Detailed Description

Common primitives to manipulate trees (binary, binomial, flat, chain) used in collectives.

Typedef Documentation

nm_coll_tree_kind_t

typedef enum nm_coll_tree_kind_e nm_coll_tree_kind_t

Definition at line 59 of file nm_coll_trees.h.

Enumeration Type Documentation

nm_coll_tree_kind_e

enum nm_coll_tree_kind_e

kind of tree

Enumerator
NM_COLL_TREE_NONE
NM_COLL_TREE_FLAT
NM_COLL_TREE_CHAIN
NM_COLL_TREE_CHAIN_MODIFIED	HPL ring-modified algorithm.
NM_COLL_TREE_2CHAINS_MODIFIED	HPL 2-rings modified.
NM_COLL_TREE_LADDER
NM_COLL_TREE_BINOMIAL
NM_COLL_TREE_3NOMIAL
NM_COLL_TREE_4NOMIAL
NM_COLL_TREE_8NOMIAL
NM_COLL_TREE_16NOMIAL
NM_COLL_TREE_BINARY
NM_COLL_TREE_3ARY
NM_COLL_TREE_4ARY
NM_COLL_TREE_8ARY
NM_COLL_TREE_HBINARY
NM_COLL_TREE_H4ARY
NM_COLL_TREE_HBINOMIAL
NM_COLL_TREE_H4NOMIAL
NM_COLL_TREE_DEFAULT	for public interfaces, will fallback to one of the previous tree kinds
_NM_COLL_TREE_MAX

Definition at line 35 of file nm_coll_trees.h.

Function Documentation

nm_coll_binary_nb_nodes_in_left_subtree()

int nm_coll_binary_nb_nodes_in_left_subtree

(

const struct nm_coll_tree_info_s *const

p_tree

)

Deprecated:

not to break compilation of coll_dynamic

nm_coll_ipow()

static int nm_coll_ipow ( int  base, int  exp  )

inlinestatic

fast integer power() = base ^ exp

Definition at line 158 of file nm_coll_trees.h.

References assert().

Here is the call graph for this function:

nm_coll_ispow2()

static int nm_coll_ispow2 ( int  x )

inlinestatic

Definition at line 132 of file nm_coll_trees.h.

nm_coll_log2_ceil()

static int nm_coll_log2_ceil ( int  x )

inlinestatic

ceil(log2(x))

Definition at line 145 of file nm_coll_trees.h.

References assert(), and nm_coll_log2_floor().

Here is the call graph for this function:

nm_coll_log2_floor()

static int nm_coll_log2_floor ( int  x )

inlinestatic

floor(log2(x))

Definition at line 138 of file nm_coll_trees.h.

References assert().

Referenced by nm_coll_log2_ceil(), and nm_coll_log4_floor().

Here is the call graph for this function:

nm_coll_log4_floor()

static int nm_coll_log4_floor ( int  x )

inlinestatic

floor(log4(x))

Definition at line 152 of file nm_coll_trees.h.

References nm_coll_log2_floor().

Here is the call graph for this function:

nm_coll_log_n_ceil()

static int nm_coll_log_n_ceil ( int  x, const int  n  )

inlinestatic

ceil(log_n(x))

Definition at line 185 of file nm_coll_trees.h.

References assert().

Here is the call graph for this function:

nm_coll_log_n_floor()

static int nm_coll_log_n_floor ( int  x, const int  n  )

inlinestatic

floor(log_n(x)

Definition at line 202 of file nm_coll_trees.h.

References assert().

Here is the call graph for this function:

nm_coll_r2v()

static int nm_coll_r2v ( int  i, const struct nm_coll_tree_info_s *  p_tree  )

inlinestatic

translate real ranks to virtual ranks (with root=0)

Definition at line 216 of file nm_coll_trees.h.

References nm_coll_tree_info_s::n, and nm_coll_tree_info_s::root.

nm_coll_tree_descendants()

void nm_coll_tree_descendants	(	const struct nm_coll_tree_info_s *	p_tree,
		int	step,
		int	self,
		int *	p_descendants
	)

get all the leaves below the 'self' vertex, including self

nm_coll_tree_destroy()

void nm_coll_tree_destroy

(

struct nm_coll_tree_info_s *

p_tree

)

Referenced by nm_coll_tree_status_destroy().

nm_coll_tree_has_descendants()

int nm_coll_tree_has_descendants

(

nm_coll_tree_kind_t

k

)

whether this coll_tree kind implements 'descendants' method for scatter/gather

nm_coll_tree_has_weight()

int nm_coll_tree_has_weight

(

nm_coll_tree_kind_t

k

)

nm_coll_tree_heuristic()

nm_coll_tree_kind_t nm_coll_tree_heuristic	(	int	comm_size,
		nm_len_t	data_size,
		const struct nm_coll_topology_s *	p_topology
	)

heuristic to select a coll_tree kind for a generic tree-based collective

nm_coll_tree_init()

void nm_coll_tree_init	(	struct nm_coll_tree_info_s *	p_tree,
		nm_coll_tree_kind_t	kind,
		int	n,
		int	self,
		const struct nm_coll_topology_s *	p_topology,
		int	root
	)

Referenced by nm_coll_tree_status_init().

nm_coll_tree_issend()

static void nm_coll_tree_issend ( struct nm_coll_tree_status_s *  p_coll_tree, int  dest, struct nm_data_s *  p_data, nm_sr_request_t *  p_req  )

inlinestatic

Definition at line 283 of file nm_coll_trees.h.

References assert(), nm_atomic_inc(), nm_group_get_gate(), nm_sr_send_init(), nm_sr_send_issend(), nm_sr_send_pack_data(), p_data, p_gate, nm_coll_tree_status_s::p_group, nm_coll_tree_status_s::p_session, nm_coll_tree_status_s::pending_reqs, and nm_coll_tree_status_s::tag.

Here is the call graph for this function:

nm_coll_tree_kind_by_name()

nm_coll_tree_kind_t nm_coll_tree_kind_by_name

(

const char *

s_kind

)

nm_coll_tree_kind_name()

const char * nm_coll_tree_kind_name

(

nm_coll_tree_kind_t

kind

)

nm_coll_tree_max_weight()

static int nm_coll_tree_max_weight ( const struct nm_coll_tree_info_s *  p_tree )

inlinestatic

find the weight for the local process, without knowing at wich step we have a parent

Definition at line 112 of file nm_coll_trees.h.

References nm_coll_tree_info_s::height, nm_coll_tree_info_s::max_arity, nm_coll_tree_step(), nm_coll_tree_weight(), and nm_coll_tree_info_s::self.

Here is the call graph for this function:

nm_coll_tree_recv()

static void nm_coll_tree_recv ( struct nm_coll_tree_status_s *  p_coll_tree, int  from, struct nm_data_s *  p_data, nm_sr_request_t *  p_req  )

inlinestatic

Definition at line 294 of file nm_coll_trees.h.

References assert(), nm_atomic_inc(), nm_group_get_gate(), nm_sr_irecv_data(), p_data, p_gate, nm_coll_tree_status_s::p_group, nm_coll_tree_status_s::p_session, nm_coll_tree_status_s::pending_reqs, and nm_coll_tree_status_s::tag.

Here is the call graph for this function:

nm_coll_tree_req_index()

static int nm_coll_tree_req_index ( struct nm_coll_tree_status_s *  p_coll_tree, nm_sr_request_t *  p_request  )

inlinestatic

Definition at line 309 of file nm_coll_trees.h.

References assert(), nm_coll_tree_status_s::children_requests, nm_coll_tree_info_s::max_arity, NM_FATAL, and nm_coll_tree_status_s::tree.

Here is the call graph for this function:

nm_coll_tree_send()

static void nm_coll_tree_send ( struct nm_coll_tree_status_s *  p_coll_tree, int  dest, struct nm_data_s *  p_data, nm_sr_request_t *  p_req  )

inlinestatic

Definition at line 274 of file nm_coll_trees.h.

References assert(), nm_atomic_inc(), nm_group_get_gate(), nm_sr_isend_data(), p_data, p_gate, nm_coll_tree_status_s::p_group, nm_coll_tree_status_s::p_session, nm_coll_tree_status_s::pending_reqs, and nm_coll_tree_status_s::tag.

Here is the call graph for this function:

nm_coll_tree_set_notifier()

static void nm_coll_tree_set_notifier ( struct nm_coll_tree_status_s *  p_coll_tree, nm_sr_request_t *  p_req, void(*)(nm_sr_event_t, const nm_sr_event_info_t *, void *)  p_notifier  )

inlinestatic

Definition at line 303 of file nm_coll_trees.h.

References NM_SR_EVENT_FINALIZED, nm_sr_request_monitor_with_ref(), and nm_coll_tree_status_s::p_session.

Here is the call graph for this function:

nm_coll_tree_status_destroy()

static void nm_coll_tree_status_destroy ( struct nm_coll_tree_status_s *  p_status )

inlinestatic

Definition at line 260 of file nm_coll_trees.h.

References assert(), nm_coll_tree_status_s::children, nm_coll_tree_status_s::children_requests, nm_coll_tree_destroy(), nm_coll_tree_status_s::p_group, nm_coll_tree_status_s::p_session, nm_coll_tree_status_s::pending_reqs, and nm_coll_tree_status_s::tree.

Here is the call graph for this function:

nm_coll_tree_status_init()

static void nm_coll_tree_status_init ( struct nm_coll_tree_status_s *  p_status, nm_session_t  p_session, nm_coll_tree_kind_t  kind, nm_group_t  p_group, int  root, int  self, nm_tag_t  tag  )

inlinestatic

initialize a common status for non-blocking collective

Note

when p_notify is called, p_status is already destroyed

Definition at line 246 of file nm_coll_trees.h.

References nm_coll_tree_status_s::children, nm_coll_tree_status_s::children_requests, nm_coll_tree_info_s::kind, nm_coll_tree_info_s::max_arity, nm_coll_tree_status_s::n_children, nm_coll_tree_init(), nm_group_get_topology(), nm_group_size(), nm_coll_tree_status_s::p_group, p_session, nm_coll_tree_status_s::p_session, nm_coll_tree_status_s::pending_reqs, root, nm_coll_tree_info_s::self, tag, nm_coll_tree_status_s::tag, and nm_coll_tree_status_s::tree.

Here is the call graph for this function:

nm_coll_tree_step()

void nm_coll_tree_step	(	const struct nm_coll_tree_info_s *	p_tree,
		int	step,
		int *	p_parent,
		int *	p_children,
		int *	n_children
	)

get the parent & children for the local node at the given step.

Note

a node can't, during a given step, have a parent and children.

by convention, steps are numbered in broadcast order from 0 to tree.height - 1

Referenced by nm_coll_tree_max_weight().

nm_coll_tree_weight()

int nm_coll_tree_weight	(	const struct nm_coll_tree_info_s *	p_tree,
		int	step,
		int	self
	)

Referenced by nm_coll_tree_max_weight().

nm_coll_tree_weight_heuristic()

nm_coll_tree_kind_t nm_coll_tree_weight_heuristic	(	int	comm_size,
		nm_len_t	data_size,
		const struct nm_coll_topology_s *	p_topology
	)

heuristic to select a coll_tree kind for a tree-based collective that needs weights (scatter/gather)

nm_coll_v2r()

static int nm_coll_v2r ( int  i, const struct nm_coll_tree_info_s *  p_tree  )

inlinestatic

translate virtual ranks (with root=0) to real ranks

Definition at line 222 of file nm_coll_trees.h.

References nm_coll_tree_info_s::n, and nm_coll_tree_info_s::root.