GPU計算におけるSIMTを考慮したQAPの効率的な並列計算解法について

カテゴリ: 部門大会

論文No: TC3-13

グループ名: 【C】平成23年電気学会電子・情報・システム部門大会講演論文集

発行日: 2011/09/07

タイトル(英語): An Efficient Parallel Solving of QAP using GPU with SIMT Feature

著者名: 筒井 茂義(阪南大学)

著者名(英語): Shigeyoshi Tsutsui(Hannan University)

キーワード: GPU計算|QAP|SIMT|ACO|タブーサーチ|GPU computation|QAP|SIMT|ACO|Taboo Search

要約(日本語): QAP（2次割当て問題）は解くことが困難な代表的な組合せ最適化問題の一つである。解法には進化計算にローカルサーチを組合せる方法が有効である。ここでは、ACOを適用しローカルサーチにはタブーサーチを用いる方法をGPU計算により並列高速に解く方法について述べる。GPUは超多スレッドプログラミングによる並列計算が可能であるが、SIMT (単一命令複数スレッド、single-instruction, multiple-thread) と呼ばれる方式であるため、分岐命令が多い問題では並列化の効果が低下する。ここではQAPを解く際におけるこの問題を解決する手法について述べ、提案方式が有効であることを示す。

PDFファイルサイズ: 5,236 Kバイト