GPUを用いた分枝限定法におけるメモリ参照効率を高めるための配列パッキング手法

概要

論文の詳細を見る
本稿では,GPU (Graphics Processing Unit) における分枝限定法の高速化を目的として,メモリ参照効率を高めるための配列パッキング手法を提案する.提案手法は,CPU の替わりに GPU が配列を詰め込むことにより,CPU・GPU 間のデータ転送を最小限に抑える.詰め込みにより配列を密に維持でき,分枝限定操作におけるメモリ参照効率を高める.GPU 上の詰め込みは,よく知られた並列 prefix sums アルゴリズムに基づく.さらに,多くの対象問題において配列要素の並び順を詰め込みの前後で維持する必要がないことに着目し,in-place 型の詰め込みを実現する.これにより,入力配列と出力配列を区別する (非 in-place な) 単純手法と比較して,およそ 2 倍の部分問題を GPU 上で並列処理できる.ナップザック問題を用いた実験では,CPU 上で配列を詰め込む既存手法と比較して 1.15 倍の速度向上を得た.また,in-place 版は非 in-place 版と比べて扱える部分問題の数を増やせたが,性能は 8.8% 減少した.
2013-09-23