]>
Commit | Line | Data |
---|---|---|
c2ba9709 JS |
1 | // -*- C++ -*- |
2 | ||
aa118a03 | 3 | // Copyright (C) 2007-2014 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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
c2ba9709 JS |
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 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
c2ba9709 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
c2ba9709 JS |
24 | |
25 | /** @file parallel/settings.h | |
ee1b5fc5 | 26 | * @brief Runtime settings and tuning parameters, heuristics to decide |
c2ba9709 JS |
27 | * whether to use parallelized algorithms. |
28 | * This file is a GNU parallel extension to the Standard C++ Library. | |
29 | * | |
ee1b5fc5 BK |
30 | * @section parallelization_decision |
31 | * The decision whether to run an algorithm in parallel. | |
c2ba9709 | 32 | * |
1acba85b | 33 | * There are several ways the user can switch on and __off the parallel |
ee1b5fc5 | 34 | * execution of an algorithm, both at compile- and run-time. |
c2ba9709 | 35 | * |
ee1b5fc5 BK |
36 | * Only sequential execution can be forced at compile-time. This |
37 | * reduces code size and protects code parts that have | |
c2ba9709 JS |
38 | * non-thread-safe side effects. |
39 | * | |
ee1b5fc5 BK |
40 | * Ultimately, forcing parallel execution at compile-time makes |
41 | * sense. Often, the sequential algorithm implementation is used as | |
42 | * a subroutine, so no reduction in code size can be achieved. Also, | |
43 | * the machine the program is run on might have only one processor | |
44 | * core, so to avoid overhead, the algorithm is executed | |
45 | * sequentially. | |
c2ba9709 | 46 | * |
ee1b5fc5 BK |
47 | * To force sequential execution of an algorithm ultimately at |
48 | * compile-time, the user must add the tag | |
1acba85b | 49 | * gnu_parallel::sequential_tag() to the end of the parameter list, |
ee1b5fc5 | 50 | * e. g. |
c2ba9709 JS |
51 | * |
52 | * \code | |
1acba85b | 53 | * std::sort(__v.begin(), __v.end(), __gnu_parallel::sequential_tag()); |
c2ba9709 JS |
54 | * \endcode |
55 | * | |
ee1b5fc5 BK |
56 | * This is compatible with all overloaded algorithm variants. No |
57 | * additional code will be instantiated, at all. The same holds for | |
58 | * most algorithm calls with iterators not providing random access. | |
c2ba9709 JS |
59 | * |
60 | * If the algorithm call is not forced to be executed sequentially | |
ee1b5fc5 BK |
61 | * at compile-time, the decision is made at run-time. |
62 | * The global variable __gnu_parallel::_Settings::algorithm_strategy | |
1acba85b | 63 | * is checked. _It is a tristate variable corresponding to: |
c2ba9709 | 64 | * |
ee1b5fc5 | 65 | * a. force_sequential, meaning the sequential algorithm is executed. |
1acba85b JS |
66 | * b. force_parallel, meaning the parallel algorithm is executed. |
67 | * c. heuristic | |
ee1b5fc5 BK |
68 | * |
69 | * For heuristic, the parallel algorithm implementation is called | |
70 | * only if the input size is sufficiently large. For most | |
71 | * algorithms, the input size is the (combined) length of the input | |
1acba85b | 72 | * sequence(__s). The threshold can be set by the user, individually |
ee1b5fc5 | 73 | * for each algorithm. The according variables are called |
1acba85b | 74 | * gnu_parallel::_Settings::[algorithm]_minimal_n . |
c2ba9709 JS |
75 | * |
76 | * For some of the algorithms, there are even more tuning options, | |
ee1b5fc5 BK |
77 | * e. g. the ability to choose from multiple algorithm variants. See |
78 | * below for details. | |
c2ba9709 JS |
79 | */ |
80 | ||
81 | // Written by Johannes Singler and Felix Putze. | |
82 | ||
83 | #ifndef _GLIBCXX_PARALLEL_SETTINGS_H | |
84 | #define _GLIBCXX_PARALLEL_SETTINGS_H 1 | |
85 | ||
c2ba9709 JS |
86 | #include <parallel/types.h> |
87 | ||
88 | /** | |
ee1b5fc5 BK |
89 | * @brief Determine at compile(?)-time if the parallel variant of an |
90 | * algorithm should be called. | |
1acba85b | 91 | * @param __c A condition that is convertible to bool that is overruled by |
ee1b5fc5 BK |
92 | * __gnu_parallel::_Settings::algorithm_strategy. Usually a decision |
93 | * based on the input size. | |
c2ba9709 | 94 | */ |
15ac3c72 JS |
95 | #define _GLIBCXX_PARALLEL_CONDITION(__c) \ |
96 | (__gnu_parallel::_Settings::get().algorithm_strategy \ | |
97 | != __gnu_parallel::force_sequential \ | |
98 | && ((__gnu_parallel::__get_max_threads() > 1 && (__c)) \ | |
99 | || __gnu_parallel::_Settings::get().algorithm_strategy \ | |
100 | == __gnu_parallel::force_parallel)) | |
c2ba9709 | 101 | |
ee1b5fc5 BK |
102 | /* |
103 | inline bool | |
1acba85b | 104 | parallel_condition(bool __c) |
c2ba9709 | 105 | { |
ee1b5fc5 | 106 | bool ret = false; |
1acba85b JS |
107 | const _Settings& __s = _Settings::get(); |
108 | if (__s.algorithm_strategy != force_seqential) | |
ee1b5fc5 | 109 | { |
1acba85b | 110 | if (__s.algorithm_strategy == force_parallel) |
15ac3c72 | 111 | ret = true; |
ee1b5fc5 | 112 | else |
15ac3c72 | 113 | ret = __get_max_threads() > 1 && __c; |
ee1b5fc5 BK |
114 | } |
115 | return ret; | |
116 | } | |
117 | */ | |
118 | ||
119 | namespace __gnu_parallel | |
c2ba9709 | 120 | { |
15ac3c72 JS |
121 | /// class _Settings |
122 | /// Run-time settings for the parallel mode including all tunable parameters. | |
ee1b5fc5 | 123 | struct _Settings |
c2ba9709 | 124 | { |
15ac3c72 | 125 | _AlgorithmStrategy algorithm_strategy; |
ee1b5fc5 | 126 | |
15ac3c72 JS |
127 | _SortAlgorithm sort_algorithm; |
128 | _PartialSumAlgorithm partial_sum_algorithm; | |
129 | _MultiwayMergeAlgorithm multiway_merge_algorithm; | |
130 | _FindAlgorithm find_algorithm; | |
c2ba9709 | 131 | |
15ac3c72 JS |
132 | _SplittingAlgorithm sort_splitting; |
133 | _SplittingAlgorithm merge_splitting; | |
134 | _SplittingAlgorithm multiway_merge_splitting; | |
c2ba9709 | 135 | |
ee1b5fc5 | 136 | // Per-algorithm settings. |
c2ba9709 | 137 | |
ee1b5fc5 | 138 | /// Minimal input size for accumulate. |
15ac3c72 | 139 | _SequenceIndex accumulate_minimal_n; |
c2ba9709 | 140 | |
ee1b5fc5 | 141 | /// Minimal input size for adjacent_difference. |
15ac3c72 | 142 | unsigned int adjacent_difference_minimal_n; |
c2ba9709 | 143 | |
ee1b5fc5 | 144 | /// Minimal input size for count and count_if. |
15ac3c72 | 145 | _SequenceIndex count_minimal_n; |
c2ba9709 | 146 | |
ee1b5fc5 | 147 | /// Minimal input size for fill. |
15ac3c72 | 148 | _SequenceIndex fill_minimal_n; |
c2ba9709 | 149 | |
ee1b5fc5 | 150 | /// Block size increase factor for find. |
15ac3c72 | 151 | double find_increasing_factor; |
dfbed397 | 152 | |
ee1b5fc5 | 153 | /// Initial block size for find. |
15ac3c72 | 154 | _SequenceIndex find_initial_block_size; |
dfbed397 | 155 | |
ee1b5fc5 | 156 | /// Maximal block size for find. |
15ac3c72 | 157 | _SequenceIndex find_maximum_block_size; |
c2ba9709 | 158 | |
ee1b5fc5 | 159 | /// Start with looking for this many elements sequentially, for find. |
15ac3c72 | 160 | _SequenceIndex find_sequential_search_size; |
c2ba9709 | 161 | |
ee1b5fc5 | 162 | /// Minimal input size for for_each. |
15ac3c72 | 163 | _SequenceIndex for_each_minimal_n; |
c2ba9709 | 164 | |
ee1b5fc5 | 165 | /// Minimal input size for generate. |
15ac3c72 | 166 | _SequenceIndex generate_minimal_n; |
c2ba9709 | 167 | |
ee1b5fc5 | 168 | /// Minimal input size for max_element. |
15ac3c72 | 169 | _SequenceIndex max_element_minimal_n; |
c2ba9709 | 170 | |
ee1b5fc5 | 171 | /// Minimal input size for merge. |
15ac3c72 | 172 | _SequenceIndex merge_minimal_n; |
c2ba9709 | 173 | |
ee1b5fc5 | 174 | /// Oversampling factor for merge. |
15ac3c72 | 175 | unsigned int merge_oversampling; |
c2ba9709 | 176 | |
ee1b5fc5 | 177 | /// Minimal input size for min_element. |
15ac3c72 | 178 | _SequenceIndex min_element_minimal_n; |
c2ba9709 | 179 | |
ee1b5fc5 | 180 | /// Minimal input size for multiway_merge. |
15ac3c72 | 181 | _SequenceIndex multiway_merge_minimal_n; |
c2ba9709 | 182 | |
ee1b5fc5 | 183 | /// Oversampling factor for multiway_merge. |
15ac3c72 | 184 | int multiway_merge_minimal_k; |
c2ba9709 | 185 | |
ee1b5fc5 | 186 | /// Oversampling factor for multiway_merge. |
15ac3c72 | 187 | unsigned int multiway_merge_oversampling; |
c2ba9709 | 188 | |
ee1b5fc5 | 189 | /// Minimal input size for nth_element. |
15ac3c72 | 190 | _SequenceIndex nth_element_minimal_n; |
c2ba9709 | 191 | |
ee1b5fc5 | 192 | /// Chunk size for partition. |
15ac3c72 | 193 | _SequenceIndex partition_chunk_size; |
c2ba9709 | 194 | |
ee1b5fc5 BK |
195 | /// Chunk size for partition, relative to input size. If > 0.0, |
196 | /// this value overrides partition_chunk_size. | |
15ac3c72 | 197 | double partition_chunk_share; |
c2ba9709 | 198 | |
ee1b5fc5 | 199 | /// Minimal input size for partition. |
15ac3c72 | 200 | _SequenceIndex partition_minimal_n; |
c2ba9709 | 201 | |
ee1b5fc5 | 202 | /// Minimal input size for partial_sort. |
15ac3c72 | 203 | _SequenceIndex partial_sort_minimal_n; |
c2ba9709 | 204 | |
721641c4 | 205 | /// Ratio for partial_sum. Assume "sum and write result" to be |
ee1b5fc5 | 206 | /// this factor slower than just "sum". |
15ac3c72 | 207 | float partial_sum_dilation; |
c2ba9709 | 208 | |
ee1b5fc5 | 209 | /// Minimal input size for partial_sum. |
15ac3c72 | 210 | unsigned int partial_sum_minimal_n; |
c2ba9709 | 211 | |
ee1b5fc5 | 212 | /// Minimal input size for random_shuffle. |
15ac3c72 | 213 | unsigned int random_shuffle_minimal_n; |
c2ba9709 | 214 | |
ee1b5fc5 | 215 | /// Minimal input size for replace and replace_if. |
15ac3c72 | 216 | _SequenceIndex replace_minimal_n; |
c2ba9709 | 217 | |
ee1b5fc5 | 218 | /// Minimal input size for set_difference. |
15ac3c72 | 219 | _SequenceIndex set_difference_minimal_n; |
c2ba9709 | 220 | |
ee1b5fc5 | 221 | /// Minimal input size for set_intersection. |
15ac3c72 | 222 | _SequenceIndex set_intersection_minimal_n; |
c2ba9709 | 223 | |
ee1b5fc5 | 224 | /// Minimal input size for set_symmetric_difference. |
15ac3c72 | 225 | _SequenceIndex set_symmetric_difference_minimal_n; |
c2ba9709 | 226 | |
ee1b5fc5 | 227 | /// Minimal input size for set_union. |
15ac3c72 | 228 | _SequenceIndex set_union_minimal_n; |
c2ba9709 | 229 | |
ee1b5fc5 | 230 | /// Minimal input size for parallel sorting. |
15ac3c72 | 231 | _SequenceIndex sort_minimal_n; |
c2ba9709 | 232 | |
ee1b5fc5 | 233 | /// Oversampling factor for parallel std::sort (MWMS). |
15ac3c72 | 234 | unsigned int sort_mwms_oversampling; |
c2ba9709 | 235 | |
ee1b5fc5 | 236 | /// Such many samples to take to find a good pivot (quicksort). |
15ac3c72 | 237 | unsigned int sort_qs_num_samples_preset; |
c2ba9709 | 238 | |
1acba85b | 239 | /// Maximal subsequence __length to switch to unbalanced __base case. |
ee1b5fc5 | 240 | /// Applies to std::sort with dynamically load-balanced quicksort. |
15ac3c72 | 241 | _SequenceIndex sort_qsb_base_case_maximal_n; |
c2ba9709 | 242 | |
ee1b5fc5 | 243 | /// Minimal input size for parallel std::transform. |
15ac3c72 | 244 | _SequenceIndex transform_minimal_n; |
c2ba9709 | 245 | |
ee1b5fc5 | 246 | /// Minimal input size for unique_copy. |
15ac3c72 | 247 | _SequenceIndex unique_copy_minimal_n; |
c2ba9709 | 248 | |
15ac3c72 | 249 | _SequenceIndex workstealing_chunk_size; |
c2ba9709 | 250 | |
ee1b5fc5 | 251 | // Hardware dependent tuning parameters. |
c2ba9709 | 252 | |
1acba85b | 253 | /// size of the L1 cache in bytes (underestimation). |
15ac3c72 | 254 | unsigned long long L1_cache_size; |
c2ba9709 | 255 | |
1acba85b | 256 | /// size of the L2 cache in bytes (underestimation). |
15ac3c72 | 257 | unsigned long long L2_cache_size; |
c2ba9709 | 258 | |
1acba85b | 259 | /// size of the Translation Lookaside Buffer (underestimation). |
15ac3c72 | 260 | unsigned int TLB_size; |
c2ba9709 | 261 | |
ee1b5fc5 | 262 | /// Overestimation of cache line size. Used to avoid false |
1acba85b | 263 | /// sharing, i.e. elements of different threads are at least this |
ee1b5fc5 | 264 | /// amount apart. |
15ac3c72 | 265 | unsigned int cache_line_size; |
c2ba9709 | 266 | |
ee1b5fc5 | 267 | // Statistics. |
c2ba9709 | 268 | |
ee1b5fc5 | 269 | /// The number of stolen ranges in load-balanced quicksort. |
15ac3c72 | 270 | _SequenceIndex qsb_steals; |
c2ba9709 | 271 | |
70202e48 JS |
272 | /// Minimal input size for search and search_n. |
273 | _SequenceIndex search_minimal_n; | |
274 | ||
22a2af95 JS |
275 | /// Block size scale-down factor with respect to current position. |
276 | float find_scale_factor; | |
277 | ||
ee1b5fc5 | 278 | /// Get the global settings. |
b91cc3b9 | 279 | _GLIBCXX_CONST static const _Settings& |
ee1b5fc5 | 280 | get() throw(); |
c2ba9709 | 281 | |
ee1b5fc5 BK |
282 | /// Set the global settings. |
283 | static void | |
284 | set(_Settings&) throw(); | |
c2ba9709 | 285 | |
ee1b5fc5 | 286 | explicit |
15ac3c72 JS |
287 | _Settings() : |
288 | algorithm_strategy(heuristic), | |
289 | sort_algorithm(MWMS), | |
290 | partial_sum_algorithm(LINEAR), | |
291 | multiway_merge_algorithm(LOSER_TREE), | |
292 | find_algorithm(CONSTANT_SIZE_BLOCKS), | |
293 | sort_splitting(EXACT), | |
294 | merge_splitting(EXACT), | |
295 | multiway_merge_splitting(EXACT), | |
296 | accumulate_minimal_n(1000), | |
297 | adjacent_difference_minimal_n(1000), | |
298 | count_minimal_n(1000), | |
299 | fill_minimal_n(1000), | |
300 | find_increasing_factor(2.0), | |
301 | find_initial_block_size(256), | |
302 | find_maximum_block_size(8192), | |
303 | find_sequential_search_size(256), | |
304 | for_each_minimal_n(1000), | |
305 | generate_minimal_n(1000), | |
306 | max_element_minimal_n(1000), | |
307 | merge_minimal_n(1000), | |
308 | merge_oversampling(10), | |
309 | min_element_minimal_n(1000), | |
310 | multiway_merge_minimal_n(1000), | |
311 | multiway_merge_minimal_k(2), multiway_merge_oversampling(10), | |
312 | nth_element_minimal_n(1000), | |
313 | partition_chunk_size(1000), | |
314 | partition_chunk_share(0.0), | |
315 | partition_minimal_n(1000), | |
316 | partial_sort_minimal_n(1000), | |
317 | partial_sum_dilation(1.0f), | |
318 | partial_sum_minimal_n(1000), | |
319 | random_shuffle_minimal_n(1000), | |
320 | replace_minimal_n(1000), | |
321 | set_difference_minimal_n(1000), | |
322 | set_intersection_minimal_n(1000), | |
323 | set_symmetric_difference_minimal_n(1000), | |
324 | set_union_minimal_n(1000), | |
325 | sort_minimal_n(1000), | |
326 | sort_mwms_oversampling(10), | |
327 | sort_qs_num_samples_preset(100), | |
328 | sort_qsb_base_case_maximal_n(100), | |
329 | transform_minimal_n(1000), | |
330 | unique_copy_minimal_n(10000), | |
331 | workstealing_chunk_size(100), | |
332 | L1_cache_size(16 << 10), | |
333 | L2_cache_size(256 << 10), | |
334 | TLB_size(128), | |
335 | cache_line_size(64), | |
70202e48 | 336 | qsb_steals(0), |
22a2af95 JS |
337 | search_minimal_n(1000), |
338 | find_scale_factor(0.01f) | |
ee1b5fc5 | 339 | { } |
c2ba9709 | 340 | }; |
c2ba9709 JS |
341 | } |
342 | ||
cbcd1e45 | 343 | #endif /* _GLIBCXX_PARALLEL_SETTINGS_H */ |