[v3] parallel mode

[Benjamin Kosnik <bkoz at redhat dot com>]

I'm delighted to announce a parallel implementation of many C++
Standard library algorithms, which been integrated into libstdc++ as
an experimental mode that will henceforth be known as the libstdc++
parallel mode. These parallel algorithms use OpenMP as a thread layer,
and should thus be portable to hardware/os combinations that support
libgomp.

This work was graciously donated to the FSF by Johannes Singler and
Leonor Frias, with the support of the University of Karlsruhe. Assisting
were Felix Putze, Marius Elvert, Felix Bondarenko, Robert Geisberger,
Robin Dapp, and myself. In addition, Johannes has agreed to continuing
to hack on this functionality.

This is designed as another specialized mode for libstdc++, similar to
the debug mode, only for code making use of parallel algorithms. 

Usage is pretty simple. C++ code that uses the STL can recompile with
-D_GLIBCXX_PARALLEL -fopenmp, and get parallized versions of the usual
STL bits. Or, algorithms can be injected explicitly by qualifying as
parallel, like so: __gnu_parallel::transform.

More details are here:

http://people.redhat.com/bkoz/parallel_mode/parallel_mode.html

Which has also been aded to the libstdc++ documentation.

There are some areas that require more thought and tuning: the
efficiency of parallel execution in the subtle interplay between
threading overhead, input size, behavior of user-defined parts,
hardware limitations (memory bandwidth) and so on. Much tuning needs
to be done. Documentation needs to be improved, etc. This effort and
research will be on-going: suggestions and help are welcome.

The current testing status is excellent, passing both the usual checks
(make check) and a new make rule (make check-parallel) that runs the
libstdc++ conformance tests with -D_GLIBCXX_PARALLEL -fopenmp.  For
the usual checks, (make check) results are identical, and for parallel
mode there are no unexpected fails. Performance testing is on-going,
but all the usual performance tests build and run.

Because of these testing results, the recent go status from the FSF on
assignments, and the stage 3 deadline, I'd like to put this in
now. Certainly, having a central SVN repository will help development.

Jakub has reviewed recent versions of this code (and provided some
feedback on testing approaches for earlier versions), and has some
suggestions about OpenMP usage. We certainly intend to address these
concerns, but would prefer to do this after the code is checked in.

Ulrich has also reviewed earlier versions of this code: I believe all
his usage suggestions have already been incorporated.

tested x86/linux
tested x86_64/linux

-benjamin

Attachment: p.20070909.bz2
Description: application/bzip