| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | VLD |
| 開催期間 | 2016-02-29 - 2016-03-02 |
| 開催地（和） | 沖縄県青年会館 |
| 開催地（英） | Okinawa Seinen Kaikan |
| テーマ（和） | システムオンシリコンを支える設計技術 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2016-02-VLD |
| 本文の言語 | 日本語 |
| タイトル（和） | 最大カット問題の高速求解に向けた二次元イジングモデルのFPGA実装 |
| サブタイトル（和） | |
| タイトル（英） | An FPGA Implementation of Fast 2D-Ising-Model Solver for the Max-Cut Problem |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 組合せ最適化問題 / combinatorial optimization problem |
| キーワード(2)（和/英） | 最大カット問題 / max-cut problem |
| キーワード(3)（和/英） | イジングモデル / ising model |
| キーワード(4)（和/英） | アニーリング / annealing |
| キーワード(5)（和/英） | FPGA / FPGA |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 業天 英範 / Hidenori Gyoten / ギョウテン ヒデノリ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 廣本 正之 / Masayuki Hiromoto / ヒロモト マサユキ |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 佐藤 高史 / Takashi Sato / サトウ タカシ |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-03-02 09:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2015-133 |
| 巻番号（vol） | vol.115 |
| 号番号（no） | no.465 |
| ページ範囲 | pp.125-130 |
| ページ数 | 6 |
| 発行日 | 2016-02-22 (VLD) |
[研究会発表申込システムのトップページに戻る]