GPUを用いた並列ソートアルゴリズムの実装と評価

摘要

GPUを用いた並列比較ソートアルゴリズムを扱う．GPU上でプログラムを高速動作させる場合，コアの計算量だけでなくメモリアクセスについても適切に考慮する必要がある．筆者らはGPU上のアルゴリズムを評価するためのモデルとしてAGPUモデルを提案しており，本モデルではI／O計算量を用いることにより，メモリアクセスの評価を行うことができる．また，筆者らはGPU上での比較ソートに関して，I／O計算量のオーダーが理論的な下界と一致するアルゴリズムを提案している．本稿ではアルゴリズムを実装し，実GPU上で評価を行うことで，本アルゴリズムの有効性を示す．