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
;
106 thread_index_t num_threads
=
107 std::min
<difference_type
>(get_max_threads(), n
- 1);
112 return parallel_partial_sum_basecase(
113 begin
+ 1, end
, result
+ 1, bin_op
, *begin
);
116 difference_type
* borders
;
119 # pragma omp parallel num_threads(num_threads)
123 num_threads
= omp_get_num_threads();
125 borders
= new difference_type
[num_threads
+ 2];
127 if (Settings::partial_sum_dilatation
== 1.0f
)
128 equally_split(n
, num_threads
+ 1, borders
);
131 difference_type chunk_length
=
133 ((double)num_threads
+ Settings::partial_sum_dilatation
)),
134 borderstart
= n
- num_threads
* chunk_length
;
136 for (int i
= 1; i
< (num_threads
+ 1); i
++)
138 borders
[i
] = borderstart
;
139 borderstart
+= chunk_length
;
141 borders
[num_threads
+ 1] = n
;
144 sums
= static_cast<value_type
*>(
145 ::operator new(sizeof(value_type
) * num_threads
));
146 OutputIterator target_end
;
149 int iam
= omp_get_thread_num();
153 parallel_partial_sum_basecase(begin
+ 1, begin
+ borders
[1],
154 result
+ 1, bin_op
, *begin
);
155 sums
[0] = *(result
+ borders
[1] - 1);
159 sums
[iam
] = std::accumulate(begin
+ borders
[iam
] + 1,
160 begin
+ borders
[iam
+ 1],
161 *(begin
+ borders
[iam
]),
162 bin_op
, __gnu_parallel::sequential_tag());
168 parallel_partial_sum_basecase(
169 sums
+ 1, sums
+ num_threads
, sums
+ 1, bin_op
, sums
[0]);
174 parallel_partial_sum_basecase(begin
+ borders
[iam
+ 1],
175 begin
+ borders
[iam
+ 2],
176 result
+ borders
[iam
+ 1], bin_op
,
186 /** @brief Parallel partial sum front-end.
187 * @param begin Begin iterator of input sequence.
188 * @param end End iterator of input sequence.
189 * @param result Begin iterator of output sequence.
190 * @param bin_op Associative binary function.
191 * @return End iterator of output sequence. */
193 typename InputIterator
,
194 typename OutputIterator
,
195 typename BinaryOperation
>
197 parallel_partial_sum(InputIterator begin
, InputIterator end
,
198 OutputIterator result
, BinaryOperation bin_op
)
200 _GLIBCXX_CALL(begin
- end
)
202 typedef std::iterator_traits
<InputIterator
> traits_type
;
203 typedef typename
traits_type::value_type value_type
;
204 typedef typename
traits_type::difference_type difference_type
;
206 difference_type n
= end
- begin
;
208 switch (Settings::partial_sum_algorithm
)
210 case Settings::LINEAR
:
211 // Need an initial offset.
212 return parallel_partial_sum_linear(begin
, end
, result
, bin_op
, n
);
214 // Partial_sum algorithm not implemented.
215 _GLIBCXX_PARALLEL_ASSERT(0);