Subversion Repositories altor32

// -*- C++ -*-

// Copyright (C) 2007, 2008, 2009, 2010 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.

    _SequenceIndex              accumulate_minimal_n;

    /// Minimal input size for adjacent_difference.

    unsigned int                adjacent_difference_minimal_n;

    /// Minimal input size for count and count_if.

    _SequenceIndex              count_minimal_n;

    /// Minimal input size for fill.

    _SequenceIndex              fill_minimal_n;

    /// Block size increase factor for find.

    double                      find_increasing_factor;

    /// Initial block size for find.

    _SequenceIndex              find_initial_block_size;

    /// Maximal block size for find.

    _SequenceIndex              find_maximum_block_size;

    /// Start with looking for this many elements sequentially, for find.

    _SequenceIndex              find_sequential_search_size;

    /// Minimal input size for for_each.

    _SequenceIndex              for_each_minimal_n;

    /// Minimal input size for generate.

    _SequenceIndex              generate_minimal_n;

    /// Minimal input size for max_element.

    _SequenceIndex              max_element_minimal_n;

    /// Minimal input size for merge.

    _SequenceIndex              merge_minimal_n;

    /// Oversampling factor for merge.

    unsigned int                merge_oversampling;

    /// Minimal input size for min_element.

    _SequenceIndex              min_element_minimal_n;

    /// Minimal input size for multiway_merge.

    _SequenceIndex              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.

    _SequenceIndex              nth_element_minimal_n;

    /// Chunk size for partition.

    _SequenceIndex              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.

    _SequenceIndex              partition_minimal_n;

    /// Minimal input size for partial_sort.

    _SequenceIndex              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.

    _SequenceIndex              replace_minimal_n;

    /// Minimal input size for set_difference.

    _SequenceIndex              set_difference_minimal_n;

    /// Minimal input size for set_intersection.

    _SequenceIndex              set_intersection_minimal_n;

    /// Minimal input size for set_symmetric_difference.

    _SequenceIndex              set_symmetric_difference_minimal_n;

    /// Minimal input size for set_union.

    _SequenceIndex              set_union_minimal_n;

    /// Minimal input size for parallel sorting.

    _SequenceIndex              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.

    _SequenceIndex              sort_qsb_base_case_maximal_n;

    /// Minimal input size for parallel std::transform.

    _SequenceIndex              transform_minimal_n;

    /// Minimal input size for unique_copy. 

    _SequenceIndex              unique_copy_minimal_n;

    _SequenceIndex              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.

    _SequenceIndex              qsb_steals;

    /// Minimal input size for search and search_n.

    _SequenceIndex              search_minimal_n;

    /// Block size scale-down factor with respect to current position.

    float                       find_scale_factor;

    /// Get the global settings.

    _GLIBCXX_CONST 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),

            search_minimal_n(1000),

            find_scale_factor(0.01f)

    { }

  };

}

#endif /* _GLIBCXX_PARALLEL_SETTINGS_H */