3 // Copyright (C) 2007, 2008 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
44 #include <bits/stl_algobase.h>
45 #include <parallel/parallel.h>
46 #include <parallel/numericfwd.h>
48 namespace __gnu_parallel
50 // Problem: there is no 0-element given.
52 /** @brief Base case prefix sum routine.
53 * @param begin Begin iterator of input sequence.
54 * @param end End iterator of input sequence.
55 * @param result Begin iterator of output sequence.
56 * @param bin_op Associative binary function.
57 * @param value Start value. Must be passed since the neutral
58 * element is unknown in general.
59 * @return End iterator of output sequence. */
60 template<typename InputIterator
,
61 typename OutputIterator
,
62 typename BinaryOperation
>
64 parallel_partial_sum_basecase(InputIterator begin
, InputIterator end
,
65 OutputIterator result
, BinaryOperation bin_op
,
66 typename
std::iterator_traits
67 <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.
92 template<typename InputIterator
,
93 typename OutputIterator
,
94 typename BinaryOperation
>
96 parallel_partial_sum_linear(InputIterator begin
, InputIterator end
,
97 OutputIterator result
, BinaryOperation bin_op
,
98 typename
std::iterator_traits
99 <InputIterator
>::difference_type n
)
101 typedef std::iterator_traits
<InputIterator
> traits_type
;
102 typedef typename
traits_type::value_type value_type
;
103 typedef typename
traits_type::difference_type difference_type
;
108 thread_index_t num_threads
=
109 std::min
<difference_type
>(get_max_threads(), n
- 1);
114 return parallel_partial_sum_basecase(
115 begin
+ 1, end
, result
+ 1, bin_op
, *begin
);
118 difference_type
* borders
;
121 const _Settings
& __s
= _Settings::get();
123 # pragma omp parallel num_threads(num_threads)
127 num_threads
= omp_get_num_threads();
129 borders
= new difference_type
[num_threads
+ 2];
131 if (__s
.partial_sum_dilation
== 1.0f
)
132 equally_split(n
, num_threads
+ 1, borders
);
135 difference_type chunk_length
=
137 / ((double)num_threads
+ __s
.partial_sum_dilation
)),
138 borderstart
= n
- num_threads
* chunk_length
;
140 for (int i
= 1; i
< (num_threads
+ 1); ++i
)
142 borders
[i
] = borderstart
;
143 borderstart
+= chunk_length
;
145 borders
[num_threads
+ 1] = n
;
148 sums
= static_cast<value_type
*>(::operator new(sizeof(value_type
)
150 OutputIterator target_end
;
153 thread_index_t iam
= omp_get_thread_num();
157 parallel_partial_sum_basecase(begin
+ 1, begin
+ borders
[1],
158 result
+ 1, bin_op
, *begin
);
159 ::new(&(sums
[iam
])) value_type(*(result
+ borders
[1] - 1));
164 value_type(std::accumulate(begin
+ borders
[iam
] + 1,
165 begin
+ borders
[iam
+ 1],
166 *(begin
+ borders
[iam
]),
168 __gnu_parallel::sequential_tag()));
174 parallel_partial_sum_basecase(
175 sums
+ 1, sums
+ num_threads
, sums
+ 1, bin_op
, sums
[0]);
180 parallel_partial_sum_basecase(begin
+ borders
[iam
+ 1],
181 begin
+ borders
[iam
+ 2],
182 result
+ borders
[iam
+ 1], bin_op
,
186 ::operator delete(sums
);
192 /** @brief Parallel partial sum front-end.
193 * @param begin Begin iterator of input sequence.
194 * @param end End iterator of input sequence.
195 * @param result Begin iterator of output sequence.
196 * @param bin_op Associative binary function.
197 * @return End iterator of output sequence. */
198 template<typename InputIterator
,
199 typename OutputIterator
,
200 typename BinaryOperation
>
202 parallel_partial_sum(InputIterator begin
, InputIterator end
,
203 OutputIterator result
, BinaryOperation bin_op
)
205 _GLIBCXX_CALL(begin
- end
)
207 typedef std::iterator_traits
<InputIterator
> traits_type
;
208 typedef typename
traits_type::value_type value_type
;
209 typedef typename
traits_type::difference_type difference_type
;
211 difference_type n
= end
- begin
;
213 switch (_Settings::get().partial_sum_algorithm
)
216 // Need an initial offset.
217 return parallel_partial_sum_linear(begin
, end
, result
, bin_op
, n
);
219 // Partial_sum algorithm not implemented.
220 _GLIBCXX_PARALLEL_ASSERT(0);
226 #endif /* _GLIBCXX_PARALLEL_PARTIAL_SUM_H */