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 41Class template ``distributed_queue`` implements a distributed queue 42across a process group. The distributed queue is an adaptor over an 43existing (local) queue, which must model the Buffer_ concept. Each 44process stores a distinct copy of the local queue, from which it draws 45or removes elements via the ``pop`` and ``top`` members. 46 47The value type of the local queue must be a model of the 48`Global Descriptor`_ concept. The ``push`` operation of the 49distributed queue passes (via a message) the value to its owning 50processor. Thus, the elements within a particular local queue are 51guaranteed to have the process owning that local queue as an owner. 52 53Synchronization of distributed queues occurs in the ``empty`` and 54``size`` functions, which will only return "empty" values (true or 0, 55respectively) when the entire distributed queue is empty. If the local 56queue is empty but the distributed queue is not, the operation will 57block until either condition changes. When the ``size`` function of a 58nonempty queue returns, it returns the size of the local queue. These 59semantics were selected so that sequential code that processes 60elements in the queue via the following idiom can be parallelized via 61introduction 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 71In the parallel version, the initial ``push`` operation will place 72the value ``x`` onto its owner's queue. All processes will 73synchronize at the call to empty, and only the process owning ``x`` 74will be allowed to execute the loop (``Q.empty()`` returns 75false). This iteration may in turn push values onto other remote 76queues, so when that process finishes execution of the loop body 77and all processes synchronize again in ``empty``, more processes 78may have nonempty local queues to execute. Once all local queues 79are empty, ``Q.empty()`` returns ``false`` for all processes. 80 81The distributed queue can receive messages at two different times: 82during synchronization and when polling ``empty``. Messages are 83always received during synchronization, to ensure that accurate 84local queue sizes can be determines. However, whether ``empty`` 85should poll for messages is specified as an option to the 86constructor. Polling may be desired when the order in which 87elements in the queue are processed is not important, because it 88permits fewer synchronization steps and less communication 89overhead. However, when more strict ordering guarantees are 90required, polling may be semantically incorrect. By disabling 91polling, one ensures that parallel execution using the idiom above 92will not process an element at a later "level" before an earlier 93"level". 94 95The distributed queue nearly models the Buffer_ 96concept. However, the ``push`` routine does not necessarily 97increase the result of ``size()`` by one (although the size of the 98global queue does increase by one). 99 100Member 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 110Build a new distributed queue that communicates over the given 111``process_group``, whose local queue is initialized via ``buffer`` and 112which may or may not poll for messages. 113 114----------------------------------------------------------------------------- 115 116:: 117 118 distributed_queue(const ProcessGroup& process_group, bool polling); 119 120Build a new distributed queue that communicates over the given 121``process_group``, whose local queue is default-initalized and which 122may or may not poll for messages. 123 124----------------------------------------------------------------------------- 125 126:: 127 128 void push(const value_type& x); 129 130Push an element onto the distributed queue. 131 132The element will be sent to its owner process to be added to that 133process's local queue. If polling is enabled for this queue and 134the owner process is the current process, the value will be 135immediately pushed onto the local queue. 136 137Complexity: O(1) messages of size O(``sizeof(value_type)``) will be 138transmitted. 139 140 141----------------------------------------------------------------------------- 142 143:: 144 145 void pop(); 146 147Pop 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 156Returns the top element in the local queue. The queue must not be 157``empty()``. 158 159----------------------------------------------------------------------------- 160 161:: 162 163 bool empty() const; 164 165Determines if the queue is empty. 166 167When the local queue is nonempty, returns true. If the local queue is 168empty, synchronizes with all other processes in the process group 169until either (1) the local queue is nonempty (returns true) (2) the 170entire distributed queue is empty (returns false). 171 172----------------------------------------------------------------------------- 173 174:: 175 176 size_type size() const; 177 178 179Determines the size of the local queue. 180 181The behavior of this routine is equivalent to the behavior of 182``empty``, except that when ``empty`` returns true this 183function returns the size of the local queue and when ``empty`` 184returns false this function returns zero. 185 186Free 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 196Constructs a distributed queue. 197 198----------------------------------------------------------------------------- 199 200Copyright (C) 2004, 2005 The Trustees of Indiana University. 201 202Authors: 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 211
