* [PATCH][libstdc++-v3 parallel mode] PR 33491
@ 2007-10-01 11:42 Johannes Singler
2007-10-02 0:11 ` Benjamin Kosnik
0 siblings, 1 reply; 3+ messages in thread
From: Johannes Singler @ 2007-10-01 11:42 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 632 bytes --]
Adds the documentation pointers requested in PR 33491.
Only changes to comments, no regressions.
Any comments?
Johannes
2007-10-01 Johannes Singler <singler@ira.uka.de>
* include/parallel/multiway_merge.h: Added reference to paper.
* include/parallel/algorithm: Added reference to MCSTL.
* include/parallel/multiseq_selection.h: Added reference to paper.
* include/parallel/workstealing.h: Added reference to paper.
* include/parallel/numeric: Added reference to MCSTL.
* include/parallel/balanced_quicksort.h: Added reference to paper.
* include/parallel/tree.h: Added reference to paper.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: PR33491.patch --]
[-- Type: text/x-patch; name="PR33491.patch", Size: 4846 bytes --]
Index: parallel/algorithm
===================================================================
--- parallel/algorithm (revision 128884)
+++ parallel/algorithm (working copy)
@@ -30,6 +30,18 @@
/** @file parallel/algorithm
* This file is a GNU extension to the Standard C++ Library.
+ *
+ * This extension is based on code of the
+ * Multi-Core Standard Template Library,
+ * and was donated to the FSF by their authors.
+ *
+ * More information:
+ *
+ * http://algo2.iti.uni-karlsruhe.de/singler/mcstl
+ *
+ * J. Singler, P. Sanders, and F. Putze.
+ * The Multi-Core Standard Template Library.
+ * In Euro-Par 2007: Parallel Processing, 2007.
*/
#ifndef _PARALLEL_ALGORITHM
Index: parallel/multiseq_selection.h
===================================================================
--- parallel/multiseq_selection.h (revision 128884)
+++ parallel/multiseq_selection.h (working copy)
@@ -32,6 +32,13 @@
* @brief Functions to find elements of a certain global rank in
* multiple sorted sequences. Also serves for splitting such
* sequence sets.
+ *
+ * The algorithm description can be found in
+ *
+ * P. J. Varman, S. D. Scheuï¬er, B. R. Iyer, and G. R. Ricard.
+ * Merging Multiple Lists on Hierarchical-Memory Multiprocessors.
+ * Journal of Parallel and Distributed Computing, 12(2):171â177, 1991.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: parallel/workstealing.h
===================================================================
--- parallel/workstealing.h (revision 128884)
+++ parallel/workstealing.h (working copy)
@@ -31,6 +31,13 @@
/** @file parallel/workstealing.h
* @brief Parallelization of embarrassingly parallel execution by
* means of work-stealing.
+ *
+ * Work stealing is described in
+ *
+ * R. D. Blumofe and C. E. Leiserson.
+ * Scheduling multithreaded computations by work stealing.
+ * Journal of the ACM, 46(5):720â748, 1999.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: parallel/numeric
===================================================================
--- parallel/numeric (revision 128884)
+++ parallel/numeric (working copy)
@@ -28,15 +28,26 @@
// reasons why the executable file might be covered by the GNU General
// Public License.
-/**
- * @file parallel/numeric
-*
- * @brief Parallel STL function calls corresponding to stl_numeric.h.
- * The functions defined here mainly do case switches and
- * call the actual parallelized versions in other files.
- * Inlining policy: Functions that basically only contain one function call,
- * are declared inline.
+/** @file parallel/numeric
+ * @brief Parallel STL function calls corresponding to stl_numeric.h.
+ * The functions defined here mainly do case switches and
+ * call the actual parallelized versions in other files.
+ * Inlining policy: Functions that basically only contain one function call,
+ * are declared inline.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
+ *
+ * This extension is based on code of the
+ * Multi-Core Standard Template Library,
+ * and was donated to the FSF by their authors.
+ *
+ * More information:
+ *
+ * http://algo2.iti.uni-karlsruhe.de/singler/mcstl
+ *
+ * J. Singler, P. Sanders, and F. Putze.
+ * The Multi-Core Standard Template Library.
+ * In Euro-Par 2007: Parallel Processing, 2007.
*/
// Written by Johannes Singler and Felix Putze.
Index: parallel/balanced_quicksort.h
===================================================================
--- parallel/balanced_quicksort.h (revision 128884)
+++ parallel/balanced_quicksort.h (working copy)
@@ -32,6 +32,14 @@
* @brief Implementation of a dynamically load-balanced parallel quicksort.
*
* It works in-place and needs only logarithmic extra memory.
+ * The algorithm is similar to the one proposed in
+ *
+ * P. Tsigas and Y. Zhang.
+ * A simple, fast parallel implementation of quicksort and
+ * its performance evaluation on SUN enterprise 10000.
+ * In 11th Euromicro Conference on Parallel, Distributed and
+ * Network-Based Processing, page 372, 2003.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: parallel/tree.h
===================================================================
--- parallel/tree.h (revision 128884)
+++ parallel/tree.h (working copy)
@@ -31,6 +31,12 @@
/** @file parallel/tree.h
* @brief Parallel red-black tree operations.
* This file is a GNU parallel extension to the Standard C++ Library.
+ *
+ * This implementation is described in
+ *
+ * Leonor Frias, Johannes Singler.
+ * Parallelization of Bulk Operations for STL Dictionaries.
+ * Workshop on Highly Parallel Processing on a Chip (HPPC) 2007.
*/
// Written by Leonor Frias Moya, Johannes Singler.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH][libstdc++-v3 parallel mode] PR 33491
2007-10-01 11:42 [PATCH][libstdc++-v3 parallel mode] PR 33491 Johannes Singler
@ 2007-10-02 0:11 ` Benjamin Kosnik
2007-10-08 15:17 ` Johannes Singler
0 siblings, 1 reply; 3+ messages in thread
From: Benjamin Kosnik @ 2007-10-02 0:11 UTC (permalink / raw)
To: Johannes Singler; +Cc: libstdc++, gcc-patches
> 2007-10-01 Johannes Singler <singler@ira.uka.de>
>
> * include/parallel/multiway_merge.h: Added reference to paper.
> * include/parallel/multiseq_selection.h: Added reference to
> * include/parallel/workstealing.h: Added reference to paper.
> * include/parallel/balanced_quicksort.h: Added reference to
> paper.
> * include/parallel/tree.h: Added reference to paper.
These are fine.
> * include/parallel/algorithm: Added reference to MCSTL.
> * include/parallel/numeric: Added reference to MCSTL.
Just add the individual papers cited:
http://algo2.iti.uni-karlsruhe.de/singler/mcstl/index.php?page=publications
To the bottom of parallel_mode.html in a new section at the bottom of
the page called "References/Further Reading."
best,
benjamin
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH][libstdc++-v3 parallel mode] PR 33491
2007-10-02 0:11 ` Benjamin Kosnik
@ 2007-10-08 15:17 ` Johannes Singler
0 siblings, 0 replies; 3+ messages in thread
From: Johannes Singler @ 2007-10-08 15:17 UTC (permalink / raw)
To: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 828 bytes --]
Benjamin Kosnik wrote:
> Just add the individual papers cited:
> http://algo2.iti.uni-karlsruhe.de/singler/mcstl/index.php?page=publications
>
> To the bottom of parallel_mode.html in a new section at the bottom of
> the page called "References/Further Reading."
Done and committed as attached.
2007-10-08 Johannes Singler <singler@ira.uka.de>
* docs/html/parallel_mode.html: Added reference to MCSTL.
More documentation on compile-time settings and tuning.
* include/parallel/multiway_merge.h: Added reference to paper.
* include/parallel/multiseq_selection.h: Added reference to paper.
* include/parallel/workstealing.h: Added reference to paper.
* include/parallel/balanced_quicksort.h: Added reference to paper.
* include/parallel/tree.h: Added reference to paper.
Johannes
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: PR33491_2.patch --]
[-- Type: text/x-patch; name="PR33491_2.patch", Size: 8318 bytes --]
Index: docs/html/parallel_mode.html
===================================================================
--- docs/html/parallel_mode.html (revision 129126)
+++ docs/html/parallel_mode.html (working copy)
@@ -35,7 +35,7 @@
<p>
Several of the standard algorithms, for instance
-<code>std::search</code>, are made parallel using OpenMP
+<code>std::sort</code>, are made parallel using OpenMP
annotations. These parallel mode constructs and can be invoked by
explicit source declaration or by compiling existing sources with a
specific compiler flag.
@@ -43,7 +43,7 @@
<h3 class="left"><a name="parallel">The libstdc++ parallel mode</a></h3>
-<p>The libstdc++ parallel mode performs parallization of algorithms,
+<p>The libstdc++ parallel mode performs parallelization of algorithms,
function objects, classes, and functions in the C++ Standard.</p>
<h4 class="left">Using the libstdc++ parallel mode</h4>
@@ -53,7 +53,7 @@
will link in <code>libgomp</code>, the GNU OpenMP <a
href="http://gcc.gnu.org/onlinedocs/libgomp">implementation</a>,
whose presence is mandatory. In addition, hardware capable of atomic
- operations is de rigueur. Actually activating these atomic
+ operations is mandatory. Actually activating these atomic
operations may require explicit compiler flags on some targets
(like sparc and x86), such as <code>-march=i686</code>,
<code>-march=native</code> or <code>-mcpu=v9</code>.
@@ -113,7 +113,14 @@
<li><code>std::unique_copy</code></li>
</ul>
+<p>The following library components in the includes
+<code><set></code> and <code><map></code> are included in the parallel mode:</p>
+<ul>
+ <li><code>std::(multi_)map/set<T>::(multi_)map/set(Iterator begin, Iterator end)</code> (bulk construction)</li>
+ <li><code>std::(multi_)map/set<T>::insert(Iterator begin, Iterator end)</code> (bulk insertion)</li>
+</ul>
+
<h4 class="left">Using the parallel algorithms without parallel mode</h4>
<p>When it is not feasible to recompile your entire application, or
@@ -380,14 +387,48 @@
<h4 class="left">Parallel mode semantics</h4>
-<p> Something about exception safety, interaction with threads,
-etc. Goal is to have the usual constraints of the STL with respect to
-exception safety and threads, but add in support for parallel
-computing.</p>
-<p> Something about compile-time settings and configuration, ie using
-<code>__gnu_parallel::Settings</code>. XXX Up in the air.</p>
+<p> The parallel mode STL algorithms are currently not exception-safe,
+i. e. user-defined functors must not throw exceptions.
+</p>
+<p> Since the current GCC OpenMP implementation does not support
+OpenMP parallel regions in concurrent threads,
+it is not possible to call parallel STL algorithm in
+concurrent threads, either.
+It might work with other compilers, though.</p>
+
+
+<h4 class="left">Configuration and Tuning</h4>
+
+<p> Some algorithm variants can be enabled/disabled/selected at compile-time.
+See <a href="latest-doxygen/compiletime__settings_8h.html">
+<code><compiletime_settings.h></code></a> and
+See <a href="latest-doxygen/compiletime__settings_8h.html">
+<code><features.h></code></a> for details.
+</p>
+
+<p>
+To specify the number of threads to be used for an algorithm,
+use <code>omp_set_num_threads</code>.
+To force a function to execute sequentially,
+even though parallelism is switched on in general,
+add <code>__gnu_parallel::sequential_tag()</code>
+to the end of the argument list.
+</p>
+
+<p>
+Parallelism always incurs some overhead. Thus, it is not
+helpful to parallelize operations on very small sets of data.
+There are measures to avoid parallelizing stuff that is not worth it.
+For each algorithm, a minimum problem size can be stated,
+usually using the variable
+<code>__gnu_parallel::Settings::[algorithm]_minimal_n</code>.
+Please see <a href="latest-doxygen/settings_8h.html">
+<code><settings.h></code><a> for details.</p>
+
+
+
<h4 class="left">Interface basics and general design</h4>
<p>All parallel algorithms are intended to have signatures that are
@@ -485,7 +526,7 @@
<algorithm> has a parallel counterpart in
<code>std::__parallel::transform</code> from
<parallel/algorithm>. In addition, these parallel
-implementatations are injected into <code>namespace
+implementations are injected into <code>namespace
__gnu_parallel</code> with using declarations.
</p>
@@ -526,6 +567,16 @@
</p>
+<h4 class="left">References / Further Reading</h4>
+
+<p>
+Johannes Singler, Peter Sanders, Felix Putze. The Multi-Core Standard Template Library. Euro-Par 2007: Parallel Processing. (LNCS 4641)
+</p>
+
+<p>
+Leonor Frias, Johannes Singler: Parallelization of Bulk Operations for STL Dictionaries. Workshop on Highly Parallel Processing on a Chip (HPPC) 2007. (LNCS)
+</p>
+
<!-- ####################################################### -->
<hr />
Index: include/parallel/multiway_merge.h
===================================================================
--- include/parallel/multiway_merge.h (revision 129126)
+++ include/parallel/multiway_merge.h (working copy)
@@ -30,6 +30,13 @@
/** @file parallel/multiway_merge.h
* @brief Implementation of sequential and parallel multiway merge.
+ *
+ * Explanations on the high-speed merging routines in the appendix of
+ *
+ * P. Sanders.
+ * Fast priority queues for cached memory.
+ * ACM Journal of Experimental Algorithmics, 5, 2000.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 129126)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -32,6 +32,13 @@
* @brief Functions to find elements of a certain global rank in
* multiple sorted sequences. Also serves for splitting such
* sequence sets.
+ *
+ * The algorithm description can be found in
+ *
+ * P. J. Varman, S. D. Scheufler, B. R. Iyer, and G. R. Ricard.
+ * Merging Multiple Lists on Hierarchical-Memory Multiprocessors.
+ * Journal of Parallel and Distributed Computing, 12(2):171â177, 1991.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: include/parallel/workstealing.h
===================================================================
--- include/parallel/workstealing.h (revision 129126)
+++ include/parallel/workstealing.h (working copy)
@@ -31,6 +31,13 @@
/** @file parallel/workstealing.h
* @brief Parallelization of embarrassingly parallel execution by
* means of work-stealing.
+ *
+ * Work stealing is described in
+ *
+ * R. D. Blumofe and C. E. Leiserson.
+ * Scheduling multithreaded computations by work stealing.
+ * Journal of the ACM, 46(5):720â748, 1999.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 129126)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -32,6 +32,14 @@
* @brief Implementation of a dynamically load-balanced parallel quicksort.
*
* It works in-place and needs only logarithmic extra memory.
+ * The algorithm is similar to the one proposed in
+ *
+ * P. Tsigas and Y. Zhang.
+ * A simple, fast parallel implementation of quicksort and
+ * its performance evaluation on SUN enterprise 10000.
+ * In 11th Euromicro Conference on Parallel, Distributed and
+ * Network-Based Processing, page 372, 2003.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
Index: include/parallel/tree.h
===================================================================
--- include/parallel/tree.h (revision 129126)
+++ include/parallel/tree.h (working copy)
@@ -30,6 +30,13 @@
/** @file parallel/tree.h
* @brief Parallel red-black tree operations.
+ *
+ * This implementation is described in
+ *
+ * Leonor Frias, Johannes Singler.
+ * Parallelization of Bulk Operations for STL Dictionaries.
+ * Workshop on Highly Parallel Processing on a Chip (HPPC) 2007.
+ *
* This file is a GNU parallel extension to the Standard C++ Library.
*/
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2007-10-08 15:17 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-10-01 11:42 [PATCH][libstdc++-v3 parallel mode] PR 33491 Johannes Singler
2007-10-02 0:11 ` Benjamin Kosnik
2007-10-08 15:17 ` Johannes Singler
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).