MSD Radix String Sort on GPU: Longer Keys, Shorter Alphabets

Access this Article

Search this Article

Abstract

This study proposes a GPU implementation of radix sort, which has so far been most successfully presented in the Thrust library from Cuda SDK. While Thrust performs sorting starting from least significant digit (LSD) to benefit from GPU architecture features, it can deal only with fixed-length keys. Our solution features MSD radix sort or bucket sort which allows for variable length keys, but is recursive and therefore difficult to implement on GPU. However, we achieved comparable performance by performing the sorting in several stages which use different parallelization schemes depending on the size and number of buckets. This solution also benefits from shorter alphabets and would be particularly efficient for, e.g., genomic data.This study proposes a GPU implementation of radix sort, which has so far been most successfully presented in the Thrust library from Cuda SDK. While Thrust performs sorting starting from least significant digit (LSD) to benefit from GPU architecture features, it can deal only with fixed-length keys. Our solution features MSD radix sort or bucket sort which allows for variable length keys, but is recursive and therefore difficult to implement on GPU. However, we achieved comparable performance by performing the sorting in several stages which use different parallelization schemes depending on the size and number of buckets. This solution also benefits from shorter alphabets and would be particularly efficient for, e.g., genomic data.

Journal

  • 研究報告計算機アーキテクチャ(ARC)

    研究報告計算機アーキテクチャ(ARC) 2013-ARC-207(21), 1-6, 2013-12-09

Codes

  • NII Article ID (NAID)
    170000079468
  • NII NACSIS-CAT ID (NCID)
    AN10096105
  • Text Lang
    ENG
  • Article Type
    Technical Report
  • Data Source
    IPSJ 
Page Top