// -*- C++ -*-
// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file parallel/settings.h
* @brief Runtime settings and tuning parameters, heuristics to decide
* whether to use parallelized algorithms.
* This file is a GNU parallel extension to the Standard C++ Library.
*
* @section parallelization_decision
* The decision whether to run an algorithm in parallel.
*
* There are several ways the user can switch on and off the parallel
* execution of an algorithm, both at compile- and run-time.
*
* Only sequential execution can be forced at compile-time. This
* reduces code size and protects code parts that have
* non-thread-safe side effects.
*
* Ultimately, forcing parallel execution at compile-time makes
* sense. Often, the sequential algorithm implementation is used as
* a subroutine, so no reduction in code size can be achieved. Also,
* the machine the program is run on might have only one processor
* core, so to avoid overhead, the algorithm is executed
* sequentially.
*
* To force sequential execution of an algorithm ultimately at
* compile-time, the user must add the tag
* __gnu_parallel::sequential_tag() to the end of the parameter list,
* e. g.
*
* \code
* std::sort(v.begin(), v.end(), __gnu_parallel::sequential_tag());
* \endcode
*
* This is compatible with all overloaded algorithm variants. No
* additional code will be instantiated, at all. The same holds for
* most algorithm calls with iterators not providing random access.
*
* If the algorithm call is not forced to be executed sequentially
* at compile-time, the decision is made at run-time.
* The global variable __gnu_parallel::_Settings::algorithm_strategy
* is checked. It is a tristate variable corresponding to:
*
* a. force_sequential, meaning the sequential algorithm is executed.
* b. force_parallel, meaning the parallel algorithm is executed.
* c. heuristic
*
* For heuristic, the parallel algorithm implementation is called
* only if the input size is sufficiently large. For most
* algorithms, the input size is the (combined) length of the input
* sequence(s). The threshold can be set by the user, individually
* for each algorithm. The according variables are called
* __gnu_parallel::_Settings::[algorithm]_minimal_n .
*
* For some of the algorithms, there are even more tuning options,
* e. g. the ability to choose from multiple algorithm variants. See
* below for details.
*/
// Written by Johannes Singler and Felix Putze.
#ifndef _GLIBCXX_PARALLEL_SETTINGS_H
#define _GLIBCXX_PARALLEL_SETTINGS_H 1
#include <parallel/types.h>
/**
* @brief Determine at compile(?)-time if the parallel variant of an
* algorithm should be called.
* @param c A condition that is convertible to bool that is overruled by
* __gnu_parallel::_Settings::algorithm_strategy. Usually a decision
* based on the input size.
*/
#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))
/*
inline bool
parallel_condition(bool c)
{
bool ret = false;
const _Settings& s = _Settings::get();
if (s.algorithm_strategy != force_seqential)
{
if (s.algorithm_strategy == force_parallel)
ret = true;
else
ret = get_max_threads() > 1 && c;
}
return ret;
}
*/
namespace __gnu_parallel
{
/// class _Settings
/// Run-time settings for the parallel mode, including all tunable parameters.
struct _Settings
{
_AlgorithmStrategy algorithm_strategy;
_SortAlgorithm sort_algorithm;
_PartialSumAlgorithm partial_sum_algorithm;
_MultiwayMergeAlgorithm multiway_merge_algorithm;
_FindAlgorithm find_algorithm;
_SplittingAlgorithm sort_splitting;
_SplittingAlgorithm merge_splitting;
_SplittingAlgorithm multiway_merge_splitting;
// Per-algorithm settings.
/// Minimal input size for accumulate.
sequence_index_t accumulate_minimal_n;
/// Minimal input size for adjacent_difference.
unsigned int adjacent_difference_minimal_n;
/// Minimal input size for count and count_if.
sequence_index_t count_minimal_n;
/// Minimal input size for fill.
sequence_index_t fill_minimal_n;
/// Block size increase factor for find.
double find_increasing_factor;
/// Initial block size for find.
sequence_index_t find_initial_block_size;
/// Maximal block size for find.
sequence_index_t find_maximum_block_size;
/// Start with looking for this many elements sequentially, for find.
sequence_index_t find_sequential_search_size;
/// Minimal input size for for_each.
sequence_index_t for_each_minimal_n;
/// Minimal input size for generate.
sequence_index_t generate_minimal_n;
/// Minimal input size for max_element.
sequence_index_t max_element_minimal_n;
/// Minimal input size for merge.
sequence_index_t merge_minimal_n;
/// Oversampling factor for merge.
unsigned int merge_oversampling;
/// Minimal input size for min_element.
sequence_index_t min_element_minimal_n;
/// Minimal input size for multiway_merge.
sequence_index_t multiway_merge_minimal_n;
/// Oversampling factor for multiway_merge.
int multiway_merge_minimal_k;
/// Oversampling factor for multiway_merge.
unsigned int multiway_merge_oversampling;
/// Minimal input size for nth_element.
sequence_index_t nth_element_minimal_n;
/// Chunk size for partition.
sequence_index_t partition_chunk_size;
/// Chunk size for partition, relative to input size. If > 0.0,
/// this value overrides partition_chunk_size.
double partition_chunk_share;
/// Minimal input size for partition.
sequence_index_t partition_minimal_n;
/// Minimal input size for partial_sort.
sequence_index_t partial_sort_minimal_n;
/// Ratio for partial_sum. Assume "sum and write result" to be
/// this factor slower than just "sum".
float partial_sum_dilation;
/// Minimal input size for partial_sum.
unsigned int partial_sum_minimal_n;
/// Minimal input size for random_shuffle.
unsigned int random_shuffle_minimal_n;
/// Minimal input size for replace and replace_if.
sequence_index_t replace_minimal_n;
/// Minimal input size for set_difference.
sequence_index_t set_difference_minimal_n;
/// Minimal input size for set_intersection.
sequence_index_t set_intersection_minimal_n;
/// Minimal input size for set_symmetric_difference.
sequence_index_t set_symmetric_difference_minimal_n;
/// Minimal input size for set_union.
sequence_index_t set_union_minimal_n;
/// Minimal input size for parallel sorting.
sequence_index_t sort_minimal_n;
/// Oversampling factor for parallel std::sort (MWMS).
unsigned int sort_mwms_oversampling;
/// Such many samples to take to find a good pivot (quicksort).
unsigned int sort_qs_num_samples_preset;
/// Maximal subsequence length to switch to unbalanced base case.
/// Applies to std::sort with dynamically load-balanced quicksort.
sequence_index_t sort_qsb_base_case_maximal_n;
/// Minimal input size for parallel std::transform.
sequence_index_t transform_minimal_n;
/// Minimal input size for unique_copy.
sequence_index_t unique_copy_minimal_n;
sequence_index_t workstealing_chunk_size;
// Hardware dependent tuning parameters.
/// Size of the L1 cache in bytes (underestimation).
unsigned long long L1_cache_size;
/// Size of the L2 cache in bytes (underestimation).
unsigned long long L2_cache_size;
/// Size of the Translation Lookaside Buffer (underestimation).
unsigned int TLB_size;
/// Overestimation of cache line size. Used to avoid false
/// sharing, i. e. elements of different threads are at least this
/// amount apart.
unsigned int cache_line_size;
// Statistics.
/// The number of stolen ranges in load-balanced quicksort.
sequence_index_t qsb_steals;
/// Get the global settings.
static const _Settings&
get() throw();
/// Set the global settings.
static void
set(_Settings&) throw();
explicit
_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)
{ }
};
}
#endif /* _GLIBCXX_PARALLEL_SETTINGS_H */