1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2016 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 #define BOOST_TEST_MODULE TestMergeSortOnGPU
12 #include <boost/test/unit_test.hpp>
13
14 #include <iostream>
15
16 #include <boost/compute/system.hpp>
17 #include <boost/compute/algorithm/is_sorted.hpp>
18 #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp>
19 #include <boost/compute/container/vector.hpp>
20
21 #include "quirks.hpp"
22 #include "check_macros.hpp"
23 #include "context_setup.hpp"
24
25 namespace bc = boost::compute;
26
BOOST_AUTO_TEST_CASE(sort_small_vector_char)27 BOOST_AUTO_TEST_CASE(sort_small_vector_char)
28 {
29 if(is_apple_cpu_device(device)) {
30 std::cerr
31 << "skipping all merge_sort_on_gpu tests due to Apple platform"
32 << " behavior when local memory is used on a CPU device"
33 << std::endl;
34 return;
35 }
36
37 using boost::compute::char_;
38 ::boost::compute::greater<char_> greater;
39 ::boost::compute::less<char_> less;
40
41 char_ data[] = { 'c', 'a', '0', '7', 'B', 'F', '\0', '$' };
42 boost::compute::vector<char_> vector(data, data + 8, queue);
43 BOOST_CHECK_EQUAL(vector.size(), size_t(8));
44 BOOST_CHECK(boost::compute::is_sorted(vector.begin(), vector.end(), queue) == false);
45
46 // <
47 boost::compute::detail::merge_sort_on_gpu(
48 vector.begin(), vector.end(), less, queue
49 );
50 BOOST_CHECK(
51 boost::compute::is_sorted(vector.begin(), vector.end(), less, queue)
52 );
53 CHECK_RANGE_EQUAL(char_, 8, vector, ('\0', '$', '0', '7', 'B', 'F', 'a', 'c'));
54
55 // >
56 boost::compute::detail::merge_sort_on_gpu(
57 vector.begin(), vector.end(), greater, queue
58 );
59 BOOST_CHECK(
60 boost::compute::is_sorted(vector.begin(), vector.end(), greater, queue)
61 );
62 CHECK_RANGE_EQUAL(char_, 8, vector, ('c', 'a', 'F', 'B', '7', '0', '$', '\0'));
63 }
64
BOOST_AUTO_TEST_CASE(sort_mid_vector_int)65 BOOST_AUTO_TEST_CASE(sort_mid_vector_int)
66 {
67 if(is_apple_cpu_device(device)) {
68 return;
69 }
70
71 using boost::compute::int_;
72 ::boost::compute::greater<int_> greater;
73 ::boost::compute::less<int_> less;
74
75 const int_ size = 748;
76 std::vector<int_> data(size);
77 for(int_ i = 0; i < size; i++){
78 data[i] = i%2 ? i : -i;
79 }
80
81 boost::compute::vector<int_> vector(data.begin(), data.end(), queue);
82 BOOST_CHECK_EQUAL(vector.size(), size);
83 BOOST_CHECK(!boost::compute::is_sorted(vector.begin(), vector.end(), queue));
84
85 // <
86 boost::compute::detail::merge_sort_on_gpu(
87 vector.begin(), vector.end(), less, queue
88 );
89 BOOST_CHECK(
90 boost::compute::is_sorted(vector.begin(), vector.end(), less, queue)
91 );
92
93 // >
94 boost::compute::detail::merge_sort_on_gpu(
95 vector.begin(), vector.end(), greater, queue
96 );
97 BOOST_CHECK(
98 boost::compute::is_sorted(vector.begin(), vector.end(), greater, queue)
99 );
100 }
101
BOOST_AUTO_TEST_CASE(sort_mid_vector_ulong)102 BOOST_AUTO_TEST_CASE(sort_mid_vector_ulong)
103 {
104 if(is_apple_cpu_device(device)) {
105 return;
106 }
107
108 using boost::compute::ulong_;
109 ::boost::compute::greater<ulong_> greater;
110 ::boost::compute::less<ulong_> less;
111
112 const ulong_ size = 260;
113 std::vector<ulong_> data(size);
114 for(ulong_ i = 0; i < size; i++){
115 data[i] = i%2 ? i : i * i;
116 }
117
118 boost::compute::vector<ulong_> vector(data.begin(), data.end(), queue);
119 BOOST_CHECK_EQUAL(vector.size(), size);
120 BOOST_CHECK(!boost::compute::is_sorted(vector.begin(), vector.end(), queue));
121
122 // <
123 boost::compute::detail::merge_sort_on_gpu(
124 vector.begin(), vector.end(), less, queue
125 );
126 BOOST_CHECK(
127 boost::compute::is_sorted(vector.begin(), vector.end(), less, queue)
128 );
129
130 // >
131 boost::compute::detail::merge_sort_on_gpu(
132 vector.begin(), vector.end(), greater, queue
133 );
134 BOOST_CHECK(
135 boost::compute::is_sorted(vector.begin(), vector.end(), greater, queue)
136 );
137 }
138
139
BOOST_AUTO_TEST_CASE(sort_mid_vector_float)140 BOOST_AUTO_TEST_CASE(sort_mid_vector_float)
141 {
142 if(is_apple_cpu_device(device)) {
143 return;
144 }
145
146 using boost::compute::float_;
147 ::boost::compute::greater<float_> greater;
148 ::boost::compute::less<float_> less;
149
150 const int size = 513;
151 std::vector<float_> data(size);
152 for(int i = 0; i < size; i++){
153 data[i] = float_(i%2 ? i : -i);
154 }
155
156 boost::compute::vector<float_> vector(data.begin(), data.end(), queue);
157 BOOST_CHECK_EQUAL(vector.size(), size);
158 BOOST_CHECK(!boost::compute::is_sorted(vector.begin(), vector.end(), queue));
159
160 // <
161 boost::compute::detail::merge_sort_on_gpu(
162 vector.begin(), vector.end(), less, queue
163 );
164 BOOST_CHECK(
165 boost::compute::is_sorted(vector.begin(), vector.end(), less, queue)
166 );
167
168 // >
169 boost::compute::detail::merge_sort_on_gpu(
170 vector.begin(), vector.end(), greater, queue
171 );
172 queue.finish();
173
174 BOOST_CHECK(
175 boost::compute::is_sorted(vector.begin(), vector.end(), greater, queue)
176 );
177 }
178
BOOST_AUTO_TEST_CASE(sort_mid_vector_double)179 BOOST_AUTO_TEST_CASE(sort_mid_vector_double)
180 {
181 if(is_apple_cpu_device(device)) {
182 return;
183 }
184
185 if(!device.supports_extension("cl_khr_fp64")){
186 std::cout << "skipping test: device does not support double" << std::endl;
187 return;
188 }
189
190 using boost::compute::double_;
191 ::boost::compute::greater<double_> greater;
192 ::boost::compute::less<double_> less;
193
194 const int size = 1023;
195 std::vector<double_> data(size);
196 for(int i = 0; i < size; i++){
197 data[i] = double_(i%2 ? i : -i);
198 }
199
200 boost::compute::vector<double_> vector(data.begin(), data.end(), queue);
201 BOOST_CHECK_EQUAL(vector.size(), size);
202 BOOST_CHECK(!boost::compute::is_sorted(vector.begin(), vector.end(), queue));
203
204 // <
205 boost::compute::detail::merge_sort_on_gpu(
206 vector.begin(), vector.end(), less, queue
207 );
208 BOOST_CHECK(
209 boost::compute::is_sorted(vector.begin(), vector.end(), less, queue)
210 );
211
212 // >
213 boost::compute::detail::merge_sort_on_gpu(
214 vector.begin(), vector.end(), greater, queue
215 );
216 queue.finish();
217
218 BOOST_CHECK(
219 boost::compute::is_sorted(vector.begin(), vector.end(), greater, queue)
220 );
221 }
222
BOOST_AUTO_TEST_CASE(sort_mid_vector_int_custom_comparison_func)223 BOOST_AUTO_TEST_CASE(sort_mid_vector_int_custom_comparison_func)
224 {
225 if(is_apple_cpu_device(device)) {
226 return;
227 }
228
229 using boost::compute::int_;
230 ::boost::compute::greater<int_> greater;
231 ::boost::compute::less<int_> less;
232
233 const int_ size = 1024;
234 std::vector<int_> data(size);
235 for(int_ i = 0; i < size; i++){
236 data[i] = i%2 ? size - i : i - size;
237 }
238
239 BOOST_COMPUTE_FUNCTION(bool, abs_sort, (int_ a, int_ b),
240 {
241 return abs(a) < abs(b);
242 });
243
244 boost::compute::vector<int_> vector(data.begin(), data.end(), queue);
245 BOOST_CHECK_EQUAL(vector.size(), size);
246 BOOST_CHECK(
247 !boost::compute::is_sorted(vector.begin(), vector.end(), abs_sort, queue)
248 );
249
250 boost::compute::detail::merge_sort_on_gpu(
251 vector.begin(), vector.end(), abs_sort, queue
252 );
253 BOOST_CHECK(
254 boost::compute::is_sorted(vector.begin(), vector.end(), abs_sort, queue)
255 );
256 }
257
BOOST_AUTO_TEST_CASE(sort_mid_vector_int2)258 BOOST_AUTO_TEST_CASE(sort_mid_vector_int2)
259 {
260 if(is_apple_cpu_device(device)) {
261 return;
262 }
263
264 using boost::compute::int2_;
265 using boost::compute::int_;
266 ::boost::compute::greater<int2_> greater;
267 ::boost::compute::less<int2_> less;
268
269 const int_ size = 1024;
270 std::vector<int2_> data(size);
271 for(int_ i = 0; i < size; i++){
272 data[i] = i%2 ? int2_(i, i) : int2_(i - size, i - size);
273 }
274
275 BOOST_COMPUTE_FUNCTION(bool, abs_sort, (int2_ a, int2_ b),
276 {
277 return abs(a.x + a.y) < abs(b.x + b.y);
278 });
279
280 boost::compute::vector<int2_> vector(data.begin(), data.end(), queue);
281 BOOST_CHECK_EQUAL(vector.size(), size);
282 BOOST_CHECK(
283 !boost::compute::is_sorted(vector.begin(), vector.end(), abs_sort, queue)
284 );
285
286 boost::compute::detail::merge_sort_on_gpu(
287 vector.begin(), vector.end(), abs_sort, queue
288 );
289 BOOST_CHECK(
290 boost::compute::is_sorted(vector.begin(), vector.end(), abs_sort, queue)
291 );
292 }
293
BOOST_AUTO_TEST_CASE(sort_mid_vector_long8)294 BOOST_AUTO_TEST_CASE(sort_mid_vector_long8)
295 {
296 if(is_apple_cpu_device(device)) {
297 return;
298 }
299
300 using boost::compute::long8_;
301 using boost::compute::long_;
302 ::boost::compute::greater<long8_> greater;
303 ::boost::compute::less<long8_> less;
304
305 const long_ size = 256;
306 std::vector<long8_> data(size);
307 for(long_ i = 0; i < size; i++){
308 data[i] = i%2 ? long8_(i) : long8_(i * i);
309 }
310
311 BOOST_COMPUTE_FUNCTION(bool, comp, (long8_ a, long8_ b),
312 {
313 return a.s0 < b.s3;
314 });
315
316 boost::compute::vector<long8_> vector(data.begin(), data.end(), queue);
317 BOOST_CHECK_EQUAL(vector.size(), size);
318 BOOST_CHECK(
319 !boost::compute::is_sorted(vector.begin(), vector.end(), comp, queue)
320 );
321
322 boost::compute::detail::merge_sort_on_gpu(
323 vector.begin(), vector.end(), comp, queue
324 );
325 BOOST_CHECK(
326 boost::compute::is_sorted(vector.begin(), vector.end(), comp, queue)
327 );
328 }
329
BOOST_AUTO_TEST_CASE(stable_sort_vector_int2)330 BOOST_AUTO_TEST_CASE(stable_sort_vector_int2)
331 {
332 if(is_apple_cpu_device(device)) {
333 return;
334 }
335
336 using boost::compute::int2_;
337
338 int2_ data[] = {
339 int2_(8, 3), int2_(5, 1),
340 int2_(2, 1), int2_(6, 1),
341 int2_(8, 1), int2_(7, 1),
342 int2_(4, 1), int2_(8, 2)
343 };
344
345 BOOST_COMPUTE_FUNCTION(bool, comp, (int2_ a, int2_ b),
346 {
347 return a.x < b.x;
348 });
349
350 boost::compute::vector<int2_> vector(data, data + 8, queue);
351 BOOST_CHECK_EQUAL(vector.size(), 8);
352 BOOST_CHECK(
353 !boost::compute::is_sorted(vector.begin(), vector.end(), comp, queue)
354 );
355
356 //
357 boost::compute::detail::merge_sort_on_gpu(
358 vector.begin(), vector.end(), comp, true /*stable*/, queue
359 );
360 BOOST_CHECK(
361 boost::compute::is_sorted(vector.begin(), vector.end(), comp, queue)
362 );
363 CHECK_RANGE_EQUAL(
364 int2_, 8, vector,
365 (
366 int2_(2, 1), int2_(4, 1),
367 int2_(5, 1), int2_(6, 1),
368 int2_(7, 1), int2_(8, 3),
369 int2_(8, 1), int2_(8, 2)
370 )
371 );
372 }
373
374 BOOST_AUTO_TEST_SUITE_END()
375