compute/algorithm/sort.hpp

0001 //---------------------------------------------------------------------------//
0002 // Copyright (c) 2013 Kyle Lutz <kyle.r.lutz@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_SORT_HPP
0012 #define BOOST_COMPUTE_ALGORITHM_SORT_HPP
0013
0014 #include <iterator>
0015
0016 #include <boost/utility/enable_if.hpp>
0017
0018 #include <boost/compute/system.hpp>
0019 #include <boost/compute/command_queue.hpp>
0020 #include <boost/compute/algorithm/detail/merge_sort_on_cpu.hpp>
0021 #include <boost/compute/algorithm/detail/merge_sort_on_gpu.hpp>
0022 #include <boost/compute/algorithm/detail/radix_sort.hpp>
0023 #include <boost/compute/algorithm/detail/insertion_sort.hpp>
0024 #include <boost/compute/algorithm/reverse.hpp>
0025 #include <boost/compute/container/mapped_view.hpp>
0026 #include <boost/compute/detail/iterator_range_size.hpp>
0027 #include <boost/compute/iterator/buffer_iterator.hpp>
0028 #include <boost/compute/type_traits/is_device_iterator.hpp>
0029
0030 namespace boost {
0031 namespace compute {
0032 namespace detail {
0033
0034 template<class T>
0035 inline void dispatch_gpu_sort(buffer_iterator<T> first,
0036                               buffer_iterator<T> last,
0037                               less<T>,
0038                               command_queue &queue,
0039                               typename boost::enable_if_c<
0040                                   is_radix_sortable<T>::value
0041                               >::type* = 0)
0042 {
0043     size_t count = detail::iterator_range_size(first, last);
0044
0045     if(count < 2){
0046         // nothing to do
0047         return;
0048     }
0049     else if(count <= 32){
0050         ::boost::compute::detail::serial_insertion_sort(first, last, queue);
0051     }
0052     else {
0053         ::boost::compute::detail::radix_sort(first, last, queue);
0054     }
0055 }
0056
0057 template<class T>
0058 inline void dispatch_gpu_sort(buffer_iterator<T> first,
0059                               buffer_iterator<T> last,
0060                               greater<T> compare,
0061                               command_queue &queue,
0062                               typename boost::enable_if_c<
0063                                   is_radix_sortable<T>::value
0064                               >::type* = 0)
0065 {
0066     size_t count = detail::iterator_range_size(first, last);
0067
0068     if(count < 2){
0069         // nothing to do
0070         return;
0071     }
0072     else if(count <= 32){
0073         ::boost::compute::detail::serial_insertion_sort(
0074             first, last, compare, queue
0075         );
0076     }
0077     else {
0078         // radix sorts in descending order
0079         ::boost::compute::detail::radix_sort(first, last, false, queue);
0080     }
0081 }
0082
0083 template<class Iterator, class Compare>
0084 inline void dispatch_gpu_sort(Iterator first,
0085                               Iterator last,
0086                               Compare compare,
0087                               command_queue &queue)
0088 {
0089     size_t count = detail::iterator_range_size(first, last);
0090
0091     if(count < 2){
0092         // nothing to do
0093         return;
0094     }
0095     else if(count <= 32){
0096         ::boost::compute::detail::serial_insertion_sort(
0097             first, last, compare, queue
0098         );
0099     }
0100     else {
0101         ::boost::compute::detail::merge_sort_on_gpu(
0102             first, last, compare, queue
0103         );
0104     }
0105 }
0106
0107 // sort() for device iterators
0108 template<class Iterator, class Compare>
0109 inline void dispatch_sort(Iterator first,
0110                           Iterator last,
0111                           Compare compare,
0112                           command_queue &queue,
0113                           typename boost::enable_if<
0114                               is_device_iterator<Iterator>
0115                           >::type* = 0)
0116 {
0117     if(queue.get_device().type() & device::gpu) {
0118         dispatch_gpu_sort(first, last, compare, queue);
0119         return;
0120     }
0121     ::boost::compute::detail::merge_sort_on_cpu(first, last, compare, queue);
0122 }
0123
0124 // sort() for host iterators
0125 template<class Iterator, class Compare>
0126 inline void dispatch_sort(Iterator first,
0127                           Iterator last,
0128                           Compare compare,
0129                           command_queue &queue,
0130                           typename boost::disable_if<
0131                               is_device_iterator<Iterator>
0132                           >::type* = 0)
0133 {
0134     typedef typename std::iterator_traits<Iterator>::value_type T;
0135
0136     size_t size = static_cast<size_t>(std::distance(first, last));
0137
0138     // create mapped buffer
0139     mapped_view<T> view(
0140         boost::addressof(*first), size, queue.get_context()
0141     );
0142
0143     // sort mapped buffer
0144     dispatch_sort(view.begin(), view.end(), compare, queue);
0145
0146     // return results to host
0147     view.map(queue);
0148 }
0149
0150 } // end detail namespace
0151
0152 /// Sorts the values in the range [\p first, \p last) according to
0153 /// \p compare.
0154 ///
0155 /// \param first first element in the range to sort
0156 /// \param last last element in the range to sort
0157 /// \param compare comparison function (by default \c less)
0158 /// \param queue command queue to perform the operation
0159 ///
0160 /// For example, to sort a vector on the device:
0161 /// \code
0162 /// // create vector on the device with data
0163 /// float data[] = { 2.f, 4.f, 1.f, 3.f };
0164 /// boost::compute::vector<float> vec(data, data + 4, queue);
0165 ///
0166 /// // sort the vector on the device
0167 /// boost::compute::sort(vec.begin(), vec.end(), queue);
0168 /// \endcode
0169 ///
0170 /// The sort() algorithm can also be directly used with host iterators. This
0171 /// example will automatically transfer the data to the device, sort it, and
0172 /// then transfer the data back to the host:
0173 /// \code
0174 /// std::vector<int> data = { 9, 3, 2, 5, 1, 4, 6, 7 };
0175 ///
0176 /// boost::compute::sort(data.begin(), data.end(), queue);
0177 /// \endcode
0178 ///
0179 /// Space complexity: \Omega(n)
0180 ///
0181 /// \see is_sorted()
0182 template<class Iterator, class Compare>
0183 inline void sort(Iterator first,
0184                  Iterator last,
0185                  Compare compare,
0186                  command_queue &queue = system::default_queue())
0187 {
0188     ::boost::compute::detail::dispatch_sort(first, last, compare, queue);
0189 }
0190
0191 /// \overload
0192 template<class Iterator>
0193 inline void sort(Iterator first,
0194                  Iterator last,
0195                  command_queue &queue = system::default_queue())
0196 {
0197     typedef typename std::iterator_traits<Iterator>::value_type value_type;
0198
0199     ::boost::compute::sort(
0200         first, last, ::boost::compute::less<value_type>(), queue
0201     );
0202 }
0203
0204 } // end compute namespace
0205 } // end boost namespace
0206
0207 #endif // BOOST_COMPUTE_ALGORITHM_SORT_HPP