We provide various algorithms to invert the communication pattern. More...

#include <sc_statistics.h>

Include dependency graph for sc_notify.h:

Macros
#define	SC_NOTIFY_STR_ALLGATHER "allgather"
	String for the allgather variant.

#define	SC_NOTIFY_STR_BINARY "binary"
	String for the binary tree variant.

#define	SC_NOTIFY_STR_NARY "nary"
	String for the n-ary tree variant.

#define	SC_NOTIFY_STR_PEX "pex"
	String for the PEX variant.

#define	SC_NOTIFY_STR_PCX "pcx"
	String for the PCX variant.

#define	SC_NOTIFY_STR_RSX "rsx"
	String for the RSX variant.

#define	SC_NOTIFY_STR_NBX "nbx"
	String for the NBX variant.

#define	SC_NOTIFY_STR_RANGES "ranges"
	String for the ranges variant.

#define	SC_NOTIFY_STR_SUPERSET "superset"
	String for the superset variant.

Typedefs
typedef struct sc_notify_s	sc_notify_t
	Opaque object used for controlling notification (AKA dynamic sparse data exchange) operations.

typedef void(*	sc_compute_superset_t) (sc_array_t , sc_array_t , sc_array_t , sc_notify_t , void *)
	Type of callback function for the SC_NOTIFY_SUPERSET variant.

Enumerations
enum	sc_notify_type_t { SC_NOTIFY_DEFAULT = -1 , SC_NOTIFY_ALLGATHER = 0 , SC_NOTIFY_BINARY , SC_NOTIFY_NARY , SC_NOTIFY_PEX , SC_NOTIFY_PCX , SC_NOTIFY_RSX , SC_NOTIFY_NBX , SC_NOTIFY_RANGES , SC_NOTIFY_SUPERSET , SC_NOTIFY_NUM_TYPES }
	Various equivalent implementations of the functionality. More...

Functions
Classic, simple interface.
int	sc_notify_allgather (int receivers, int num_receivers, int senders, int *num_senders, sc_MPI_Comm mpicomm)
	Collective call to notify a set of receiver ranks of current rank. More...

int	sc_notify (int receivers, int num_receivers, int senders, int *num_senders, sc_MPI_Comm mpicomm)
	Collective call to notify a set of receiver ranks of current rank. More...

void	sc_notify_nary (sc_array_t receivers, sc_array_t senders, sc_array_t in_payload, sc_array_t out_payload, sc_MPI_Comm mpicomm)
	The n-ary tree implementation of the notify functionality. More...

void	sc_notify_ext (sc_array_t receivers, sc_array_t senders, sc_array_t in_payload, sc_array_t out_payload, sc_MPI_Comm mpicomm)
	The default implementation of the notify functionality, currently PEX. More...

Optional, most general interface.
sc_notify_t *	sc_notify_new (sc_MPI_Comm mpicomm)
	Create a notify controller that can be used in sc_notify_payload and sc_notify_payloadv. More...

void	sc_notify_destroy (sc_notify_t *notify)
	Destroy a notify controller constructed with sc_notify_new. More...

size_t	sc_notify_get_eager_threshold (sc_notify_t *notify)
	Get the payload size above which payloads are no longer transferred with notification packets in sc_notify_payload. More...

void	sc_notify_set_eager_threshold (sc_notify_t *notify, size_t thresh)
	Get the payload size above which payloads are no longer transferred with notification packets in sc_notify_payload. More...

sc_statistics_t *	sc_notify_get_stats (sc_notify_t *notify)
	Get the sc_statistics_t object for logging runtimes (added by function name). More...

void	sc_notify_set_stats (sc_notify_t notify, sc_statistics_t stats)
	Set a sc_statistics_t object for logging runtimes (added by function name). More...

sc_MPI_Comm	sc_notify_get_comm (sc_notify_t *notify)
	Get the MPI communicator of a notify controller. More...

int	sc_notify_supports_type (sc_notify_type_t type)
	Query whether sc_notify_set_type supports a given type. More...

sc_notify_type_t	sc_notify_get_type (sc_notify_t *notify)
	Get the type of a notify controller. More...

int	sc_notify_set_type (sc_notify_t *notify, sc_notify_type_t type)
	Set the type of a notify controller. More...

void	sc_notify_nary_get_widths (sc_notify_t notify, int ntop, int nint, int nbot)
	For a notify of type SC_NOTIFY_NARY, get the branching widths of the recursive algorithm. More...

void	sc_notify_nary_set_widths (sc_notify_t *notify, int ntop, int nint, int nbot)
	For a notify of type SC_NOTIFY_NARY, set the branching widths of the recursive algorithm. More...

int	sc_notify_ranges_get_num_ranges (sc_notify_t *notify)
	Query the number of ranges for the SC_NOTIFY_RANGES method. More...

void	sc_notify_ranges_set_num_ranges (sc_notify_t *notify, int num_ranges)
	Set the number of ranges for the SC_NOTIFY_RANGES method. More...

void	sc_notify_superset_get_callback (sc_notify_t notify, sc_compute_superset_t compute_superset, void *ctx)
	Query the callback for the SC_NOTIFY_SUPERSET method. More...

void	sc_notify_superset_set_callback (sc_notify_t notify, sc_compute_superset_t compute_superset, void ctx)
	Set the callback for the SC_NOTIFY_SUPERSET method. More...

void	sc_notify_payload (sc_array_t receivers, sc_array_t senders, sc_array_t in_payload, sc_array_t out_payload, int sorted, sc_notify_t *notify)
	Collective call to notify a set of receiver ranks of current rank. More...

void	sc_notify_payloadv (sc_array_t receivers, sc_array_t senders, sc_array_t out_payload, sc_array_t in_payload, sc_array_t out_offsets, sc_array_t in_offsets, int sorted, sc_notify_t *notify)
	Collective call to notify a set of receiver ranks of current rank and send a variable size message to the receiver. More...

Variables
int	sc_notify_nary_ntop_default
	Default number of children at root node of nary tree; initialized to 2.

int	sc_notify_nary_nint_default
	Default number of children at intermediate tree nodes; initialized to 2.

int	sc_notify_nary_nbot_default
	Default number of children at deepest level of tree; initialized to 2.

const char *	sc_notify_type_strings [SC_NOTIFY_NUM_TYPES]
	Names for each notify method.

sc_notify_type_t	sc_notify_type_default
	The default type used when constructing a notify controller; initialized to SC_NOTIFY_PEX.

size_t	sc_notify_eager_threshold_default
	The default threshold for payload sizes (in bytes) that are communicated with the notification packet. More...

int	sc_notify_ranges_num_ranges_default
	For the SC_NOTIFY_RANGES method, the default is 25.

Detailed Description

We provide various algorithms to invert the communication pattern.

The task at hand is: given an individual set of receiver ranks for each process in a sender role, compute efficiently for the receiver role of each rank the set of senders to it.

This file implements two approaches that solve the problem scalably.

The first and original historic one offers the choice between a binary tree recursion, an n-ary tree recursion, optionally with payload data, and an allgather version. The n-ary tree version contains the binary one as a special case. It is called sc_notify_nary and can be configured by the global variables
- sc_notify_nary_ntop_default; #children of the root tree node,
- sc_notify_nary_nint_default; #children of intermediate nodes,
- sc_notify_nary_nbot_default; #siblings of each leaf node.
Thus it can be tailored to match for example distributed NUMA architectures. The default for each variable is a conservative 2 to choose a binary tree.

Another addition to the family is sc_notify_ext for the best known default, which is currently the PEX algorithm.
The more recent and general variant allows to choose between practically all currently known algorithms, enumerated by sc_notify_type_t. This is managed by first creating a configuration object sc_notify_t, setting its type and further parameters, and passing it into the general sc_notify_payload or sc_notify_payloadv functions.

Enumeration Type Documentation

◆ sc_notify_type_t

enum sc_notify_type_t

Various equivalent implementations of the functionality.

Enumerator
SC_NOTIFY_DEFAULT	Choose whatever type is stored in sc_notify_type_default.
SC_NOTIFY_ALLGATHER	Choose allgather algorithm. Likely suboptimal.
SC_NOTIFY_BINARY	Choose simple binary recursion.
SC_NOTIFY_NARY	Choose nary (k-way) recursion.
SC_NOTIFY_PEX	Choose alltoall algorithm (AKA personalized exchange). Current best choice.
SC_NOTIFY_PCX	Choose reduce_scatter algorithm (AKA personalized census).
SC_NOTIFY_RSX	Choose remote summation algorithm.
SC_NOTIFY_NBX	Choose non-blocking consensus algorithm.
SC_NOTIFY_RANGES	Use the sc_ranges functionality. Likely suboptimal.
SC_NOTIFY_SUPERSET	Use a computable superset of communicators, computed by a callback function.
SC_NOTIFY_NUM_TYPES	End of list marker for notify algorithms.

Function Documentation

◆ sc_notify()

int sc_notify	(	int *	receivers,
		int	num_receivers,
		int *	senders,
		int *	num_senders,
		sc_MPI_Comm	mpicomm
	)

Collective call to notify a set of receiver ranks of current rank.

More generally, this function serves to transpose the nonzero pattern of a matrix, where each row and column corresponds to an MPI rank in order. We use a binary tree to construct the communication pattern. This minimizes the number of messages at the cost of more messages compared to a fatter tree such as configurable with sc_notify_nary.

Parameters

[in]	receivers	Sorted and unique array of MPI ranks to inform.
[in]	num_receivers	Count of ranks contained in receivers.
[in,out]	senders	Array of at least size sc_MPI_Comm_size. On output it contains the notifying ranks, whose number is returned in num_senders.
[out]	num_senders	On output the number of notifying ranks.
[in]	mpicomm	MPI communicator to use.

Returns: Aborts on MPI error or returns sc_MPI_SUCCESS.

◆ sc_notify_allgather()

int sc_notify_allgather	(	int *	receivers,
		int	num_receivers,
		int *	senders,
		int *	num_senders,
		sc_MPI_Comm	mpicomm
	)

Collective call to notify a set of receiver ranks of current rank.

This version uses one call to sc_MPI_Allgather and one to sc_MPI_Allgatherv. We provide hand-coded alternatives sc_notify and sc_notify_nary.

Parameters

[in]	receivers	Sorted and unique array of MPI ranks to inform.
[in]	num_receivers	Count of ranks contained in receivers.
[in,out]	senders	Array of at least size sc_MPI_Comm_size. On output it contains the notifying ranks.
[out]	num_senders	On output the number of notifying ranks.
[in]	mpicomm	MPI communicator to use.

Returns: Aborts on MPI error or returns sc_MPI_SUCCESS.

◆ sc_notify_destroy()

void sc_notify_destroy ( sc_notify_t * notify )

Destroy a notify controller constructed with sc_notify_new.

Parameters

[in,out] notify The notify controller that will be destroyed. Pointer is invalid on completion.

◆ sc_notify_ext()

void sc_notify_ext	(	sc_array_t *	receivers,
		sc_array_t *	senders,
		sc_array_t *	in_payload,
		sc_array_t *	out_payload,
		sc_MPI_Comm	mpicomm
	)

The default implementation of the notify functionality, currently PEX.

This function optionally transfers a fixed-size payload per rank.

Parameters

[in,out]	receivers	Sorted, unique array of int members. If senders is NULL, repurposed as output.
[in,out]	senders	Aarray of int members, resized on output. If NULL, the output is placed in receivers.
[in,out]	in_payload	Array of same length as receivers with arbitrary data to be transmitted to senders. If out_payload is NULL, repurposed as output. Both payload arrays may be NULL altogether.
[in,out]	out_payload	Of same type as in_payload, resized on output. If NULL, the result is placed in in_payload.
[in]	mpicomm	MPI communicator to use.

Returns: Aborts on MPI error or returns sc_MPI_SUCCESS.

◆ sc_notify_get_comm()

sc_MPI_Comm sc_notify_get_comm ( sc_notify_t * notify )

Get the MPI communicator of a notify controller.

Parameters

[in] notify The notify controller.

Returns: The mpi communicator over which the notification occurs.

◆ sc_notify_get_eager_threshold()

size_t sc_notify_get_eager_threshold ( sc_notify_t * notify )

Get the payload size above which payloads are no longer transferred with notification packets in sc_notify_payload.

Parameters

[in] notify The notify controller.

Returns: The size in bytes of the maximum eager payload size.

◆ sc_notify_get_stats()

sc_statistics_t* sc_notify_get_stats ( sc_notify_t * notify )

Get the sc_statistics_t object for logging runtimes (added by function name).

Parameters

[in,out] notify The notify controller.

Returns: The sc_statistics_t * object, may be NULL.

◆ sc_notify_get_type()

sc_notify_type_t sc_notify_get_type ( sc_notify_t * notify )

Get the type of a notify controller.

Parameters

[in] notify The notify controller.

Returns: The type of the notify controller (see sc_notify_type_t).

◆ sc_notify_nary()

void sc_notify_nary	(	sc_array_t *	receivers,
		sc_array_t *	senders,
		sc_array_t *	in_payload,
		sc_array_t *	out_payload,
		sc_MPI_Comm	mpicomm
	)

The n-ary tree implementation of the notify functionality.

This function optionally transfers a fixed-size payload per rank.

Parameters

[in,out]	receivers	Sorted, unique array of int members. If senders is NULL, repurposed as output.
[in,out]	senders	Aarray of int members, resized on output. If NULL, the output is placed in receivers.
[in,out]	in_payload	Array of same length as receivers with arbitrary data to be transmitted to senders. If out_payload is NULL, repurposed as output. Both payload arrays may be NULL altogether. If out_payload is not NULL, in_payload must not be NULL either.
[in,out]	out_payload	Of same type as in_payload, resized on output. If NULL, the result is placed in in_payload.
[in]	mpicomm	MPI communicator to use.

Returns: Aborts on MPI error or returns sc_MPI_SUCCESS.

◆ sc_notify_nary_get_widths()

void sc_notify_nary_get_widths	(	sc_notify_t *	notify,
		int *	ntop,
		int *	nint,
		int *	nbot
	)

For a notify of type SC_NOTIFY_NARY, get the branching widths of the recursive algorithm.

Parameters

[in]	notify	The notify controller must be of type SC_NOTIFY_NARY.
[out]	ntop	The number of children at root node of nary tree.
[out]	nint	The number of children at intermediate tree nodes.
[out]	nbot	The number of children at deepest level of the tree.

◆ sc_notify_nary_set_widths()

void sc_notify_nary_set_widths	(	sc_notify_t *	notify,
		int	ntop,
		int	nint,
		int	nbot
	)

For a notify of type SC_NOTIFY_NARY, set the branching widths of the recursive algorithm.

Parameters

[in,out]	notify	The notify controller must be of type SC_NOTIFY_NARY.
[in]	ntop	The number of children at root node of nary tree.
[in]	nint	The number of children at intermediate tree nodes.
[in]	nbot	The number of children at deepest level of the tree.

◆ sc_notify_new()

sc_notify_t* sc_notify_new ( sc_MPI_Comm mpicomm )

Create a notify controller that can be used in sc_notify_payload and sc_notify_payloadv.

Parameters

[in] mpicomm The MPI communicator over which the notification occurs.

Returns: Pointer to a notify controller that should be destroyed with sc_notify_destroy.

◆ sc_notify_payload()

void sc_notify_payload	(	sc_array_t *	receivers,
		sc_array_t *	senders,
		sc_array_t *	in_payload,
		sc_array_t *	out_payload,
		int	sorted,
		sc_notify_t *	notify
	)

Collective call to notify a set of receiver ranks of current rank.

This function aborts on MPI error.

Parameters

[in,out]	receivers	On input, sorted and uniqued array of type int. Contains the MPI ranks to inform. If senders is not NULL, treated read-only. If senders is NULL, takes its role on output. In this case it must not be a view.
[in,out]	senders	If NULL, the result is placed in receivers as written below for the non-NULL case. If not NULL, array of type int and any length. Its entries on input are ignored and overwritten. On output it is resized to the number of notifying ranks, which it contains in order. Thus, it must not be a view.
[in,out]	in_payload	This array pointer may be NULL. If not NULL, it must have num_receivers entries that are the same size on every process. If not NULL and out_payload is NULL, it must not be a view, and it will be resized to contain the output and have *num_senders entries.
[in,out]	out_payload	This array pointer may be NULL. If not, it must not be a view, and on output will have * num_senders entries.
[in]	sorted	whether receivers and senders are required to be sorted by MPI rank.
[in]	notify	Notify controller to use.

◆ sc_notify_payloadv()

void sc_notify_payloadv	(	sc_array_t *	receivers,
		sc_array_t *	senders,
		sc_array_t *	out_payload,
		sc_array_t *	in_payload,
		sc_array_t *	out_offsets,
		sc_array_t *	in_offsets,
		int	sorted,
		sc_notify_t *	notify
	)

Collective call to notify a set of receiver ranks of current rank and send a variable size message to the receiver.

This function aborts on MPI error.

Parameters

[in,out]	receivers	On input, sorted and uniqued array of type int. Contains the MPI ranks to inform. If senders is not NULL, treated read-only. If senders is NULL, takes its role on output. In this case it must not be a view.
[in,out]	senders	If NULL, the result is placed in receivers as written below for the non-NULL case. If not NULL, array of type int and any length. Its entries on input are ignored and overwritten. On output it is resized to the number of notifying ranks, which it contains in order. Thus, it must not be a view.
[in,out]	in_payload	This array pointer may be NULL. If not, it must not be a view and have entries that are the same size on every process. This data will be communicated to the receivers. If out_payload is NULL, this will be resized to contain the received payload.
[in,out]	out_payload	This array pointer may be NULL. If not, it must not be a view and have entries that are the same size on every process. If not NULL, this array will be resized to contain the received payload.
[in,out]	in_offsets	If in_payload is not NULL, this is an array of int's of size num_receivers + 1, giving offsets for the portion of the payload to be sent to every receiver. If out_offsets is NULL, it will be resized to give offsets of the received payload.
[in,out]	out_offsets	This array pointer may be NULL. If in_payload is not NULL, it is an array of int's that will be resized to num_senders + 1, giving offsets for the portion of the payload received from each sender.
[in]	sorted	whether receivers and senders (and thus in_offsets and out_offsets) are required to be sorted by MPI rank.
[in]	notify	Notify controller to use.

◆ sc_notify_ranges_get_num_ranges()

int sc_notify_ranges_get_num_ranges ( sc_notify_t * notify )

Query the number of ranges for the SC_NOTIFY_RANGES method.

Parameters

[in] notify Must be of type SC_NOTIFY_RANGES.

Returns: Number of ranges.

◆ sc_notify_ranges_set_num_ranges()

void sc_notify_ranges_set_num_ranges	(	sc_notify_t *	notify,
		int	num_ranges
	)

Set the number of ranges for the SC_NOTIFY_RANGES method.

Parameters

[in,out]	notify	Must be of type SC_NOTIFY_RANGES.
[in]	num_ranges	Number of ranges.

◆ sc_notify_set_eager_threshold()

void sc_notify_set_eager_threshold	(	sc_notify_t *	notify,
		size_t	thresh
	)

Get the payload size above which payloads are no longer transferred with notification packets in sc_notify_payload.

Parameters

[in,out]	notify	The notify controller.
[in]	thresh	The size in bytes of the maximum eager payload size.

◆ sc_notify_set_stats()

void sc_notify_set_stats	(	sc_notify_t *	notify,
		sc_statistics_t *	stats
	)

Set a sc_statistics_t object for logging runtimes (added by function name).

Parameters

[in,out]	notify	The notify controller.
[in]	stats	The sc_statistics_t object. The notify controller will add timings for functions to the object, listed under their function names.

◆ sc_notify_set_type()

int sc_notify_set_type	(	sc_notify_t *	notify,
		sc_notify_type_t	type
	)

Set the type of a notify controller.

Parameters

[in,out]	notify	The notify controller.
[in]	type	The type of algorithm used to affect the dynamic sparse data exchange.

Returns: false if the type is supported by the current MPI version, true otherwise.

◆ sc_notify_superset_get_callback()

void sc_notify_superset_get_callback	(	sc_notify_t *	notify,
		sc_compute_superset_t *	compute_superset,
		void *	ctx
	)

Query the callback for the SC_NOTIFY_SUPERSET method.

Parameters

[in]	notify	Must be of type SC_NOTIFY_SUPERSET.
[out]	compute_superset	Output the callback function.
[out]	ctx	Output the callback Context.

◆ sc_notify_superset_set_callback()

void sc_notify_superset_set_callback	(	sc_notify_t *	notify,
		sc_compute_superset_t	compute_superset,
		void *	ctx
	)

Set the callback for the SC_NOTIFY_SUPERSET method.

Parameters

[in,out]	notify	Must be of type SC_NOTIFY_SUPERSET.
[in]	compute_superset	Callback function.
[in]	ctx	Context passed to callback function.

◆ sc_notify_supports_type()

int sc_notify_supports_type ( sc_notify_type_t type )

Query whether sc_notify_set_type supports a given type.

Parameters

[in] type Notify algorithm type from sc_notify_type_t.

Returns: True if supported, false if not.

Variable Documentation

◆ sc_notify_eager_threshold_default

size_t sc_notify_eager_threshold_default

extern

The default threshold for payload sizes (in bytes) that are communicated with the notification packet.

Initialized to 1024 (2^10)

Macros

Typedefs

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ sc_notify_type_t

Function Documentation

◆ sc_notify()

◆ sc_notify_allgather()

◆ sc_notify_destroy()

◆ sc_notify_ext()

◆ sc_notify_get_comm()

◆ sc_notify_get_eager_threshold()

◆ sc_notify_get_stats()

◆ sc_notify_get_type()

◆ sc_notify_nary()

◆ sc_notify_nary_get_widths()

◆ sc_notify_nary_set_widths()

◆ sc_notify_new()

◆ sc_notify_payload()

◆ sc_notify_payloadv()

◆ sc_notify_ranges_get_num_ranges()

◆ sc_notify_ranges_set_num_ranges()

◆ sc_notify_set_eager_threshold()

◆ sc_notify_set_stats()

◆ sc_notify_set_type()

◆ sc_notify_superset_get_callback()

◆ sc_notify_superset_set_callback()

◆ sc_notify_supports_type()

Variable Documentation

◆ sc_notify_eager_threshold_default