Parallel Butterfly Sorting Algorithm on GPU
Bilal Jan, Bartolomeo Montrucchio, Carlo Stefano Ragusa, Fiaz G. Khan, Omar Khan · 2013
Efficient sorting is vital for overall performance of the underlying application. This paper presents Butterfly Network Sort (BNS) for sorting large data sets. A minimal version of the algorithm Min-Max Butterfly is also shown for searching minimum and maximum values in data. Both algorithms are implemented on GPUs using OpenCL exploiting data parallelism model. Results obtained on different GPU architectures show better performance of butterfly sorting in terms of sorting time and rate. The comparison of butterfly sorting with other algorithms:bitonic, odd-even and rank sort show significant speedup improvements against all on Nvidia Quadro-6000 GPU with relatively better sorting time and rate