ceph/src/boost/libs/graph_parallel/doc/distributed_queue.rst

   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