A distributed queue adaptor. More...

#include <queue.hpp>

Public Types
typedef ProcessGroup	process_group_type

typedef Buffer	buffer_type

typedef buffer_type::value_type	value_type

typedef buffer_type::size_type	size_type

Public Member Functions
	distributed_queue (const ProcessGroup &process_group, const OwnerMap &owner, const Buffer &buffer, bool polling=false)
	Construct a new distributed queue. More...

	distributed_queue (const ProcessGroup &process_group=ProcessGroup(), const OwnerMap &owner=OwnerMap(), const Buffer &buffer=Buffer(), const UnaryPredicate &pred=UnaryPredicate(), bool polling=false)
	Construct a new distributed queue. More...

	distributed_queue (const ProcessGroup &process_group, const OwnerMap &owner, const UnaryPredicate &pred, bool polling=false)
	Construct a new distributed queue. More...

virtual	~distributed_queue ()
	Virtual destructor required with virtual functions. More...

void	push (const value_type &x)
	Push an element onto the distributed queue. More...

void	pop ()
	Pop an element off the local queue. More...

value_type &	top ()
	Return the element at the top of the local queue. More...

const value_type &	top () const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts. More...

bool	empty () const
	Determine if the queue is empty. More...

size_type	size () const
	Determine the size of the local queue. More...

virtual bool	do_synchronize () const
	Synchronize the distributed queue and determine if all queues are empty. More...

Detailed Description

template<typename ProcessGroup, typename OwnerMap, typename Buffer, typename UnaryPredicate = always_push>
class boost::graph::distributed::distributed_queue< ProcessGroup, OwnerMap, Buffer, UnaryPredicate >

A distributed queue adaptor.

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