488 lines
18 KiB
ReStructuredText
488 lines
18 KiB
ReStructuredText
.. Copyright (C) 2004-2008 The Trustees of Indiana University.
|
|
Use, modification and distribution is subject to the Boost Software
|
|
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
|
|
==================================
|
|
|Logo| Parallel BGL Process Groups
|
|
==================================
|
|
|
|
.. contents::
|
|
|
|
Introduction
|
|
------------
|
|
|
|
Process groups are an abstraction of a set of communicating processes
|
|
that coordinate to solve the same problem. Process groups contain
|
|
facilities for identifying the processes within that group, sending
|
|
and receiving messages between the processes in that group, and
|
|
performing collective communications involving all processes in the
|
|
group simultaneously.
|
|
|
|
Communication model
|
|
-------------------
|
|
|
|
Process groups are based on an extended version of the Bulk
|
|
Synchronous Parallel (BSP) model of computation. Parallel computations
|
|
in the BSP model are organized into *supersteps*, each of which
|
|
consists of a computation phase followed by a communication
|
|
phase. During the computation phase, all processes in the process
|
|
group work exclusively on local data, and there is no inter-process
|
|
communication. During the communication phase, all of the processes
|
|
exchange message with each other. Messages sent in the communication
|
|
phase of a superstep will be received in the next superstep.
|
|
|
|
The boundary between supersteps in the Parallel BGL corresponds to the
|
|
``synchronize`` operation. Whenever a process has completed its local
|
|
computation phase and sent all of the messages required for that
|
|
superstep, it invokes the ``synchronize`` operation on the process
|
|
group. Once all processes in the process group have entered
|
|
``synchronize``, they exchange messages and then continue with the
|
|
next superstep.
|
|
|
|
The Parallel BGL loosens the BSP model significantly, to provide a
|
|
more natural programming model that also provides some performance
|
|
benefits over the strict BSP model. The primary extension is the
|
|
ability to receive messages sent within the same superstep
|
|
"asynchronously", either to free up message buffers or to respond to
|
|
an immediate request for information. For particularly unstructured
|
|
computations, the ability to send a message and get an immediate reply
|
|
can simplify many computations that would otherwise need to be split
|
|
into two separate supersteps. Additionally, the Parallel BGL augments
|
|
the BSP model with support for multiple distributed data structures,
|
|
each of which are provided with a different communication space but
|
|
whose messages will all be synchronized concurrently.
|
|
|
|
Distributed data structures
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
A typical computation with the Parallel BGL involves several
|
|
distributed data structures working in concern. For example, a simple
|
|
breadth-first search involves the distributed graph data structure
|
|
containing the graph itself, a distributed queue that manages the
|
|
traversal through the graph, and a distributed property map that
|
|
tracks which vertices have already been visited as part of the
|
|
search.
|
|
|
|
The Parallel BGL manages these distributed data structures by allowing
|
|
each of the data structures to attach themselves to the process group
|
|
itself. When a distributed data structure attaches to the process
|
|
group, it receives its own copy of the process group that allows the
|
|
distributed data structure to communicate without colliding with the
|
|
communications from other distributed data structures. When the
|
|
process group is synchronized, all of the distributed data structures
|
|
attached to that process group are automatically synchronized, so that
|
|
all of the distributed data structures in a computation remain
|
|
synchronized.
|
|
|
|
A distributed data structure attaches itself to the process group by
|
|
creating a copy of the process group and passing an
|
|
``attach_distributed_object`` flag to the process group
|
|
constructor. So long as this copy of the process group persists, the
|
|
distributed data structure is attached the process group. For this
|
|
reason, most distributed data structures keep a copy of the process
|
|
group as member data, constructing the member with
|
|
``attach_distributed_object``, e.g.,
|
|
|
|
::
|
|
|
|
template<typename ProcessGroup>
|
|
struct distributed_data_structure
|
|
{
|
|
explicit distributed_data_structure(const ProcessGroup& pg)
|
|
: process_group(pg, boost::parallel::attach_distributed_object())
|
|
{ }
|
|
|
|
private:
|
|
ProcessGroup process_group;
|
|
};
|
|
|
|
|
|
Asynchronous receives
|
|
~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
Distributed data structures in the Parallel BGL can "asynchronously"
|
|
receive and process messages before the end of a BSP
|
|
superstep. Messages can be received any time that a process is inside
|
|
the process group operations, and the scheduling of message receives
|
|
is entirely managed by the process group.
|
|
|
|
Distributed data structures receive messages through
|
|
"triggers". Triggers are function objects responsible for processing a
|
|
received message. Each trigger is registered with the ``trigger``
|
|
method of the process group using a specific message
|
|
tag (an integer) and the type of data that is expected to be
|
|
contained within that message. Whenever a message with that tag
|
|
becomes available, the progress group will call the trigger with the
|
|
source of the message, the message tag, the data contained in the
|
|
message, and the "context" of the message.
|
|
|
|
The majority of triggers have no return value, although it is common
|
|
that the triggers send messages back to the source process. In certain
|
|
cases where the trigger's purpose is to immediately reply with a
|
|
value, the trigger should be registered with the
|
|
``trigger_with_reply`` method and should return the value that will be
|
|
sent back to the caller. The ``trigger_with_reply`` facility is only
|
|
useful in conjunction with out-of-band messaging, discussed next.
|
|
|
|
Out-of-band messaging
|
|
~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
The majority of messages sent by the Parallel BGL are sent through the
|
|
normal send operations, to be received in the next superstep or, in
|
|
some cases, received "early" by a trigger. These messages are not
|
|
time-sensitive, so they will be delivered whenever the process group
|
|
processes them.
|
|
|
|
Some messages, however, require immediate responses. For example, if a
|
|
process needs to determine the current value associated with a vertex
|
|
owned by another process, the first process must send a request to the
|
|
second process and block while waiting for a response. For such
|
|
messages, the Parallel BGL's process groups provide an out-of-band
|
|
messaging mechanism. Out-of-band messages are transmitted immediately,
|
|
with a much higher priority than other messages. The sending of
|
|
out-of-band messages can be coupled with a receive operation that
|
|
waits until the remote process has received the message and sent its
|
|
reply. For example, in the following code the process sends a message
|
|
containing the string ``name`` to process ``owner`` with tag
|
|
``msg_get_descriptor_by_name`` via an out-of-band message. The
|
|
receiver of that message will immediately deliver the message via a
|
|
trigger, that returns the resulting value--a
|
|
``vertex_descriptor``--that will be passed back to the process that
|
|
initiated the communication. The full communication happens
|
|
immediately, within the current superstep.
|
|
|
|
::
|
|
|
|
std::string name;
|
|
vertex_descriptor descriptor;
|
|
send_oob_with_reply(process_group, owner, msg_get_descriptor_by_name,
|
|
name, descriptor);
|
|
|
|
Reference
|
|
---------
|
|
|
|
The Parallel BGL process groups specify an interface that can be
|
|
implemented by various communication subsystems. In this reference
|
|
section, we use the placeholder type ``ProcessGroup`` to stand in for
|
|
the various process group implementations that exist. There is only
|
|
one implementation of the process group interface at this time:
|
|
|
|
- `MPI BSP process group`_
|
|
|
|
::
|
|
|
|
enum trigger_receive_context {
|
|
trc_none,
|
|
trc_in_synchronization,
|
|
trc_early_receive,
|
|
trc_out_of_band
|
|
};
|
|
|
|
class ProcessGroup
|
|
{
|
|
// Process group constructors
|
|
ProcessGroup();
|
|
ProcessGroup(const ProcessGroup&, boost::parallel::attach_distributed_object);
|
|
|
|
// Triggers
|
|
template<typename Type, typename Handler>
|
|
void trigger(int tag, const Handler& handler);
|
|
|
|
template<typename Type, typename Handler>
|
|
void trigger_with_reply(int tag, const Handler& handler);
|
|
|
|
trigger_receive_context trigger_context() const;
|
|
|
|
// Helper operations
|
|
void poll();
|
|
ProcessGroup base() const;
|
|
};
|
|
|
|
// Process query
|
|
int process_id(const ProcessGroup&);
|
|
int num_processes(const ProcessGroup&);
|
|
|
|
// Message transmission
|
|
template<typename T>
|
|
void send(const ProcessGroup& pg, int dest, int tag, const T& value);
|
|
|
|
template<typename T>
|
|
void receive(const ProcessGroup& pg, int source, int tag, T& value);
|
|
|
|
optional<std::pair<int, int> > probe(const ProcessGroup& pg);
|
|
|
|
// Synchronization
|
|
void synchronize(const ProcessGroup& pg);
|
|
|
|
// Out-of-band communication
|
|
template<typename T>
|
|
void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value);
|
|
|
|
template<typename T, typename U>
|
|
void
|
|
send_oob_with_reply(const ProcessGroup& pg, int dest, int
|
|
tag, const T& send_value, U& receive_value);
|
|
|
|
template<typename T>
|
|
void receive_oob(const ProcessGroup& pg, int source, int tag, T& value);
|
|
|
|
|
|
Process group constructors
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
::
|
|
|
|
ProcessGroup();
|
|
|
|
Constructs a new process group with a different communication space
|
|
from any other process group.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
ProcessGroup(const ProcessGroup& pg, boost::parallel::attach_distributed_object);
|
|
|
|
Attaches a new distributed data structure to the process group
|
|
``pg``. The resulting process group can be used for communication
|
|
within that new distributed data structure. When the newly-constructed
|
|
process group is eventually destroyed, the distributed data structure
|
|
is detached from the process group.
|
|
|
|
Triggers
|
|
~~~~~~~~
|
|
|
|
::
|
|
|
|
template<typename Type, typename Handler>
|
|
void trigger(int tag, const Handler& handler);
|
|
|
|
Registers a trigger with the given process group. The trigger will
|
|
watch for messages with the given ``tag``. When such a message is
|
|
available, it will be received into a value of type ``Type``, and the
|
|
function object ``handler`` will be invoked with four parameters:
|
|
|
|
source
|
|
The rank of the source process (an ``int``)
|
|
|
|
tag
|
|
The tag used to send the message (also an ``int``)
|
|
|
|
data:
|
|
The data transmitted with the message. The data will have the type
|
|
specified when the trigger was registered.
|
|
|
|
context:
|
|
The context in which the trigger is executed. This will be a value of
|
|
type ``trigger_receive_context``, which stages whether the trigger
|
|
is being executed during synchronization, asynchronously in response
|
|
to an "early" receive (often to free up communication buffers), or
|
|
in response to an "out-of-band" message.
|
|
|
|
Triggers can only be registered by process groups that result from
|
|
attaching a distributed data structure. A trigger can be invoked in
|
|
response to either a normal send operation or an out-of-band send
|
|
operation. There is also a `simple trigger interface`_ for defining
|
|
triggers in common cases.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
template<typename Type, typename Handler>
|
|
void trigger_with_reply(int tag, const Handler& handler);
|
|
|
|
Like the ``trigger`` method, registers a trigger with the given
|
|
process group. The trigger will watch for messages with the given
|
|
``tag``. When such a message is available, it will be received into a
|
|
value of type ``Type`` and ``handler`` will be invoked, just as with a
|
|
normal trigger. However, a trigger registered with
|
|
``trigger_with_reply`` must return a value, which will be immediately
|
|
sent back to the process that initiated the send resulting in this
|
|
trigger. Thus, ``trigger_with_reply`` should only be used for messages
|
|
that need immediate responses. These triggers can only be invoked via
|
|
the out-of-band sends that wait for the reply, via
|
|
``send_oob_with_reply``. There is also a `simple trigger interface`_
|
|
for defining triggers in common cases.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
trigger_receive_context trigger_context() const;
|
|
|
|
Retrieves the current context of the process group with respect to the
|
|
invocation of triggers. When ``trc_none``, the process group is not
|
|
currently invoking any triggers. Otherwise, this value describes in
|
|
what context the currently executing trigger is being invoked.
|
|
|
|
|
|
Helper operations
|
|
~~~~~~~~~~~~~~~~~
|
|
|
|
::
|
|
|
|
void poll();
|
|
|
|
Permits the process group to receive any incomining messages,
|
|
processing them via triggers. If you have a long-running computation
|
|
that does not invoke any of the process group's communication
|
|
routines, you should call ``poll`` occasionally to along incoming
|
|
messages to be processed.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
ProcessGroup base() const;
|
|
|
|
Retrieves the "base" process group for this process group, which is a
|
|
copy of the underlying process group that does not reference any
|
|
specific distributed data structure.
|
|
|
|
Process query
|
|
~~~~~~~~~~~~~
|
|
|
|
::
|
|
|
|
int process_id(const ProcessGroup& pg);
|
|
|
|
Retrieves the ID (or "rank") of the calling process within the process
|
|
group. Process IDs are values in the range [0, ``num_processes(pg)``)
|
|
that uniquely identify the process. Process IDs can be used to
|
|
initiate communication with another process.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
int num_processes(const ProcessGroup& pg);
|
|
|
|
Returns the number of processes within the process group.
|
|
|
|
|
|
Message transmission
|
|
~~~~~~~~~~~~~~~~~~~~
|
|
|
|
::
|
|
|
|
template<typename T>
|
|
void send(const ProcessGroup& pg, int dest, int tag, const T& value);
|
|
|
|
Sends a message with the given ``tag`` and carrying the given
|
|
``value`` to the process with ID ``dest`` in the given process
|
|
group. All message sends are non-blocking, meaning that this send
|
|
operation will not block while waiting for the communication to
|
|
complete. There is no guarantee when the message will be received,
|
|
except that it will become available to the destination process by the
|
|
end of the superstep, in the collective call to ``synchronize``.
|
|
|
|
Any type of value can be transmitted via ``send``, so long as it
|
|
provides the appropriate functionality to be serialized with the
|
|
Boost.Serialization library.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
template<typename T>
|
|
void receive(const ProcessGroup& pg, int source, int tag, T& value);
|
|
|
|
Receives a message with the given ``tag`` sent from the process
|
|
``source``, updating ``value`` with the payload of the message. This
|
|
receive operation can only receive messages sent within the previous
|
|
superstep via the ``send`` operation. If no such message is available
|
|
at the time ``receive`` is called, the program is ill-formed.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
optional<std::pair<int, int> > probe(const ProcessGroup& pg);
|
|
|
|
Determines whether a message is available. The probe operation checks
|
|
for any messages that were sent in the previous superstep but have not
|
|
yet been received. If such a message exists, ``probe`` returns a
|
|
(source, tag) pair describing the message. Otherwise, ``probe`` will
|
|
return an empty ``boost::optional``.
|
|
|
|
A typical use of ``probe`` is to continually probe for messages at the
|
|
beginning of the superstep, receiving and processing those messages
|
|
until no messages remain.
|
|
|
|
|
|
Synchronization
|
|
~~~~~~~~~~~~~~~
|
|
|
|
::
|
|
|
|
void synchronize(const ProcessGroup& pg);
|
|
|
|
The ``synchronize`` function is a collective operation that must be
|
|
invoked by all of the processes within the process group. A call to
|
|
``synchronize`` marks the end of a superstep in the parallel
|
|
computation. All messages sent before the end of the superstep will be
|
|
received into message buffers, and can be processed by the program in
|
|
the next superstep. None of the processes will leave the
|
|
``synchronize`` function until all of the processes have entered the
|
|
function and exchanged messages, so that all processes are always on
|
|
the same superstep.
|
|
|
|
Out-of-band communication
|
|
~~~~~~~~~~~~~~~~~~~~~~~~~
|
|
|
|
::
|
|
|
|
template<typename T>
|
|
void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value);
|
|
|
|
Sends and out-of-band message. This out-of-band send operation acts
|
|
like the normal ``send`` operation, except that out-of-band messages
|
|
are delivered immediately through a high-priority channel.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
template<typename T, typename U>
|
|
void
|
|
send_oob_with_reply(const ProcessGroup& pg, int dest, int
|
|
tag, const T& send_value, U& receive_value);
|
|
|
|
Sends an out-of-band message and waits for a reply. The
|
|
``send_oob_with_reply`` function can only be invoked with message tags
|
|
that correspond to triggers registered with
|
|
``trigger_with_reply``. This operation will send the message
|
|
immediately (through the high-priority, out-of-band channel), then
|
|
wait until the remote process sends a reply. The data from the reply
|
|
is stored into ``receive_value``.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
template<typename T>
|
|
void receive_oob(const ProcessGroup& pg, int source, int tag, T& value);
|
|
|
|
Receives an out-of-band message with the given ``source`` and
|
|
``tag``. As with the normal ``receive`` operation, it is an error to
|
|
call ``receive_oob`` if no message matching the source and tag is
|
|
available. This routine is used only rarely; for most circumstances,
|
|
use ``send_oob_with_reply`` to perform an immediate send with a
|
|
reply.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
Copyright (C) 2007 Douglas Gregor
|
|
|
|
Copyright (C) 2007 Matthias Troyer
|
|
|
|
.. |Logo| image:: pbgl-logo.png
|
|
:align: middle
|
|
:alt: Parallel BGL
|
|
:target: http://www.osl.iu.edu/research/pbgl
|
|
|
|
.. _MPI BSP process group: mpi_bsp_process_group.html
|
|
.. _Simple trigger interface: simple_trigger.html
|