講演名 2013-05-20
六目並べハードウェアデザインコンテストへの挑戦(基調講演,リコンフィギャラブルシステム,一般)
佐野 健太郎,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) 本稿では、FPGAデザインコンテストのために開発した六目並べハードウェアソルバーNexus6-mk3について、そのアルゴリズム、アーキテクチャ、実装と性能を解説する。このソルバーは、本研究で提案する探索候補の2段階生成手法にアルファベータ枝刈り法を組み合わせたmini-Max深さ優先探索により、探索時間を大幅に削減している。評価関数の計算や探索候補である子ノード生成の細粒度並列性を活用するハードウェアアクセラレータにより、110MHz動作のNIOS IIプロセッサおよび2.93GHz動作のCore i7プロセッサ単一コアに対し、それぞれ約8万倍と640倍の速度向上が達成された。使用したFPGAボードは安価で消費電力が低く、コスト性能比や電力性能比の点でも、FPGAによるソルバーはソフトウェア実装と比べて非常に優れた実現方法であることが示された。
抄録(英) This paper describes an algorithm, an architecture, and implementation of our Connect6 hardware solver, called Nexus6-mk3, to be used in several design competition series. Nexus6-mk3 is based on our proposed two-level move refinement method and the alpha-beta pruning method to reduce time of depth-first search by the mini-Max algorithm. The hardware accelerator on FPGA achieves about 80000 and 640 times faster processing than an NIOS II processor at 110MHz on FPGA and a single core of Intel Core i7 processor running at 2.93 GHz, respectively. The solution with a very cheap and low-power FPGA demonstrates that the FPGA-based solver is advantageous not only for processing performance, but also performance per cost and performance per power.
キーワード(和) 六目並べソルバー / FPGA / ハードウェアアクセラレータ / ゲーム木探索
キーワード(英) Connect6 solver / FPGA / hardware accelerator / game-tree search
資料番号 RECONF2013-1
発行日

研究会情報
研究会 RECONF
開催期間 2013/5/13(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Reconfigurable Systems (RECONF)
本文の言語 JPN
タイトル(和) 六目並べハードウェアデザインコンテストへの挑戦(基調講演,リコンフィギャラブルシステム,一般)
サブタイトル(和)
タイトル(英) Challenging Connect6 Hardware Design Competitions
サブタイトル(和)
キーワード(1)(和/英) 六目並べソルバー / Connect6 solver
キーワード(2)(和/英) FPGA / FPGA
キーワード(3)(和/英) ハードウェアアクセラレータ / hardware accelerator
キーワード(4)(和/英) ゲーム木探索 / game-tree search
第 1 著者 氏名(和/英) 佐野 健太郎 / Kentaro SANO
第 1 著者 所属(和/英) 東北大学大学院情報科学研究科
Graduate School of Information Sciences, Tohoku University
発表年月日 2013-05-20
資料番号 RECONF2013-1
巻番号(vol) vol.113
号番号(no) 52
ページ範囲 pp.-
ページ数 6
発行日