Parallel bucket sorting on graphics processing units based on convex optimization
Data(s) |
01/01/2015
|
---|---|
Resumo |
We found an interesting relation between convex optimization and sorting problem. We present a parallel algorithm to compute multiple order statistics of the data by minimizing a number of related convex functions. The computed order statistics serve as splitters that group the data into buckets suitable for parallel bitonic sorting. This led us to a parallel bucket sort algorithm, which we implemented for many-core architecture of graphics processing units (GPUs). The proposed sorting method is competitive to the state-of-the-art GPU sorting algorithms and is superior to most of them for long sorting keys. |
Identificador | |
Idioma(s) |
eng |
Publicador |
Taylor & Francis |
Relação |
http://dro.deakin.edu.au/eserv/DU:30056837/beliakov-parallelbucket-2015.pdf http://dro.deakin.edu.au/eserv/DU:30056837/beliakov-parallelbucket-inpress-2013.pdf http://dx.doi.org/10.1080/02331934.2013.836645 |
Direitos |
2013, Taylor & Francis |
Palavras-Chave | #convex optimization #cutting plane method #GPU #order statistic #parallel selection #parallel sorting |
Tipo |
Journal Article |