WorkStream Namespace Reference

Functions
template<typename Worker , typename Copier , typename Iterator , typename ScratchData , typename CopyData >
void	run (const std::vector< std::vector< Iterator > > &colored_iterators, Worker worker, Copier copier, const ScratchData &sample_scratch_data, const CopyData &sample_copy_data, const unsigned int queue_length=2 *MultithreadInfo::n_threads(), const unsigned int chunk_size=8)
template<typename Worker , typename Copier , typename Iterator , typename ScratchData , typename CopyData >
void	run (const Iterator &begin, const typename identity< Iterator >::type &end, Worker worker, Copier copier, const ScratchData &sample_scratch_data, const CopyData &sample_copy_data, const unsigned int queue_length=2 *MultithreadInfo::n_threads(), const unsigned int chunk_size=8)
template<typename MainClass , typename Iterator , typename ScratchData , typename CopyData >
void	run (const Iterator &begin, const typename identity< Iterator >::type &end, MainClass &main_object, void(MainClass::*worker)(const Iterator &, ScratchData &, CopyData &), void(MainClass::*copier)(const CopyData &), const ScratchData &sample_scratch_data, const CopyData &sample_copy_data, const unsigned int queue_length=2 *MultithreadInfo::n_threads(), const unsigned int chunk_size=8)

Detailed Description

A namespace whose main template function supports running multiple threads each of which operates on a subset of the given range of objects. The class uses the Intel Threading Building Blocks (TBB) to load balance the individual subranges onto the available threads. For a lengthy discussion of the rationale of this class, see the Parallel computing with multiple processors module. It is used in the tutorial first in step-9, and again in step-13, step-14, step-32 and others.

The class is built on the following premise: One frequently has some work that needs to be done on a sequence of objects; a prototypical example is assembling cell contributions to a system matrix or right hand side. In many such examples, part of the work can be done entirely independently and in parallel, possibly using several processor cores on a machine with shared memory. However, some other part of this work may need to be synchronized and be done in order. In the example of assembling a matrix, the computation of local contributions can be done entirely in parallel, but copying the local contributions into the global matrix requires some care: First, several threads can't write at the same time, but need to synchronize writing using a mutex; secondly, we want the order in which local contributions are added to the global matrix to be always the same because floating point addition is not commutative and adding local contributions to the global matrix in different orders leads to subtly different results that can affect the number of iterations for iterative solvers as well as the round-off error in the solution in random ways. Consequently, we want to ensure that only one thread at a time writes into the global matrix, and that results are copied in a stable and reproducible order.

This class implements a framework for this work model. It works with a stream of objects given by an iterator range, runs a worker function in parallel on all of these objects and then passes each object to a postprocessor function that runs sequentially and gets objects in exactly the order in which they appear in the input iterator range. None of the synchronization work is exposed to the user of this class.

Internally, the range given to the run() function of this class is split into a sequence of "items", which are then distributed according to some internal algorithm onto the number of available threads. An item is an element of the range of iterators on which we are to operate; for example, for the purpose of assembling matrices or evaluating error indicators, an item could be a cell. The TBB library determines how many threads are created (typically as many as there are processor cores), but the number of items that may be active at any given time is specified by the argument to the constructor. It should be bigger or equal to the number of processor cores - the default is four times the number of cores on the current system.

Items are created upon request by the TBB whenever one of the worker threads is idle or is expected to become idle. It is then handed off to a worker function, typically a member function of a main class. These worker functions are run in parallel on a number of threads, and there is no guarantee that they are asked to work on items in any particular order, in particular not necessarily in the order in which items are generated from the iterator range.

Typically, worker functions need additional data, for example FEValues objects, input data vectors, etc, some of which can not be shared among threads. To this end, the run() function takes another template argument, ScratchData, which designates a type objects of which are stored with each item and which threads can use as private data without having to share them with other threads. The run() function takes an additional argument with an object of type ScratchData that is going to be copied for the arguments passed to each of the worker functions.

In addition, worker functions store their results in objects of template type CopyData. These are then handed off to a separate function, called copier, that may use the stored results to transfer them into permanent storage. For example, it may copy the results of local contributions to a matrix computed by a worker function into the global matrix. In contrast to the worker function, however, only one instance of the copier is run at any given time; it can therefore safely copy local contributions into the global matrix without the need to lock the global object using a mutex or similar means. Furthermore, it is guaranteed that the copier is run with CopyData objects in the same order in which their associated items were created; consequently, even if worker threads may compute results in unspecified order, the copier always receives the results in exactly the same order as the items were created.

Once an item is processed by the copier, it is deleted and the ScratchData and CopyData objects that were used in its computation are considered unused and may be re-used for the next invocation of the worker function, on this or another thread.

The member variables in ScratchData and CopyData can be accessed independently of other concurrent uses of copies of these data structures. Therefore, it is perfectly fine to resize auxiliary data structures associated with ScratchData and CopyData to different lengths on each cell. For example, a vector holding densities at each quadrature point which is used with LocalIntegrators::L2::weighted_mass_matrix() to assemble the local matrix could be resized to the corresponding number of quadrature points of the current cell in hp::DoFHandler. Similarly, local stiffness matrix in CopyData can be resized in accordance with the number of local DoFs on the current cell.

The functions in this namespace only really work in parallel when multithread mode was selected during deal.II configuration. Otherwise they simply work on each item sequentially.

Author

Wolfgang Bangerth, 2007, 2008, 2009, 2013. Bruno Turcksin, 2013.

Function Documentation

run() [1/3]

template<typename Worker , typename Copier , typename Iterator , typename ScratchData , typename CopyData >

void WorkStream::run	(	const std::vector< std::vector< Iterator > > &	colored_iterators,
		Worker	worker,
		Copier	copier,
		const ScratchData &	sample_scratch_data,
		const CopyData &	sample_copy_data,
		const unsigned int	queue_length = 2*MultithreadInfo::n_threads(),
		const unsigned int	chunk_size = 8
	)

This is one of two main functions of the WorkStream concept, doing work as described in the introduction to this namespace. It corresponds to implementation 3 of the paper by Turcksin, Kronbichler and Bangerth, see workstream_paper. As such, it takes not a range of iterators described by a begin and end iterator, but a "colored" graph of iterators where each color represents cells for which writing the cell contributions into the global object does not conflict (in other words, these cells are not neighbors). Each "color" is represented by std::vectors of cells. The first argument to this function, a set of sets of cells (which are represent as a vector of vectors, for efficiency), is typically constructed by calling GraphColoring::make_graph_coloring(). See there for more information.

This function that can be used for worker and copier objects that are either pointers to non-member functions or objects that allow to be called with an operator(), for example objects created by std::bind.

The two data types ScratchData and CopyData need to have a working copy constructor. ScratchData is only used in the worker function, while CopyData is the object passed from the worker to the copier.

The queue_length argument indicates the number of items that can be live at any given time. Each item consists of chunk_size elements of the input stream that will be worked on by the worker and copier functions one after the other on the same thread.

Note

If your data objects are large, or their constructors are expensive, it is helpful to keep in mind that queue_length copies of the ScratchData object and queue_length*chunk_size copies of the CopyData object are generated.

Definition at line 1106 of file work_stream.h.

run() [2/3]

template<typename Worker , typename Copier , typename Iterator , typename ScratchData , typename CopyData >

void WorkStream::run	(	const Iterator &	begin,
		const typename identity< Iterator >::type &	end,
		Worker	worker,
		Copier	copier,
		const ScratchData &	sample_scratch_data,
		const CopyData &	sample_copy_data,
		const unsigned int	queue_length = 2*MultithreadInfo::n_threads(),
		const unsigned int	chunk_size = 8
	)

This is one of two main functions of the WorkStream concept, doing work as described in the introduction to this namespace. It corresponds to implementation 2 of the paper by Turcksin, Kronbichler and Bangerth (see workstream_paper).

This function that can be used for worker and copier objects that are either pointers to non-member functions or objects that allow to be called with an operator(), for example objects created by std::bind. If the copier is an empty function, it is ignored in the pipeline.

The argument passed as end must be convertible to the same type as begin, but doesn't have to be of the same type itself. This allows to write code like WorkStream().run(dof_handler.begin_active(), dof_handler.end(), ... where the first is of type DoFHandler::active_cell_iterator whereas the second is of type DoFHandler::raw_cell_iterator.

The two data types ScratchData and CopyData need to have a working copy constructor. ScratchData is only used in the worker function, while CopyData is the object passed from the worker to the copier.

The queue_length argument indicates the number of items that can be live at any given time. Each item consists of chunk_size elements of the input stream that will be worked on by the worker and copier functions one after the other on the same thread.

Note

If your data objects are large, or their constructors are expensive, it is helpful to keep in mind that queue_length copies of the ScratchData object and queue_length*chunk_size copies of the CopyData object are generated.

Definition at line 994 of file work_stream.h.

run() [3/3]

template<typename MainClass , typename Iterator , typename ScratchData , typename CopyData >

void WorkStream::run	(	const Iterator &	begin,
		const typename identity< Iterator >::type &	end,
		MainClass &	main_object,
		void(MainClass::*)(const Iterator &, ScratchData &, CopyData &)	worker,
		void(MainClass::*)(const CopyData &)	copier,
		const ScratchData &	sample_scratch_data,
		const CopyData &	sample_copy_data,
		const unsigned int	queue_length = 2*MultithreadInfo::n_threads(),
		const unsigned int	chunk_size = 8
	)

This is a variant of one of the two main functions of the WorkStream concept, doing work as described in the introduction to this namespace. It corresponds to implementation 2 of the paper by Turcksin, Kronbichler and Bangerth (see workstream_paper).

This is the function that can be used for worker and copier functions that are member functions of a class. If the copier is an empty function, it is ignored in the pipeline.

The argument passed as end must be convertible to the same type as begin, but doesn't have to be of the same type itself. This allows to write code like WorkStream().run(dof_handler.begin_active(), dof_handler.end(), ... where the first is of type DoFHandler::active_cell_iterator whereas the second is of type DoFHandler::raw_cell_iterator.

The queue_length argument indicates the number of items that can be live at any given time. Each item consists of chunk_size elements of the input stream that will be worked on by the worker and copier functions one after the other on the same thread.

Note

If your data objects are large, or their constructors are expensive, it is helpful to keep in mind that queue_length copies of the ScratchData object and queue_length*chunk_size copies of the CopyData object are generated.

Definition at line 1217 of file work_stream.h.