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

この論文にアクセスする

この論文をさがす

抄録

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.

収録刊行物

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

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

各種コード

  • NII論文ID(NAID)
    170000079468
  • NII書誌ID(NCID)
    AN10096105
  • 本文言語コード
    ENG
  • 資料種別
    Technical Report
  • データ提供元
    IPSJ 
ページトップへ