libstdc++-v3/doc/html/manual/bk01pt12ch31s04.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3 <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 Stylesheets V1.75.2" /><meta name="keywords" content="&#10;      C++&#10;    , &#10;      library&#10;    , &#10;      parallel&#10;    " /><meta name="keywords" content="&#10;      ISO C++&#10;    , &#10;      library&#10;    " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="parallel_mode.html" title="Chapter 31. Parallel Mode" /><link rel="prev" href="bk01pt12ch31s03.html" title="Using" /><link rel="next" href="bk01pt12ch31s05.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="bk01pt12ch31s03.html">Prev</a> </td><th width="60%" align="center">Chapter 31. Parallel Mode</th><td width="20%" align="right"> <a accesskey="n" href="bk01pt12ch31s05.html">Next</a></td></tr></table><hr /></div><div class="sect1" title="Design"><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>
   4   </p><div class="sect2" title="Interface Basics"><div class="titlepage"><div><div><h3 class="title"><a id="parallel_mode.design.intro"></a>Interface Basics</h3></div></div></div><p>
   5 All parallel algorithms are intended to have signatures that are
   6 equivalent to the ISO C++ algorithms replaced. For instance, the
   7 <code class="function">std::adjacent_find</code> function is declared as:
   8 </p><pre class="programlisting">
   9 namespace std
  10 {
  11   template&lt;typename _FIter&gt;
  12     _FIter
  13     adjacent_find(_FIter, _FIter);
  14 }
  15 </pre><p>
  16 Which means that there should be something equivalent for the parallel
  17 version. Indeed, this is the case:
  18 </p><pre class="programlisting">
  19 namespace std
  20 {
  21   namespace __parallel
  22   {
  23     template&lt;typename _FIter&gt;
  24       _FIter
  25       adjacent_find(_FIter, _FIter);
  26
  27     ...
  28   }
  29 }
  30 </pre><p>But.... why the ellipses?
  31 </p><p> The ellipses in the example above represent additional overloads
  32 required for the parallel version of the function. These additional
  33 overloads are used to dispatch calls from the ISO C++ function
  34 signature to the appropriate parallel function (or sequential
  35 function, if no parallel functions are deemed worthy), based on either
  36 compile-time or run-time conditions.
  37 </p><p> The available signature options are specific for the different
  38 algorithms/algorithm classes.</p><p> The general view of overloads for the parallel algorithms look like this:
  39 </p><div class="itemizedlist"><ul class="itemizedlist" 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
  40     (several signatures)</p></li></ul></div><p> Please note that the implementation may use additional functions
  41 (designated with the <code class="code">_switch</code> suffix) to dispatch from the
  42 ISO C++ signature to the correct parallel version. Also, some of the
  43 algorithms do not have support for run-time conditions, so the last
  44 overload is therefore missing.
  45 </p></div><div class="sect2" title="Configuration and Tuning"><div class="titlepage"><div><div><h3 class="title"><a id="parallel_mode.design.tuning"></a>Configuration and Tuning</h3></div></div></div><div class="sect3" title="Setting up the OpenMP Environment"><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>
  46 Several aspects of the overall runtime environment can be manipulated
  47 by standard OpenMP function calls.
  48 </p><p>
  49 To specify the number of threads to be used for the algorithms globally,
  50 use the function <code class="function">omp_set_num_threads</code>. An example:
  51 </p><pre class="programlisting">
  52 #include &lt;stdlib.h&gt;
  53 #include &lt;omp.h&gt;
  54
  55 int main()
  56 {
  57   // Explicitly set number of threads.
  58   const int threads_wanted = 20;
  59   omp_set_dynamic(false);
  60   omp_set_num_threads(threads_wanted);
  61
  62   // Call parallel mode algorithms.
  63
  64   return 0;
  65 }
  66 </pre><p>
  67  Some algorithms allow the number of threads being set for a particular call,
  68  by augmenting the algorithm variant.
  69  See the next section for further information.
  70 </p><p>
  71 Other parts of the runtime environment able to be manipulated include
  72 nested parallelism (<code class="function">omp_set_nested</code>), schedule kind
  73 (<code class="function">omp_set_schedule</code>), and others. See the OpenMP
  74 documentation for more information.
  75 </p></div><div class="sect3" title="Compile Time Switches"><div class="titlepage"><div><div><h4 class="title"><a id="parallel_mode.design.tuning.compile"></a>Compile Time Switches</h4></div></div></div><p>
  76 To force an algorithm to execute sequentially, even though parallelism
  77 is switched on in general via the macro <code class="constant">_GLIBCXX_PARALLEL</code>,
  78 add <code class="classname">__gnu_parallel::sequential_tag()</code> to the end
  79 of the algorithm's argument list.
  80 </p><p>
  81 Like so:
  82 </p><pre class="programlisting">
  83 std::sort(v.begin(), v.end(), __gnu_parallel::sequential_tag());
  84 </pre><p>
  85 Some parallel algorithm variants can be excluded from compilation by
  86 preprocessor defines. See the doxygen documentation on
  87 <code class="code">compiletime_settings.h</code> and <code class="code">features.h</code> for details.
  88 </p><p>
  89 For some algorithms, the desired variant can be chosen at compile-time by
  90 appending a tag object. The available options are specific to the particular
  91 algorithm (class).
  92 </p><p>
  93 For the "embarrassingly parallel" algorithms, there is only one "tag object
  94 type", the enum _Parallelism.
  95 It takes one of the following values,
  96 <code class="code">__gnu_parallel::parallel_tag</code>,
  97 <code class="code">__gnu_parallel::balanced_tag</code>,
  98 <code class="code">__gnu_parallel::unbalanced_tag</code>,
  99 <code class="code">__gnu_parallel::omp_loop_tag</code>,
 100 <code class="code">__gnu_parallel::omp_loop_static_tag</code>.
 101 This means that the actual parallelization strategy is chosen at run-time.
 102 (Choosing the variants at compile-time will come soon.)
 103 </p><p>
 104 For the following algorithms in general, we have
 105 <code class="code">__gnu_parallel::parallel_tag</code> and
 106 <code class="code">__gnu_parallel::default_parallel_tag</code>, in addition to
 107 <code class="code">__gnu_parallel::sequential_tag</code>.
 108 <code class="code">__gnu_parallel::default_parallel_tag</code> chooses the default
 109 algorithm at compiletime, as does omitting the tag.
 110 <code class="code">__gnu_parallel::parallel_tag</code> postpones the decision to runtime
 111 (see next section).
 112 For all tags, the number of threads desired for this call can optionally be
 113 passed to the respective tag's constructor.
 114 </p><p>
 115 The <code class="code">multiway_merge</code> algorithm comes with the additional choices,
 116 <code class="code">__gnu_parallel::exact_tag</code> and
 117 <code class="code">__gnu_parallel::sampling_tag</code>.
 118 Exact and sampling are the two available splitting strategies.
 119 </p><p>
 120 For the <code class="code">sort</code> and <code class="code">stable_sort</code> algorithms, there are
 121 several additional choices, namely
 122 <code class="code">__gnu_parallel::multiway_mergesort_tag</code>,
 123 <code class="code">__gnu_parallel::multiway_mergesort_exact_tag</code>,
 124 <code class="code">__gnu_parallel::multiway_mergesort_sampling_tag</code>,
 125 <code class="code">__gnu_parallel::quicksort_tag</code>, and
 126 <code class="code">__gnu_parallel::balanced_quicksort_tag</code>.
 127 Multiway mergesort comes with the two splitting strategies for multi-way
 128 merging. The quicksort options cannot be used for <code class="code">stable_sort</code>.
 129 </p></div><div class="sect3" title="Run Time Settings and Defaults"><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>
 130 The default parallelization strategy, the choice of specific algorithm
 131 strategy, the minimum threshold limits for individual parallel
 132 algorithms, and aspects of the underlying hardware can be specified as
 133 desired via manipulation
 134 of <code class="classname">__gnu_parallel::_Settings</code> member data.
 135 </p><p>
 136 First off, the choice of parallelization strategy: serial, parallel,
 137 or heuristically deduced. This corresponds
 138 to <code class="code">__gnu_parallel::_Settings::algorithm_strategy</code> and is a
 139 value of enum <span class="type">__gnu_parallel::_AlgorithmStrategy</span>
 140 type. Choices
 141 include: <span class="type">heuristic</span>, <span class="type">force_sequential</span>,
 142 and <span class="type">force_parallel</span>. The default is <span class="type">heuristic</span>.
 143 </p><p>
 144 Next, the sub-choices for algorithm variant, if not fixed at compile-time.
 145 Specific algorithms like <code class="function">find</code> or <code class="function">sort</code>
 146 can be implemented in multiple ways: when this is the case,
 147 a <code class="classname">__gnu_parallel::_Settings</code> member exists to
 148 pick the default strategy. For
 149 example, <code class="code">__gnu_parallel::_Settings::sort_algorithm</code> can
 150 have any values of
 151 enum <span class="type">__gnu_parallel::_SortAlgorithm</span>: <span class="type">MWMS</span>, <span class="type">QS</span>,
 152 or <span class="type">QS_BALANCED</span>.
 153 </p><p>
 154 Likewise for setting the minimal threshold for algorithm
 155 parallelization.  Parallelism always incurs some overhead. Thus, it is
 156 not helpful to parallelize operations on very small sets of
 157 data. Because of this, measures are taken to avoid parallelizing below
 158 a certain, pre-determined threshold. For each algorithm, a minimum
 159 problem size is encoded as a variable in the
 160 active <code class="classname">__gnu_parallel::_Settings</code> object.  This
 161 threshold variable follows the following naming scheme:
 162 <code class="code">__gnu_parallel::_Settings::[algorithm]_minimal_n</code>.  So,
 163 for <code class="function">fill</code>, the threshold variable
 164 is <code class="code">__gnu_parallel::_Settings::fill_minimal_n</code>,
 165 </p><p>
 166 Finally, hardware details like L1/L2 cache size can be hardwired
 167 via <code class="code">__gnu_parallel::_Settings::L1_cache_size</code> and friends.
 168 </p><p>
 169 </p><p>
 170 All these configuration variables can be changed by the user, if
 171 desired.
 172 There exists one global instance of the class <code class="classname">_Settings</code>,
 173 i. e. it is a singleton. It can be read and written by calling
 174 <code class="code">__gnu_parallel::_Settings::get</code> and
 175 <code class="code">__gnu_parallel::_Settings::set</code>, respectively.
 176 Please note that the first call return a const object, so direct manipulation
 177 is forbidden.
 178 See <a class="ulink" href="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00076.html" target="_top">
 179   <code class="filename">settings.h</code></a>
 180 for complete details.
 181 </p><p>
 182 A small example of tuning the default:
 183 </p><pre class="programlisting">
 184 #include &lt;parallel/algorithm&gt;
 185 #include &lt;parallel/settings.h&gt;
 186
 187 int main()
 188 {
 189   __gnu_parallel::_Settings s;
 190   s.algorithm_strategy = __gnu_parallel::force_parallel;
 191   __gnu_parallel::_Settings::set(s);
 192
 193   // Do work... all algorithms will be parallelized, always.
 194
 195   return 0;
 196 }
 197 </pre></div></div><div class="sect2" title="Implementation Namespaces"><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
 198 explicitly sequential:
 199 <code class="code">__gnu_serial</code>.
 200 </p><p> Two namespaces contain the parallel mode:
 201 <code class="code">std::__parallel</code> and <code class="code">__gnu_parallel</code>.
 202 </p><p> Parallel implementations of standard components, including
 203 template helpers to select parallelism, are defined in <code class="code">namespace
 204 std::__parallel</code>. For instance, <code class="function">std::transform</code> from <code class="filename">algorithm</code> has a parallel counterpart in
 205 <code class="function">std::__parallel::transform</code> from <code class="filename">parallel/algorithm</code>. In addition, these parallel
 206 implementations are injected into <code class="code">namespace
 207 __gnu_parallel</code> with using declarations.
 208 </p><p> Support and general infrastructure is in <code class="code">namespace
 209 __gnu_parallel</code>.
 210 </p><p> More information, and an organized index of types and functions
 211 related to the parallel mode on a per-namespace basis, can be found in
 212 the generated source documentation.
 213 </p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt12ch31s03.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="bk01pt12ch31s05.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Using </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> Testing</td></tr></table></div></body></html>