libstdc++
partial_sum.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/partial_sum.h
00026  *  @brief Parallel implementation of std::partial_sum(), i.e. prefix
00027 *  sums.
00028  *  This file is a GNU parallel extension to the Standard C++ Library.
00029  */
00030 
00031 // Written by Johannes Singler.
00032 
00033 #ifndef _GLIBCXX_PARALLEL_PARTIAL_SUM_H
00034 #define _GLIBCXX_PARALLEL_PARTIAL_SUM_H 1
00035 
00036 #include <omp.h>
00037 #include <new>
00038 #include <bits/stl_algobase.h>
00039 #include <parallel/parallel.h>
00040 #include <parallel/numericfwd.h>
00041 
00042 namespace __gnu_parallel
00043 {
00044   // Problem: there is no 0-element given.
00045 
00046   /** @brief Base case prefix sum routine.
00047    *  @param __begin Begin iterator of input sequence.
00048    *  @param __end End iterator of input sequence.
00049    *  @param __result Begin iterator of output sequence.
00050    *  @param __bin_op Associative binary function.
00051    *  @param __value Start value. Must be passed since the neutral
00052    *  element is unknown in general.
00053    *  @return End iterator of output sequence. */
00054   template<typename _IIter,
00055        typename _OutputIterator,
00056        typename _BinaryOperation>
00057     _OutputIterator
00058     __parallel_partial_sum_basecase(_IIter __begin, _IIter __end,
00059                     _OutputIterator __result,
00060                     _BinaryOperation __bin_op,
00061       typename std::iterator_traits <_IIter>::value_type __value)
00062     {
00063       if (__begin == __end)
00064     return __result;
00065 
00066       while (__begin != __end)
00067     {
00068       __value = __bin_op(__value, *__begin);
00069       *__result = __value;
00070       ++__result;
00071       ++__begin;
00072     }
00073       return __result;
00074     }
00075 
00076   /** @brief Parallel partial sum implementation, two-phase approach,
00077       no recursion.
00078       *  @param __begin Begin iterator of input sequence.
00079       *  @param __end End iterator of input sequence.
00080       *  @param __result Begin iterator of output sequence.
00081       *  @param __bin_op Associative binary function.
00082       *  @param __n Length of sequence.
00083       *  @return End iterator of output sequence.
00084       */
00085   template<typename _IIter,
00086        typename _OutputIterator,
00087        typename _BinaryOperation>
00088     _OutputIterator
00089     __parallel_partial_sum_linear(_IIter __begin, _IIter __end,
00090                   _OutputIterator __result,
00091                   _BinaryOperation __bin_op,
00092       typename std::iterator_traits<_IIter>::difference_type __n)
00093     {
00094       typedef std::iterator_traits<_IIter> _TraitsType;
00095       typedef typename _TraitsType::value_type _ValueType;
00096       typedef typename _TraitsType::difference_type _DifferenceType;
00097 
00098       if (__begin == __end)
00099     return __result;
00100 
00101       _ThreadIndex __num_threads =
00102         std::min<_DifferenceType>(__get_max_threads(), __n - 1);
00103 
00104       if (__num_threads < 2)
00105     {
00106       *__result = *__begin;
00107       return __parallel_partial_sum_basecase(__begin + 1, __end,
00108                          __result + 1, __bin_op,
00109                          *__begin);
00110     }
00111 
00112       _DifferenceType* __borders;
00113       _ValueType* __sums;
00114 
00115       const _Settings& __s = _Settings::get();
00116 
00117 #     pragma omp parallel num_threads(__num_threads)
00118       {
00119 #       pragma omp single
00120     {
00121       __num_threads = omp_get_num_threads();
00122         
00123       __borders = new _DifferenceType[__num_threads + 2];
00124 
00125       if (__s.partial_sum_dilation == 1.0f)
00126         __equally_split(__n, __num_threads + 1, __borders);
00127       else
00128         {
00129           _DifferenceType __first_part_length =
00130           std::max<_DifferenceType>(1,
00131             __n / (1.0f + __s.partial_sum_dilation * __num_threads));
00132           _DifferenceType __chunk_length =
00133           (__n - __first_part_length) / __num_threads;
00134           _DifferenceType __borderstart =
00135           __n - __num_threads * __chunk_length;
00136           __borders[0] = 0;
00137           for (_ThreadIndex __i = 1; __i < (__num_threads + 1); ++__i)
00138         {
00139           __borders[__i] = __borderstart;
00140           __borderstart += __chunk_length;
00141         }
00142           __borders[__num_threads + 1] = __n;
00143         }
00144 
00145       __sums = static_cast<_ValueType*>(::operator new(sizeof(_ValueType)
00146                                                            * __num_threads));
00147       _OutputIterator __target_end;
00148     } //single
00149 
00150         _ThreadIndex __iam = omp_get_thread_num();
00151         if (__iam == 0)
00152           {
00153             *__result = *__begin;
00154             __parallel_partial_sum_basecase(__begin + 1,
00155                         __begin + __borders[1],
00156                         __result + 1,
00157                         __bin_op, *__begin);
00158             ::new(&(__sums[__iam])) _ValueType(*(__result + __borders[1] - 1));
00159           }
00160         else
00161           {
00162             ::new(&(__sums[__iam]))
00163               _ValueType(__gnu_parallel::accumulate(
00164                                          __begin + __borders[__iam] + 1,
00165                                          __begin + __borders[__iam + 1],
00166                                          *(__begin + __borders[__iam]),
00167                                          __bin_op,
00168                                          __gnu_parallel::sequential_tag()));
00169           }
00170 
00171 #       pragma omp barrier
00172 
00173 #       pragma omp single
00174     __parallel_partial_sum_basecase(__sums + 1, __sums + __num_threads,
00175                     __sums + 1, __bin_op, __sums[0]);
00176 
00177 #       pragma omp barrier
00178 
00179     // Still same team.
00180         __parallel_partial_sum_basecase(__begin + __borders[__iam + 1],
00181                     __begin + __borders[__iam + 2],
00182                     __result + __borders[__iam + 1],
00183                     __bin_op, __sums[__iam]);
00184       } //parallel
00185 
00186       for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
00187     __sums[__i].~_ValueType();
00188       ::operator delete(__sums);
00189 
00190       delete[] __borders;
00191 
00192       return __result + __n;
00193     }
00194 
00195   /** @brief Parallel partial sum front-__end.
00196    *  @param __begin Begin iterator of input sequence.
00197    *  @param __end End iterator of input sequence.
00198    *  @param __result Begin iterator of output sequence.
00199    *  @param __bin_op Associative binary function.
00200    *  @return End iterator of output sequence. */
00201   template<typename _IIter,
00202        typename _OutputIterator,
00203        typename _BinaryOperation>
00204     _OutputIterator
00205     __parallel_partial_sum(_IIter __begin, _IIter __end,
00206                _OutputIterator __result, _BinaryOperation __bin_op)
00207     {
00208       _GLIBCXX_CALL(__begin - __end)
00209 
00210       typedef std::iterator_traits<_IIter> _TraitsType;
00211       typedef typename _TraitsType::value_type _ValueType;
00212       typedef typename _TraitsType::difference_type _DifferenceType;
00213 
00214       _DifferenceType __n = __end - __begin;
00215 
00216       switch (_Settings::get().partial_sum_algorithm)
00217     {
00218     case LINEAR:
00219       // Need an initial offset.
00220       return __parallel_partial_sum_linear(__begin, __end, __result,
00221                            __bin_op, __n);
00222     default:
00223       // Partial_sum algorithm not implemented.
00224       _GLIBCXX_PARALLEL_ASSERT(0);
00225       return __result + __n;
00226     }
00227     }
00228 }
00229 
00230 #endif /* _GLIBCXX_PARALLEL_PARTIAL_SUM_H */