Title:	A COMPARISON-FREE SORTING ALGORITHM ON CPUs
Author(s):	Saleh Abdel-hafeez, Ann Gordon-Ross and Samer Abubaker
ISBN:	978-989-8533-56-2
Editors:	Hans Weghorn
Year:	2016
Edition:	Single
Keywords:	Comparison-Free, Large Data, Parallel Computing, SIMD, Sorting Algorithms
Type:	Full Paper
First Page:	3
Last Page:	10
Language:	English
Cover:
Full Contents:	click to dowload
Paper Abstract:	The paper presents a new sorting algorithm that takes input data integer elements and sorts them without any comparison operations between the data—a comparison-free sorting. The algorithm uses a one-hot representation for each input element that is stored in a two-dimensional matrix called a one-hot matrix. Concurrently, each input element is also stored in a one-dimensional matrix in the input element’s integer representation. Subsequently, the transposed one-hot matrix is mapped to a binary matrix producing a sorted matrix with all elements in their sorted order. The algorithm exploits parallelism that is suitable for single instruction multiple thread (SIMT) computing that can harness the resources of these computing machines, such as CPUs with multiple cores and GPUs with large thread blocks. We analyze our algorithm’s sorting time on varying CPU architectures, including single- and multi-threaded implementations on a single CPU. Our results show a fast sorting time for the single-threaded implementation that surpasses most common sorting algorithms with an average speedup of 6X for a number of input elements ranging from 23 to 230. Additional analysis using 8 threads with varying single-instruction-multiple-data (SIMD) widths shows an average speedup of 3.9X as compared to current parallel sorting algorithms for larger input sizes on the order of 230 and higher.
	Go Back