1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>Parallel BGL Parallel BGL Process Groups</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-parallel-bgl-process-groups"> 12<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> 13 14<!-- Copyright (C) 2004-2008 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<div class="contents topic" id="contents"> 19<p class="topic-title first">Contents</p> 20<ul class="simple"> 21<li><a class="reference internal" href="#introduction" id="id1">Introduction</a></li> 22<li><a class="reference internal" href="#communication-model" id="id2">Communication model</a><ul> 23<li><a class="reference internal" href="#distributed-data-structures" id="id3">Distributed data structures</a></li> 24<li><a class="reference internal" href="#asynchronous-receives" id="id4">Asynchronous receives</a></li> 25<li><a class="reference internal" href="#out-of-band-messaging" id="id5">Out-of-band messaging</a></li> 26</ul> 27</li> 28<li><a class="reference internal" href="#reference" id="id6">Reference</a><ul> 29<li><a class="reference internal" href="#process-group-constructors" id="id7">Process group constructors</a></li> 30<li><a class="reference internal" href="#triggers" id="id8">Triggers</a></li> 31<li><a class="reference internal" href="#helper-operations" id="id9">Helper operations</a></li> 32<li><a class="reference internal" href="#process-query" id="id10">Process query</a></li> 33<li><a class="reference internal" href="#message-transmission" id="id11">Message transmission</a></li> 34<li><a class="reference internal" href="#synchronization" id="id12">Synchronization</a></li> 35<li><a class="reference internal" href="#out-of-band-communication" id="id13">Out-of-band communication</a></li> 36</ul> 37</li> 38</ul> 39</div> 40<div class="section" id="introduction"> 41<h1><a class="toc-backref" href="#id1">Introduction</a></h1> 42<p>Process groups are an abstraction of a set of communicating processes 43that coordinate to solve the same problem. Process groups contain 44facilities for identifying the processes within that group, sending 45and receiving messages between the processes in that group, and 46performing collective communications involving all processes in the 47group simultaneously.</p> 48</div> 49<div class="section" id="communication-model"> 50<h1><a class="toc-backref" href="#id2">Communication model</a></h1> 51<p>Process groups are based on an extended version of the Bulk 52Synchronous Parallel (BSP) model of computation. Parallel computations 53in the BSP model are organized into <em>supersteps</em>, each of which 54consists of a computation phase followed by a communication 55phase. During the computation phase, all processes in the process 56group work exclusively on local data, and there is no inter-process 57communication. During the communication phase, all of the processes 58exchange message with each other. Messages sent in the communication 59phase of a superstep will be received in the next superstep.</p> 60<p>The boundary between supersteps in the Parallel BGL corresponds to the 61<tt class="docutils literal"><span class="pre">synchronize</span></tt> operation. Whenever a process has completed its local 62computation phase and sent all of the messages required for that 63superstep, it invokes the <tt class="docutils literal"><span class="pre">synchronize</span></tt> operation on the process 64group. Once all processes in the process group have entered 65<tt class="docutils literal"><span class="pre">synchronize</span></tt>, they exchange messages and then continue with the 66next superstep.</p> 67<p>The Parallel BGL loosens the BSP model significantly, to provide a 68more natural programming model that also provides some performance 69benefits over the strict BSP model. The primary extension is the 70ability to receive messages sent within the same superstep 71"asynchronously", either to free up message buffers or to respond to 72an immediate request for information. For particularly unstructured 73computations, the ability to send a message and get an immediate reply 74can simplify many computations that would otherwise need to be split 75into two separate supersteps. Additionally, the Parallel BGL augments 76the BSP model with support for multiple distributed data structures, 77each of which are provided with a different communication space but 78whose messages will all be synchronized concurrently.</p> 79<div class="section" id="distributed-data-structures"> 80<h2><a class="toc-backref" href="#id3">Distributed data structures</a></h2> 81<p>A typical computation with the Parallel BGL involves several 82distributed data structures working in concern. For example, a simple 83breadth-first search involves the distributed graph data structure 84containing the graph itself, a distributed queue that manages the 85traversal through the graph, and a distributed property map that 86tracks which vertices have already been visited as part of the 87search.</p> 88<p>The Parallel BGL manages these distributed data structures by allowing 89each of the data structures to attach themselves to the process group 90itself. When a distributed data structure attaches to the process 91group, it receives its own copy of the process group that allows the 92distributed data structure to communicate without colliding with the 93communications from other distributed data structures. When the 94process group is synchronized, all of the distributed data structures 95attached to that process group are automatically synchronized, so that 96all of the distributed data structures in a computation remain 97synchronized.</p> 98<p>A distributed data structure attaches itself to the process group by 99creating a copy of the process group and passing an 100<tt class="docutils literal"><span class="pre">attach_distributed_object</span></tt> flag to the process group 101constructor. So long as this copy of the process group persists, the 102distributed data structure is attached the process group. For this 103reason, most distributed data structures keep a copy of the process 104group as member data, constructing the member with 105<tt class="docutils literal"><span class="pre">attach_distributed_object</span></tt>, e.g.,</p> 106<pre class="literal-block"> 107template<typename ProcessGroup> 108struct distributed_data_structure 109{ 110 explicit distributed_data_structure(const ProcessGroup& pg) 111 : process_group(pg, boost::parallel::attach_distributed_object()) 112 { } 113 114private: 115 ProcessGroup process_group; 116}; 117</pre> 118</div> 119<div class="section" id="asynchronous-receives"> 120<h2><a class="toc-backref" href="#id4">Asynchronous receives</a></h2> 121<p>Distributed data structures in the Parallel BGL can "asynchronously" 122receive and process messages before the end of a BSP 123superstep. Messages can be received any time that a process is inside 124the process group operations, and the scheduling of message receives 125is entirely managed by the process group.</p> 126<p>Distributed data structures receive messages through 127"triggers". Triggers are function objects responsible for processing a 128received message. Each trigger is registered with the <tt class="docutils literal"><span class="pre">trigger</span></tt> 129method of the process group using a specific message 130tag (an integer) and the type of data that is expected to be 131contained within that message. Whenever a message with that tag 132becomes available, the progress group will call the trigger with the 133source of the message, the message tag, the data contained in the 134message, and the "context" of the message.</p> 135<p>The majority of triggers have no return value, although it is common 136that the triggers send messages back to the source process. In certain 137cases where the trigger's purpose is to immediately reply with a 138value, the trigger should be registered with the 139<tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> method and should return the value that will be 140sent back to the caller. The <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> facility is only 141useful in conjunction with out-of-band messaging, discussed next.</p> 142</div> 143<div class="section" id="out-of-band-messaging"> 144<h2><a class="toc-backref" href="#id5">Out-of-band messaging</a></h2> 145<p>The majority of messages sent by the Parallel BGL are sent through the 146normal send operations, to be received in the next superstep or, in 147some cases, received "early" by a trigger. These messages are not 148time-sensitive, so they will be delivered whenever the process group 149processes them.</p> 150<p>Some messages, however, require immediate responses. For example, if a 151process needs to determine the current value associated with a vertex 152owned by another process, the first process must send a request to the 153second process and block while waiting for a response. For such 154messages, the Parallel BGL's process groups provide an out-of-band 155messaging mechanism. Out-of-band messages are transmitted immediately, 156with a much higher priority than other messages. The sending of 157out-of-band messages can be coupled with a receive operation that 158waits until the remote process has received the message and sent its 159reply. For example, in the following code the process sends a message 160containing 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 161<tt class="docutils literal"><span class="pre">msg_get_descriptor_by_name</span></tt> via an out-of-band message. The 162receiver of that message will immediately deliver the message via a 163trigger, that returns the resulting value--a 164<tt class="docutils literal"><span class="pre">vertex_descriptor</span></tt>--that will be passed back to the process that 165initiated the communication. The full communication happens 166immediately, within the current superstep.</p> 167<pre class="literal-block"> 168std::string name; 169vertex_descriptor descriptor; 170send_oob_with_reply(process_group, owner, msg_get_descriptor_by_name, 171 name, descriptor); 172</pre> 173</div> 174</div> 175<div class="section" id="reference"> 176<h1><a class="toc-backref" href="#id6">Reference</a></h1> 177<p>The Parallel BGL process groups specify an interface that can be 178implemented by various communication subsystems. In this reference 179section, we use the placeholder type <tt class="docutils literal"><span class="pre">ProcessGroup</span></tt> to stand in for 180the various process group implementations that exist. There is only 181one implementation of the process group interface at this time:</p> 182<blockquote> 183<ul class="simple"> 184<li><a class="reference external" href="mpi_bsp_process_group.html">MPI BSP process group</a></li> 185</ul> 186</blockquote> 187<pre class="literal-block"> 188enum trigger_receive_context { 189 trc_none, 190 trc_in_synchronization, 191 trc_early_receive, 192 trc_out_of_band 193}; 194 195class ProcessGroup 196{ 197 // Process group constructors 198 ProcessGroup(); 199 ProcessGroup(const ProcessGroup&, boost::parallel::attach_distributed_object); 200 201 // Triggers 202 template<typename Type, typename Handler> 203 void trigger(int tag, const Handler& handler); 204 205 template<typename Type, typename Handler> 206 void trigger_with_reply(int tag, const Handler& handler); 207 208 trigger_receive_context trigger_context() const; 209 210 // Helper operations 211 void poll(); 212 ProcessGroup base() const; 213}; 214 215// Process query 216int process_id(const ProcessGroup&); 217int num_processes(const ProcessGroup&); 218 219// Message transmission 220template<typename T> 221 void send(const ProcessGroup& pg, int dest, int tag, const T& value); 222 223template<typename T> 224 void receive(const ProcessGroup& pg, int source, int tag, T& value); 225 226optional<std::pair<int, int> > probe(const ProcessGroup& pg); 227 228// Synchronization 229void synchronize(const ProcessGroup& pg); 230 231// Out-of-band communication 232template<typename T> 233 void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value); 234 235template<typename T, typename U> 236 void 237 send_oob_with_reply(const ProcessGroup& pg, int dest, int 238 tag, const T& send_value, U& receive_value); 239 240template<typename T> 241 void receive_oob(const ProcessGroup& pg, int source, int tag, T& value); 242</pre> 243<div class="section" id="process-group-constructors"> 244<h2><a class="toc-backref" href="#id7">Process group constructors</a></h2> 245<pre class="literal-block"> 246ProcessGroup(); 247</pre> 248<p>Constructs a new process group with a different communication space 249from any other process group.</p> 250<hr class="docutils" /> 251<pre class="literal-block"> 252ProcessGroup(const ProcessGroup& pg, boost::parallel::attach_distributed_object); 253</pre> 254<p>Attaches a new distributed data structure to the process group 255<tt class="docutils literal"><span class="pre">pg</span></tt>. The resulting process group can be used for communication 256within that new distributed data structure. When the newly-constructed 257process group is eventually destroyed, the distributed data structure 258is detached from the process group.</p> 259</div> 260<div class="section" id="triggers"> 261<h2><a class="toc-backref" href="#id8">Triggers</a></h2> 262<pre class="literal-block"> 263template<typename Type, typename Handler> 264 void trigger(int tag, const Handler& handler); 265</pre> 266<p>Registers a trigger with the given process group. The trigger will 267watch for messages with the given <tt class="docutils literal"><span class="pre">tag</span></tt>. When such a message is 268available, it will be received into a value of type <tt class="docutils literal"><span class="pre">Type</span></tt>, and the 269function object <tt class="docutils literal"><span class="pre">handler</span></tt> will be invoked with four parameters:</p> 270<dl class="docutils"> 271<dt>source</dt> 272<dd>The rank of the source process (an <tt class="docutils literal"><span class="pre">int</span></tt>)</dd> 273<dt>tag</dt> 274<dd>The tag used to send the message (also an <tt class="docutils literal"><span class="pre">int</span></tt>)</dd> 275<dt>data:</dt> 276<dd>The data transmitted with the message. The data will have the type 277specified when the trigger was registered.</dd> 278<dt>context:</dt> 279<dd>The context in which the trigger is executed. This will be a value of 280type <tt class="docutils literal"><span class="pre">trigger_receive_context</span></tt>, which stages whether the trigger 281is being executed during synchronization, asynchronously in response 282to an "early" receive (often to free up communication buffers), or 283in response to an "out-of-band" message.</dd> 284</dl> 285<p>Triggers can only be registered by process groups that result from 286attaching a distributed data structure. A trigger can be invoked in 287response to either a normal send operation or an out-of-band send 288operation. There is also a <a class="reference external" href="simple_trigger.html">simple trigger interface</a> for defining 289triggers in common cases.</p> 290<hr class="docutils" /> 291<pre class="literal-block"> 292template<typename Type, typename Handler> 293 void trigger_with_reply(int tag, const Handler& handler); 294</pre> 295<p>Like the <tt class="docutils literal"><span class="pre">trigger</span></tt> method, registers a trigger with the given 296process group. The trigger will watch for messages with the given 297<tt class="docutils literal"><span class="pre">tag</span></tt>. When such a message is available, it will be received into a 298value 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 299normal trigger. However, a trigger registered with 300<tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> must return a value, which will be immediately 301sent back to the process that initiated the send resulting in this 302trigger. Thus, <tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt> should only be used for messages 303that need immediate responses. These triggers can only be invoked via 304the out-of-band sends that wait for the reply, via 305<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> 306for defining triggers in common cases.</p> 307<hr class="docutils" /> 308<pre class="literal-block"> 309trigger_receive_context trigger_context() const; 310</pre> 311<p>Retrieves the current context of the process group with respect to the 312invocation of triggers. When <tt class="docutils literal"><span class="pre">trc_none</span></tt>, the process group is not 313currently invoking any triggers. Otherwise, this value describes in 314what context the currently executing trigger is being invoked.</p> 315</div> 316<div class="section" id="helper-operations"> 317<h2><a class="toc-backref" href="#id9">Helper operations</a></h2> 318<pre class="literal-block"> 319void poll(); 320</pre> 321<p>Permits the process group to receive any incomining messages, 322processing them via triggers. If you have a long-running computation 323that does not invoke any of the process group's communication 324routines, you should call <tt class="docutils literal"><span class="pre">poll</span></tt> occasionally to along incoming 325messages to be processed.</p> 326<hr class="docutils" /> 327<pre class="literal-block"> 328ProcessGroup base() const; 329</pre> 330<p>Retrieves the "base" process group for this process group, which is a 331copy of the underlying process group that does not reference any 332specific distributed data structure.</p> 333</div> 334<div class="section" id="process-query"> 335<h2><a class="toc-backref" href="#id10">Process query</a></h2> 336<pre class="literal-block"> 337int process_id(const ProcessGroup& pg); 338</pre> 339<p>Retrieves the ID (or "rank") of the calling process within the process 340group. Process IDs are values in the range [0, <tt class="docutils literal"><span class="pre">num_processes(pg)</span></tt>) 341that uniquely identify the process. Process IDs can be used to 342initiate communication with another process.</p> 343<hr class="docutils" /> 344<pre class="literal-block"> 345int num_processes(const ProcessGroup& pg); 346</pre> 347<p>Returns the number of processes within the process group.</p> 348</div> 349<div class="section" id="message-transmission"> 350<h2><a class="toc-backref" href="#id11">Message transmission</a></h2> 351<pre class="literal-block"> 352template<typename T> 353 void send(const ProcessGroup& pg, int dest, int tag, const T& value); 354</pre> 355<p>Sends a message with the given <tt class="docutils literal"><span class="pre">tag</span></tt> and carrying the given 356<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 357group. All message sends are non-blocking, meaning that this send 358operation will not block while waiting for the communication to 359complete. There is no guarantee when the message will be received, 360except that it will become available to the destination process by the 361end of the superstep, in the collective call to <tt class="docutils literal"><span class="pre">synchronize</span></tt>.</p> 362<p>Any type of value can be transmitted via <tt class="docutils literal"><span class="pre">send</span></tt>, so long as it 363provides the appropriate functionality to be serialized with the 364Boost.Serialization library.</p> 365<hr class="docutils" /> 366<pre class="literal-block"> 367template<typename T> 368 void receive(const ProcessGroup& pg, int source, int tag, T& value); 369</pre> 370<p>Receives a message with the given <tt class="docutils literal"><span class="pre">tag</span></tt> sent from the process 371<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 372receive operation can only receive messages sent within the previous 373superstep via the <tt class="docutils literal"><span class="pre">send</span></tt> operation. If no such message is available 374at the time <tt class="docutils literal"><span class="pre">receive</span></tt> is called, the program is ill-formed.</p> 375<hr class="docutils" /> 376<pre class="literal-block"> 377optional<std::pair<int, int> > probe(const ProcessGroup& pg); 378</pre> 379<p>Determines whether a message is available. The probe operation checks 380for any messages that were sent in the previous superstep but have not 381yet been received. If such a message exists, <tt class="docutils literal"><span class="pre">probe</span></tt> returns a 382(source, tag) pair describing the message. Otherwise, <tt class="docutils literal"><span class="pre">probe</span></tt> will 383return an empty <tt class="docutils literal"><span class="pre">boost::optional</span></tt>.</p> 384<p>A typical use of <tt class="docutils literal"><span class="pre">probe</span></tt> is to continually probe for messages at the 385beginning of the superstep, receiving and processing those messages 386until no messages remain.</p> 387</div> 388<div class="section" id="synchronization"> 389<h2><a class="toc-backref" href="#id12">Synchronization</a></h2> 390<pre class="literal-block"> 391void synchronize(const ProcessGroup& pg); 392</pre> 393<p>The <tt class="docutils literal"><span class="pre">synchronize</span></tt> function is a collective operation that must be 394invoked by all of the processes within the process group. A call to 395<tt class="docutils literal"><span class="pre">synchronize</span></tt> marks the end of a superstep in the parallel 396computation. All messages sent before the end of the superstep will be 397received into message buffers, and can be processed by the program in 398the next superstep. None of the processes will leave the 399<tt class="docutils literal"><span class="pre">synchronize</span></tt> function until all of the processes have entered the 400function and exchanged messages, so that all processes are always on 401the same superstep.</p> 402</div> 403<div class="section" id="out-of-band-communication"> 404<h2><a class="toc-backref" href="#id13">Out-of-band communication</a></h2> 405<pre class="literal-block"> 406template<typename T> 407 void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value); 408</pre> 409<p>Sends and out-of-band message. This out-of-band send operation acts 410like the normal <tt class="docutils literal"><span class="pre">send</span></tt> operation, except that out-of-band messages 411are delivered immediately through a high-priority channel.</p> 412<hr class="docutils" /> 413<pre class="literal-block"> 414template<typename T, typename U> 415 void 416 send_oob_with_reply(const ProcessGroup& pg, int dest, int 417 tag, const T& send_value, U& receive_value); 418</pre> 419<p>Sends an out-of-band message and waits for a reply. The 420<tt class="docutils literal"><span class="pre">send_oob_with_reply</span></tt> function can only be invoked with message tags 421that correspond to triggers registered with 422<tt class="docutils literal"><span class="pre">trigger_with_reply</span></tt>. This operation will send the message 423immediately (through the high-priority, out-of-band channel), then 424wait until the remote process sends a reply. The data from the reply 425is stored into <tt class="docutils literal"><span class="pre">receive_value</span></tt>.</p> 426<hr class="docutils" /> 427<pre class="literal-block"> 428template<typename T> 429 void receive_oob(const ProcessGroup& pg, int source, int tag, T& value); 430</pre> 431<p>Receives an out-of-band message with the given <tt class="docutils literal"><span class="pre">source</span></tt> and 432<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 433call <tt class="docutils literal"><span class="pre">receive_oob</span></tt> if no message matching the source and tag is 434available. This routine is used only rarely; for most circumstances, 435use <tt class="docutils literal"><span class="pre">send_oob_with_reply</span></tt> to perform an immediate send with a 436reply.</p> 437<hr class="docutils" /> 438<p>Copyright (C) 2007 Douglas Gregor</p> 439<p>Copyright (C) 2007 Matthias Troyer</p> 440</div> 441</div> 442</div> 443<div class="footer"> 444<hr class="footer" /> 445Generated on: 2009-05-31 00:22 UTC. 446Generated 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. 447 448</div> 449</body> 450</html> 451
