Sorting Large Multifield Records on a GPU

摘要

We extend the fastest comparison based (sample sort) and non-comparison based (radix sort) number sorting algorithms on a GPU to sort large multifield records. Two extensions - direct (the entire record is moved whenever its key is to be moved) and indirect ((key, index) pairs are sorted using the direct extension and then records are ordered according to the obtained index permutation) are discussed. Our results show that for the By Field layout, the direct extension of the radix sort algorithm GRS[1] is the fastest for 32-bit keys when records have at least 12 fields, otherwise, the direct extension of the radix sort algorithm SRTS[14] is the fastest. For the Hybrid layout, the indirect extension of SRTS is the fastest for records with 2 or more keys.