1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" /> 7<title>Parallel BGL Distributed queue adaptor</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-distributed-queue-adaptor"> 12<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> 13 14<!-- Copyright (C) 2004-2008 The Trustees of Indiana University. 15Use, modification and distribution is subject to the Boost Software 16License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17http://www.boost.org/LICENSE_1_0.txt) --> 18<pre class="literal-block"> 19template<typename ProcessGroup, typename Buffer> 20class distributed_queue 21{ 22public: 23 typedef ProcessGroup process_group_type; 24 typedef Buffer buffer_type; 25 typedef typename buffer_type::value_type value_type; 26 typedef typename buffer_type::size_type size_type; 27 28 explicit 29 distributed_queue(const ProcessGroup& process_group = ProcessGroup(), 30 const Buffer& buffer = Buffer(), 31 bool polling = false); 32 33 distributed_queue(const ProcessGroup& process_group, bool polling); 34 35 void push(const value_type& x); 36 void pop(); 37 value_type& top(); 38 const value_type& top() const; 39 bool empty() const; 40 size_type size() const; 41}; 42 43template<typename ProcessGroup, typename Buffer> 44inline distributed_queue<ProcessGroup, Buffer> 45make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer, 46 bool polling = false); 47</pre> 48<p>Class template <tt class="docutils literal"><span class="pre">distributed_queue</span></tt> implements a distributed queue 49across a process group. The distributed queue is an adaptor over an 50existing (local) queue, which must model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html">Buffer</a> concept. Each 51process stores a distinct copy of the local queue, from which it draws 52or 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> 53<p>The value type of the local queue must be a model of the 54<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 55distributed queue passes (via a message) the value to its owning 56processor. Thus, the elements within a particular local queue are 57guaranteed to have the process owning that local queue as an owner.</p> 58<p>Synchronization of distributed queues occurs in the <tt class="docutils literal"><span class="pre">empty</span></tt> and 59<tt class="docutils literal"><span class="pre">size</span></tt> functions, which will only return "empty" values (true or 0, 60respectively) when the entire distributed queue is empty. If the local 61queue is empty but the distributed queue is not, the operation will 62block until either condition changes. When the <tt class="docutils literal"><span class="pre">size</span></tt> function of a 63nonempty queue returns, it returns the size of the local queue. These 64semantics were selected so that sequential code that processes 65elements in the queue via the following idiom can be parallelized via 66introduction of a distributed queue:</p> 67<pre class="literal-block"> 68distributed_queue<...> Q; 69Q.push(x); 70while (!Q.empty()) { 71 // do something, that may push a value onto Q 72} 73</pre> 74<p>In the parallel version, the initial <tt class="docutils literal"><span class="pre">push</span></tt> operation will place 75the value <tt class="docutils literal"><span class="pre">x</span></tt> onto its owner's queue. All processes will 76synchronize at the call to empty, and only the process owning <tt class="docutils literal"><span class="pre">x</span></tt> 77will be allowed to execute the loop (<tt class="docutils literal"><span class="pre">Q.empty()</span></tt> returns 78false). This iteration may in turn push values onto other remote 79queues, so when that process finishes execution of the loop body 80and all processes synchronize again in <tt class="docutils literal"><span class="pre">empty</span></tt>, more processes 81may have nonempty local queues to execute. Once all local queues 82are 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> 83<p>The distributed queue can receive messages at two different times: 84during synchronization and when polling <tt class="docutils literal"><span class="pre">empty</span></tt>. Messages are 85always received during synchronization, to ensure that accurate 86local queue sizes can be determines. However, whether <tt class="docutils literal"><span class="pre">empty</span></tt> 87should poll for messages is specified as an option to the 88constructor. Polling may be desired when the order in which 89elements in the queue are processed is not important, because it 90permits fewer synchronization steps and less communication 91overhead. However, when more strict ordering guarantees are 92required, polling may be semantically incorrect. By disabling 93polling, one ensures that parallel execution using the idiom above 94will not process an element at a later "level" before an earlier 95"level".</p> 96<p>The distributed queue nearly models the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Buffer.html">Buffer</a> 97concept. However, the <tt class="docutils literal"><span class="pre">push</span></tt> routine does not necessarily 98increase the result of <tt class="docutils literal"><span class="pre">size()</span></tt> by one (although the size of the 99global queue does increase by one).</p> 100<div class="section" id="member-functions"> 101<h1>Member Functions</h1> 102<pre class="literal-block"> 103explicit 104distributed_queue(const ProcessGroup& process_group = ProcessGroup(), 105 const Buffer& buffer = Buffer(), 106 bool polling = false); 107</pre> 108<p>Build a new distributed queue that communicates over the given 109<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 110which may or may not poll for messages.</p> 111<hr class="docutils" /> 112<pre class="literal-block"> 113distributed_queue(const ProcessGroup& process_group, bool polling); 114</pre> 115<p>Build a new distributed queue that communicates over the given 116<tt class="docutils literal"><span class="pre">process_group</span></tt>, whose local queue is default-initalized and which 117may or may not poll for messages.</p> 118<hr class="docutils" /> 119<pre class="literal-block"> 120void push(const value_type& x); 121</pre> 122<p>Push an element onto the distributed queue.</p> 123<p>The element will be sent to its owner process to be added to that 124process's local queue. If polling is enabled for this queue and 125the owner process is the current process, the value will be 126immediately pushed onto the local queue.</p> 127<p>Complexity: O(1) messages of size O(<tt class="docutils literal"><span class="pre">sizeof(value_type)</span></tt>) will be 128transmitted.</p> 129<hr class="docutils" /> 130<pre class="literal-block"> 131void pop(); 132</pre> 133<p>Pop an element off the local queue. The queue must not be <tt class="docutils literal"><span class="pre">empty()</span></tt>.</p> 134<hr class="docutils" /> 135<pre class="literal-block"> 136value_type& top(); 137const value_type& top(); 138</pre> 139<p>Returns the top element in the local queue. The queue must not be 140<tt class="docutils literal"><span class="pre">empty()</span></tt>.</p> 141<hr class="docutils" /> 142<pre class="literal-block"> 143bool empty() const; 144</pre> 145<p>Determines if the queue is empty.</p> 146<p>When the local queue is nonempty, returns true. If the local queue is 147empty, synchronizes with all other processes in the process group 148until either (1) the local queue is nonempty (returns true) (2) the 149entire distributed queue is empty (returns false).</p> 150<hr class="docutils" /> 151<pre class="literal-block"> 152size_type size() const; 153</pre> 154<p>Determines the size of the local queue.</p> 155<p>The behavior of this routine is equivalent to the behavior of 156<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 157function returns the size of the local queue and when <tt class="docutils literal"><span class="pre">empty</span></tt> 158returns false this function returns zero.</p> 159</div> 160<div class="section" id="free-functions"> 161<h1>Free Functions</h1> 162<pre class="literal-block"> 163template<typename ProcessGroup, typename Buffer> 164inline distributed_queue<ProcessGroup, Buffer> 165make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer, 166 bool polling = false); 167</pre> 168<p>Constructs a distributed queue.</p> 169<hr class="docutils" /> 170<p>Copyright (C) 2004, 2005 The Trustees of Indiana University.</p> 171<p>Authors: Douglas Gregor and Andrew Lumsdaine</p> 172</div> 173</div> 174<div class="footer"> 175<hr class="footer" /> 176Generated on: 2009-05-31 00:22 UTC. 177Generated 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. 178 179</div> 180</body> 181</html> 182
