Deakin University
Browse

Parallel bucket sorting on graphics processing units based on convex optimization

Version 2 2024-06-06, 05:41
Version 1 2023-10-26, 04:22
journal contribution
posted on 2023-10-26, 04:22 authored by Gleb BeliakovGleb Beliakov, Gang LiGang Li, Shaowu Liu
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.

History

Journal

Optimization

Volume

64

Pagination

1033 - 1055

Location

Abingdon, Eng.

ISSN

0233-1934

eISSN

1029-4945

Language

eng

Publication classification

C1 Refereed article in a scholarly journal

Copyright notice

2013, Taylor & Francis

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC