List of Figures

• The Future adaptor function template behavior: It takes a function pointer for an N-ary function and returns a future N-ary function object.
• The execution pattern of the example given in page : The statement labeled (A) creates an int future object out of the foo function pointer by first creating a future_ptr_to_unary_function object using the future_ptr_fun adaptor and schedules it with argument 4. Statement (B) represents an unrelated computation. Statement (C) requires the future to be resolved as a result of the addition operation between the int future object and an integer constant 3 to produce 'final'.
• Typical forms of sequential algorithms in STL style: The sequential algorithm takes in some iterators (the one in the figure takes 3) and other input parameters, traverses the iterators sequentially and produces an output.
• In a typical parallel algorithm strategy objects are used to convert the sequential iterators to per-thread parallel iterators which are used in the partial algorithms by each thread. The results computed by each of the threads in the partial algorithms are composed to produce the final output.
• Sequential iterators and the corresponding per-thread parallel iterators with 3 threads for Block, Cyclic, and Grab Strategies: For each of Begin and End sequential iterators there are 3 per-thread iterators. Their traversal pattern depends on the strategy used.

Abstract:

The Standard Template Library (STL) [15, 19] is a C++ implementation of the generic programming paradigm [16]. Unlike in typical container class libraries, algorithms in this paradigm do not work directly on collection container objects. They work on iterators (access and traversal objects) exported by containers. Given N data types, M containers, and K algorithms as components of a software system, STL provides a mechanism - using C++ templates and the generic programming paradigm - to reduce the possibly N*M*K implementations to N+M+K implementations.

Over the last decade significant research has been done in the area of object-oriented parallelism and a number of models, libraries, and language extensions have been proposed and implemented. C++ has been an important language for writing parallel libraries and for extending for parallelism. In this paper we discuss how the generic programming paradigm in STL can be used and extended to support parallel programming in a manner that allows good expressibility, code reuse, and extensibility of the library. We look at control and data-parallel abstractions. We also discuss how different strategies for work distribution in parallel algorithms can be supported in the spirit of generic programming. We describe the relevant abstractions in Coir<Futures> [23], our STL-based parallel C++ library for shared memory parallelism.