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

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