Skip to content

R
riscv-gcc-1
Switch branch/tag
Find file
Normal viewHistoryPermalink
parallel_mode_design.html 12.9 KB
Newer Older
PR libstdc++/54102, part 2
27f36b78
 
Benjamin Kosnik committed
1 
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
appendix_contributing.xml: Remove broken link and defer to general documentation…
fa93ca85
 
Jonathan Wakely committed
2 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Design</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.78.1" /><meta name="keywords" content="C++, library, parallel" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="parallel_mode.html" title="Chapter 18. Parallel Mode" /><link rel="prev" href="parallel_mode_using.html" title="Using" /><link rel="next" href="parallel_mode_test.html" title="Testing" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Design</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="parallel_mode_using.html">Prev</a> </td><th width="60%" align="center">Chapter 18. Parallel Mode</th><td width="20%" align="right"> <a accesskey="n" href="parallel_mode_test.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.ext.parallel_mode.design"></a>Design</h2></div></div></div><p>
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
3 
  </p><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="parallel_mode.design.intro"></a>Interface Basics</h3></div></div></div><p>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
4 
All parallel algorithms are intended to have signatures that are
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
5 
equivalent to the ISO C++ algorithms replaced. For instance, the
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
6 
<code class="function">std::adjacent_find</code> function is declared as:
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 
</p><pre class="programlisting">
namespace std
{
  template&lt;typename _FIter&gt;
    _FIter
    adjacent_find(_FIter, _FIter);
}
</pre><p>
Which means that there should be something equivalent for the parallel
version. Indeed, this is the case:
</p><pre class="programlisting">
namespace std
{
  namespace __parallel
  {
    template&lt;typename _FIter&gt;
      _FIter
      adjacent_find(_FIter, _FIter);

    ...
  }
}
[multiple changes]
4394b61e
 
Benjamin Kosnik committed
29 30 
</pre><p>But.... why the ellipses?
</p><p> The ellipses in the example above represent additional overloads
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
31 32 33 34 35 
required for the parallel version of the function. These additional
overloads are used to dispatch calls from the ISO C++ function
signature to the appropriate parallel function (or sequential
function, if no parallel functions are deemed worthy), based on either
compile-time or run-time conditions.
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
36 37 
</p><p> The available signature options are specific for the different
algorithms/algorithm classes.</p><p> The general view of overloads for the parallel algorithms look like this:
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
38 
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>ISO C++ signature</p></li><li class="listitem"><p>ISO C++ signature + sequential_tag argument</p></li><li class="listitem"><p>ISO C++ signature + algorithm-specific tag type
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
39 
    (several signatures)</p></li></ul></div><p> Please note that the implementation may use additional functions
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
40 41 42 43 
(designated with the <code class="code">_switch</code> suffix) to dispatch from the
ISO C++ signature to the correct parallel version. Also, some of the
algorithms do not have support for run-time conditions, so the last
overload is therefore missing.
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
44 
</p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="parallel_mode.design.tuning"></a>Configuration and Tuning</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="parallel_mode.design.tuning.omp"></a>Setting up the OpenMP Environment</h4></div></div></div><p>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
45 46 
Several aspects of the overall runtime environment can be manipulated
by standard OpenMP function calls.
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
47 
</p><p>
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
48 49 
To specify the number of threads to be used for the algorithms globally,
use the function <code class="function">omp_set_num_threads</code>. An example:
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
50 51 52 53 54 55 56 57 58 59 60 
</p><pre class="programlisting">
#include &lt;stdlib.h&gt;
#include &lt;omp.h&gt;

int main()
{
  // Explicitly set number of threads.
  const int threads_wanted = 20;
  omp_set_dynamic(false);
  omp_set_num_threads(threads_wanted);
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
61 
  // Call parallel mode algorithms.
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
62 63 64 65 

  return 0;
}
</pre><p>
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
66 67 68 69 
 Some algorithms allow the number of threads being set for a particular call,
 by augmenting the algorithm variant.
 See the next section for further information.
</p><p>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
70 71 72 73 
Other parts of the runtime environment able to be manipulated include
nested parallelism (<code class="function">omp_set_nested</code>), schedule kind
(<code class="function">omp_set_schedule</code>), and others. See the OpenMP
documentation for more information.
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
74 
</p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="parallel_mode.design.tuning.compile"></a>Compile Time Switches</h4></div></div></div><p>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
75 76 77 
To force an algorithm to execute sequentially, even though parallelism
is switched on in general via the macro <code class="constant">_GLIBCXX_PARALLEL</code>,
add <code class="classname">__gnu_parallel::sequential_tag()</code> to the end
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
78 
of the algorithm's argument list.
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
79 80 81 82 83 
</p><p>
Like so:
</p><pre class="programlisting">
std::sort(v.begin(), v.end(), __gnu_parallel::sequential_tag());
</pre><p>
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
84 85 86 
Some parallel algorithm variants can be excluded from compilation by
preprocessor defines. See the doxygen documentation on
<code class="code">compiletime_settings.h</code> and <code class="code">features.h</code> for details.
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
87 
</p><p>
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 
For some algorithms, the desired variant can be chosen at compile-time by
appending a tag object. The available options are specific to the particular
algorithm (class).
</p><p>
For the "embarrassingly parallel" algorithms, there is only one "tag object
type", the enum _Parallelism.
It takes one of the following values,
<code class="code">__gnu_parallel::parallel_tag</code>,
<code class="code">__gnu_parallel::balanced_tag</code>,
<code class="code">__gnu_parallel::unbalanced_tag</code>,
<code class="code">__gnu_parallel::omp_loop_tag</code>,
<code class="code">__gnu_parallel::omp_loop_static_tag</code>.
This means that the actual parallelization strategy is chosen at run-time.
(Choosing the variants at compile-time will come soon.)
</p><p>
For the following algorithms in general, we have
<code class="code">__gnu_parallel::parallel_tag</code> and
<code class="code">__gnu_parallel::default_parallel_tag</code>, in addition to
<code class="code">__gnu_parallel::sequential_tag</code>.
faq.xml: Link to manual.
18246ced
 
Jonathan Wakely committed
107 
<code class="code">__gnu_parallel::default_parallel_tag</code> chooses the default
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
108 109 110 111 112 113 114 115 116 117 118 119 120 121 
algorithm at compiletime, as does omitting the tag.
<code class="code">__gnu_parallel::parallel_tag</code> postpones the decision to runtime
(see next section).
For all tags, the number of threads desired for this call can optionally be
passed to the respective tag's constructor.
</p><p>
The <code class="code">multiway_merge</code> algorithm comes with the additional choices,
<code class="code">__gnu_parallel::exact_tag</code> and
<code class="code">__gnu_parallel::sampling_tag</code>.
Exact and sampling are the two available splitting strategies.
</p><p>
For the <code class="code">sort</code> and <code class="code">stable_sort</code> algorithms, there are
several additional choices, namely
<code class="code">__gnu_parallel::multiway_mergesort_tag</code>,
faq.xml: Link to manual.
18246ced
 
Jonathan Wakely committed
122 
<code class="code">__gnu_parallel::multiway_mergesort_exact_tag</code>,
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
123 124 125 126 127 
<code class="code">__gnu_parallel::multiway_mergesort_sampling_tag</code>,
<code class="code">__gnu_parallel::quicksort_tag</code>, and
<code class="code">__gnu_parallel::balanced_quicksort_tag</code>.
Multiway mergesort comes with the two splitting strategies for multi-way
merging. The quicksort options cannot be used for <code class="code">stable_sort</code>.
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
128 
</p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="parallel_mode.design.tuning.settings"></a>Run Time Settings and Defaults</h4></div></div></div><p>
[multiple changes]
4394b61e
 
Benjamin Kosnik committed
129 
The default parallelization strategy, the choice of specific algorithm
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
130 131 132 133 
strategy, the minimum threshold limits for individual parallel
algorithms, and aspects of the underlying hardware can be specified as
desired via manipulation
of <code class="classname">__gnu_parallel::_Settings</code> member data.
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
134 
</p><p>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
135 
First off, the choice of parallelization strategy: serial, parallel,
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
136 
or heuristically deduced. This corresponds
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
137 138 139 140 
to <code class="code">__gnu_parallel::_Settings::algorithm_strategy</code> and is a
value of enum <span class="type">__gnu_parallel::_AlgorithmStrategy</span>
type. Choices
include: <span class="type">heuristic</span>, <span class="type">force_sequential</span>,
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
141 
and <span class="type">force_parallel</span>. The default is <span class="type">heuristic</span>.
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
142 
</p><p>
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
143 144 
Next, the sub-choices for algorithm variant, if not fixed at compile-time.
Specific algorithms like <code class="function">find</code> or <code class="function">sort</code>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
145 146 147 148 149 150 151 152 153 
can be implemented in multiple ways: when this is the case,
a <code class="classname">__gnu_parallel::_Settings</code> member exists to
pick the default strategy. For
example, <code class="code">__gnu_parallel::_Settings::sort_algorithm</code> can
have any values of
enum <span class="type">__gnu_parallel::_SortAlgorithm</span>: <span class="type">MWMS</span>, <span class="type">QS</span>,
or <span class="type">QS_BALANCED</span>.
</p><p>
Likewise for setting the minimal threshold for algorithm
[multiple changes]
4394b61e
 
Benjamin Kosnik committed
154 
parallelization.  Parallelism always incurs some overhead. Thus, it is
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
155 156 157 158 159 160 161 162 
not helpful to parallelize operations on very small sets of
data. Because of this, measures are taken to avoid parallelizing below
a certain, pre-determined threshold. For each algorithm, a minimum
problem size is encoded as a variable in the
active <code class="classname">__gnu_parallel::_Settings</code> object.  This
threshold variable follows the following naming scheme:
<code class="code">__gnu_parallel::_Settings::[algorithm]_minimal_n</code>.  So,
for <code class="function">fill</code>, the threshold variable
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
163 
is <code class="code">__gnu_parallel::_Settings::fill_minimal_n</code>,
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
164 165 166 167 
</p><p>
Finally, hardware details like L1/L2 cache size can be hardwired
via <code class="code">__gnu_parallel::_Settings::L1_cache_size</code> and friends.
</p><p>
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
168 
</p><p>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
169 
All these configuration variables can be changed by the user, if
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
170 171 172 173 174 175 176 
desired.
There exists one global instance of the class <code class="classname">_Settings</code>,
i. e. it is a singleton. It can be read and written by calling
<code class="code">__gnu_parallel::_Settings::get</code> and
<code class="code">__gnu_parallel::_Settings::set</code>, respectively.
Please note that the first call return a const object, so direct manipulation
is forbidden.
*: Regenerate.
6247d6df
 
Benjamin Kosnik committed
177 
See <a class="link" href="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01005.html" target="_top">
parallel_mode.xml: Clarify use of explicit parallel algorithms.
d3cf4d72
 
Benjamin Kosnik committed
178 
  <code class="filename">settings.h</code></a>
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 
for complete details.
</p><p>
A small example of tuning the default:
</p><pre class="programlisting">
#include &lt;parallel/algorithm&gt;
#include &lt;parallel/settings.h&gt;

int main()
{
  __gnu_parallel::_Settings s;
  s.algorithm_strategy = __gnu_parallel::force_parallel;
  __gnu_parallel::_Settings::set(s);

  // Do work... all algorithms will be parallelized, always.

  return 0;
}
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
196 
</pre></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="parallel_mode.design.impl"></a>Implementation Namespaces</h3></div></div></div><p> One namespace contain versions of code that are always
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
197 
explicitly sequential:
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
198 199 
<code class="code">__gnu_serial</code>.
</p><p> Two namespaces contain the parallel mode:
faq.xml: Link to manual.
18246ced
 
Jonathan Wakely committed
200 
<code class="code">std::__parallel</code> and <code class="code">__gnu_parallel</code>.
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
201 202 
</p><p> Parallel implementations of standard components, including
template helpers to select parallelism, are defined in <code class="code">namespace
re PR libstdc++/35256 (Bad link on http://gcc.gnu.org/onlinedocs/libstdc++/parallel_mode.html)
1285e2a2
 
Benjamin Kosnik committed
203 204 
std::__parallel</code>. For instance, <code class="function">std::transform</code> from <code class="filename">algorithm</code> has a parallel counterpart in
<code class="function">std::__parallel::transform</code> from <code class="filename">parallel/algorithm</code>. In addition, these parallel
*: Populate with regenerated files.
46abada0
 
Benjamin Kosnik committed
205 206 207 208 209 210 211 
implementations are injected into <code class="code">namespace
__gnu_parallel</code> with using declarations.
</p><p> Support and general infrastructure is in <code class="code">namespace
__gnu_parallel</code>.
</p><p> More information, and an organized index of types and functions
related to the parallel mode on a per-namespace basis, can be found in
the generated source documentation.
*: Regenerate.
53b03cce
 
Benjamin Kosnik committed
212 
</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="parallel_mode_using.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="parallel_mode.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="parallel_mode_test.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Using </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Testing</td></tr></table></div></body></html>