211 lines
7.2 KiB
ReStructuredText
211 lines
7.2 KiB
ReStructuredText
.. Copyright (C) 2004-2008 The Trustees of Indiana University.
|
|
Use, modification and distribution is subject to the Boost Software
|
|
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
|
|
================================
|
|
|Logo| Distributed queue adaptor
|
|
================================
|
|
|
|
::
|
|
|
|
template<typename ProcessGroup, typename Buffer>
|
|
class distributed_queue
|
|
{
|
|
public:
|
|
typedef ProcessGroup process_group_type;
|
|
typedef Buffer buffer_type;
|
|
typedef typename buffer_type::value_type value_type;
|
|
typedef typename buffer_type::size_type size_type;
|
|
|
|
explicit
|
|
distributed_queue(const ProcessGroup& process_group = ProcessGroup(),
|
|
const Buffer& buffer = Buffer(),
|
|
bool polling = false);
|
|
|
|
distributed_queue(const ProcessGroup& process_group, bool polling);
|
|
|
|
void push(const value_type& x);
|
|
void pop();
|
|
value_type& top();
|
|
const value_type& top() const;
|
|
bool empty() const;
|
|
size_type size() const;
|
|
};
|
|
|
|
template<typename ProcessGroup, typename Buffer>
|
|
inline distributed_queue<ProcessGroup, Buffer>
|
|
make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer,
|
|
bool polling = false);
|
|
|
|
Class template ``distributed_queue`` implements a distributed queue
|
|
across a process group. The distributed queue is an adaptor over an
|
|
existing (local) queue, which must model the Buffer_ concept. Each
|
|
process stores a distinct copy of the local queue, from which it draws
|
|
or removes elements via the ``pop`` and ``top`` members.
|
|
|
|
The value type of the local queue must be a model of the
|
|
`Global Descriptor`_ concept. The ``push`` operation of the
|
|
distributed queue passes (via a message) the value to its owning
|
|
processor. Thus, the elements within a particular local queue are
|
|
guaranteed to have the process owning that local queue as an owner.
|
|
|
|
Synchronization of distributed queues occurs in the ``empty`` and
|
|
``size`` functions, which will only return "empty" values (true or 0,
|
|
respectively) when the entire distributed queue is empty. If the local
|
|
queue is empty but the distributed queue is not, the operation will
|
|
block until either condition changes. When the ``size`` function of a
|
|
nonempty queue returns, it returns the size of the local queue. These
|
|
semantics were selected so that sequential code that processes
|
|
elements in the queue via the following idiom can be parallelized via
|
|
introduction of a distributed queue:
|
|
|
|
::
|
|
|
|
distributed_queue<...> Q;
|
|
Q.push(x);
|
|
while (!Q.empty()) {
|
|
// do something, that may push a value onto Q
|
|
}
|
|
|
|
In the parallel version, the initial ``push`` operation will place
|
|
the value ``x`` onto its owner's queue. All processes will
|
|
synchronize at the call to empty, and only the process owning ``x``
|
|
will be allowed to execute the loop (``Q.empty()`` returns
|
|
false). This iteration may in turn push values onto other remote
|
|
queues, so when that process finishes execution of the loop body
|
|
and all processes synchronize again in ``empty``, more processes
|
|
may have nonempty local queues to execute. Once all local queues
|
|
are empty, ``Q.empty()`` returns ``false`` for all processes.
|
|
|
|
The distributed queue can receive messages at two different times:
|
|
during synchronization and when polling ``empty``. Messages are
|
|
always received during synchronization, to ensure that accurate
|
|
local queue sizes can be determines. However, whether ``empty``
|
|
should poll for messages is specified as an option to the
|
|
constructor. Polling may be desired when the order in which
|
|
elements in the queue are processed is not important, because it
|
|
permits fewer synchronization steps and less communication
|
|
overhead. However, when more strict ordering guarantees are
|
|
required, polling may be semantically incorrect. By disabling
|
|
polling, one ensures that parallel execution using the idiom above
|
|
will not process an element at a later "level" before an earlier
|
|
"level".
|
|
|
|
The distributed queue nearly models the Buffer_
|
|
concept. However, the ``push`` routine does not necessarily
|
|
increase the result of ``size()`` by one (although the size of the
|
|
global queue does increase by one).
|
|
|
|
Member Functions
|
|
----------------
|
|
|
|
::
|
|
|
|
explicit
|
|
distributed_queue(const ProcessGroup& process_group = ProcessGroup(),
|
|
const Buffer& buffer = Buffer(),
|
|
bool polling = false);
|
|
|
|
Build a new distributed queue that communicates over the given
|
|
``process_group``, whose local queue is initialized via ``buffer`` and
|
|
which may or may not poll for messages.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
distributed_queue(const ProcessGroup& process_group, bool polling);
|
|
|
|
Build a new distributed queue that communicates over the given
|
|
``process_group``, whose local queue is default-initalized and which
|
|
may or may not poll for messages.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
void push(const value_type& x);
|
|
|
|
Push an element onto the distributed queue.
|
|
|
|
The element will be sent to its owner process to be added to that
|
|
process's local queue. If polling is enabled for this queue and
|
|
the owner process is the current process, the value will be
|
|
immediately pushed onto the local queue.
|
|
|
|
Complexity: O(1) messages of size O(``sizeof(value_type)``) will be
|
|
transmitted.
|
|
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
void pop();
|
|
|
|
Pop an element off the local queue. The queue must not be ``empty()``.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
value_type& top();
|
|
const value_type& top();
|
|
|
|
Returns the top element in the local queue. The queue must not be
|
|
``empty()``.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
bool empty() const;
|
|
|
|
Determines if the queue is empty.
|
|
|
|
When the local queue is nonempty, returns true. If the local queue is
|
|
empty, synchronizes with all other processes in the process group
|
|
until either (1) the local queue is nonempty (returns true) (2) the
|
|
entire distributed queue is empty (returns false).
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
::
|
|
|
|
size_type size() const;
|
|
|
|
|
|
Determines the size of the local queue.
|
|
|
|
The behavior of this routine is equivalent to the behavior of
|
|
``empty``, except that when ``empty`` returns true this
|
|
function returns the size of the local queue and when ``empty``
|
|
returns false this function returns zero.
|
|
|
|
Free Functions
|
|
--------------
|
|
|
|
::
|
|
|
|
template<typename ProcessGroup, typename Buffer>
|
|
inline distributed_queue<ProcessGroup, Buffer>
|
|
make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer,
|
|
bool polling = false);
|
|
|
|
Constructs a distributed queue.
|
|
|
|
-----------------------------------------------------------------------------
|
|
|
|
Copyright (C) 2004, 2005 The Trustees of Indiana University.
|
|
|
|
Authors: Douglas Gregor and Andrew Lumsdaine
|
|
|
|
.. |Logo| image:: pbgl-logo.png
|
|
:align: middle
|
|
:alt: Parallel BGL
|
|
:target: http://www.osl.iu.edu/research/pbgl
|
|
|
|
.. _Global descriptor: GlobalDescriptor.html
|
|
.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
|