Tree-based algorithms of MPI collective operations

Functions
int	MPIB_Bcast_binomial (void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm)
int	MPIB_Reduce_binomial (void *sendbuf, void *recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)
int	MPIB_Scatter_binomial (void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Gather_binomial (void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Scatterv_binomial (void *sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Gatherv_binomial (void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Scatterv_sorted_binomial_asc (void *sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Gatherv_sorted_binomial_asc (void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Scatterv_sorted_binomial_dsc (void *sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Gatherv_sorted_binomial_dsc (void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Scatterv_Traff (void *sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
int	MPIB_Gatherv_Traff (void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm)

---

Detailed Description

This module provides tree-based algorithms of MPI collective operations. For rapid implementation, the Graph Boost C++ library is used. The sources of tree algorithms of collectives must be compiled by C++.

A tree-based algorithm of a collective operation X consists of the following components:

• Communication tree MPIB::comm_tree
• Function template for the tree-based algorithm MPIB_X_tree_algorithm (described in Function templates for tree-based algorithms of MPI collective operations)
• Communication tree builder Y_builder, a C++ class that builds a communication tree. (described in MPIB::BRSG and MPIB::SGv)

The tree-based implementation looks as follows:

extern "C" int MPIB_X_Y(standard args) {
    return MPIB_X_tree_algorithm(Y_builder(), standard args);
}

For example, MPIB_Scatter_binomial, a binomial scatter.

This approach provides flexibility:

• Tree-based algorithm of the collective operation is a basis for implementation of algorithms with communication trees of different shapes (for example, binomial and binary algorithms of scatter use the general tree-based algorithm of scatter).
• Communication tree is a universal interface between tree-based algorithms and tree builders. It can be reused for different communication operations (for example, scatter/gather and bcast/reduce use the same simple communication tree).
• Tree and communication tree builders can be reused per tree shape (for example, the same binomial communication tree builder is used in binomial scatter/gather and bcast/reduce).

---

Function Documentation

int MPIB_Bcast_binomial	(	void *	buffer,
		int	count,
		MPI_Datatype	datatype,
		int	root,
		MPI_Comm	comm
	)

Binomial Bcast

int MPIB_Reduce_binomial	(	void *	sendbuf,
		void *	recvbuf,
		int	count,
		MPI_Datatype	datatype,
		MPI_Op	op,
		int	root,
		MPI_Comm	comm
	)

Binomial Reduce

int MPIB_Scatter_binomial	(	void *	sendbuf,
		int	sendcount,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int	recvcount,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial Scatter

int MPIB_Gather_binomial	(	void *	sendbuf,
		int	sendcount,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int	recvcount,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial Gather

int MPIB_Scatterv_binomial	(	void *	sendbuf,
		int *	sendcounts,
		int *	displs,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int	recvcount,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial scatterv

int MPIB_Gatherv_binomial	(	void *	sendbuf,
		int	sendcount,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int *	recvcounts,
		int *	displs,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial gatherv.

int MPIB_Scatterv_sorted_binomial_asc	(	void *	sendbuf,
		int *	sendcounts,
		int *	displs,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int	recvcount,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial scatterv with children sorted by counts in ascending order.

int MPIB_Gatherv_sorted_binomial_asc	(	void *	sendbuf,
		int	sendcount,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int *	recvcounts,
		int *	displs,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial gatherv with children sorted by counts in ascending order.

int MPIB_Scatterv_sorted_binomial_dsc	(	void *	sendbuf,
		int *	sendcounts,
		int *	displs,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int	recvcount,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial scatterv with children sorted by counts in descending order.

int MPIB_Gatherv_sorted_binomial_dsc	(	void *	sendbuf,
		int	sendcount,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int *	recvcounts,
		int *	displs,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Binomial gatherv with children sorted by counts in descending order.

int MPIB_Scatterv_Traff	(	void *	sendbuf,
		int *	sendcounts,
		int *	displs,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int	recvcount,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Traff algorithm of Scatterv. Based on .

int MPIB_Gatherv_Traff	(	void *	sendbuf,
		int	sendcount,
		MPI_Datatype	sendtype,
		void *	recvbuf,
		int *	recvcounts,
		int *	displs,
		MPI_Datatype	recvtype,
		int	root,
		MPI_Comm	comm
	)

Traff algorithm of Gatherv. Based on .