On Sorting and Load-Balancing on GPUs

In this paper we present GPU-Quicksort, an efficientQuicksort algorithm suitable for highly parallel multi-coregraphics processors. Quicksort has previously been consideredas an inefficient sorting solution for graphics processors,but we show that GPU-Quicksort often performs betterthan the fastest known sorting implementations for graphicsprocessors, such as radix and bitonic sort. Quicksortcan thus be seen as a viable alternative for sorting largequantities of data on graphics processors.We also present a comparison of different load balancingschemes. To get maximum performance on the manycoregraphics processors it is important to have an evenbalance of the workload so that all processing units contributeequally to the task at hand. This can be hard toachieve when the cost of a task is not known beforehandand when new sub-tasks are created dynamically during execution.With the recent advent of scatter operations andatomic hardware primitives it is now possible to bring someof the more elaborate dynamic load balancing schemes fromthe conventional SMP systems domain to the graphics processordomain