GPU accelerate parallel Odd-Even merge sort: An OpenCL method

摘要

Odd-Even merge sort is a basic problem in computer supported cooperative work in design area. However, it is not effective because of the high complexity O(nlg²n) in CPU platform. In this paper, we present a novel implementation based on the OpenCL programming model on recent GPU (Graphic Processing Unit). Our implementation was based on Knuth''s algorithm and do some change. Due to limitations of OpenCL, we utilize a flag variable to make it avoid the direct backward control flow. As results, our implementation achieves 18× speedups compared with the CPU C++ STL quick sort. And it gets almost linear speedup for next generations of GPU because of the complete parallelism in each iteration process. Meanwhile, our approach makes the odd-even merge sort effectively in practice because of the high performance. Furthermore, the approach used in this paper for cooperating thousands of processing units to parallel process can also be used in other cooperation areas.