GPUを用いた分枝限定法におけるメモリ参照効率を高めるための配列パッキング手法
書誌事項
- タイトル別名
-
- An Array Packing Method for Increasing Memory Reference Efficiency of the Branch and Bound Method on a 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 (2), 1-7, 2013-09-23
一般社団法人情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1573105977757929472
-
- NII論文ID
- 110009606423
-
- NII書誌ID
- AN10463942
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles