boost_1_45_0/libs/graph_parallel/doc/distributed_queue.rst - nest-learning-thermostat/5.0/boost - Git at Google

 .. 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
	.. 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