33 #ifndef _GLIBCXX_PARALLEL_PARTIAL_SUM_H
34 #define _GLIBCXX_PARALLEL_PARTIAL_SUM_H 1
54 template<
typename InputIterator,
55 typename OutputIterator,
56 typename BinaryOperation>
59 OutputIterator result, BinaryOperation bin_op,
61 <InputIterator>::value_type value)
68 value = bin_op(value, *begin);
86 template<
typename InputIterator,
87 typename OutputIterator,
88 typename BinaryOperation>
91 OutputIterator result, BinaryOperation bin_op,
93 <InputIterator>::difference_type n)
96 typedef typename traits_type::value_type value_type;
97 typedef typename traits_type::difference_type difference_type;
103 std::min<difference_type>(get_max_threads(), n - 1);
109 begin + 1, end, result + 1, bin_op, *begin);
112 difference_type* borders;
117 # pragma omp parallel num_threads(num_threads)
121 num_threads = omp_get_num_threads();
123 borders =
new difference_type[num_threads + 2];
129 difference_type chunk_length =
132 borderstart = n - num_threads * chunk_length;
134 for (
int i = 1; i < (num_threads + 1); ++i)
136 borders[i] = borderstart;
137 borderstart += chunk_length;
139 borders[num_threads + 1] = n;
142 sums =
static_cast<value_type*
>(::operator
new(
sizeof(value_type)
144 OutputIterator target_end;
152 result + 1, bin_op, *begin);
153 ::new(&(sums[iam])) value_type(*(result + borders[1] - 1));
159 begin + borders[iam + 1],
160 *(begin + borders[iam]),
169 sums + 1, sums + num_threads, sums + 1, bin_op, sums[0]);
175 begin + borders[iam + 2],
176 result + borders[iam + 1], bin_op,
180 ::operator
delete(sums);
192 template<
typename InputIterator,
193 typename OutputIterator,
194 typename BinaryOperation>
197 OutputIterator result, BinaryOperation bin_op)
202 typedef typename traits_type::value_type value_type;
203 typedef typename traits_type::difference_type difference_type;
205 difference_type n = end - begin;
214 _GLIBCXX_PARALLEL_ASSERT(0);
#define _GLIBCXX_CALL(n)
Macro to produce log message when entering a function.
OutputIterator parallel_partial_sum_basecase(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::value_type value)
Base case prefix sum routine.
class _Settings Run-time settings for the parallel mode, including all tunable parameters.
Forces sequential execution at compile time.
GNU parallel code for public use.
OutputIterator parallel_partial_sum_linear(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits< InputIterator >::difference_type n)
Parallel partial sum implementation, two-phase approach, no recursion.
static const _Settings & get()
Get the global settings.
OutputIterator parallel_partial_sum(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op)
Parallel partial sum front-end.
float partial_sum_dilation
Ratio for partial_sum. Assume "sum and write result" to be this factor slower than just "sum"...
uint16 thread_index_t
Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...
End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
Accumulate values in a range.
OutputIterator equally_split(difference_type n, thread_index_t num_threads, OutputIterator s)
Function to split a sequence into parts of almost equal size.