OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [libstdc++-v3/] [doc/] [html/] [manual/] [bk01pt12ch31s04.html] - Blame information for rev 424

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 424 jeremybenn 
<?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/a01005.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>

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.