settings.h

Go to the documentation of this file.

/***************************************************************************
 * include/stxxl/bits/parallel/settings.h
 *
 * Settings and tuning parameters, heuristics to decide whether to use
 * parallelized algorithms.
 * Extracted from MCSTL http://algo2.iti.uni-karlsruhe.de/singler/mcstl/
 *
 * Part of the STXXL. See http://stxxl.sourceforge.net
 *
 * Copyright (C) 2007 Johannes Singler <[email protected]>
 * Copyright (C) 2014 Timo Bingmann <[email protected]>
 *
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_PARALLEL_SETTINGS_HEADER
#define STXXL_PARALLEL_SETTINGS_HEADER

#include <stxxl/bits/config.h>
#include <stxxl/bits/namespace.h>
#include <stxxl/bits/parallel/types.h>

#if STXXL_PARALLEL
 #include <omp.h>
#endif

STXXL_BEGIN_NAMESPACE

namespace parallel {

/** The extensible condition on whether the parallel variant of an algorithm sould be called.
 * \param c A condition that is overruled by stxxl::parallel::SETTINGS::force_parallel,
 * i. e. usually a decision based on the input size. */
#define STXXL_PARALLEL_CONDITION(c) (!(SETTINGS::force_sequential) && ((SETTINGS::num_threads > 1 && (c)) || SETTINGS::force_parallel))

/** Pseudo-integer that gets its initial value from \c omp_get_max_threads(). */
class NumberOfThreads
{
public:
 int num_threads;

 NumberOfThreads()
 {
#if STXXL_PARALLEL
 num_threads = omp_get_max_threads();
#else
 num_threads = 1;
#endif // STXXL_PARALLEL
 if (num_threads < 1)
 num_threads = 1;
 }

 operator int ()
 {
 return num_threads;
 }

 int operator = (int nt)
 {
 num_threads = nt;
 return num_threads;
 }
};

/** Run-time settings for the MCSTL.
 * \param must_be_int This template parameter exists only to avoid having an
 * object file belonging to the library. It should always be set to int,
 * to ensure deterministic behavior. */
template <typename must_be_int = int>
struct Settings
{
public:
 /** Different parallel sorting algorithms to choose from: multi-way mergesort, quicksort, load-balanced quicksort. */
 enum SortAlgorithm { MWMS, QS, QS_BALANCED };
 /** Different merging algorithms: bubblesort-alike, loser-tree variants, enum sentinel */
 enum MultiwayMergeAlgorithm { BUBBLE, LOSER_TREE, LOSER_TREE_COMBINED, LOSER_TREE_SENTINEL, MWM_ALGORITHM_LAST };
 /** Different splitting strategies for sorting/merging: by sampling, exact */
 enum Splitting { SAMPLING, EXACT };

 /** Number of thread to be used.
 * Initialized to omp_get_max_threads(), but can be overridden by the user.
 */
 static NumberOfThreads num_threads;

 /** Force all algorithms to be executed sequentially.
 * This setting cannot be overwritten. */
 static volatile bool force_sequential;

 /** Force all algorithms to be executed in parallel.
 * This setting can be overriden by
 * mcstl::sequential_tag (compile-time), and
 * force_sequential (run-time). */
 static volatile bool force_parallel;

 /** Algorithm to use for sorting. */
 static volatile SortAlgorithm sort_algorithm;

 /** Strategy to use for splitting the input when sorting (MWMS). */
 static volatile Splitting sort_splitting;

 /** Minimal input size for parallel sorting. */
 static volatile sequence_index_t sort_minimal_n;
 /** Oversampling factor for parallel std::sort (MWMS). */
 static volatile unsigned int sort_mwms_oversampling;

 /** Oversampling factor for parallel std::merge.
 * Such many samples per thread are collected. */
 static volatile unsigned int merge_oversampling;

 /** Algorithm to use for parallel mcstl::multiway_merge. */
 static volatile MultiwayMergeAlgorithm multiway_merge_algorithm;
 /** Splitting strategy to use for parallel mcstl::multiway_merge. */
 static volatile Splitting multiway_merge_splitting;
 /** Oversampling factor for parallel mcstl::multiway_merge. */
 static volatile unsigned int multiway_merge_oversampling;
 /** Minimal input size for parallel mcstl::multiway_merge. */
 static volatile sequence_index_t multiway_merge_minimal_n;
 /** Oversampling factor for parallel mcstl::multiway_merge. */
 static volatile int multiway_merge_minimal_k;

//hardware dependent tuning parameters
 /** Size of the L1 cache in bytes (underestimation). */
 static volatile unsigned long long L1_cache_size;
 /** Size of the L2 cache in bytes (underestimation). */
 static volatile unsigned long long L2_cache_size;
 /** Size of the Translation Lookaside Buffer (underestimation). */
 static volatile 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. */
 static unsigned int cache_line_size; //overestimation
};

/** Convenience typedef to avoid to have write \c Settings<>. */
typedef Settings<> SETTINGS;

template <typename must_be_int>
volatile bool Settings<must_be_int>::force_parallel = false;

template <typename must_be_int>
volatile bool Settings<must_be_int>::force_sequential = false;

template <typename must_be_int>
volatile typename Settings<must_be_int>::SortAlgorithm Settings<must_be_int>::sort_algorithm = Settings<must_be_int>::MWMS;

template <typename must_be_int>
volatile typename Settings<must_be_int>::Splitting Settings<must_be_int>::sort_splitting = Settings<must_be_int>::EXACT;

template <typename must_be_int>
volatile sequence_index_t Settings<must_be_int>::sort_minimal_n = 1000;

template <typename must_be_int>
volatile unsigned int Settings<must_be_int>::sort_mwms_oversampling = 10;

template <typename must_be_int>
volatile unsigned int Settings<must_be_int>::merge_oversampling = 10;

template <typename must_be_int>
volatile sequence_index_t Settings<must_be_int>::multiway_merge_minimal_n = 1000;

template <typename must_be_int>
volatile int Settings<must_be_int>::multiway_merge_minimal_k = 2;

template <typename must_be_int>
volatile typename Settings<must_be_int>::MultiwayMergeAlgorithm Settings<must_be_int>::multiway_merge_algorithm = Settings<must_be_int>::LOSER_TREE;

template <typename must_be_int>
volatile typename Settings<must_be_int>::Splitting Settings<must_be_int>::multiway_merge_splitting = Settings<must_be_int>::EXACT;

template <typename must_be_int>
volatile unsigned int Settings<must_be_int>::multiway_merge_oversampling = 10;

//hardware dependent tuning parameters
template <typename must_be_int>
volatile unsigned long long Settings<must_be_int>::L1_cache_size = 16 << 10;

template <typename must_be_int>
volatile unsigned long long Settings<must_be_int>::L2_cache_size = 256 << 10;

template <typename must_be_int>
volatile unsigned int Settings<must_be_int>::TLB_size = 128;

template <typename must_be_int>
unsigned int Settings<must_be_int>::cache_line_size = 64; //overestimation

template <typename must_be_int>
NumberOfThreads Settings<must_be_int>::num_threads;

} // namespace parallel

STXXL_END_NAMESPACE

#endif // !STXXL_PARALLEL_SETTINGS_HEADER