compute/algorithm/reduce_by_key.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2015 Jakub Szuppe <j.szuppe@gmail.com>
0003 //
0004 // Distributed under the Boost Software License, Version 1.0
0005 // See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt
0007 //
0008 // See http://boostorg.github.com/compute for more information.
0009 //---------------------------------------------------------------------------//
0010
0011 #ifndef BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP
0013
0014 #include <iterator>
0015 #include <utility>
0016
0017 #include <boost/static_assert.hpp>
0018
0019 #include <boost/compute/command_queue.hpp>
0020 #include <boost/compute/device.hpp>
0021 #include <boost/compute/functional.hpp>
0022 #include <boost/compute/system.hpp>
0023 #include <boost/compute/algorithm/detail/reduce_by_key.hpp>
0024 #include <boost/compute/type_traits/is_device_iterator.hpp>
0025
0026 namespace boost {
0027 namespace compute {
0028
0029 /// The \c reduce_by_key() algorithm performs reduction for each contiguous
0030 /// subsequence of values determinate by equivalent keys.
0031 ///
0032 /// Returns a pair of iterators at the end of the ranges [\p keys_result, keys_result_last)
0033 /// and [\p values_result, \p values_result_last).
0034 ///
0035 /// If no function is specified, \c plus will be used.
0036 /// If no predicate is specified, \c equal_to will be used.
0037 ///
0038 /// \param keys_first the first key
0039 /// \param keys_last the last key
0040 /// \param values_first the first input value
0041 /// \param keys_result iterator pointing to the key output
0042 /// \param values_result iterator pointing to the reduced value output
0043 /// \param function binary reduction function
0044 /// \param predicate binary predicate which returns true only if two keys are equal
0045 /// \param queue command queue to perform the operation
0046 ///
0047 /// The \c reduce_by_key() algorithm assumes that the binary reduction function
0048 /// is associative. When used with non-associative functions the result may
0049 /// be non-deterministic and vary in precision. Notably this affects the
0050 /// \c plus<float>() function as floating-point addition is not associative
0051 /// and may produce slightly different results than a serial algorithm.
0052 ///
0053 /// For example, to calculate the sum of the values for each key:
0054 ///
0055 /// \snippet test/test_reduce_by_key.cpp reduce_by_key_int
0056 ///
0057 /// Space complexity on GPUs: \Omega(2n)<br>
0058 /// Space complexity on CPUs: \Omega(1)
0059 ///
0060 /// \see reduce()
0061 template<class InputKeyIterator, class InputValueIterator,
0062          class OutputKeyIterator, class OutputValueIterator,
0063          class BinaryFunction, class BinaryPredicate>
0064 inline std::pair<OutputKeyIterator, OutputValueIterator>
0065 reduce_by_key(InputKeyIterator keys_first,
0066               InputKeyIterator keys_last,
0067               InputValueIterator values_first,
0068               OutputKeyIterator keys_result,
0069               OutputValueIterator values_result,
0070               BinaryFunction function,
0071               BinaryPredicate predicate,
0072               command_queue &queue = system::default_queue())
0073 {
0074     BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value);
0075     BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value);
0076     BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value);
0077     BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value);
0078
0079     return detail::dispatch_reduce_by_key(keys_first, keys_last, values_first,
0080                                           keys_result, values_result,
0081                                           function, predicate,
0082                                           queue);
0083 }
0084
0085 /// \overload
0086 template<class InputKeyIterator, class InputValueIterator,
0087          class OutputKeyIterator, class OutputValueIterator,
0088          class BinaryFunction>
0089 inline std::pair<OutputKeyIterator, OutputValueIterator>
0090 reduce_by_key(InputKeyIterator keys_first,
0091               InputKeyIterator keys_last,
0092               InputValueIterator values_first,
0093               OutputKeyIterator keys_result,
0094               OutputValueIterator values_result,
0095               BinaryFunction function,
0096               command_queue &queue = system::default_queue())
0097 {
0098     BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value);
0099     BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value);
0100     BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value);
0101     BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value);
0102     typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type;
0103
0104     return reduce_by_key(keys_first, keys_last, values_first,
0105                          keys_result, values_result,
0106                          function, equal_to<key_type>(),
0107                          queue);
0108 }
0109
0110 /// \overload
0111 template<class InputKeyIterator, class InputValueIterator,
0112          class OutputKeyIterator, class OutputValueIterator>
0113 inline std::pair<OutputKeyIterator, OutputValueIterator>
0114 reduce_by_key(InputKeyIterator keys_first,
0115               InputKeyIterator keys_last,
0116               InputValueIterator values_first,
0117               OutputKeyIterator keys_result,
0118               OutputValueIterator values_result,
0119               command_queue &queue = system::default_queue())
0120 {
0121     BOOST_STATIC_ASSERT(is_device_iterator<InputKeyIterator>::value);
0122     BOOST_STATIC_ASSERT(is_device_iterator<InputValueIterator>::value);
0123     BOOST_STATIC_ASSERT(is_device_iterator<OutputKeyIterator>::value);
0124     BOOST_STATIC_ASSERT(is_device_iterator<OutputValueIterator>::value);
0125     typedef typename std::iterator_traits<InputKeyIterator>::value_type key_type;
0126     typedef typename std::iterator_traits<InputValueIterator>::value_type value_type;
0127
0128     return reduce_by_key(keys_first, keys_last, values_first,
0129                          keys_result, values_result,
0130                          plus<value_type>(), equal_to<key_type>(),
0131                          queue);
0132 }
0133
0134 } // end compute namespace
0135 } // end boost namespace
0136
0137 #endif // BOOST_COMPUTE_ALGORITHM_REDUCE_BY_KEY_HPP