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_DETAIL_REDUCE_BY_KEY_HPP
12 #define BOOST_COMPUTE_ALGORITHM_DETAIL_REDUCE_BY_KEY_HPP
13
14 #include <algorithm>
15 #include <iterator>
16
17 #include <boost/compute/command_queue.hpp>
18 #include <boost/compute/functional.hpp>
19 #include <boost/compute/container/vector.hpp>
20 #include <boost/compute/detail/iterator_range_size.hpp>
21 #include <boost/compute/algorithm/detail/serial_reduce_by_key.hpp>
22 #include <boost/compute/algorithm/detail/reduce_by_key_with_scan.hpp>
23 #include <boost/compute/type_traits.hpp>
24
25 namespace boost {
26 namespace compute {
27 namespace detail {
28
29 template<class InputKeyIterator, class InputValueIterator,
30 class OutputKeyIterator, class OutputValueIterator,
31 class BinaryFunction, class BinaryPredicate>
reduce_by_key_on_gpu(InputKeyIterator keys_first,InputKeyIterator keys_last,InputValueIterator values_first,OutputKeyIterator keys_result,OutputValueIterator values_result,BinaryFunction function,BinaryPredicate predicate,command_queue & queue)32 size_t reduce_by_key_on_gpu(InputKeyIterator keys_first,
33 InputKeyIterator keys_last,
34 InputValueIterator values_first,
35 OutputKeyIterator keys_result,
36 OutputValueIterator values_result,
37 BinaryFunction function,
38 BinaryPredicate predicate,
39 command_queue &queue)
40 {
41 return detail::reduce_by_key_with_scan(keys_first, keys_last, values_first,
42 keys_result, values_result, function,
43 predicate, queue);
44 }
45
46 template<class InputKeyIterator, class InputValueIterator,
47 class OutputKeyIterator, class OutputValueIterator>
reduce_by_key_on_gpu_requirements_met(InputKeyIterator keys_first,InputValueIterator values_first,OutputKeyIterator keys_result,OutputValueIterator values_result,const size_t count,command_queue & queue)48 bool reduce_by_key_on_gpu_requirements_met(InputKeyIterator keys_first,
49 InputValueIterator values_first,
50 OutputKeyIterator keys_result,
51 OutputValueIterator values_result,
52 const size_t count,
53 command_queue &queue)
54 {
55 const device &device = queue.get_device();
56 return (count > 256)
57 && !(device.type() & device::cpu)
58 && reduce_by_key_with_scan_requirements_met(keys_first, values_first,
59 keys_result,values_result,
60 count, queue);
61 return true;
62 }
63
64 template<class InputKeyIterator, class InputValueIterator,
65 class OutputKeyIterator, class OutputValueIterator,
66 class BinaryFunction, class BinaryPredicate>
67 inline std::pair<OutputKeyIterator, OutputValueIterator>
dispatch_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)68 dispatch_reduce_by_key(InputKeyIterator keys_first,
69 InputKeyIterator keys_last,
70 InputValueIterator values_first,
71 OutputKeyIterator keys_result,
72 OutputValueIterator values_result,
73 BinaryFunction function,
74 BinaryPredicate predicate,
75 command_queue &queue)
76 {
77 typedef typename
78 std::iterator_traits<OutputKeyIterator>::difference_type key_difference_type;
79 typedef typename
80 std::iterator_traits<OutputValueIterator>::difference_type value_difference_type;
81
82 const size_t count = detail::iterator_range_size(keys_first, keys_last);
83 if (count < 2) {
84 boost::compute::copy_n(keys_first, count, keys_result, queue);
85 boost::compute::copy_n(values_first, count, values_result, queue);
86 return
87 std::make_pair<OutputKeyIterator, OutputValueIterator>(
88 keys_result + static_cast<key_difference_type>(count),
89 values_result + static_cast<value_difference_type>(count)
90 );
91 }
92
93 size_t result_size = 0;
94 if(reduce_by_key_on_gpu_requirements_met(keys_first, values_first, keys_result,
95 values_result, count, queue)){
96 result_size =
97 detail::reduce_by_key_on_gpu(keys_first, keys_last, values_first,
98 keys_result, values_result, function,
99 predicate, queue);
100 }
101 else {
102 result_size =
103 detail::serial_reduce_by_key(keys_first, keys_last, values_first,
104 keys_result, values_result, function,
105 predicate, queue);
106 }
107
108 return
109 std::make_pair<OutputKeyIterator, OutputValueIterator>(
110 keys_result + static_cast<key_difference_type>(result_size),
111 values_result + static_cast<value_difference_type>(result_size)
112 );
113 }
114
115 } // end detail namespace
116 } // end compute namespace
117 } // end boost namespace
118
119 #endif // BOOST_COMPUTE_ALGORITHM_DETAIL_REDUCE_BY_KEY_HPP
120