講演名 2021-09-10
ベイジアンネットワークの構造学習におけるローカルスコア計算のFPGAによる並列化
宮城 竜大(京大), 高瀬 英希(東大/JSTさきがけ),
PDFダウンロードページ PDFダウンロードページへ
抄録(和) ベイジアンネットワーク(BN)は,データセット内の変数間の関係を表す有向非巡回グラフである.最適なBN構造の学習は一般的にNP困難であるため,利用可能なメモリ量に応じてスケーラビリティが制限されるのが一般的である.本論文では,FPGAを用いて最適なBN構造を学習するための新しいスケーラブルな手法を提案する.必要なメモリ量を削減するため,本手法ではローカルスコアを計算する親集合のサイズを制限し,その結果を保存しない.そのため,指数関数的なサイズのローカルスコア全体を保存しなければならない従来の動的計画法と比較して,本手法はメモリ効率の点で有利である.さらに,処理要素を並列に繰り返し使用して少ない論理資源で高い並列性を抽出できるローカルスコアの計算方法を提案する.30変数のBNを用いて評価した結果,アクセラレータはシングルコアの実装に比べてローカルスコアを最大230倍高速に計算し,その性能はFPGAリソースの増加に伴って劇的に向上した.また,アクセラレータを用いた構造学習は,シングルコア実装を用いた構造学習に比べて,最大で3.5倍の速度で実行された.
抄録(英) Bayesian network (BN) is a directed acyclic graph that represents relationships among variables in data sets. Because learning optimal BN structure is generally NP-hard, the scalability is typically limited depending on the amount of available memory. This paper proposes a novel scalable method for learning optimal BN structure using FPGA. To reduce the amount of required memory, our approach limits the size of the parent set to calculate local scores and does not store their results. Therefore, our method has an advantage in terms of memory efficiency compared with previous dynamic programming algorithms, which have to store entire exponentially-sized local scores. We further propose a calculation method of local scores with the iterative use of processing elements in parallel. Evaluated with a 30-variable BN, the accelerator calculated local scores up to 230 times faster than the single-core implementation, and its performance improved dramatically with increasing FPGA resources. Furthermore, structure learning with the accelerator performed up to 3.5 times faster than structure learning with the single-core implementation.
キーワード(和) FPGA / ベイジアンネットワーク / 再構成可能コンピューティング / 協調設計
キーワード(英) FPGA / Bayesian networks / reconfigurable computing / codesign
資料番号 RECONF2021-22
発行日 2021-09-03 (RECONF)

研究会情報
研究会 RECONF
開催期間 2021/9/10(から1日開催)
開催地(和) オンライン開催
開催地(英) Online
テーマ(和) リコンフィギャラブルシステム,一般
テーマ(英) Reconfigurable system, etc.
委員長氏名(和) 佐野 健太郎(理研)
委員長氏名(英) Kentaro Sano(RIKEN)
副委員長氏名(和) 山口 佳樹(筑波大) / 泉 知論(立命館大)
副委員長氏名(英) Yoshiki Yamaguchi(Tsukuba Univ.) / Tomonori Izumi(Ritsumeikan Univ.)
幹事氏名(和) 小林 悠記(NEC) / 中原 啓貴(東工大)
幹事氏名(英) Yuuki Kobayashi(NEC) / Hiroki Nakahara(Tokyo Inst. of Tech.)
幹事補佐氏名(和) 竹村 幸尚(インテル) / 長名 保範(琉球大学)
幹事補佐氏名(英) Yukitaka Takemura(INTEL) / Yasunori Osana(Ryukyu Univ.)

講演論文情報詳細
申込み研究会 Technical Committee on Reconfigurable Systems
本文の言語 JPN
タイトル(和) ベイジアンネットワークの構造学習におけるローカルスコア計算のFPGAによる並列化
サブタイトル(和)
タイトル(英) Parallel Calculation of Local Scores in Bayesian Network Structure Learning using FPGA
サブタイトル(和)
キーワード(1)(和/英) FPGA / FPGA
キーワード(2)(和/英) ベイジアンネットワーク / Bayesian networks
キーワード(3)(和/英) 再構成可能コンピューティング / reconfigurable computing
キーワード(4)(和/英) 協調設計 / codesign
第 1 著者 氏名(和/英) 宮城 竜大 / Ryota Miyagi
第 1 著者 所属(和/英) 京都大学(略称:京大)
Kyoto University(略称:Kyoto Univ.)
第 2 著者 氏名(和/英) 高瀬 英希 / Hideki Takase
第 2 著者 所属(和/英) 東京大学/JSTさきがけ(略称:東大/JSTさきがけ)
The University of Tokyo/JST PRESTO(略称:U. Tokyo/JST)
発表年月日 2021-09-10
資料番号 RECONF2021-22
巻番号(vol) vol.121
号番号(no) RECONF-175
ページ範囲 pp.30-35(RECONF),
ページ数 6
発行日 2021-09-03 (RECONF)