Trees for collectives

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

Collaboration diagram for Trees for collectives:

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_BINARY , NM_COLL_TREE_3ARY ,   NM_COLL_TREE_4ARY , NM_COLL_TREE_8ARY , 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, 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. More...
int	nm_coll_tree_weight (const struct nm_coll_tree_info_s *p_tree, int step, int self)
static 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)
nm_coll_tree_kind_t	nm_coll_tree_env (void)
	get tree kind from environment More...
nm_coll_tree_kind_t	nm_coll_tree_heuristic (int comm_size __attribute__((unused)), nm_len_t data_size)
int	nm_coll_binary_nb_nodes_in_left_subtree (const struct nm_coll_tree_info_s *const p_tree)
static int	nm_coll_log2_floor (int x)
	floor(log2(x)) More...
static int	nm_coll_log2_ceil (int x)
	ceil(log2(x)) More...
static int	nm_coll_log4_floor (int x)
	floor(log4(x)) More...
static int	nm_coll_ipow (int base, int exp)
	fast integer power() = base ^ exp More...
static int	nm_coll_log_n_ceil (int x, const int n)
	ceil(log_n(x)) More...
static int	nm_coll_log_n_floor (int x, const int n)
	floor(log_n(x) More...
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) More...
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 More...
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 More...
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 54 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_BINARY
NM_COLL_TREE_3ARY
NM_COLL_TREE_4ARY
NM_COLL_TREE_8ARY
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 140 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 127 of file nm_coll_trees.h.

References 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 120 of file nm_coll_trees.h.

Referenced by nm_coll_log2_ceil(), and nm_coll_log4_floor().

Here is the caller graph for this function:

nm_coll_log4_floor()

static int nm_coll_log4_floor ( int  x )

inlinestatic

floor(log4(x))

Definition at line 134 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 158 of file nm_coll_trees.h.

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 175 of file nm_coll_trees.h.

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 189 of file nm_coll_trees.h.

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

nm_coll_tree_env()

nm_coll_tree_kind_t nm_coll_tree_env

(

void

)

get tree kind from environment

nm_coll_tree_heuristic()

nm_coll_tree_kind_t nm_coll_tree_heuristic	(	int comm_size	__attribute__(unused),
		nm_len_t	data_size
	)

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,
		int	root
	)

Referenced by nm_coll_tree_status_init().

Here is the caller graph for this function:

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 254 of file nm_coll_trees.h.

References nm_atomic_inc(), nm_group_get_gate(), nm_sr_send_init(), nm_sr_send_issend(), nm_sr_send_pack_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()

static const char * nm_coll_tree_kind_name ( nm_coll_tree_kind_t  kind )

inlinestatic

Definition at line 81 of file nm_coll_trees.h.

References _NM_COLL_TREE_MAX, and NM_COLL_TREE_NONE.

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 265 of file nm_coll_trees.h.

References nm_atomic_inc(), nm_group_get_gate(), nm_sr_irecv_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 281 of file nm_coll_trees.h.

References nm_coll_tree_status_s::children_requests, nm_coll_tree_info_s::max_arity, NM_FATAL, and nm_coll_tree_status_s::tree.

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 245 of file nm_coll_trees.h.

References nm_atomic_inc(), nm_group_get_gate(), nm_sr_isend_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 274 of file nm_coll_trees.h.

References NM_SR_EVENT_FINALIZED, nm_sr_request_monitor(), nm_sr_request_set_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 232 of file nm_coll_trees.h.

References nm_coll_tree_status_s::children, nm_coll_tree_status_s::children_requests, nm_coll_tree_status_s::p_group, nm_coll_tree_status_s::p_session, and nm_coll_tree_status_s::pending_reqs.

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 219 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_size(), nm_coll_tree_status_s::p_group, p_session, nm_coll_tree_status_s::p_session, nm_coll_tree_status_s::pending_reqs, nm_coll_tree_info_s::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

nm_coll_tree_weight()

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

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 195 of file nm_coll_trees.h.

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