FM / parallel

/usr/include/c++/4.4.4/parallel/

/usr/include/c++/4.4.4/parallel

Name	Size	Mode	Actions
algo.h	104807	0644	edit dl rm
algobase.h	11140	0644	edit dl rm
algorithm	1385	0644	edit dl rm
algorithmfwd.h	30167	0644	edit dl rm
balanced_quicksort.h	16157	0644	edit dl rm
base.h	12313	0644	edit dl rm
basic_iterator.h	1606	0644	edit dl rm
checkers.h	4605	0644	edit dl rm
compatibility.h	10301	0644	edit dl rm
compiletime_settings.h	2818	0644	edit dl rm
equally_split.h	3191	0644	edit dl rm
features.h	3580	0644	edit dl rm
find.h	14295	0644	edit dl rm
find_selectors.h	7092	0644	edit dl rm
for_each.h	3666	0644	edit dl rm
for_each_selectors.h	9804	0644	edit dl rm
iterator.h	5270	0644	edit dl rm
list_partition.h	5929	0644	edit dl rm
losertree.h	25725	0644	edit dl rm
merge.h	9549	0644	edit dl rm
multiseq_selection.h	16706	0644	edit dl rm
multiway_merge.h	72745	0644	edit dl rm
multiway_mergesort.h	15478	0644	edit dl rm
numeric	19494	0644	edit dl rm
numericfwd.h	6934	0644	edit dl rm
omp_loop.h	3996	0644	edit dl rm
omp_loop_static.h	4037	0644	edit dl rm
parallel.h	1577	0644	edit dl rm
partial_sum.h	7042	0644	edit dl rm
partition.h	14909	0644	edit dl rm
par_loop.h	4541	0644	edit dl rm
queue.h	4904	0644	edit dl rm
quicksort.h	5914	0644	edit dl rm
random_number.h	3808	0644	edit dl rm
random_shuffle.h	17696	0644	edit dl rm
search.h	5598	0644	edit dl rm
settings.h	10987	0644	edit dl rm
set_operations.h	14472	0644	edit dl rm
sort.h	7421	0644	edit dl rm
tags.h	6103	0644	edit dl rm
types.h	4116	0644	edit dl rm
unique_copy.h	5811	0644	edit dl rm
workstealing.h	10088	0644	edit dl rm

Edit: /usr/include/c++/4.4.4/parallel/multiway_mergesort.h (15478B)

// -*- 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/multiway_mergesort.h
 *  @brief Parallel multiway merge sort.
 *  This file is a GNU parallel extension to the Standard C++ Library.
 */

// Written by Johannes Singler.

#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H
#define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1

#include <vector>

#include <parallel/basic_iterator.h>
#include <bits/stl_algo.h>
#include <parallel/parallel.h>
#include <parallel/multiway_merge.h>

namespace __gnu_parallel
{

/** @brief Subsequence description. */
template<typename _DifferenceTp>
  struct Piece
  {
    typedef _DifferenceTp difference_type;

/** @brief Begin of subsequence. */
    difference_type begin;

/** @brief End of subsequence. */
    difference_type end;
  };

/** @brief Data accessed by all threads.
  *
  *  PMWMS = parallel multiway mergesort */
template<typename RandomAccessIterator>
  struct PMWMSSortingData
  {
    typedef std::iterator_traits<RandomAccessIterator> traits_type;
    typedef typename traits_type::value_type value_type;
    typedef typename traits_type::difference_type difference_type;

/** @brief Number of threads involved. */
    thread_index_t num_threads;

/** @brief Input begin. */
    RandomAccessIterator source;

/** @brief Start indices, per thread. */
    difference_type* starts;

/** @brief Storage in which to sort. */
    value_type** temporary;

/** @brief Samples. */
    value_type* samples;

/** @brief Offsets to add to the found positions. */
    difference_type* offsets;

/** @brief Pieces of data to merge @c [thread][sequence] */
    std::vector<Piece<difference_type> >* pieces;
};

/**
  *  @brief Select samples from a sequence.
  *  @param sd Pointer to algorithm data. Result will be placed in
  *  @c sd->samples.
  *  @param num_samples Number of samples to select.
  */
template<typename RandomAccessIterator, typename _DifferenceTp>
  void 
  determine_samples(PMWMSSortingData<RandomAccessIterator>* sd,
                    _DifferenceTp num_samples)
  {
    typedef std::iterator_traits<RandomAccessIterator> traits_type;
    typedef typename traits_type::value_type value_type;
    typedef _DifferenceTp difference_type;

thread_index_t iam = omp_get_thread_num();

difference_type* es = new difference_type[num_samples + 2];

equally_split(sd->starts[iam + 1] - sd->starts[iam], 
                  num_samples + 1, es);

for (difference_type i = 0; i < num_samples; ++i)
      ::new(&(sd->samples[iam * num_samples + i]))
	  value_type(sd->source[sd->starts[iam] + es[i + 1]]);

delete[] es;
  }

/** @brief Split consistently. */
template<bool exact, typename RandomAccessIterator,
          typename Comparator, typename SortingPlacesIterator>
  struct split_consistently
  {
  };

/** @brief Split by exact splitting. */
template<typename RandomAccessIterator, typename Comparator,
          typename SortingPlacesIterator>
  struct split_consistently
    <true, RandomAccessIterator, Comparator, SortingPlacesIterator>
  {
    void operator()(
      const thread_index_t iam,
      PMWMSSortingData<RandomAccessIterator>* sd,
      Comparator& comp,
      const typename
        std::iterator_traits<RandomAccessIterator>::difference_type
          num_samples)
      const
  {
#   pragma omp barrier

std::vector<std::pair<SortingPlacesIterator, SortingPlacesIterator> >
        seqs(sd->num_threads);
    for (thread_index_t s = 0; s < sd->num_threads; s++)
      seqs[s] = std::make_pair(sd->temporary[s],
                                sd->temporary[s]
                                    + (sd->starts[s + 1] - sd->starts[s]));

std::vector<SortingPlacesIterator> offsets(sd->num_threads);

// if not last thread
    if (iam < sd->num_threads - 1)
      multiseq_partition(seqs.begin(), seqs.end(),
                          sd->starts[iam + 1], offsets.begin(), comp);

for (int seq = 0; seq < sd->num_threads; seq++)
      {
        // for each sequence
        if (iam < (sd->num_threads - 1))
          sd->pieces[iam][seq].end = offsets[seq] - seqs[seq].first;
        else
          // very end of this sequence
          sd->pieces[iam][seq].end =
              sd->starts[seq + 1] - sd->starts[seq];
      }

#   pragma omp barrier

for (thread_index_t seq = 0; seq < sd->num_threads; seq++)
      {
        // For each sequence.
        if (iam > 0)
          sd->pieces[iam][seq].begin = sd->pieces[iam - 1][seq].end;
        else
          // Absolute beginning.
          sd->pieces[iam][seq].begin = 0;
      }
  }   
  };

/** @brief Split by sampling. */ 
template<typename RandomAccessIterator, typename Comparator,
          typename SortingPlacesIterator>
  struct split_consistently<false, RandomAccessIterator, Comparator,
                             SortingPlacesIterator>
  {
    void operator()(
        const thread_index_t iam,
        PMWMSSortingData<RandomAccessIterator>* sd,
        Comparator& comp,
        const typename
          std::iterator_traits<RandomAccessIterator>::difference_type
            num_samples)
        const
    {
      typedef std::iterator_traits<RandomAccessIterator> traits_type;
      typedef typename traits_type::value_type value_type;
      typedef typename traits_type::difference_type difference_type;

determine_samples(sd, num_samples);

#     pragma omp barrier

#     pragma omp single
      __gnu_sequential::sort(sd->samples,
                             sd->samples + (num_samples * sd->num_threads),
                             comp);

#     pragma omp barrier

for (thread_index_t s = 0; s < sd->num_threads; ++s)
        {
          // For each sequence.
          if (num_samples * iam > 0)
            sd->pieces[iam][s].begin =
                std::lower_bound(sd->temporary[s],
                    sd->temporary[s]
                        + (sd->starts[s + 1] - sd->starts[s]),
                    sd->samples[num_samples * iam],
                    comp)
                - sd->temporary[s];
          else
            // Absolute beginning.
            sd->pieces[iam][s].begin = 0;

if ((num_samples * (iam + 1)) < (num_samples * sd->num_threads))
            sd->pieces[iam][s].end =
                std::lower_bound(sd->temporary[s],
                        sd->temporary[s]
                            + (sd->starts[s + 1] - sd->starts[s]),
                        sd->samples[num_samples * (iam + 1)],
                        comp)
                - sd->temporary[s];
          else
            // Absolute end.
            sd->pieces[iam][s].end = sd->starts[s + 1] - sd->starts[s];
        }
    }
  };
  
template<bool stable, typename RandomAccessIterator, typename Comparator>
  struct possibly_stable_sort
  {
  };

template<typename RandomAccessIterator, typename Comparator>
  struct possibly_stable_sort<true, RandomAccessIterator, Comparator>
  {
    void operator()(const RandomAccessIterator& begin,
                     const RandomAccessIterator& end, Comparator& comp) const
    {
      __gnu_sequential::stable_sort(begin, end, comp); 
    }
  };

template<typename RandomAccessIterator, typename Comparator>
  struct possibly_stable_sort<false, RandomAccessIterator, Comparator>
  {
    void operator()(const RandomAccessIterator begin,
                     const RandomAccessIterator end, Comparator& comp) const
    {
      __gnu_sequential::sort(begin, end, comp); 
    }
  };

template<bool stable, typename SeqRandomAccessIterator,
          typename RandomAccessIterator, typename Comparator,
          typename DiffType>
  struct possibly_stable_multiway_merge
  {
  };

template<typename SeqRandomAccessIterator, typename RandomAccessIterator,
          typename Comparator, typename DiffType>
  struct possibly_stable_multiway_merge
    <true, SeqRandomAccessIterator, RandomAccessIterator, Comparator,
    DiffType>
  {
    void operator()(const SeqRandomAccessIterator& seqs_begin,
                      const SeqRandomAccessIterator& seqs_end,
                      const RandomAccessIterator& target,
                      Comparator& comp,
                      DiffType length_am) const
    {
      stable_multiway_merge(seqs_begin, seqs_end, target, length_am, comp,
                       sequential_tag());
    }
  };

template<typename SeqRandomAccessIterator, typename RandomAccessIterator,
          typename Comparator, typename DiffType>
  struct possibly_stable_multiway_merge
    <false, SeqRandomAccessIterator, RandomAccessIterator, Comparator,
    DiffType>
  {
    void operator()(const SeqRandomAccessIterator& seqs_begin,
                      const SeqRandomAccessIterator& seqs_end,
                      const RandomAccessIterator& target,
                      Comparator& comp,
                      DiffType length_am) const
    {
      multiway_merge(seqs_begin, seqs_end, target, length_am, comp,
                       sequential_tag());
    }
  };

/** @brief PMWMS code executed by each thread.
  *  @param sd Pointer to algorithm data.
  *  @param comp Comparator.
  */
template<bool stable, bool exact, typename RandomAccessIterator,
          typename Comparator>
  void 
  parallel_sort_mwms_pu(PMWMSSortingData<RandomAccessIterator>* sd,
                        Comparator& comp)
  {
    typedef std::iterator_traits<RandomAccessIterator> traits_type;
    typedef typename traits_type::value_type value_type;
    typedef typename traits_type::difference_type difference_type;

thread_index_t iam = omp_get_thread_num();

// Length of this thread's chunk, before merging.
    difference_type length_local = sd->starts[iam + 1] - sd->starts[iam];

// Sort in temporary storage, leave space for sentinel.

typedef value_type* SortingPlacesIterator;

sd->temporary[iam] =
        static_cast<value_type*>(
        ::operator new(sizeof(value_type) * (length_local + 1)));

// Copy there.
    std::uninitialized_copy(sd->source + sd->starts[iam],
                            sd->source + sd->starts[iam] + length_local,
                            sd->temporary[iam]);

possibly_stable_sort<stable, SortingPlacesIterator, Comparator>()
        (sd->temporary[iam], sd->temporary[iam] + length_local, comp);

// Invariant: locally sorted subsequence in sd->temporary[iam],
    // sd->temporary[iam] + length_local.

// No barrier here: Synchronization is done by the splitting routine.

difference_type num_samples =
        _Settings::get().sort_mwms_oversampling * sd->num_threads - 1;
    split_consistently
      <exact, RandomAccessIterator, Comparator, SortingPlacesIterator>()
        (iam, sd, comp, num_samples);

// Offset from target begin, length after merging.
    difference_type offset = 0, length_am = 0;
    for (thread_index_t s = 0; s < sd->num_threads; s++)
      {
        length_am += sd->pieces[iam][s].end - sd->pieces[iam][s].begin;
        offset += sd->pieces[iam][s].begin;
      }

typedef std::vector<
      std::pair<SortingPlacesIterator, SortingPlacesIterator> >
        seq_vector_type;
    seq_vector_type seqs(sd->num_threads);

for (int s = 0; s < sd->num_threads; ++s)
      {
        seqs[s] =
          std::make_pair(sd->temporary[s] + sd->pieces[iam][s].begin,
        sd->temporary[s] + sd->pieces[iam][s].end);
      }

possibly_stable_multiway_merge<
        stable,
        typename seq_vector_type::iterator,
        RandomAccessIterator,
        Comparator, difference_type>()
          (seqs.begin(), seqs.end(),
           sd->source + offset, comp,
           length_am);

#   pragma omp barrier

::operator delete(sd->temporary[iam]);
  }

/** @brief PMWMS main call.
  *  @param begin Begin iterator of sequence.
  *  @param end End iterator of sequence.
  *  @param comp Comparator.
  *  @param n Length of sequence.
  *  @param num_threads Number of threads to use.
  */
template<bool stable, bool exact, typename RandomAccessIterator,
           typename Comparator>
  void
  parallel_sort_mwms(RandomAccessIterator begin, RandomAccessIterator end,
                     Comparator comp,
                     thread_index_t num_threads)
  {
    _GLIBCXX_CALL(end - begin)

typedef std::iterator_traits<RandomAccessIterator> traits_type;
    typedef typename traits_type::value_type value_type;
    typedef typename traits_type::difference_type difference_type;

difference_type n = end - begin;

if (n <= 1)
      return;

// at least one element per thread
    if (num_threads > n)
      num_threads = static_cast<thread_index_t>(n);

// shared variables
    PMWMSSortingData<RandomAccessIterator> sd;
    difference_type* starts;

#   pragma omp parallel num_threads(num_threads)
      {
        num_threads = omp_get_num_threads();  //no more threads than requested

#       pragma omp single
          {
            sd.num_threads = num_threads;
            sd.source = begin;

sd.temporary = new value_type*[num_threads];

if (!exact)
              {
                difference_type size =
                    (_Settings::get().sort_mwms_oversampling * num_threads - 1)
                        * num_threads;
                sd.samples = static_cast<value_type*>(
                              ::operator new(size * sizeof(value_type)));
              }
            else
              sd.samples = NULL;

sd.offsets = new difference_type[num_threads - 1];
            sd.pieces = new std::vector<Piece<difference_type> >[num_threads];
            for (int s = 0; s < num_threads; ++s)
              sd.pieces[s].resize(num_threads);
            starts = sd.starts = new difference_type[num_threads + 1];

difference_type chunk_length = n / num_threads;
            difference_type split = n % num_threads;
            difference_type pos = 0;
            for (int i = 0; i < num_threads; ++i)
              {
                starts[i] = pos;
                pos += (i < split) ? (chunk_length + 1) : chunk_length;
              }
            starts[num_threads] = pos;
          } //single

// Now sort in parallel.
        parallel_sort_mwms_pu<stable, exact>(&sd, comp);
      } //parallel

delete[] starts;
    delete[] sd.temporary;

if (!exact)
      ::operator delete(sd.samples);

delete[] sd.offsets;
    delete[] sd.pieces;
  }
} //namespace __gnu_parallel

#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H */

cmd: