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.73.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="start" 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" lang="en" xml:lang="en"><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" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="manual.ext.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> Compile-time conditions are referred to as "embarrassingly
  38 parallel," and are denoted with the appropriate dispatch object, i.e.,
  39 one of <code class="code">__gnu_parallel::sequential_tag</code>,
  40 <code class="code">__gnu_parallel::parallel_tag</code>,
  41 <code class="code">__gnu_parallel::balanced_tag</code>,
  42 <code class="code">__gnu_parallel::unbalanced_tag</code>,
  43 <code class="code">__gnu_parallel::omp_loop_tag</code>, or
  44 <code class="code">__gnu_parallel::omp_loop_static_tag</code>.
  45 </p><p> Run-time conditions depend on the hardware being used, the number
  46 of threads available, etc., and are denoted by the use of the enum
  47 <code class="code">__gnu_parallel::parallelism</code>. Values of this enum include
  48 <code class="code">__gnu_parallel::sequential</code>,
  49 <code class="code">__gnu_parallel::parallel_unbalanced</code>,
  50 <code class="code">__gnu_parallel::parallel_balanced</code>,
  51 <code class="code">__gnu_parallel::parallel_omp_loop</code>,
  52 <code class="code">__gnu_parallel::parallel_omp_loop_static</code>, or
  53 <code class="code">__gnu_parallel::parallel_taskqueue</code>.
  54 </p><p> Putting all this together, the general view of overloads for the
  55 parallel algorithms look like this:
  56 </p><div class="itemizedlist"><ul type="disc"><li><p>ISO C++ signature</p></li><li><p>ISO C++ signature + sequential_tag argument</p></li><li><p>ISO C++ signature + parallelism argument</p></li></ul></div><p> Please note that the implementation may use additional functions
  57 (designated with the <code class="code">_switch</code> suffix) to dispatch from the
  58 ISO C++ signature to the correct parallel version. Also, some of the
  59 algorithms do not have support for run-time conditions, so the last
  60 overload is therefore missing.
  61 </p></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="manual.ext.parallel_mode.design.tuning"></a>Configuration and Tuning</h3></div></div></div><div class="sect3" lang="en" xml:lang="en"><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>
  62 Several aspects of the overall runtime environment can be manipulated
  63 by standard OpenMP function calls.
  64 </p><p>
  65 To specify the number of threads to be used for an algorithm, use the
  66 function <code class="function">omp_set_num_threads</code>. An example:
  67 </p><pre class="programlisting">
  68 #include &lt;stdlib.h&gt;
  69 #include &lt;omp.h&gt;
  70
  71 int main()
  72 {
  73   // Explicitly set number of threads.
  74   const int threads_wanted = 20;
  75   omp_set_dynamic(false);
  76   omp_set_num_threads(threads_wanted);
  77
  78   // Do work.
  79
  80   return 0;
  81 }
  82 </pre><p>
  83 Other parts of the runtime environment able to be manipulated include
  84 nested parallelism (<code class="function">omp_set_nested</code>), schedule kind
  85 (<code class="function">omp_set_schedule</code>), and others. See the OpenMP
  86 documentation for more information.
  87 </p></div><div class="sect3" lang="en" xml:lang="en"><div class="titlepage"><div><div><h4 class="title"><a id="parallel_mode.design.tuning.compile"></a>Compile Time Switches</h4></div></div></div><p>
  88 To force an algorithm to execute sequentially, even though parallelism
  89 is switched on in general via the macro <code class="constant">_GLIBCXX_PARALLEL</code>,
  90 add <code class="classname">__gnu_parallel::sequential_tag()</code> to the end
  91 of the algorithm's argument list, or explicitly qualify the algorithm
  92 with the <code class="code">__gnu_parallel::</code> namespace.
  93 </p><p>
  94 Like so:
  95 </p><pre class="programlisting">
  96 std::sort(v.begin(), v.end(), __gnu_parallel::sequential_tag());
  97 </pre><p>
  98 or
  99 </p><pre class="programlisting">
 100 __gnu_serial::sort(v.begin(), v.end());
 101 </pre><p>
 102 In addition, some parallel algorithm variants can be enabled/disabled/selected
 103 at compile-time.
 104 </p><p>
 105 See <a class="ulink" href="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00446.html" target="_top"><code class="filename">compiletime_settings.h</code></a> and
 106 See <a class="ulink" href="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00505.html" target="_top"><code class="filename">features.h</code></a> for details.
 107 </p></div><div class="sect3" lang="en" xml:lang="en"><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>
 108 The default parallelization strategy, the choice of specific algorithm
 109 strategy, the minimum threshold limits for individual parallel
 110 algorithms, and aspects of the underlying hardware can be specified as
 111 desired via manipulation
 112 of <code class="classname">__gnu_parallel::_Settings</code> member data.
 113 </p><p>
 114 First off, the choice of parallelization strategy: serial, parallel,
 115 or implementation-deduced. This corresponds
 116 to <code class="code">__gnu_parallel::_Settings::algorithm_strategy</code> and is a
 117 value of enum <span class="type">__gnu_parallel::_AlgorithmStrategy</span>
 118 type. Choices
 119 include: <span class="type">heuristic</span>, <span class="type">force_sequential</span>,
 120 and <span class="type">force_parallel</span>. The default is
 121 implementation-deduced, i.e. <span class="type">heuristic</span>.
 122 </p><p>
 123 Next, the sub-choices for algorithm implementation. Specific
 124 algorithms like <code class="function">find</code> or <code class="function">sort</code>
 125 can be implemented in multiple ways: when this is the case,
 126 a <code class="classname">__gnu_parallel::_Settings</code> member exists to
 127 pick the default strategy. For
 128 example, <code class="code">__gnu_parallel::_Settings::sort_algorithm</code> can
 129 have any values of
 130 enum <span class="type">__gnu_parallel::_SortAlgorithm</span>: <span class="type">MWMS</span>, <span class="type">QS</span>,
 131 or <span class="type">QS_BALANCED</span>.
 132 </p><p>
 133 Likewise for setting the minimal threshold for algorithm
 134 parallelization.  Parallelism always incurs some overhead. Thus, it is
 135 not helpful to parallelize operations on very small sets of
 136 data. Because of this, measures are taken to avoid parallelizing below
 137 a certain, pre-determined threshold. For each algorithm, a minimum
 138 problem size is encoded as a variable in the
 139 active <code class="classname">__gnu_parallel::_Settings</code> object.  This
 140 threshold variable follows the following naming scheme:
 141 <code class="code">__gnu_parallel::_Settings::[algorithm]_minimal_n</code>.  So,
 142 for <code class="function">fill</code>, the threshold variable
 143 is <code class="code">__gnu_parallel::_Settings::fill_minimal_n</code>
 144 </p><p>
 145 Finally, hardware details like L1/L2 cache size can be hardwired
 146 via <code class="code">__gnu_parallel::_Settings::L1_cache_size</code> and friends.
 147 </p><p>
 148 All these configuration variables can be changed by the user, if
 149 desired.  Please
 150 see <a class="ulink" href="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00640.html" target="_top"><code class="filename">settings.h</code></a>
 151 for complete details.
 152 </p><p>
 153 A small example of tuning the default:
 154 </p><pre class="programlisting">
 155 #include &lt;parallel/algorithm&gt;
 156 #include &lt;parallel/settings.h&gt;
 157
 158 int main()
 159 {
 160   __gnu_parallel::_Settings s;
 161   s.algorithm_strategy = __gnu_parallel::force_parallel;
 162   __gnu_parallel::_Settings::set(s);
 163
 164   // Do work... all algorithms will be parallelized, always.
 165
 166   return 0;
 167 }
 168 </pre></div></div><div class="sect2" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="manual.ext.parallel_mode.design.impl"></a>Implementation Namespaces</h3></div></div></div><p> One namespace contain versions of code that are always
 169 explicitly sequential:
 170 <code class="code">__gnu_serial</code>.
 171 </p><p> Two namespaces contain the parallel mode:
 172 <code class="code">std::__parallel</code> and <code class="code">__gnu_parallel</code>.
 173 </p><p> Parallel implementations of standard components, including
 174 template helpers to select parallelism, are defined in <code class="code">namespace
 175 std::__parallel</code>. For instance, <code class="function">std::transform</code> from <code class="filename">algorithm</code> has a parallel counterpart in
 176 <code class="function">std::__parallel::transform</code> from <code class="filename">parallel/algorithm</code>. In addition, these parallel
 177 implementations are injected into <code class="code">namespace
 178 __gnu_parallel</code> with using declarations.
 179 </p><p> Support and general infrastructure is in <code class="code">namespace
 180 __gnu_parallel</code>.
 181 </p><p> More information, and an organized index of types and functions
 182 related to the parallel mode on a per-namespace basis, can be found in
 183 the generated source documentation.
 184 </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>