Utilities::MPI::ConsensusAlgorithms Namespace Reference

Classes
class	AnonymousProcess
class	Interface
class	NBX
class	PEX
class	Process
class	Selector
class	Serial

Functions
template<typename RequestType , typename AnswerType >
std::vector< unsigned int >	nbx (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< AnswerType(const unsigned int, const RequestType &)> &answer_request, const std::function< void(const unsigned int, const AnswerType &)> &process_answer, const MPI_Comm &comm)
template<typename RequestType >
std::vector< unsigned int >	nbx (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< void(const unsigned int, const RequestType &)> &process_request, const MPI_Comm &comm)
template<typename RequestType , typename AnswerType >
std::vector< unsigned int >	pex (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< AnswerType(const unsigned int, const RequestType &)> &answer_request, const std::function< void(const unsigned int, const AnswerType &)> &process_answer, const MPI_Comm &comm)
template<typename RequestType >
std::vector< unsigned int >	pex (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< void(const unsigned int, const RequestType &)> &process_request, const MPI_Comm &comm)
template<typename RequestType , typename AnswerType >
std::vector< unsigned int >	serial (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< AnswerType(const unsigned int, const RequestType &)> &answer_request, const std::function< void(const unsigned int, const AnswerType &)> &process_answer, const MPI_Comm &comm)
template<typename RequestType >
std::vector< unsigned int >	serial (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< void(const unsigned int, const RequestType &)> &process_request, const MPI_Comm &comm)
template<typename RequestType , typename AnswerType >
std::vector< unsigned int >	selector (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< AnswerType(const unsigned int, const RequestType &)> &answer_request, const std::function< void(const unsigned int, const AnswerType &)> &process_answer, const MPI_Comm &comm)
template<typename RequestType >
std::vector< unsigned int >	selector (const std::vector< unsigned int > &targets, const std::function< RequestType(const unsigned int)> &create_request, const std::function< void(const unsigned int, const RequestType &)> &process_request, const MPI_Comm &comm)

Detailed Description

A namespace for algorithms that implement the task of communicating in a dynamic-sparse way. In computer science, this is often called a consensus problem.

The problem consensus algorithms are trying to solve is this: Let's say you have \(P\) processes that work together via MPI. Each (or at least some) of these want to send information to some of the other processes, or request information from other processes. No process knows which other process wants to communicate with them. The challenge is to determine who needs to talk to whom and what information needs to be sent, and to come up with an algorithm that ensures that this communication happens.

That this is not a trivial problem can be seen by an analogy of the postal service. There, some senders may request information from some other participants in the postal service. So they send a letter that requests the information, but the recipients do not know how many such letters they need to expect (or that they should expect any at all). They also do not know how long they need to keep checking their mailbox for incoming requests. The recipients can be considered reliable, however: We can assume that everyone who is sent a request puts a letter with the answer in the mail. This time at least the recipients of these answers know that they are waiting for these answers because they have previously sent a request. They do not know in advance, however, when the answer will arrive and how long to wait. The goal of a consensus algorithm is then to come up with a strategy in which every participant can say who they want to send requests to, what that request is, and is then guaranteed an answer. The algorithm will only return when all requests by all participants have been answered and the answer delivered to the requesters.

The problem is generally posed in terms of requests and answers. In practice, either of these two may be empty messages. For example, processes may simply want to send information to others that they know these others need; in this case, the "answer" message may be empty and its meaning is simply an affirmation that the information was received. Similarly, in some cases processes simply need to inform others that they want information, but the destination process knows what information is being requested (based on where in the program the request happens) and can send that information without there be any identifying information in the request; in that case, the request message may be empty and simply serve to identify the requester. (Each message can be queried for its sender.)

As mentioned in the first paragraph, the algorithms we are interested in are "dynamic-sparse":

• Dynamic: By the time the algorithm is called, the other processes do not know yet that they have to answer requests.
• Sparse: Each process only has to communicate with a small subset of processes of the MPI communicator.

In order to run the communication algorithms, users of this class have to provide a number of pieces of information:

• An MPI communicator.
• On each process, a list of ranks of processes to communicate with.
• Functionality to pack/unpack data to send as either the original request or as part of the answer. This information is typically either provided as direct objects (for the first two of the points above), or as function objects (for the third point above). In the latter case, the function objects are often simply lambda functions declared right in the context where one wants to run a consensus algorithm; these lambda functions may then reference variables that are active at the point of declaration of the lambda function, such as variables local to the surrounding function.

Available implementations

There are many ways to implement the general functionality required for these "consensus algorithms". This namespace provides several implementations of consensus algorithms, specifically the NBX and PEX algorithms, along with a serial one for the case where one wants to run such an algorithm on a single process. The key entry points to these algorithms are the nbx(), pex(), serial(), and selector() functions that take a communicator, a list of targets, and a number of functions as argument. The selector() function redirects to the other implementations based on the number of processes that participate in an MPI universe, since some implementations are better or worse suited for large or small parallel computations.

This namespace also implements specializations of each of the functions for the specific case where a calling process is not actually interested in receiving and processing answers – that is, the goal is simply to send messages to a number of targets, but no answer is required; all we want to know is that by the end of the call, all targets have been sent their respective data. This, strictly speaking, does not fall under the umbrella of "consensus algorithms", but is really just a "some-to-some" communication. (This operation is also provided by the Utilities::MPI::some_to_some() function, though with a different interface.) For this special case, the functions in this namespace only need to receive an MPI communicator, a list of targets, and function objects that encode and decode the messages to be sent, but no functions for encoding a reply, or processing a reply.

Function Documentation

nbx() [1/2]

template<typename RequestType , typename AnswerType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::nbx	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< AnswerType(const unsigned int, const RequestType &)> &	answer_request,
		const std::function< void(const unsigned int, const AnswerType &)> &	process_answer,
		const MPI_Comm &	comm
	)

This function implements a concrete algorithm for the consensus algorithms problem (see the documentation of the surrounding namespace), using only point-to-point communications and a single IBarrier. This algorithm is suitable for very large process counts because it does not require the allocation of arrays with size proportional to the number of processes.

Note

This class closely follows [83], but our implementation also deals with payloads.

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	answer_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and returns the message that forms the answer that should be sent back to the requesting process.
[in]	process_answer	A function object that takes as argument the rank of a process from which we have received an answer to a previously sent request, along with the message that forms this answer. This function is used to describe what the caller of the consensus algorithm wants to do with the received answer.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType	The type of the object to be sent.
AnswerType	The type of the object to be received.

nbx() [2/2]

template<typename RequestType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::nbx	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< void(const unsigned int, const RequestType &)> &	process_request,
		const MPI_Comm &	comm
	)

This function provides a specialization of the one above for the case where a sending process does not require an answer. Strictly speaking, the name "request" is then incorrect, as it is simply one process sending a message to another, but we keep the name for symmetry with the function above that processes both requests and answers.

Since the function does not deal with answers, the algorithm implemented is really just a "some-to-some algorithm", as also provided by the Utilities::MPI::some_to_some() function.

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	process_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and processes that message.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType

The type of the object to be sent.

pex() [1/2]

template<typename RequestType , typename AnswerType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::pex	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< AnswerType(const unsigned int, const RequestType &)> &	answer_request,
		const std::function< void(const unsigned int, const AnswerType &)> &	process_answer,
		const MPI_Comm &	comm
	)

This function implements a concrete algorithm for the consensus algorithms problem (see the documentation of the surrounding namespace), using a two step approach. In the first step the source ranks are determined and in the second step a static sparse data exchange is performed. This algorithm is most suitable for relatively small process counts – say, less than 100.

Note

In contrast to NBX, this class splits the same task into two distinct steps. In the first step, all processes are identified who want to send a request to this process. In the second step, the data is exchanged. However, since - in the second step - now it is clear how many requests have to be answered, i.e. when this process can stop waiting for requests, no IBarrier is needed.

Under the hood, this function uses Utilities::MPI::compute_point_to_point_communication_pattern() to determine the source processes, which itself is based on the NBX-algorithm from [83] that is implemented in the ConsensusAlgorithms::NBX class (a sister class to the current one).

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	answer_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and returns the message that forms the answer that should be sent back to the requesting process.
[in]	process_answer	A function object that takes as argument the rank of a process from which we have received an answer to a previously sent request, along with the message that forms this answer. This function is used to describe what the caller of the consensus algorithm wants to do with the received answer.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType	The type of the object to be sent.
AnswerType	The type of the object to be received.

pex() [2/2]

template<typename RequestType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::pex	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< void(const unsigned int, const RequestType &)> &	process_request,
		const MPI_Comm &	comm
	)

This function provides a specialization of the one above for the case where a sending process does not require an answer. Strictly speaking, the name "request" is then incorrect, as it is simply one process sending a message to another, but we keep the name for symmetry with the function above that processes both requests and answers.

Since the function does not deal with answers, the algorithm implemented is really just a "some-to-some algorithm", as also provided by the Utilities::MPI::some_to_some() function.

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	process_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and processes that message.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType

The type of the object to be sent.

serial() [1/2]

template<typename RequestType , typename AnswerType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::serial	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< AnswerType(const unsigned int, const RequestType &)> &	answer_request,
		const std::function< void(const unsigned int, const AnswerType &)> &	process_answer,
		const MPI_Comm &	comm
	)

This function implements a concrete algorithm for the consensus algorithms problem (see the documentation of the surrounding namespace), as a fall-back option for the case where the communicator provided has only one rank (or when MPI is simply not used at all).

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	answer_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and returns the message that forms the answer that should be sent back to the requesting process.
[in]	process_answer	A function object that takes as argument the rank of a process from which we have received an answer to a previously sent request, along with the message that forms this answer. This function is used to describe what the caller of the consensus algorithm wants to do with the received answer.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType	The type of the object to be sent.
AnswerType	The type of the object to be received.

serial() [2/2]

template<typename RequestType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::serial	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< void(const unsigned int, const RequestType &)> &	process_request,
		const MPI_Comm &	comm
	)

This function provides a specialization of the one above for the case where a sending process does not require an answer. Strictly speaking, the name "request" is then incorrect, as it is simply one process sending a message to another, but we keep the name for symmetry with the function above that processes both requests and answers.

Since the function does not deal with answers, the algorithm implemented is really just a "some-to-some algorithm", as also provided by the Utilities::MPI::some_to_some() function.

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	process_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and processes that message.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType

The type of the object to be sent.

selector() [1/2]

template<typename RequestType , typename AnswerType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::selector	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< AnswerType(const unsigned int, const RequestType &)> &	answer_request,
		const std::function< void(const unsigned int, const AnswerType &)> &	process_answer,
		const MPI_Comm &	comm
	)

This function implements a concrete algorithm for the consensus algorithms problem (see the documentation of the surrounding namespace). In particular, it delegates its work to one of the other functions in this namespace depending on the number of processes in the MPI communicator. For a small number of processes it uses pex() and for a large number of processes nbx(). The threshold depends if the program is compiled in debug or release mode, but the goal is to always use the most efficient algorithm for however many processes participate in the communication.

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	answer_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and returns the message that forms the answer that should be sent back to the requesting process.
[in]	process_answer	A function object that takes as argument the rank of a process from which we have received an answer to a previously sent request, along with the message that forms this answer. This function is used to describe what the caller of the consensus algorithm wants to do with the received answer.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType	The type of the object to be sent.
AnswerType	The type of the object to be received.

selector() [2/2]

template<typename RequestType >

std::vector< unsigned int > Utilities::MPI::ConsensusAlgorithms::selector	(	const std::vector< unsigned int > &	targets,
		const std::function< RequestType(const unsigned int)> &	create_request,
		const std::function< void(const unsigned int, const RequestType &)> &	process_request,
		const MPI_Comm &	comm
	)

This function provides a specialization of the one above for the case where a sending process does not require an answer. Strictly speaking, the name "request" is then incorrect, as it is simply one process sending a message to another, but we keep the name for symmetry with the function above that processes both requests and answers.

Since the function does not deal with answers, the algorithm implemented is really just a "some-to-some algorithm", as also provided by the Utilities::MPI::some_to_some() function.

Parameters

[in]	targets	A vector that contains the ranks of processes to which requests should be sent and from which answers need to be received.
[in]	create_request	A function object that takes the rank of a target process as argument and returns the message that forms the request to this target.
[in]	process_request	A function that takes as arguments the rank of the process that has sent a request to us, along with the message of the request, and processes that message.
[in]	comm	The MPI communicator on which the whole algorithm is to be performed.

Template Parameters

RequestType

The type of the object to be sent.