1// -*- C++ -*- 2 3// Copyright (C) 2007-2014 Free Software Foundation, Inc. 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 3, 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// 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. 19 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/>. 24 25/** @file parallel/settings.h 26 * @brief Runtime settings and tuning parameters, heuristics to decide 27 * whether to use parallelized algorithms. 28 * This file is a GNU parallel extension to the Standard C++ Library. 29 * 30 * @section parallelization_decision 31 * The decision whether to run an algorithm in parallel. 32 * 33 * There are several ways the user can switch on and __off the parallel 34 * execution of an algorithm, both at compile- and run-time. 35 * 36 * Only sequential execution can be forced at compile-time. This 37 * reduces code size and protects code parts that have 38 * non-thread-safe side effects. 39 * 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. 46 * 47 * To force sequential execution of an algorithm ultimately at 48 * compile-time, the user must add the tag 49* gnu_parallel::sequential_tag() to the end of the parameter list, 50 * e. g. 51 * 52 * \code 53 * std::sort(__v.begin(), __v.end(), __gnu_parallel::sequential_tag()); 54 * \endcode 55 * 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. 59 * 60 * If the algorithm call is not forced to be executed sequentially 61 * at compile-time, the decision is made at run-time. 62 * The global variable __gnu_parallel::_Settings::algorithm_strategy 63 * is checked. _It is a tristate variable corresponding to: 64 * 65 * a. force_sequential, meaning the sequential algorithm is executed. 66* b. force_parallel, meaning the parallel algorithm is executed. 67* c. heuristic 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 72* sequence(__s). The threshold can be set by the user, individually 73 * for each algorithm. The according variables are called 74* gnu_parallel::_Settings::[algorithm]_minimal_n . 75 * 76 * For some of the algorithms, there are even more tuning options, 77 * e. g. the ability to choose from multiple algorithm variants. See 78 * below for details. 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 86#include <parallel/types.h> 87 88/** 89 * @brief Determine at compile(?)-time if the parallel variant of an 90 * algorithm should be called. 91 * @param __c A condition that is convertible to bool that is overruled by 92 * __gnu_parallel::_Settings::algorithm_strategy. Usually a decision 93 * based on the input size. 94 */ 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)) 101 102/* 103inline bool 104parallel_condition(bool __c) 105{ 106 bool ret = false; 107 const _Settings& __s = _Settings::get(); 108 if (__s.algorithm_strategy != force_seqential) 109 { 110 if (__s.algorithm_strategy == force_parallel) 111 ret = true; 112 else 113 ret = __get_max_threads() > 1 && __c; 114 } 115 return ret; 116} 117*/ 118 119namespace __gnu_parallel 120{ 121 /// class _Settings 122 /// Run-time settings for the parallel mode including all tunable parameters. 123 struct _Settings 124 { 125 _AlgorithmStrategy algorithm_strategy; 126 127 _SortAlgorithm sort_algorithm; 128 _PartialSumAlgorithm partial_sum_algorithm; 129 _MultiwayMergeAlgorithm multiway_merge_algorithm; 130 _FindAlgorithm find_algorithm; 131 132 _SplittingAlgorithm sort_splitting; 133 _SplittingAlgorithm merge_splitting; 134 _SplittingAlgorithm multiway_merge_splitting; 135 136 // Per-algorithm settings. 137 138 /// Minimal input size for accumulate. 139 _SequenceIndex accumulate_minimal_n; 140 141 /// Minimal input size for adjacent_difference. 142 unsigned int adjacent_difference_minimal_n; 143 144 /// Minimal input size for count and count_if. 145 _SequenceIndex count_minimal_n; 146 147 /// Minimal input size for fill. 148 _SequenceIndex fill_minimal_n; 149 150 /// Block size increase factor for find. 151 double find_increasing_factor; 152 153 /// Initial block size for find. 154 _SequenceIndex find_initial_block_size; 155 156 /// Maximal block size for find. 157 _SequenceIndex find_maximum_block_size; 158 159 /// Start with looking for this many elements sequentially, for find. 160 _SequenceIndex find_sequential_search_size; 161 162 /// Minimal input size for for_each. 163 _SequenceIndex for_each_minimal_n; 164 165 /// Minimal input size for generate. 166 _SequenceIndex generate_minimal_n; 167 168 /// Minimal input size for max_element. 169 _SequenceIndex max_element_minimal_n; 170 171 /// Minimal input size for merge. 172 _SequenceIndex merge_minimal_n; 173 174 /// Oversampling factor for merge. 175 unsigned int merge_oversampling; 176 177 /// Minimal input size for min_element. 178 _SequenceIndex min_element_minimal_n; 179 180 /// Minimal input size for multiway_merge. 181 _SequenceIndex multiway_merge_minimal_n; 182 183 /// Oversampling factor for multiway_merge. 184 int multiway_merge_minimal_k; 185 186 /// Oversampling factor for multiway_merge. 187 unsigned int multiway_merge_oversampling; 188 189 /// Minimal input size for nth_element. 190 _SequenceIndex nth_element_minimal_n; 191 192 /// Chunk size for partition. 193 _SequenceIndex partition_chunk_size; 194 195 /// Chunk size for partition, relative to input size. If > 0.0, 196 /// this value overrides partition_chunk_size. 197 double partition_chunk_share; 198 199 /// Minimal input size for partition. 200 _SequenceIndex partition_minimal_n; 201 202 /// Minimal input size for partial_sort. 203 _SequenceIndex partial_sort_minimal_n; 204 205 /// Ratio for partial_sum. Assume "sum and write result" to be 206 /// this factor slower than just "sum". 207 float partial_sum_dilation; 208 209 /// Minimal input size for partial_sum. 210 unsigned int partial_sum_minimal_n; 211 212 /// Minimal input size for random_shuffle. 213 unsigned int random_shuffle_minimal_n; 214 215 /// Minimal input size for replace and replace_if. 216 _SequenceIndex replace_minimal_n; 217 218 /// Minimal input size for set_difference. 219 _SequenceIndex set_difference_minimal_n; 220 221 /// Minimal input size for set_intersection. 222 _SequenceIndex set_intersection_minimal_n; 223 224 /// Minimal input size for set_symmetric_difference. 225 _SequenceIndex set_symmetric_difference_minimal_n; 226 227 /// Minimal input size for set_union. 228 _SequenceIndex set_union_minimal_n; 229 230 /// Minimal input size for parallel sorting. 231 _SequenceIndex sort_minimal_n; 232 233 /// Oversampling factor for parallel std::sort (MWMS). 234 unsigned int sort_mwms_oversampling; 235 236 /// Such many samples to take to find a good pivot (quicksort). 237 unsigned int sort_qs_num_samples_preset; 238 239 /// Maximal subsequence __length to switch to unbalanced __base case. 240 /// Applies to std::sort with dynamically load-balanced quicksort. 241 _SequenceIndex sort_qsb_base_case_maximal_n; 242 243 /// Minimal input size for parallel std::transform. 244 _SequenceIndex transform_minimal_n; 245 246 /// Minimal input size for unique_copy. 247 _SequenceIndex unique_copy_minimal_n; 248 249 _SequenceIndex workstealing_chunk_size; 250 251 // Hardware dependent tuning parameters. 252 253 /// size of the L1 cache in bytes (underestimation). 254 unsigned long long L1_cache_size; 255 256 /// size of the L2 cache in bytes (underestimation). 257 unsigned long long L2_cache_size; 258 259 /// size of the Translation Lookaside Buffer (underestimation). 260 unsigned int TLB_size; 261 262 /// Overestimation of cache line size. Used to avoid false 263 /// sharing, i.e. elements of different threads are at least this 264 /// amount apart. 265 unsigned int cache_line_size; 266 267 // Statistics. 268 269 /// The number of stolen ranges in load-balanced quicksort. 270 _SequenceIndex qsb_steals; 271 272 /// Minimal input size for search and search_n. 273 _SequenceIndex search_minimal_n; 274 275 /// Block size scale-down factor with respect to current position. 276 float find_scale_factor; 277 278 /// Get the global settings. 279 _GLIBCXX_CONST static const _Settings& 280 get() throw(); 281 282 /// Set the global settings. 283 static void 284 set(_Settings&) throw(); 285 286 explicit 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), 336 qsb_steals(0), 337 search_minimal_n(1000), 338 find_scale_factor(0.01f) 339 { } 340 }; 341} 342 343#endif /* _GLIBCXX_PARALLEL_SETTINGS_H */ 344