1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2015 Jakub Szuppe <j.szuppe@gmail.com>
3 //
4 // Distributed under the Boost Software License, Version 1.0
5 // See accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt
7 //
8 // See http://boostorg.github.com/compute for more information.
9 //---------------------------------------------------------------------------//
10
11 #ifndef BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP
12 #define BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP
13
14 #include <iterator>
15 #include <utility>
16
17 #include <boost/static_assert.hpp>
18
19 #include <boost/compute/command_queue.hpp>
20 #include <boost/compute/device.hpp>
21 #include <boost/compute/functional.hpp>
22 #include <boost/compute/system.hpp>
23 #include <boost/compute/algorithm/detail/reduce_by_key.hpp>
24 #include <boost/compute/type_traits/is_device_iterator.hpp>
25
26 namespace boost {
27 namespace compute {
28
29 /// The \c reduce_by_key() algorithm performs reduction for each contiguous
30 /// subsequence of values determinate by equivalent keys.
31 ///
32 /// Returns a pair of iterators at the end of the ranges [\p keys_result, keys_result_last)
33 /// and [\p values_result, \p values_result_last).
34 ///
35 /// If no function is specified, \c plus will be used.
36 /// If no predicate is specified, \c equal_to will be used.
37 ///
38 /// \param keys_first the first key
39 /// \param keys_last the last key
40 /// \param values_first the first input value
41 /// \param keys_result iterator pointing to the key output
42 /// \param values_result iterator pointing to the reduced value output
43 /// \param function binary reduction function
44 /// \param predicate binary predicate which returns true only if two keys are equal
45 /// \param queue command queue to perform the operation
46 ///
47 /// The \c reduce_by_key() algorithm assumes that the binary reduction function
48 /// is associative. When used with non-associative functions the result may
49 /// be non-deterministic and vary in precision. Notably this affects the
50 /// \c plus<float>() function as floating-point addition is not associative
51 /// and may produce slightly different results than a serial algorithm.
52 ///
53 /// For example, to calculate the sum of the values for each key:
54 ///
55 /// \snippet test/test_reduce_by_key.cpp reduce_by_key_int
56 ///
57 /// Space complexity on GPUs: \Omega(2n)<br>
58 /// Space complexity on CPUs: \Omega(1)
59 ///
60 /// \see reduce()
61 template<class InputKeyIterator, class InputValueIterator,
62 class OutputKeyIterator, class OutputValueIterator,
63 class BinaryFunction, class BinaryPredicate>
64 inline std::pair<OutputKeyIterator, OutputValueIterator>
reduce_by_key(InputKeyIterator keys_first,InputKeyIterator keys_last,InputValueIterator values_first,OutputKeyIterator keys_result,OutputValueIterator values_result,BinaryFunction function,BinaryPredicate predicate,command_queue & queue=system::default_queue ())65 reduce_by_key(InputKeyIterator keys_first,
66 InputKeyIterator keys_last,
67 InputValueIterator values_first,
68 OutputKeyIterator keys_result,
69 OutputValueIterator values_result,
70 BinaryFunction function,
71 BinaryPredicate predicate,
72 command_queue &queue = system::default_queue())
73 {
74 BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value);
75 BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value);
76 BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value);
77 BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value);
78
79 return detail::dispatch_reduce_by_key(keys_first, keys_last, values_first,
80 keys_result, values_result,
81 function, predicate,
82 queue);
83 }
84
85 /// \overload
86 template<class InputKeyIterator, class InputValueIterator,
87 class OutputKeyIterator, class OutputValueIterator,
88 class BinaryFunction>
89 inline std::pair<OutputKeyIterator, OutputValueIterator>
reduce_by_key(InputKeyIterator keys_first,InputKeyIterator keys_last,InputValueIterator values_first,OutputKeyIterator keys_result,OutputValueIterator values_result,BinaryFunction function,command_queue & queue=system::default_queue ())90 reduce_by_key(InputKeyIterator keys_first,
91 InputKeyIterator keys_last,
92 InputValueIterator values_first,
93 OutputKeyIterator keys_result,
94 OutputValueIterator values_result,
95 BinaryFunction function,
96 command_queue &queue = system::default_queue())
97 {
98 BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value);
99 BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value);
100 BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value);
101 BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value);
102 typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type;
103
104 return reduce_by_key(keys_first, keys_last, values_first,
105 keys_result, values_result,
106 function, equal_to<key_type>(),
107 queue);
108 }
109
110 /// \overload
111 template<class InputKeyIterator, class InputValueIterator,
112 class OutputKeyIterator, class OutputValueIterator>
113 inline std::pair<OutputKeyIterator, OutputValueIterator>
reduce_by_key(InputKeyIterator keys_first,InputKeyIterator keys_last,InputValueIterator values_first,OutputKeyIterator keys_result,OutputValueIterator values_result,command_queue & queue=system::default_queue ())114 reduce_by_key(InputKeyIterator keys_first,
115 InputKeyIterator keys_last,
116 InputValueIterator values_first,
117 OutputKeyIterator keys_result,
118 OutputValueIterator values_result,
119 command_queue &queue = system::default_queue())
120 {
121 BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value);
122 BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value);
123 BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value);
124 BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value);
125 typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type;
126 typedef typename std::iterator_traits<InputValueIterator>::value_type value_type;
127
128 return reduce_by_key(keys_first, keys_last, values_first,
129 keys_result, values_result,
130 plus<value_type>(), equal_to<key_type>(),
131 queue);
132 }
133
134 } // end compute namespace
135 } // end boost namespace
136
137 #endif // BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP
138