]>
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| Distributed queue adaptor | |
8 | ================================ | |
9 | ||
10 | :: | |
11 | ||
12 | template<typename ProcessGroup, typename Buffer> | |
13 | class distributed_queue | |
14 | { | |
15 | public: | |
16 | typedef ProcessGroup process_group_type; | |
17 | typedef Buffer buffer_type; | |
18 | typedef typename buffer_type::value_type value_type; | |
19 | typedef typename buffer_type::size_type size_type; | |
20 | ||
21 | explicit | |
22 | distributed_queue(const ProcessGroup& process_group = ProcessGroup(), | |
23 | const Buffer& buffer = Buffer(), | |
24 | bool polling = false); | |
25 | ||
26 | distributed_queue(const ProcessGroup& process_group, bool polling); | |
27 | ||
28 | void push(const value_type& x); | |
29 | void pop(); | |
30 | value_type& top(); | |
31 | const value_type& top() const; | |
32 | bool empty() const; | |
33 | size_type size() const; | |
34 | }; | |
35 | ||
36 | template<typename ProcessGroup, typename Buffer> | |
37 | inline distributed_queue<ProcessGroup, Buffer> | |
38 | make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer, | |
39 | bool polling = false); | |
40 | ||
41 | Class template ``distributed_queue`` implements a distributed queue | |
42 | across a process group. The distributed queue is an adaptor over an | |
43 | existing (local) queue, which must model the Buffer_ concept. Each | |
44 | process stores a distinct copy of the local queue, from which it draws | |
45 | or removes elements via the ``pop`` and ``top`` members. | |
46 | ||
47 | The value type of the local queue must be a model of the | |
48 | `Global Descriptor`_ concept. The ``push`` operation of the | |
49 | distributed queue passes (via a message) the value to its owning | |
50 | processor. Thus, the elements within a particular local queue are | |
51 | guaranteed to have the process owning that local queue as an owner. | |
52 | ||
53 | Synchronization of distributed queues occurs in the ``empty`` and | |
54 | ``size`` functions, which will only return "empty" values (true or 0, | |
55 | respectively) when the entire distributed queue is empty. If the local | |
56 | queue is empty but the distributed queue is not, the operation will | |
57 | block until either condition changes. When the ``size`` function of a | |
58 | nonempty queue returns, it returns the size of the local queue. These | |
59 | semantics were selected so that sequential code that processes | |
60 | elements in the queue via the following idiom can be parallelized via | |
61 | introduction of a distributed queue: | |
62 | ||
63 | :: | |
64 | ||
65 | distributed_queue<...> Q; | |
66 | Q.push(x); | |
67 | while (!Q.empty()) { | |
68 | // do something, that may push a value onto Q | |
69 | } | |
70 | ||
71 | In the parallel version, the initial ``push`` operation will place | |
72 | the value ``x`` onto its owner's queue. All processes will | |
73 | synchronize at the call to empty, and only the process owning ``x`` | |
74 | will be allowed to execute the loop (``Q.empty()`` returns | |
75 | false). This iteration may in turn push values onto other remote | |
76 | queues, so when that process finishes execution of the loop body | |
77 | and all processes synchronize again in ``empty``, more processes | |
78 | may have nonempty local queues to execute. Once all local queues | |
79 | are empty, ``Q.empty()`` returns ``false`` for all processes. | |
80 | ||
81 | The distributed queue can receive messages at two different times: | |
82 | during synchronization and when polling ``empty``. Messages are | |
83 | always received during synchronization, to ensure that accurate | |
84 | local queue sizes can be determines. However, whether ``empty`` | |
85 | should poll for messages is specified as an option to the | |
86 | constructor. Polling may be desired when the order in which | |
87 | elements in the queue are processed is not important, because it | |
88 | permits fewer synchronization steps and less communication | |
89 | overhead. However, when more strict ordering guarantees are | |
90 | required, polling may be semantically incorrect. By disabling | |
91 | polling, one ensures that parallel execution using the idiom above | |
92 | will not process an element at a later "level" before an earlier | |
93 | "level". | |
94 | ||
95 | The distributed queue nearly models the Buffer_ | |
96 | concept. However, the ``push`` routine does not necessarily | |
97 | increase the result of ``size()`` by one (although the size of the | |
98 | global queue does increase by one). | |
99 | ||
100 | Member Functions | |
101 | ---------------- | |
102 | ||
103 | :: | |
104 | ||
105 | explicit | |
106 | distributed_queue(const ProcessGroup& process_group = ProcessGroup(), | |
107 | const Buffer& buffer = Buffer(), | |
108 | bool polling = false); | |
109 | ||
110 | Build a new distributed queue that communicates over the given | |
111 | ``process_group``, whose local queue is initialized via ``buffer`` and | |
112 | which may or may not poll for messages. | |
113 | ||
114 | ----------------------------------------------------------------------------- | |
115 | ||
116 | :: | |
117 | ||
118 | distributed_queue(const ProcessGroup& process_group, bool polling); | |
119 | ||
120 | Build a new distributed queue that communicates over the given | |
121 | ``process_group``, whose local queue is default-initalized and which | |
122 | may or may not poll for messages. | |
123 | ||
124 | ----------------------------------------------------------------------------- | |
125 | ||
126 | :: | |
127 | ||
128 | void push(const value_type& x); | |
129 | ||
130 | Push an element onto the distributed queue. | |
131 | ||
132 | The element will be sent to its owner process to be added to that | |
133 | process's local queue. If polling is enabled for this queue and | |
134 | the owner process is the current process, the value will be | |
135 | immediately pushed onto the local queue. | |
136 | ||
137 | Complexity: O(1) messages of size O(``sizeof(value_type)``) will be | |
138 | transmitted. | |
139 | ||
140 | ||
141 | ----------------------------------------------------------------------------- | |
142 | ||
143 | :: | |
144 | ||
145 | void pop(); | |
146 | ||
147 | Pop an element off the local queue. The queue must not be ``empty()``. | |
148 | ||
149 | ----------------------------------------------------------------------------- | |
150 | ||
151 | :: | |
152 | ||
153 | value_type& top(); | |
154 | const value_type& top(); | |
155 | ||
156 | Returns the top element in the local queue. The queue must not be | |
157 | ``empty()``. | |
158 | ||
159 | ----------------------------------------------------------------------------- | |
160 | ||
161 | :: | |
162 | ||
163 | bool empty() const; | |
164 | ||
165 | Determines if the queue is empty. | |
166 | ||
167 | When the local queue is nonempty, returns true. If the local queue is | |
168 | empty, synchronizes with all other processes in the process group | |
169 | until either (1) the local queue is nonempty (returns true) (2) the | |
170 | entire distributed queue is empty (returns false). | |
171 | ||
172 | ----------------------------------------------------------------------------- | |
173 | ||
174 | :: | |
175 | ||
176 | size_type size() const; | |
177 | ||
178 | ||
179 | Determines the size of the local queue. | |
180 | ||
181 | The behavior of this routine is equivalent to the behavior of | |
182 | ``empty``, except that when ``empty`` returns true this | |
183 | function returns the size of the local queue and when ``empty`` | |
184 | returns false this function returns zero. | |
185 | ||
186 | Free Functions | |
187 | -------------- | |
188 | ||
189 | :: | |
190 | ||
191 | template<typename ProcessGroup, typename Buffer> | |
192 | inline distributed_queue<ProcessGroup, Buffer> | |
193 | make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer, | |
194 | bool polling = false); | |
195 | ||
196 | Constructs a distributed queue. | |
197 | ||
198 | ----------------------------------------------------------------------------- | |
199 | ||
200 | Copyright (C) 2004, 2005 The Trustees of Indiana University. | |
201 | ||
202 | Authors: Douglas Gregor and Andrew Lumsdaine | |
203 | ||
204 | .. |Logo| image:: pbgl-logo.png | |
205 | :align: middle | |
206 | :alt: Parallel BGL | |
207 | :target: http://www.osl.iu.edu/research/pbgl | |
208 | ||
209 | .. _Global descriptor: GlobalDescriptor.html | |
210 | .. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html |