]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
5817ff8e | 3 | // Copyright (C) 2007, 2008 Free Software Foundation, Inc. |
c2ba9709 JS |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
8 | // Foundation; either version 2, or (at your option) any later | |
9 | // version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License | |
17 | // along with this library; see the file COPYING. If not, write to | |
18 | // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, | |
19 | // MA 02111-1307, USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free | |
22 | // software library without restriction. Specifically, if other files | |
23 | // instantiate templates or use macros or inline functions from this | |
24 | // file, or you compile this file and link it with other files to | |
25 | // produce an executable, this file does not by itself cause the | |
26 | // resulting executable to be covered by the GNU General Public | |
27 | // License. This exception does not however invalidate any other | |
28 | // reasons why the executable file might be covered by the GNU General | |
29 | // Public License. | |
30 | ||
31 | /** @file parallel/settings.h | |
32 | * @brief Settings and tuning parameters, heuristics to decide | |
33 | * whether to use parallelized algorithms. | |
34 | * This file is a GNU parallel extension to the Standard C++ Library. | |
35 | * | |
5817ff8e PC |
36 | * @section parallelization_decision The decision whether to run |
37 | * an algorithm in parallel. | |
c2ba9709 JS |
38 | * |
39 | * There are several ways the user can switch on and off the | |
40 | * parallel execution of an algorithm, both at compile- and | |
41 | * run-time. | |
42 | * | |
43 | * Only sequential execution can be forced at compile-time. | |
44 | * This reduces code size and protects code parts that have | |
45 | * non-thread-safe side effects. | |
46 | * | |
47 | * Ultimately forcing parallel execution at compile-time does | |
48 | * make much sense. | |
49 | * Often, the sequential algorithm implementation is used as | |
50 | * a subroutine, so no reduction in code size can be achieved. | |
51 | * Also, the machine the program is run on might have only one | |
52 | * processor core, so to avoid overhead, the algorithm is | |
53 | * executed sequentially. | |
54 | * | |
55 | * To force sequential execution of an algorithm ultimately | |
56 | * at compile-time, the user must add the tag | |
57 | * __gnu_parallel::sequential_tag() to the end of the | |
58 | * parameter list, e. g. | |
59 | * | |
60 | * \code | |
61 | * std::sort(v.begin(), v.end(), __gnu_parallel::sequential_tag()); | |
62 | * \endcode | |
63 | * | |
64 | * This is compatible with all overloaded algorithm variants. | |
65 | * No additional code will be instantiated, at all. | |
66 | * The same holds for most algorithm calls with iterators | |
67 | * not providing random access. | |
68 | * | |
69 | * If the algorithm call is not forced to be executed sequentially | |
70 | * at compile-time, the decision is made at run-time, for each call. | |
71 | * First, the two (conceptually) global variables | |
72 | * __gnu_parallel::Settings::force_sequential and | |
73 | * __gnu_parallel::Settings::force_parallel are executed. | |
74 | * If the former one is true, the sequential algorithm is executed. | |
75 | * If the latter one is true and the former one is false, | |
76 | * the algorithm is executed in parallel. | |
77 | * | |
78 | * If none of these conditions has fired so far, a heuristic is used. | |
79 | * The parallel algorithm implementation is called only if the | |
80 | * input size is sufficiently large. | |
81 | * For most algorithms, the input size is the (combined) length of | |
82 | * the input sequence(s). | |
83 | * The threshold can be set by the user, individually for each | |
84 | * algorithm. | |
85 | * The according variables are called | |
86 | * __gnu_parallel::Settings::[algorithm]_minimal_n . | |
87 | * | |
88 | * For some of the algorithms, there are even more tuning options, | |
89 | * e. g. the ability to choose from multiple algorithm variants. | |
90 | * See the __gnu_parallel::Settings class for details. | |
91 | */ | |
92 | ||
93 | // Written by Johannes Singler and Felix Putze. | |
94 | ||
95 | #ifndef _GLIBCXX_PARALLEL_SETTINGS_H | |
96 | #define _GLIBCXX_PARALLEL_SETTINGS_H 1 | |
97 | ||
98 | #include <omp.h> | |
99 | #include <parallel/types.h> | |
100 | ||
101 | /** | |
102 | * @brief The extensible condition on whether the parallel variant of | |
28dac70a | 103 | * an algorithm should be called. |
c2ba9709 JS |
104 | * @param c A condition that is overruled by |
105 | * __gnu_parallel::Settings::force_parallel, i. e. usually a decision based on | |
106 | * the input size. | |
107 | */ | |
5817ff8e PC |
108 | #define _GLIBCXX_PARALLEL_CONDITION(c) \ |
109 | (!(__gnu_parallel::Settings::force_sequential) \ | |
110 | && ((__gnu_parallel::get_max_threads() > 1 \ | |
111 | && (c)) || __gnu_parallel::Settings::force_parallel)) | |
c2ba9709 JS |
112 | |
113 | namespace __gnu_parallel | |
114 | { | |
115 | // NB: Including this file cannot produce (unresolved) symbols from | |
116 | // the OpenMP runtime unless the parallel mode is actually invoked | |
28dac70a | 117 | // and active, which implies that the OpenMP runtime is actually |
c2ba9709 JS |
118 | // going to be linked in. |
119 | inline int | |
120 | get_max_threads() | |
121 | { return omp_get_max_threads() > 1 ? omp_get_max_threads() : 1; } | |
122 | ||
123 | namespace | |
124 | { | |
125 | // XXX look at _Tune in mt_allocator.h | |
126 | /** @brief Run-time settings for the parallel mode. */ | |
127 | struct Settings | |
128 | { | |
129 | /** @brief Different parallel sorting algorithms to choose | |
130 | from: multi-way mergesort, quicksort, load-balanced | |
131 | quicksort. */ | |
132 | enum SortAlgorithm | |
133 | { MWMS, QS, QS_BALANCED }; | |
134 | ||
135 | /** @brief Different merging algorithms: bubblesort-alike, | |
136 | loser-tree variants, enum sentinel */ | |
137 | enum MultiwayMergeAlgorithm | |
5817ff8e PC |
138 | { BUBBLE, LOSER_TREE_EXPLICIT, LOSER_TREE, LOSER_TREE_COMBINED, |
139 | LOSER_TREE_SENTINEL, MWM_ALGORITHM_LAST }; | |
c2ba9709 JS |
140 | |
141 | /** @brief Different splitting strategies for sorting/merging: | |
142 | by sampling, exact */ | |
143 | enum Splitting | |
144 | { SAMPLING, EXACT }; | |
145 | ||
146 | /** @brief Different partial sum algorithms: recursive, linear */ | |
147 | enum PartialSumAlgorithm | |
148 | { RECURSIVE, LINEAR }; | |
149 | ||
150 | /** @brief Different find distribution strategies: growing | |
151 | blocks, equal-sized blocks, equal splitting. */ | |
152 | enum FindDistribution | |
153 | { GROWING_BLOCKS, CONSTANT_SIZE_BLOCKS, EQUAL_SPLIT }; | |
154 | ||
155 | /** @brief Force all algorithms to be executed sequentially. | |
156 | * This setting cannot be overwritten. */ | |
157 | static volatile bool force_sequential; | |
158 | ||
159 | /** @brief Force all algorithms to be executed in parallel. | |
a3e6b31a | 160 | * This setting can be overridden by __gnu_parallel::sequential_tag |
c2ba9709 JS |
161 | * (compile-time), and force_sequential (run-time). */ |
162 | static volatile bool force_parallel; | |
163 | ||
164 | /** @brief Algorithm to use for sorting. */ | |
165 | static volatile SortAlgorithm sort_algorithm; | |
166 | ||
167 | /** @brief Strategy to use for splitting the input when | |
168 | sorting (MWMS). */ | |
169 | static volatile Splitting sort_splitting; | |
170 | ||
171 | /** @brief Minimal input size for parallel sorting. */ | |
172 | static volatile sequence_index_t sort_minimal_n; | |
dfbed397 | 173 | |
c2ba9709 JS |
174 | /** @brief Oversampling factor for parallel std::sort (MWMS). */ |
175 | static volatile unsigned int sort_mwms_oversampling; | |
dfbed397 | 176 | |
c2ba9709 JS |
177 | /** @brief Such many samples to take to find a good pivot |
178 | (quicksort). */ | |
179 | static volatile unsigned int sort_qs_num_samples_preset; | |
180 | ||
a3e6b31a | 181 | /** @brief Maximal subsequence length to switch to unbalanced |
c2ba9709 JS |
182 | * base case. Applies to std::sort with dynamically |
183 | * load-balanced quicksort. */ | |
184 | static volatile sequence_index_t sort_qsb_base_case_maximal_n; | |
185 | ||
186 | /** @brief Minimal input size for parallel std::partition. */ | |
187 | static volatile sequence_index_t partition_minimal_n; | |
188 | ||
189 | /** @brief Chunk size for parallel std::partition. */ | |
190 | static volatile sequence_index_t partition_chunk_size; | |
191 | ||
192 | /** @brief Chunk size for parallel std::partition, relative to | |
193 | * input size. If >0.0, this value overrides | |
194 | * partition_chunk_size. */ | |
195 | static volatile double partition_chunk_share; | |
196 | ||
197 | /** @brief Minimal input size for parallel std::nth_element. */ | |
198 | static volatile sequence_index_t nth_element_minimal_n; | |
199 | ||
200 | /** @brief Minimal input size for parallel std::partial_sort. */ | |
201 | static volatile sequence_index_t partial_sort_minimal_n; | |
202 | ||
203 | /** @brief Minimal input size for parallel std::adjacent_difference. */ | |
204 | static volatile unsigned int adjacent_difference_minimal_n; | |
205 | ||
206 | /** @brief Minimal input size for parallel std::partial_sum. */ | |
207 | static volatile unsigned int partial_sum_minimal_n; | |
208 | ||
209 | /** @brief Algorithm to use for std::partial_sum. */ | |
210 | static volatile PartialSumAlgorithm partial_sum_algorithm; | |
211 | ||
212 | /** @brief Assume "sum and write result" to be that factor | |
213 | * slower than just "sum". This value is used for | |
214 | * std::partial_sum. */ | |
215 | static volatile float partial_sum_dilatation; | |
216 | ||
217 | /** @brief Minimal input size for parallel std::random_shuffle. */ | |
218 | static volatile unsigned int random_shuffle_minimal_n; | |
219 | ||
220 | /** @brief Minimal input size for parallel std::merge. */ | |
221 | static volatile sequence_index_t merge_minimal_n; | |
222 | ||
223 | /** @brief Splitting strategy for parallel std::merge. */ | |
224 | static volatile Splitting merge_splitting; | |
225 | ||
226 | /** @brief Oversampling factor for parallel std::merge. | |
227 | * Such many samples per thread are collected. */ | |
228 | static volatile unsigned int merge_oversampling; | |
229 | ||
230 | /** @brief Algorithm to use for parallel | |
231 | __gnu_parallel::multiway_merge. */ | |
232 | static volatile MultiwayMergeAlgorithm multiway_merge_algorithm; | |
233 | ||
234 | /** @brief Splitting strategy to use for parallel | |
235 | __gnu_parallel::multiway_merge. */ | |
236 | static volatile Splitting multiway_merge_splitting; | |
237 | ||
238 | //// Oversampling factor for parallel __gnu_parallel::multiway_merge. | |
239 | static volatile unsigned int multiway_merge_oversampling; | |
240 | ||
241 | /// Minimal input size for parallel __gnu_parallel::multiway_merge. | |
242 | static volatile sequence_index_t multiway_merge_minimal_n; | |
243 | ||
244 | /// Oversampling factor for parallel __gnu_parallel::multiway_merge. | |
245 | static volatile int multiway_merge_minimal_k; | |
246 | ||
247 | /** @brief Minimal input size for parallel std::unique_copy. */ | |
248 | static volatile sequence_index_t unique_copy_minimal_n; | |
249 | ||
250 | static volatile sequence_index_t workstealing_chunk_size; | |
251 | ||
252 | /** @brief Minimal input size for parallel std::for_each. */ | |
253 | static volatile sequence_index_t for_each_minimal_n; | |
254 | ||
255 | /** @brief Minimal input size for parallel std::count and | |
256 | std::count_if. */ | |
257 | static volatile sequence_index_t count_minimal_n; | |
258 | ||
259 | /** @brief Minimal input size for parallel std::transform. */ | |
260 | static volatile sequence_index_t transform_minimal_n; | |
261 | ||
262 | /** @brief Minimal input size for parallel std::replace and | |
263 | std::replace_if. */ | |
264 | static volatile sequence_index_t replace_minimal_n; | |
265 | ||
266 | /** @brief Minimal input size for parallel std::generate. */ | |
267 | static volatile sequence_index_t generate_minimal_n; | |
268 | ||
269 | /** @brief Minimal input size for parallel std::fill. */ | |
270 | static volatile sequence_index_t fill_minimal_n; | |
271 | ||
272 | /** @brief Minimal input size for parallel std::min_element. */ | |
273 | static volatile sequence_index_t min_element_minimal_n; | |
274 | ||
275 | /** @brief Minimal input size for parallel std::max_element. */ | |
276 | static volatile sequence_index_t max_element_minimal_n; | |
277 | ||
278 | /** @brief Minimal input size for parallel std::accumulate. */ | |
279 | static volatile sequence_index_t accumulate_minimal_n; | |
280 | ||
281 | /** @brief Distribution strategy for parallel std::find. */ | |
282 | static volatile FindDistribution find_distribution; | |
283 | ||
284 | /** @brief Start with looking for that many elements | |
285 | sequentially, for std::find. */ | |
286 | static volatile sequence_index_t find_sequential_search_size; | |
287 | ||
288 | /** @brief Initial block size for parallel std::find. */ | |
289 | static volatile sequence_index_t find_initial_block_size; | |
290 | ||
291 | /** @brief Maximal block size for parallel std::find. */ | |
292 | static volatile sequence_index_t find_maximum_block_size; | |
293 | ||
294 | /** @brief Block size increase factor for parallel std::find. */ | |
295 | static volatile double find_increasing_factor; | |
296 | ||
297 | //set operations | |
298 | /** @brief Minimal input size for parallel std::set_union. */ | |
299 | static volatile sequence_index_t set_union_minimal_n; | |
300 | ||
301 | /** @brief Minimal input size for parallel | |
302 | std::set_symmetric_difference. */ | |
303 | static volatile sequence_index_t set_symmetric_difference_minimal_n; | |
304 | ||
305 | /** @brief Minimal input size for parallel std::set_difference. */ | |
306 | static volatile sequence_index_t set_difference_minimal_n; | |
307 | ||
308 | /** @brief Minimal input size for parallel std::set_intersection. */ | |
309 | static volatile sequence_index_t set_intersection_minimal_n; | |
310 | ||
311 | //hardware dependent tuning parameters | |
312 | /** @brief Size of the L1 cache in bytes (underestimation). */ | |
313 | static volatile unsigned long long L1_cache_size; | |
314 | ||
315 | /** @brief Size of the L2 cache in bytes (underestimation). */ | |
316 | static volatile unsigned long long L2_cache_size; | |
317 | ||
318 | /** @brief Size of the Translation Lookaside Buffer | |
319 | (underestimation). */ | |
320 | static volatile unsigned int TLB_size; | |
321 | ||
322 | /** @brief Overestimation of cache line size. Used to avoid | |
323 | * false sharing, i. e. elements of different threads are at | |
324 | * least this amount apart. */ | |
325 | static unsigned int cache_line_size; | |
326 | ||
327 | //statistics | |
328 | /** @brief Statistic on the number of stolen ranges in | |
329 | load-balanced quicksort.*/ | |
330 | static volatile sequence_index_t qsb_steals; | |
331 | }; | |
332 | ||
333 | volatile bool Settings::force_parallel = false; | |
334 | volatile bool Settings::force_sequential = false; | |
335 | volatile Settings::SortAlgorithm Settings::sort_algorithm = Settings::MWMS; | |
336 | volatile Settings::Splitting Settings::sort_splitting = Settings::EXACT; | |
337 | volatile sequence_index_t Settings::sort_minimal_n = 1000; | |
338 | ||
339 | volatile unsigned int Settings::sort_mwms_oversampling = 10; | |
340 | volatile unsigned int Settings::sort_qs_num_samples_preset = 100; | |
341 | volatile sequence_index_t Settings::sort_qsb_base_case_maximal_n = 100; | |
342 | volatile sequence_index_t Settings::partition_minimal_n = 1000; | |
343 | volatile sequence_index_t Settings::nth_element_minimal_n = 1000; | |
344 | volatile sequence_index_t Settings::partial_sort_minimal_n = 1000; | |
345 | volatile sequence_index_t Settings::partition_chunk_size = 1000; | |
346 | volatile double Settings::partition_chunk_share = 0.0; | |
347 | volatile unsigned int Settings::adjacent_difference_minimal_n = 1000; | |
5817ff8e PC |
348 | volatile Settings::PartialSumAlgorithm Settings:: |
349 | partial_sum_algorithm = Settings::LINEAR; | |
c2ba9709 JS |
350 | volatile unsigned int Settings::partial_sum_minimal_n = 1000; |
351 | volatile float Settings::partial_sum_dilatation = 1.0f; | |
352 | volatile unsigned int Settings::random_shuffle_minimal_n = 1000; | |
353 | volatile Settings::Splitting Settings::merge_splitting = Settings::EXACT; | |
354 | volatile sequence_index_t Settings::merge_minimal_n = 1000; | |
355 | volatile unsigned int Settings::merge_oversampling = 10; | |
356 | volatile sequence_index_t Settings::multiway_merge_minimal_n = 1000; | |
357 | volatile int Settings::multiway_merge_minimal_k = 2; | |
358 | ||
359 | // unique copy | |
360 | volatile sequence_index_t Settings::unique_copy_minimal_n = 10000; | |
5817ff8e PC |
361 | volatile Settings::MultiwayMergeAlgorithm Settings:: |
362 | multiway_merge_algorithm = Settings::LOSER_TREE; | |
363 | volatile Settings::Splitting Settings::multiway_merge_splitting = | |
364 | Settings::EXACT; | |
c2ba9709 | 365 | volatile unsigned int Settings::multiway_merge_oversampling = 10; |
5817ff8e PC |
366 | volatile Settings::FindDistribution Settings::find_distribution = |
367 | Settings::CONSTANT_SIZE_BLOCKS; | |
c2ba9709 JS |
368 | volatile sequence_index_t Settings::find_sequential_search_size = 256; |
369 | volatile sequence_index_t Settings::find_initial_block_size = 256; | |
370 | volatile sequence_index_t Settings::find_maximum_block_size = 8192; | |
371 | volatile double Settings::find_increasing_factor = 2.0; | |
372 | volatile sequence_index_t Settings::workstealing_chunk_size = 100; | |
373 | volatile sequence_index_t Settings::for_each_minimal_n = 1000; | |
374 | volatile sequence_index_t Settings::count_minimal_n = 1000; | |
375 | volatile sequence_index_t Settings::transform_minimal_n = 1000; | |
376 | volatile sequence_index_t Settings::replace_minimal_n = 1000; | |
377 | volatile sequence_index_t Settings::generate_minimal_n = 1000; | |
378 | volatile sequence_index_t Settings::fill_minimal_n = 1000; | |
379 | volatile sequence_index_t Settings::min_element_minimal_n = 1000; | |
380 | volatile sequence_index_t Settings::max_element_minimal_n = 1000; | |
381 | volatile sequence_index_t Settings::accumulate_minimal_n = 1000; | |
382 | ||
383 | //set operations | |
384 | volatile sequence_index_t Settings::set_union_minimal_n = 1000; | |
385 | volatile sequence_index_t Settings::set_intersection_minimal_n = 1000; | |
386 | volatile sequence_index_t Settings::set_difference_minimal_n = 1000; | |
5817ff8e PC |
387 | volatile sequence_index_t Settings::set_symmetric_difference_minimal_n = |
388 | 1000; | |
c2ba9709 JS |
389 | volatile unsigned long long Settings::L1_cache_size = 16 << 10; |
390 | volatile unsigned long long Settings::L2_cache_size = 256 << 10; | |
391 | volatile unsigned int Settings::TLB_size = 128; | |
392 | unsigned int Settings::cache_line_size = 64; | |
393 | ||
394 | //statistics | |
395 | volatile sequence_index_t Settings::qsb_steals = 0; | |
396 | } // end anonymous namespace | |
397 | ||
398 | } | |
399 | ||
400 | #endif /* _GLIBCXX_SETTINGS_H */ |