123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487 |
- .. 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
|