3 // Copyright (C) 2007 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/partial_sum.h
32 * @brief Parallel implementation of std::partial_sum(), i. e. prefix
34 * This file is a GNU parallel extension to the Standard C++ Library.
37 // Written by Johannes Singler.
39 #ifndef _GLIBCXX_PARALLEL_PARTIAL_SUM_H
40 #define _GLIBCXX_PARALLEL_PARTIAL_SUM_H 1
43 #include <bits/stl_algobase.h>
44 #include <parallel/parallel.h>
45 #include <parallel/numericfwd.h>
47 namespace __gnu_parallel
49 // Problem: there is no 0-element given.
51 /** @brief Base case prefix sum routine.
52 * @param begin Begin iterator of input sequence.
53 * @param end End iterator of input sequence.
54 * @param result Begin iterator of output sequence.
55 * @param bin_op Associative binary function.
56 * @param value Start value. Must be passed since the neutral
57 * element is unknown in general.
58 * @return End iterator of output sequence. */
60 typename InputIterator,
61 typename OutputIterator,
62 typename BinaryOperation>
64 parallel_partial_sum_basecase(
65 InputIterator begin, InputIterator end,
66 OutputIterator result, BinaryOperation bin_op,
67 typename std::iterator_traits<InputIterator>::value_type value)
74 value = bin_op(value, *begin);
82 /** @brief Parallel partial sum implementation, two-phase approach,
84 * @param begin Begin iterator of input sequence.
85 * @param end End iterator of input sequence.
86 * @param result Begin iterator of output sequence.
87 * @param bin_op Associative binary function.
88 * @param n Length of sequence.
89 * @param num_threads Number of threads to use.
90 * @return End iterator of output sequence.
93 typename InputIterator,
94 typename OutputIterator,
95 typename BinaryOperation>
97 parallel_partial_sum_linear(
98 InputIterator begin, InputIterator end,
99 OutputIterator result, BinaryOperation bin_op,
100 typename std::iterator_traits<InputIterator>::difference_type n)
102 typedef std::iterator_traits<InputIterator> traits_type;
103 typedef typename traits_type::value_type value_type;
104 typedef typename traits_type::difference_type difference_type;
109 thread_index_t num_threads =
110 std::min<difference_type>(get_max_threads(), n - 1);
115 return parallel_partial_sum_basecase(
116 begin + 1, end, result + 1, bin_op, *begin);
119 difference_type* borders;
122 # pragma omp parallel num_threads(num_threads)
126 num_threads = omp_get_num_threads();
128 borders = new difference_type[num_threads + 2];
130 if (Settings::partial_sum_dilatation == 1.0f)
131 equally_split(n, num_threads + 1, borders);
134 difference_type chunk_length =
136 ((double)num_threads + Settings::partial_sum_dilatation)),
137 borderstart = n - num_threads * chunk_length;
139 for (int i = 1; i < (num_threads + 1); ++i)
141 borders[i] = borderstart;
142 borderstart += chunk_length;
144 borders[num_threads + 1] = n;
147 sums = static_cast<value_type*>(
148 ::operator new(sizeof(value_type) * num_threads));
149 OutputIterator target_end;
152 thread_index_t iam = omp_get_thread_num();
156 parallel_partial_sum_basecase(begin + 1, begin + borders[1],
157 result + 1, bin_op, *begin);
158 new(&(sums[iam])) value_type(*(result + borders[1] - 1));
162 new(&(sums[iam])) value_type(
163 std::accumulate(begin + borders[iam] + 1,
164 begin + borders[iam + 1],
165 *(begin + borders[iam]),
166 bin_op, __gnu_parallel::sequential_tag()));
172 parallel_partial_sum_basecase(
173 sums + 1, sums + num_threads, sums + 1, bin_op, sums[0]);
178 parallel_partial_sum_basecase(begin + borders[iam + 1],
179 begin + borders[iam + 2],
180 result + borders[iam + 1], bin_op,
190 /** @brief Parallel partial sum front-end.
191 * @param begin Begin iterator of input sequence.
192 * @param end End iterator of input sequence.
193 * @param result Begin iterator of output sequence.
194 * @param bin_op Associative binary function.
195 * @return End iterator of output sequence. */
197 typename InputIterator,
198 typename OutputIterator,
199 typename BinaryOperation>
201 parallel_partial_sum(InputIterator begin, InputIterator end,
202 OutputIterator result, BinaryOperation bin_op)
204 _GLIBCXX_CALL(begin - end)
206 typedef std::iterator_traits<InputIterator> traits_type;
207 typedef typename traits_type::value_type value_type;
208 typedef typename traits_type::difference_type difference_type;
210 difference_type n = end - begin;
212 switch (Settings::partial_sum_algorithm)
214 case Settings::LINEAR:
215 // Need an initial offset.
216 return parallel_partial_sum_linear(begin, end, result, bin_op, n);
218 // Partial_sum algorithm not implemented.
219 _GLIBCXX_PARALLEL_ASSERT(0);