Details

Autor(en) / Beteiligte

• Kobus, Robin
• Nelgen, Johannes
• Henkys, Valentin
• Schmidt, Bertil

Titel

Faster Segmented Sort on GPUs

Ist Teil von

• Euro-Par 2023: Parallel Processing, p.664-678

Ort / Verlag

Cham: Springer Nature Switzerland

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• Efficient parallel implementations of various sorting algorithms on modern hardware platforms are essential to numerous application areas. In this paper, we first measure the performance of the leading segmented sort implementation on CUDA-enabled GPUs and determine optimal setups using the resulting runtimes. Subsequently, we propose a number of changes that improve efficiency for segments of specific lengths. Furthermore, an alternative key-only version is introduced, that is specifically optimized to just sort keys instead of key-value pairs, which allows for further optimization. Performance is evaluated by comparing runtimes of the original algorithm with our improved version for segments of different lengths resulting in average speedups between 1.26 and 1.35 on four GPUs of different generations (Pascal, Volta, Ampere, Ada Lovelace). Furthermore, comparison to alternative segmented sort implementations from CUB and ModernGPU results in average speedups of at least 2.2 and 2.5, respectively, across all tested architectures. To illustrate how our improved sorting algorithm can be beneficial in a practical application, we have integrated it into the MetaCache-GPU pipeline for metagenomic DNA classification resulting in speedups of up to 25.6% for the sorting step. Code is publicly available at https://gitlab.rlp.net/pararch/faster-segmented-sort-on-gpus.