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