File Executor.h

↰ Parent directory (ADS/parallel)

The layer of execution of the parallel algorithms of Namespace ADS, beyond the book: an executor is anything that runs the calls f( 0 ) , … , f( n - 1 ) of a function f on its threads and returns when all have returned (bulk()), and that tells how many threads it has (concurrency()); the parallel algorithms of Namespace ADS take one as their first argument, and the sequential ones, which take none, stay what they are.

Definition (ADS/parallel/Executor.h)

Detailed Description

The executors are Sequential, which runs the calls in order on the calling thread, ThreadPool [see File ThreadPool.h], the pool of Namespace ADS on std::thread with a deque of work stealing per thread, and, when their libraries are there, FastFlowExecutor, OpenMPExecutor and TBBExecutor [see File FastFlowExecutor.h, File OpenMPExecutor.h and File TBBExecutor.h], the same calls on the threads of FastFlow, of OpenMP and of oneTBB. An executor may also have invoke( f , g ), which runs f and g in parallel; the others get it from bulk().

On these the header builds the patterns that the algorithms share, each a function of the executor:

  • parallelInvoke( ex , f , g ), the fork and join of two calls;

  • parallelFor( ex , first , last , f ) and parallelForBlocks( ex , first , last , f ), the loop over :math:` [ first , last ) ` cut into blocks of at least grain indices, which the threads claim one at a time from a counter, so that a faster thread takes more blocks (the dynamic schedule); the second gives f a whole block, f( lo , hi ), which lets the compiler vectorize its loop;

  • parallelReduce( ex , first , last , id , f , op ), the reduction of the blocks by f( lo , hi ) into partial results, combined by op in the order of the blocks;

  • parallelInclusiveScan() and parallelExclusiveScan(), the prefix sums by an associative op, in one pass over the memory. The blocks depend only on the number of indices and on the grain, never on the number of threads: at most kBlocks of them, each of at least grain indices. Hence a reduction gives the same result on every executor, Sequential included, also with an operation that is associative only up to rounding, e.g., the sum of doubles; that result is the sum by blocks, not the one of std::accumulate.

The prefix sums are those of Merrill and Garland, written for the processors instead of the graphics cards: the input is cut into tiles of about 64 KB, which the threads claim in increasing order from a counter. A thread reduces its tile c into its aggregate :math:` a_c ` (the tile then stays in its cache), publishes it, and looks back at the tiles before it: from c - 1 down, it adds on the left the aggregate of each tile that has published only that, and stops at the first one that has published its inclusive prefix :math:` P_{c’} = x_0 oplus cdots oplus x_{end( c’ )} `, so that :math:`[

P_{c - 1} = P_{c’} oplus a_{c’ + 1} oplus cdots oplus a_{c - 1} ;

` then it publishes :math:` P_c = P_{c - 1} oplus a_c ` and writes the prefixes of its tile, reading it again from the cache. The input is read from the memory once and the output written once, 2 n moves, where the scan in two passes of Blelloch (the reduction of the blocks, then their scan) reads the input twice, 3 n. A tile waits only for tiles claimed before it, which threads that are running hold; the first tile not done has no tile to wait for, so that the scan always ends, on any executor. The look-back reads O( 1 ) tiles on average when the threads go at the same pace, and at most c.

The algorithms take :math:` O( W / p + D ) ` time on p threads for work W and depth D, with the dynamic schedule within a factor of 2 of the best when the blocks are many more than the threads (the greedy schedule of Graham); the reduction and the scans have :math:` W = O( n ) ` and :math:` D = O( n / B + B ) ` for B blocks.

The contracts [see File Contract.h]: f may run on any thread, and its calls on distinct indices must not race; an exception thrown by a call stops the claim of new blocks and is thrown again by the algorithm, after the calls already started have returned; op is associative. R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17(2), 416-429, 1969, doi:10.1137/0117039

    1. Blelloch, Prefix sums and their applications, Technical Report CMU-CS-90-190, Carnegie Mellon University, 1990

  1. Merrill, M. Garland, Single-pass parallel prefix scan with decoupled look-back, Technical Report NVR-2016-002, NVIDIA, 2016

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions

Variables