ModErn Text Analysis
META Enumerates Textual Applications
Classes | Functions
meta::parallel Namespace Reference

Implementation of a thread pool and a parallel for loop. More...

Classes

class  semaphore
 Implements a counting semaphore. More...
 
class  thread_pool
 Represents a collection of a fixed number of threads, which tasks can be added to. More...
 

Functions

template<class Iterator , class LocalStorage , class MappingFunction , class ReductionFunction >
std::result_of< LocalStorage()>::type reduction (Iterator begin, Iterator end, thread_pool &pool, LocalStorage &&ls_fn, MappingFunction &&map_fn, ReductionFunction &&red_fn)
 Performs a reduction across a set of mapped values in parallel. More...
 
template<class Iterator , class LocalStorage , class MappingFunction , class ReductionFunction >
std::result_of< LocalStorage()>::type reduction (Iterator begin, Iterator end, LocalStorage &&ls_fn, MappingFunction &&map_fn, ReductionFunction &&red_fn)
 
template<class RandomIt , class Compare >
void sort (RandomIt begin, RandomIt end, thread_pool &pool, Compare comp)
 Runs a parallel merge sort, deferring to std::sort at small problem sizes. More...
 
template<class RandomIt >
void sort (RandomIt begin, RandomIt end, thread_pool &pool)
 Runs a parallel merge sort, deferring to std::sort at small problem sizes. More...
 
template<class Iterator , class Function >
std::vector< std::future< typename std::result_of< Function(Iterator, Iterator)>::type > > for_each_block (Iterator begin, Iterator end, thread_pool &pool, Function &&fn)
 Runs the given function on sub-ranges of [begin, end) in parallel. More...
 
template<class Iterator , class Function >
void parallel_for (Iterator begin, Iterator end, Function func)
 Runs the given function on the range denoted by begin and end in parallel. More...
 
template<class Iterator , class Function >
void parallel_for (Iterator begin, Iterator end, thread_pool &pool, Function func)
 Runs the given function on the range denoted by begin and end in parallel. More...
 

Detailed Description

Implementation of a thread pool and a parallel for loop.

Function Documentation

§ reduction()

template<class Iterator , class LocalStorage , class MappingFunction , class ReductionFunction >
std::result_of<LocalStorage()>::type meta::parallel::reduction ( Iterator  begin,
Iterator  end,
thread_pool pool,
LocalStorage &&  ls_fn,
MappingFunction &&  map_fn,
ReductionFunction &&  red_fn 
)

Performs a reduction across a set of mapped values in parallel.

This algorithm has three distinct phases:

  1. Initialization: each thread invokes the LocalStorage functor, which should return the local storage needed to perform the reduction across the set of values that will be assigned to a particular thread. This is done within the thread to ensure that memory allocations occur within the worker thread (so it can take advantage of thread-local heap structures in, for example, jemalloc).
  2. Mapping: each thread invokes the MappingFunction functor, which is a binary operator that takes a mutable reference to the thread's local storage that was created using the LocalStorage functor as its first argument and the element in the iterator range (by const ref) as its second argument. It is not expected to return anything as the calculation results should be being placed in the thread's local storage.
  3. Reduction: finally, the main thread will compute the final value of the reduction by applying ReductionFunction across the local storage for each of the threads. ReductionFunction is a binary functor that takes the return type of LocalStorage by mutable reference as the first argument and a const reference to an object of the same type as the second argument. It is not expected to return anything and instead should compute the reduction by modifying the first argument.

§ sort() [1/2]

template<class RandomIt , class Compare >
void meta::parallel::sort ( RandomIt  begin,
RandomIt  end,
thread_pool pool,
Compare  comp 
)

Runs a parallel merge sort, deferring to std::sort at small problem sizes.

Parameters
beginThe beginning of the range
endThe end of the range
poolThe thread pool to use for running the sort
compThe comparison function for the sort

§ sort() [2/2]

template<class RandomIt >
void meta::parallel::sort ( RandomIt  begin,
RandomIt  end,
thread_pool pool 
)

Runs a parallel merge sort, deferring to std::sort at small problem sizes.

Parameters
beginThe beginning of the range
endThe end of the range
poolThe thread pool to use for running the sort
compThe comparison function for the sort

§ for_each_block()

template<class Iterator , class Function >
std::vector<std::future< typename std::result_of<Function(Iterator, Iterator)>::type> > meta::parallel::for_each_block ( Iterator  begin,
Iterator  end,
thread_pool pool,
Function &&  fn 
)

Runs the given function on sub-ranges of [begin, end) in parallel.

Parameters
beginThe beginning of the range
endThe ending of the range
poolThe thread_pool to run on
fnThe binary function that operates over iterator ranges

§ parallel_for() [1/2]

template<class Iterator , class Function >
void meta::parallel::parallel_for ( Iterator  begin,
Iterator  end,
Function  func 
)

Runs the given function on the range denoted by begin and end in parallel.

Parameters
beginThe first element to operate on
endOne past the last element to operate on
funcThe function to perform on each element

§ parallel_for() [2/2]

template<class Iterator , class Function >
void meta::parallel::parallel_for ( Iterator  begin,
Iterator  end,
thread_pool pool,
Function  func 
)

Runs the given function on the range denoted by begin and end in parallel.

Parameters
beginThe first element to operate on
endOne past the last element to operate on
poolThe thread pool to use
funcThe function to perform on each element