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% 減少した.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1573105977757929472
  • NII論文ID
    110009606423
  • NII書誌ID
    AN10463942
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ