講演抄録/キーワード |
講演名 |
2016-03-02 09:25
最大カット問題の高速求解に向けた二次元イジングモデルのFPGA実装 ○業天英範・廣本正之・佐藤高史(京大) VLD2015-133 |
抄録 |
(和) |
組合せ最適化問題を解く方法としてイジングモデルを用いた解法が最近注目されている.この解法では極めて高い並列性が得られるため,従来手法より高速な計算が可能となる.本稿では,FPGAを用いて実装した二次元イジングモデルにより組合せ最適化問題を解き,その性能を評価する.既存の整数計画法によるソフトウェアソルバと提案手法で最大カット問題のベンチマークを解き,提案手法が$10^5$倍高速に厳密解の92%以上の精度の解を求められることを確認した. |
(英) |
Ising-model-based solver attracts increasing attention as an excellent candidate for solving the combinatorial optimization problem.
The solver solves the problems in a highly parallel manner, realizing very fast calculation.
In this paper, we implemented an FPGA-based 2D-ising-model solver for the max-cut problem.
Through numerical experiments, it was demonstrated that our proposed solver is five orders of magnitude faster than the existing software-based solver utilizing integer linear programming (ILP), in solving max-cut problem benchmarks at 92% quality to the optimal solution. |
キーワード |
(和) |
組合せ最適化問題 / 最大カット問題 / イジングモデル / アニーリング / FPGA / / / |
(英) |
combinatorial optimization problem / max-cut problem / ising model / annealing / FPGA / / / |
文献情報 |
信学技報, vol. 115, no. 465, VLD2015-133, pp. 125-130, 2016年2月. |
資料番号 |
VLD2015-133 |
発行日 |
2016-02-22 (VLD) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
VLD2015-133 |