123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL Distributed queue adaptor</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-distributed-queue-adaptor">
- <h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Distributed queue adaptor</h1>
- <!-- 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) -->
- <pre class="literal-block">
- 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);
- </pre>
- <p>Class template <tt class="docutils literal"><span class="pre">distributed_queue</span></tt> implements a distributed queue
- across a process group. The distributed queue is an adaptor over an
- existing (local) queue, which must model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html">Buffer</a> concept. Each
- process stores a distinct copy of the local queue, from which it draws
- or removes elements via the <tt class="docutils literal"><span class="pre">pop</span></tt> and <tt class="docutils literal"><span class="pre">top</span></tt> members.</p>
- <p>The value type of the local queue must be a model of the
- <a class="reference external" href="GlobalDescriptor.html">Global Descriptor</a> concept. The <tt class="docutils literal"><span class="pre">push</span></tt> 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.</p>
- <p>Synchronization of distributed queues occurs in the <tt class="docutils literal"><span class="pre">empty</span></tt> and
- <tt class="docutils literal"><span class="pre">size</span></tt> 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 <tt class="docutils literal"><span class="pre">size</span></tt> 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:</p>
- <pre class="literal-block">
- distributed_queue<...> Q;
- Q.push(x);
- while (!Q.empty()) {
- // do something, that may push a value onto Q
- }
- </pre>
- <p>In the parallel version, the initial <tt class="docutils literal"><span class="pre">push</span></tt> operation will place
- the value <tt class="docutils literal"><span class="pre">x</span></tt> onto its owner's queue. All processes will
- synchronize at the call to empty, and only the process owning <tt class="docutils literal"><span class="pre">x</span></tt>
- will be allowed to execute the loop (<tt class="docutils literal"><span class="pre">Q.empty()</span></tt> 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 <tt class="docutils literal"><span class="pre">empty</span></tt>, more processes
- may have nonempty local queues to execute. Once all local queues
- are empty, <tt class="docutils literal"><span class="pre">Q.empty()</span></tt> returns <tt class="docutils literal"><span class="pre">false</span></tt> for all processes.</p>
- <p>The distributed queue can receive messages at two different times:
- during synchronization and when polling <tt class="docutils literal"><span class="pre">empty</span></tt>. Messages are
- always received during synchronization, to ensure that accurate
- local queue sizes can be determines. However, whether <tt class="docutils literal"><span class="pre">empty</span></tt>
- 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".</p>
- <p>The distributed queue nearly models the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html">Buffer</a>
- concept. However, the <tt class="docutils literal"><span class="pre">push</span></tt> routine does not necessarily
- increase the result of <tt class="docutils literal"><span class="pre">size()</span></tt> by one (although the size of the
- global queue does increase by one).</p>
- <div class="section" id="member-functions">
- <h1>Member Functions</h1>
- <pre class="literal-block">
- explicit
- distributed_queue(const ProcessGroup& process_group = ProcessGroup(),
- const Buffer& buffer = Buffer(),
- bool polling = false);
- </pre>
- <p>Build a new distributed queue that communicates over the given
- <tt class="docutils literal"><span class="pre">process_group</span></tt>, whose local queue is initialized via <tt class="docutils literal"><span class="pre">buffer</span></tt> and
- which may or may not poll for messages.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- distributed_queue(const ProcessGroup& process_group, bool polling);
- </pre>
- <p>Build a new distributed queue that communicates over the given
- <tt class="docutils literal"><span class="pre">process_group</span></tt>, whose local queue is default-initalized and which
- may or may not poll for messages.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void push(const value_type& x);
- </pre>
- <p>Push an element onto the distributed queue.</p>
- <p>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.</p>
- <p>Complexity: O(1) messages of size O(<tt class="docutils literal"><span class="pre">sizeof(value_type)</span></tt>) will be
- transmitted.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- void pop();
- </pre>
- <p>Pop an element off the local queue. The queue must not be <tt class="docutils literal"><span class="pre">empty()</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- value_type& top();
- const value_type& top();
- </pre>
- <p>Returns the top element in the local queue. The queue must not be
- <tt class="docutils literal"><span class="pre">empty()</span></tt>.</p>
- <hr class="docutils" />
- <pre class="literal-block">
- bool empty() const;
- </pre>
- <p>Determines if the queue is empty.</p>
- <p>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).</p>
- <hr class="docutils" />
- <pre class="literal-block">
- size_type size() const;
- </pre>
- <p>Determines the size of the local queue.</p>
- <p>The behavior of this routine is equivalent to the behavior of
- <tt class="docutils literal"><span class="pre">empty</span></tt>, except that when <tt class="docutils literal"><span class="pre">empty</span></tt> returns true this
- function returns the size of the local queue and when <tt class="docutils literal"><span class="pre">empty</span></tt>
- returns false this function returns zero.</p>
- </div>
- <div class="section" id="free-functions">
- <h1>Free Functions</h1>
- <pre class="literal-block">
- template<typename ProcessGroup, typename Buffer>
- inline distributed_queue<ProcessGroup, Buffer>
- make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer,
- bool polling = false);
- </pre>
- <p>Constructs a distributed queue.</p>
- <hr class="docutils" />
- <p>Copyright (C) 2004, 2005 The Trustees of Indiana University.</p>
- <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:22 UTC.
- Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
- </div>
- </body>
- </html>
|