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