]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //---------------------------------------------------------------------------// |
2 | // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@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_SORT_HPP | |
12 | #define BOOST_COMPUTE_ALGORITHM_SORT_HPP | |
13 | ||
14 | #include <iterator> | |
15 | ||
16 | #include <boost/utility/enable_if.hpp> | |
17 | ||
18 | #include <boost/compute/system.hpp> | |
19 | #include <boost/compute/command_queue.hpp> | |
20 | #include <boost/compute/algorithm/detail/merge_sort_on_cpu.hpp> | |
21 | #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp> | |
22 | #include <boost/compute/algorithm/detail/radix_sort.hpp> | |
23 | #include <boost/compute/algorithm/detail/insertion_sort.hpp> | |
24 | #include <boost/compute/algorithm/reverse.hpp> | |
25 | #include <boost/compute/container/mapped_view.hpp> | |
26 | #include <boost/compute/detail/iterator_range_size.hpp> | |
27 | #include <boost/compute/iterator/buffer_iterator.hpp> | |
28 | #include <boost/compute/type_traits/is_device_iterator.hpp> | |
29 | ||
30 | namespace boost { | |
31 | namespace compute { | |
32 | namespace detail { | |
33 | ||
34 | template<class T> | |
35 | inline void dispatch_gpu_sort(buffer_iterator<T> first, | |
36 | buffer_iterator<T> last, | |
37 | less<T>, | |
38 | command_queue &queue, | |
39 | typename boost::enable_if_c< | |
40 | is_radix_sortable<T>::value | |
41 | >::type* = 0) | |
42 | { | |
43 | size_t count = detail::iterator_range_size(first, last); | |
44 | ||
45 | if(count < 2){ | |
46 | // nothing to do | |
47 | return; | |
48 | } | |
49 | else if(count <= 32){ | |
50 | ::boost::compute::detail::serial_insertion_sort(first, last, queue); | |
51 | } | |
52 | else { | |
53 | ::boost::compute::detail::radix_sort(first, last, queue); | |
54 | } | |
55 | } | |
56 | ||
57 | template<class T> | |
58 | inline void dispatch_gpu_sort(buffer_iterator<T> first, | |
59 | buffer_iterator<T> last, | |
60 | greater<T> compare, | |
61 | command_queue &queue, | |
62 | typename boost::enable_if_c< | |
63 | is_radix_sortable<T>::value | |
64 | >::type* = 0) | |
65 | { | |
66 | size_t count = detail::iterator_range_size(first, last); | |
67 | ||
68 | if(count < 2){ | |
69 | // nothing to do | |
70 | return; | |
71 | } | |
72 | else if(count <= 32){ | |
73 | ::boost::compute::detail::serial_insertion_sort( | |
74 | first, last, compare, queue | |
75 | ); | |
76 | } | |
77 | else { | |
78 | // radix sorts in descending order | |
79 | ::boost::compute::detail::radix_sort(first, last, false, queue); | |
80 | } | |
81 | } | |
82 | ||
83 | template<class Iterator, class Compare> | |
84 | inline void dispatch_gpu_sort(Iterator first, | |
85 | Iterator last, | |
86 | Compare compare, | |
87 | command_queue &queue) | |
88 | { | |
89 | size_t count = detail::iterator_range_size(first, last); | |
90 | ||
91 | if(count < 2){ | |
92 | // nothing to do | |
93 | return; | |
94 | } | |
95 | else if(count <= 32){ | |
96 | ::boost::compute::detail::serial_insertion_sort( | |
97 | first, last, compare, queue | |
98 | ); | |
99 | } | |
100 | else { | |
101 | ::boost::compute::detail::merge_sort_on_gpu( | |
102 | first, last, compare, queue | |
103 | ); | |
104 | } | |
105 | } | |
106 | ||
107 | // sort() for device iterators | |
108 | template<class Iterator, class Compare> | |
109 | inline void dispatch_sort(Iterator first, | |
110 | Iterator last, | |
111 | Compare compare, | |
112 | command_queue &queue, | |
113 | typename boost::enable_if< | |
114 | is_device_iterator<Iterator> | |
115 | >::type* = 0) | |
116 | { | |
117 | if(queue.get_device().type() & device::gpu) { | |
118 | dispatch_gpu_sort(first, last, compare, queue); | |
119 | return; | |
120 | } | |
121 | ::boost::compute::detail::merge_sort_on_cpu(first, last, compare, queue); | |
122 | } | |
123 | ||
124 | // sort() for host iterators | |
125 | template<class Iterator, class Compare> | |
126 | inline void dispatch_sort(Iterator first, | |
127 | Iterator last, | |
128 | Compare compare, | |
129 | command_queue &queue, | |
130 | typename boost::disable_if< | |
131 | is_device_iterator<Iterator> | |
132 | >::type* = 0) | |
133 | { | |
134 | typedef typename std::iterator_traits<Iterator>::value_type T; | |
135 | ||
136 | size_t size = static_cast<size_t>(std::distance(first, last)); | |
137 | ||
138 | // create mapped buffer | |
139 | mapped_view<T> view( | |
140 | boost::addressof(*first), size, queue.get_context() | |
141 | ); | |
142 | ||
143 | // sort mapped buffer | |
144 | dispatch_sort(view.begin(), view.end(), compare, queue); | |
145 | ||
146 | // return results to host | |
147 | view.map(queue); | |
148 | } | |
149 | ||
150 | } // end detail namespace | |
151 | ||
152 | /// Sorts the values in the range [\p first, \p last) according to | |
153 | /// \p compare. | |
154 | /// | |
155 | /// \param first first element in the range to sort | |
156 | /// \param last last element in the range to sort | |
157 | /// \param compare comparison function (by default \c less) | |
158 | /// \param queue command queue to perform the operation | |
159 | /// | |
160 | /// For example, to sort a vector on the device: | |
161 | /// \code | |
162 | /// // create vector on the device with data | |
163 | /// float data[] = { 2.f, 4.f, 1.f, 3.f }; | |
164 | /// boost::compute::vector<float> vec(data, data + 4, queue); | |
165 | /// | |
166 | /// // sort the vector on the device | |
167 | /// boost::compute::sort(vec.begin(), vec.end(), queue); | |
168 | /// \endcode | |
169 | /// | |
170 | /// The sort() algorithm can also be directly used with host iterators. This | |
171 | /// example will automatically transfer the data to the device, sort it, and | |
172 | /// then transfer the data back to the host: | |
173 | /// \code | |
174 | /// std::vector<int> data = { 9, 3, 2, 5, 1, 4, 6, 7 }; | |
175 | /// | |
176 | /// boost::compute::sort(data.begin(), data.end(), queue); | |
177 | /// \endcode | |
178 | /// | |
179 | /// \see is_sorted() | |
180 | template<class Iterator, class Compare> | |
181 | inline void sort(Iterator first, | |
182 | Iterator last, | |
183 | Compare compare, | |
184 | command_queue &queue = system::default_queue()) | |
185 | { | |
186 | ::boost::compute::detail::dispatch_sort(first, last, compare, queue); | |
187 | } | |
188 | ||
189 | /// \overload | |
190 | template<class Iterator> | |
191 | inline void sort(Iterator first, | |
192 | Iterator last, | |
193 | command_queue &queue = system::default_queue()) | |
194 | { | |
195 | typedef typename std::iterator_traits<Iterator>::value_type value_type; | |
196 | ||
197 | ::boost::compute::sort( | |
198 | first, last, ::boost::compute::less<value_type>(), queue | |
199 | ); | |
200 | } | |
201 | ||
202 | } // end compute namespace | |
203 | } // end boost namespace | |
204 | ||
205 | #endif // BOOST_COMPUTE_ALGORITHM_SORT_HPP |