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