摘要 |
A generic adaptor for converting from a sequential iterator to a parallel iterator is provided for the parallelization of sequential algorithms. The parallel algorithm implementation of a sequential algorithm is provided by the use of a template function with one template parameter in addition to those parameters of the corresponding sequential algorithm. This additional parameter is a strategy object which is an instance of a strategy class. In the body of the parallel algorithm, the strategy object is used to convert each sequential iterator to a plurality of per-thread parallel iterators. Each per-thread parallel iterator traverses those portions of a container for which the thread corresponding to this per-thread parallel iterator is responsible. When each thread has computed a partial result, the results are composed through a reduction operation if the partial results are an associative or commutative operation for a particular work distribution. A strategy class is conceptually an iterator adaptor which provides an operator that converts a sequential iterator to a plurality of per-thread parallel iterators. For instance, given two sequential iterators 'first' and 'last' corresponding to the beginning and end of a container sequence, a block strategy class may provide N pairs of per-thread parallel iterators, begini and endi, such that each of the N threads may process one of N blocks of data between 'first' and 'last'. Similarly, a cyclic strategy class may provide N per-thread parallel iterators that hop over an iteration space of a container by lengths of N where N is the number of threads participating.
|