AGPUモデルでの並列ソートアルゴリズムの計算量について

摘要

本稿ではAGPUモデルにおける並列ソートアルゴリズムの計算量を扱う．まず，既存のバイトニックソートとGPU-Warpsortの計算量を解析する．次に，AGPUモデルでの比較ソートのI／O計算量の下界を与える．1マルチプロセッサ内のコア数をわ，総コア数をp，マルチプロセッサ内の総共有メモリ量をMワードとすると，n要素の比較ソートに必要なグローバルメモリ読み込み回数はΩ（(n/b)log_(M/p)(n/b)）である．さらに，I／O計算量がこの下界に一致するソートアルゴリズムを提案する．時間計算量はO（(n/p)log(n/b)logb）である．