Requirements of a Strategy Class

The strategy class should export a type definition for a corresponding per-thread iterator for one or more STL sequential iterators. Providing a per-thread iterator for each of the sequential iterators makes a strategy class more usable in the sense that it can possibly be used to parallelize all STL-based sequential algorithms.

Many algorithms (e.g., for_each, count, find) in STL work with iterator pairs - to indicate the beginning and end of a sequence. They might also have a third iterator that follows the traversal between the first two iterators. To help the parallelization of such algorithms a strategy class may provide two '()' operators:

1. operator()(const int size, iterator_type begin, iterator_type end, thread_iterator_type& thr_begin, thread_iterator_type& thr_end); This operator basically returns the per-thread iterators given a pair of sequential iterators. The size parameter indicates the number of participating threads. This operator may be defined for one or more of the iterator types.
2. operator()(const int size, iterator_type1 begin1, iterator_type1 end1, iterator_type2 begin2, thread_iterator_type1& thr_begin1, thread_iterator_type1& thr_end1, thread_iterator_type2& thr_begin2); In addition to returning per-thread iterators corresponding to 'begin1' and 'end1', this also returns the per-thread iterator corresponding to iterator 'begin2' that depends on 'begin1' and 'end1'.

In many algorithms the traversals from begin1 and begin2 typically happen in sync and make some assumptions about the relative positions. So the corresponding per-thread iterator should not lose this relation information. Static strategies can support iterators that retain this relationship because the traversal paths of the per-thread iterators are known. But dynamic strategies like the Grab strategy cannot guarantee this because the scope of the monitors used to control the traversal are per-iterator and using monitors over two iterator traversals would mean that we cannot reuse the sequential algorithm. Hence, while the parallel versions of some algorithms like swap_ranges and transform for static strategies are simple extensions of the sequential ones, the ones for the dynamic strategies may be quite different.

There are other algorithms in which even different static strategies might need different implementations. This depends on how the per-thread partial results are composed to produce the final results. For instance, the remove algorithm which removes elements of a particular value from a list for a Cyclic work strategy cannot compose the updated list by merely appending them in a reduction operation since this would put back the elements out of order. However, this can be done for the Block strategy.

Thus, it may not be possible to provide the same algorithm implementation for two different strategy classes for efficiency or correctness reasons. For this reason we introduce strategy tags and strategy categories similar to iterator tags and iterator categories in STL.