123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL Parallel BGL Process Groups</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-parallel-bgl-process-groups">
- <h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Parallel BGL Process Groups</h1>
- <!-- 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) -->
- <div class="contents topic" id="contents">
- <p class="topic-title first">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#introduction" id="id1">Introduction</a></li>
- <li><a class="reference internal" href="#communication-model" id="id2">Communication model</a><ul>
- <li><a class="reference internal" href="#distributed-data-structures" id="id3">Distributed data structures</a></li>
- <li><a class="reference internal" href="#asynchronous-receives" id="id4">Asynchronous receives</a></li>
- <li><a class="reference internal" href="#out-of-band-messaging" id="id5">Out-of-band messaging</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#reference" id="id6">Reference</a><ul>
- <li><a class="reference internal" href="#process-group-constructors" id="id7">Process group constructors</a></li>
- <li><a class="reference internal" href="#triggers" id="id8">Triggers</a></li>
- <li><a class="reference internal" href="#helper-operations" id="id9">Helper operations</a></li>
- <li><a class="reference internal" href="#process-query" id="id10">Process query</a></li>
- <li><a class="reference internal" href="#message-transmission" id="id11">Message transmission</a></li>
- <li><a class="reference internal" href="#synchronization" id="id12">Synchronization</a></li>
- <li><a class="reference internal" href="#out-of-band-communication" id="id13">Out-of-band communication</a></li>
- </ul>
- </li>
- </ul>
- </div>
- <div class="section" id="introduction">
- <h1><a class="toc-backref" href="#id1">Introduction</a></h1>
- <p>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.</p>
- </div>
- <div class="section" id="communication-model">
- <h1><a class="toc-backref" href="#id2">Communication model</a></h1>
- <p>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 <em>supersteps</em>, 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.</p>
- <p>The boundary between supersteps in the Parallel BGL corresponds to the
- <tt class="docutils literal"><span class="pre">synchronize</span></tt> operation. Whenever a process has completed its local
- computation phase and sent all of the messages required for that
- superstep, it invokes the <tt class="docutils literal"><span class="pre">synchronize</span></tt> operation on the process
- group. Once all processes in the process group have entered
- <tt class="docutils literal"><span class="pre">synchronize</span></tt>, they exchange messages and then continue with the
- next superstep.</p>
- <p>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.</p>
- <div class="section" id="distributed-data-structures">
- <h2><a class="toc-backref" href="#id3">Distributed data structures</a></h2>
- <p>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.</p>
- <p>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.</p>
- <p>A distributed data structure attaches itself to the process group by
- creating a copy of the process group and passing an
- <tt class="docutils literal"><span class="pre">attach_distributed_object</span></tt> 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
- <tt class="docutils literal"><span class="pre">attach_distributed_object</span></tt>, e.g.,</p>
- <pre class="literal-block">
- 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;
- };
- </pre>
- </div>
- <div class="section" id="asynchronous-receives">
- <h2><a class="toc-backref" href="#id4">Asynchronous receives</a></h2>
- <p>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.</p>
- <p>Distributed data structures receive messages through
- "triggers". Triggers are function objects responsible for processing a
- received message. Each trigger is registered with the <tt class="docutils literal"><span class="pre">trigger</span></tt>
- 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.</p>
- <p>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
- <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> method and should return the value that will be
- sent back to the caller. The <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> facility is only
- useful in conjunction with out-of-band messaging, discussed next.</p>
- </div>
- <div class="section" id="out-of-band-messaging">
- <h2><a class="toc-backref" href="#id5">Out-of-band messaging</a></h2>
- <p>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.</p>
- <p>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 <tt class="docutils literal"><span class="pre">name</span></tt> to process <tt class="docutils literal"><span class="pre">owner</span></tt> with tag
- <tt class="docutils literal"><span class="pre">msg_get_descriptor_by_name</span></tt> 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
- <tt class="docutils literal"><span class="pre">vertex_descriptor</span></tt>--that will be passed back to the process that
- initiated the communication. The full communication happens
- immediately, within the current superstep.</p>
- <pre class="literal-block">
- std::string name;
- vertex_descriptor descriptor;
- send_oob_with_reply(process_group, owner, msg_get_descriptor_by_name,
- name, descriptor);
- </pre>
- </div>
- </div>
- <div class="section" id="reference">
- <h1><a class="toc-backref" href="#id6">Reference</a></h1>
- <p>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 <tt class="docutils literal"><span class="pre">ProcessGroup</span></tt> to stand in for
- the various process group implementations that exist. There is only
- one implementation of the process group interface at this time:</p>
- <blockquote>
- <ul class="simple">
- <li><a class="reference external" href="mpi_bsp_process_group.html">MPI BSP process group</a></li>
- </ul>
- </blockquote>
- <pre class="literal-block">
- 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);
- </pre>
- <div class="section" id="process-group-constructors">
- <h2><a class="toc-backref" href="#id7">Process group constructors</a></h2>
- <pre class="literal-block">
- ProcessGroup();
- </pre>
- <p>Constructs a new process group with a different communication space
- from any other process group.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- ProcessGroup(const ProcessGroup& pg, boost::parallel::attach_distributed_object);
- </pre>
- <p>Attaches a new distributed data structure to the process group
- <tt class="docutils literal"><span class="pre">pg</span></tt>. 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.</p>
- </div>
- <div class="section" id="triggers">
- <h2><a class="toc-backref" href="#id8">Triggers</a></h2>
- <pre class="literal-block">
- template<typename Type, typename Handler>
- void trigger(int tag, const Handler& handler);
- </pre>
- <p>Registers a trigger with the given process group. The trigger will
- watch for messages with the given <tt class="docutils literal"><span class="pre">tag</span></tt>. When such a message is
- available, it will be received into a value of type <tt class="docutils literal"><span class="pre">Type</span></tt>, and the
- function object <tt class="docutils literal"><span class="pre">handler</span></tt> will be invoked with four parameters:</p>
- <dl class="docutils">
- <dt>source</dt>
- <dd>The rank of the source process (an <tt class="docutils literal"><span class="pre">int</span></tt>)</dd>
- <dt>tag</dt>
- <dd>The tag used to send the message (also an <tt class="docutils literal"><span class="pre">int</span></tt>)</dd>
- <dt>data:</dt>
- <dd>The data transmitted with the message. The data will have the type
- specified when the trigger was registered.</dd>
- <dt>context:</dt>
- <dd>The context in which the trigger is executed. This will be a value of
- type <tt class="docutils literal"><span class="pre">trigger_receive_context</span></tt>, 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.</dd>
- </dl>
- <p>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 <a class="reference external" href="simple_trigger.html">simple trigger interface</a> for defining
- triggers in common cases.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template<typename Type, typename Handler>
- void trigger_with_reply(int tag, const Handler& handler);
- </pre>
- <p>Like the <tt class="docutils literal"><span class="pre">trigger</span></tt> method, registers a trigger with the given
- process group. The trigger will watch for messages with the given
- <tt class="docutils literal"><span class="pre">tag</span></tt>. When such a message is available, it will be received into a
- value of type <tt class="docutils literal"><span class="pre">Type</span></tt> and <tt class="docutils literal"><span class="pre">handler</span></tt> will be invoked, just as with a
- normal trigger. However, a trigger registered with
- <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> must return a value, which will be immediately
- sent back to the process that initiated the send resulting in this
- trigger. Thus, <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> 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
- <tt class="docutils literal"><span class="pre">send_oob_with_reply</span></tt>. There is also a <a class="reference external" href="simple_trigger.html">simple trigger interface</a>
- for defining triggers in common cases.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- trigger_receive_context trigger_context() const;
- </pre>
- <p>Retrieves the current context of the process group with respect to the
- invocation of triggers. When <tt class="docutils literal"><span class="pre">trc_none</span></tt>, the process group is not
- currently invoking any triggers. Otherwise, this value describes in
- what context the currently executing trigger is being invoked.</p>
- </div>
- <div class="section" id="helper-operations">
- <h2><a class="toc-backref" href="#id9">Helper operations</a></h2>
- <pre class="literal-block">
- void poll();
- </pre>
- <p>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 <tt class="docutils literal"><span class="pre">poll</span></tt> occasionally to along incoming
- messages to be processed.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- ProcessGroup base() const;
- </pre>
- <p>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.</p>
- </div>
- <div class="section" id="process-query">
- <h2><a class="toc-backref" href="#id10">Process query</a></h2>
- <pre class="literal-block">
- int process_id(const ProcessGroup& pg);
- </pre>
- <p>Retrieves the ID (or "rank") of the calling process within the process
- group. Process IDs are values in the range [0, <tt class="docutils literal"><span class="pre">num_processes(pg)</span></tt>)
- that uniquely identify the process. Process IDs can be used to
- initiate communication with another process.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- int num_processes(const ProcessGroup& pg);
- </pre>
- <p>Returns the number of processes within the process group.</p>
- </div>
- <div class="section" id="message-transmission">
- <h2><a class="toc-backref" href="#id11">Message transmission</a></h2>
- <pre class="literal-block">
- template<typename T>
- void send(const ProcessGroup& pg, int dest, int tag, const T& value);
- </pre>
- <p>Sends a message with the given <tt class="docutils literal"><span class="pre">tag</span></tt> and carrying the given
- <tt class="docutils literal"><span class="pre">value</span></tt> to the process with ID <tt class="docutils literal"><span class="pre">dest</span></tt> 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 <tt class="docutils literal"><span class="pre">synchronize</span></tt>.</p>
- <p>Any type of value can be transmitted via <tt class="docutils literal"><span class="pre">send</span></tt>, so long as it
- provides the appropriate functionality to be serialized with the
- Boost.Serialization library.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template<typename T>
- void receive(const ProcessGroup& pg, int source, int tag, T& value);
- </pre>
- <p>Receives a message with the given <tt class="docutils literal"><span class="pre">tag</span></tt> sent from the process
- <tt class="docutils literal"><span class="pre">source</span></tt>, updating <tt class="docutils literal"><span class="pre">value</span></tt> with the payload of the message. This
- receive operation can only receive messages sent within the previous
- superstep via the <tt class="docutils literal"><span class="pre">send</span></tt> operation. If no such message is available
- at the time <tt class="docutils literal"><span class="pre">receive</span></tt> is called, the program is ill-formed.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- optional<std::pair<int, int> > probe(const ProcessGroup& pg);
- </pre>
- <p>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, <tt class="docutils literal"><span class="pre">probe</span></tt> returns a
- (source, tag) pair describing the message. Otherwise, <tt class="docutils literal"><span class="pre">probe</span></tt> will
- return an empty <tt class="docutils literal"><span class="pre">boost::optional</span></tt>.</p>
- <p>A typical use of <tt class="docutils literal"><span class="pre">probe</span></tt> is to continually probe for messages at the
- beginning of the superstep, receiving and processing those messages
- until no messages remain.</p>
- </div>
- <div class="section" id="synchronization">
- <h2><a class="toc-backref" href="#id12">Synchronization</a></h2>
- <pre class="literal-block">
- void synchronize(const ProcessGroup& pg);
- </pre>
- <p>The <tt class="docutils literal"><span class="pre">synchronize</span></tt> function is a collective operation that must be
- invoked by all of the processes within the process group. A call to
- <tt class="docutils literal"><span class="pre">synchronize</span></tt> 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
- <tt class="docutils literal"><span class="pre">synchronize</span></tt> function until all of the processes have entered the
- function and exchanged messages, so that all processes are always on
- the same superstep.</p>
- </div>
- <div class="section" id="out-of-band-communication">
- <h2><a class="toc-backref" href="#id13">Out-of-band communication</a></h2>
- <pre class="literal-block">
- template<typename T>
- void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value);
- </pre>
- <p>Sends and out-of-band message. This out-of-band send operation acts
- like the normal <tt class="docutils literal"><span class="pre">send</span></tt> operation, except that out-of-band messages
- are delivered immediately through a high-priority channel.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template<typename T, typename U>
- void
- send_oob_with_reply(const ProcessGroup& pg, int dest, int
- tag, const T& send_value, U& receive_value);
- </pre>
- <p>Sends an out-of-band message and waits for a reply. The
- <tt class="docutils literal"><span class="pre">send_oob_with_reply</span></tt> function can only be invoked with message tags
- that correspond to triggers registered with
- <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt>. 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 <tt class="docutils literal"><span class="pre">receive_value</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- template<typename T>
- void receive_oob(const ProcessGroup& pg, int source, int tag, T& value);
- </pre>
- <p>Receives an out-of-band message with the given <tt class="docutils literal"><span class="pre">source</span></tt> and
- <tt class="docutils literal"><span class="pre">tag</span></tt>. As with the normal <tt class="docutils literal"><span class="pre">receive</span></tt> operation, it is an error to
- call <tt class="docutils literal"><span class="pre">receive_oob</span></tt> if no message matching the source and tag is
- available. This routine is used only rarely; for most circumstances,
- use <tt class="docutils literal"><span class="pre">send_oob_with_reply</span></tt> to perform an immediate send with a
- reply.</p>
- <hr class="docutils" />
- <p>Copyright (C) 2007 Douglas Gregor</p>
- <p>Copyright (C) 2007 Matthias Troyer</p>
- </div>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:22 UTC.
- Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
- </div>
- </body>
- </html>
|