algorithm/detail/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_DETAIL_REDUCE_BY_KEY_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_DETAIL_REDUCE_BY_KEY_HPP
0013
0014 #include <algorithm>
0015 #include <iterator>
0016
0017 #include <boost/compute/command_queue.hpp>
0018 #include <boost/compute/functional.hpp>
0019 #include <boost/compute/container/vector.hpp>
0020 #include <boost/compute/detail/iterator_range_size.hpp>
0021 #include <boost/compute/algorithm/detail/serial_reduce_by_key.hpp>
0022 #include <boost/compute/algorithm/detail/reduce_by_key_with_scan.hpp>
0023 #include <boost/compute/type_traits.hpp>
0024
0025 namespace boost {
0026 namespace compute {
0027 namespace detail {
0028
0029 template<class InputKeyIterator, class InputValueIterator,
0030          class OutputKeyIterator, class OutputValueIterator,
0031          class BinaryFunction, class BinaryPredicate>
0032 size_t reduce_by_key_on_gpu(InputKeyIterator keys_first,
0033                             InputKeyIterator keys_last,
0034                             InputValueIterator values_first,
0035                             OutputKeyIterator keys_result,
0036                             OutputValueIterator values_result,
0037                             BinaryFunction function,
0038                             BinaryPredicate predicate,
0039                             command_queue &queue)
0040 {
0041     return detail::reduce_by_key_with_scan(keys_first, keys_last, values_first,
0042                                            keys_result, values_result, function,
0043                                            predicate, queue);
0044 }
0045
0046 template<class InputKeyIterator, class InputValueIterator,
0047          class OutputKeyIterator, class OutputValueIterator>
0048 bool reduce_by_key_on_gpu_requirements_met(InputKeyIterator keys_first,
0049                                            InputValueIterator values_first,
0050                                            OutputKeyIterator keys_result,
0051                                            OutputValueIterator values_result,
0052                                            const size_t count,
0053                                            command_queue &queue)
0054 {
0055     const device &device = queue.get_device();
0056     return (count > 256)
0057                && !(device.type() & device::cpu)
0058                && reduce_by_key_with_scan_requirements_met(keys_first, values_first,
0059                                                            keys_result,values_result,
0060                                                            count, queue);
0061     return true;
0062 }
0063
0064 template<class InputKeyIterator, class InputValueIterator,
0065          class OutputKeyIterator, class OutputValueIterator,
0066          class BinaryFunction, class BinaryPredicate>
0067 inline std::pair<OutputKeyIterator, OutputValueIterator>
0068 dispatch_reduce_by_key(InputKeyIterator keys_first,
0069                        InputKeyIterator keys_last,
0070                        InputValueIterator values_first,
0071                        OutputKeyIterator keys_result,
0072                        OutputValueIterator values_result,
0073                        BinaryFunction function,
0074                        BinaryPredicate predicate,
0075                        command_queue &queue)
0076 {
0077     typedef typename
0078         std::iterator_traits<OutputKeyIterator>::difference_type key_difference_type;
0079     typedef typename
0080         std::iterator_traits<OutputValueIterator>::difference_type value_difference_type;
0081
0082     const size_t count = detail::iterator_range_size(keys_first, keys_last);
0083     if (count < 2) {
0084         boost::compute::copy_n(keys_first, count, keys_result, queue);
0085         boost::compute::copy_n(values_first, count, values_result, queue);
0086         return
0087             std::make_pair<OutputKeyIterator, OutputValueIterator>(
0088                 keys_result + static_cast<key_difference_type>(count),
0089                 values_result + static_cast<value_difference_type>(count)
0090             );
0091     }
0092
0093     size_t result_size = 0;
0094     if(reduce_by_key_on_gpu_requirements_met(keys_first, values_first, keys_result,
0095                                              values_result, count, queue)){
0096         result_size =
0097             detail::reduce_by_key_on_gpu(keys_first, keys_last, values_first,
0098                                          keys_result, values_result, function,
0099                                          predicate, queue);
0100     }
0101     else {
0102         result_size =
0103               detail::serial_reduce_by_key(keys_first, keys_last, values_first,
0104                                            keys_result, values_result, function,
0105                                            predicate, queue);
0106     }
0107
0108     return
0109         std::make_pair<OutputKeyIterator, OutputValueIterator>(
0110             keys_result + static_cast<key_difference_type>(result_size),
0111             values_result + static_cast<value_difference_type>(result_size)
0112         );
0113 }
0114
0115 } // end detail namespace
0116 } // end compute namespace
0117 } // end boost namespace
0118
0119 #endif // BOOST_COMPUTE_ALGORITHM_DETAIL_REDUCE_BY_KEY_HPP