Presentation | 2021-09-10 Parallel Calculation of Local Scores in Bayesian Network Structure Learning using FPGA Ryota Miyagi, Hideki Takase, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | 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. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | FPGA / Bayesian networks / reconfigurable computing / codesign |
Paper # | RECONF2021-22 |
Date of Issue | 2021-09-03 (RECONF) |
Conference Information | |
Committee | RECONF |
---|---|
Conference Date | 2021/9/10(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Online |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Reconfigurable system, etc. |
Chair | Kentaro Sano(RIKEN) |
Vice Chair | Yoshiki Yamaguchi(Tsukuba Univ.) / Tomonori Izumi(Ritsumeikan Univ.) |
Secretary | Yoshiki Yamaguchi(NEC) / Tomonori Izumi(Tokyo Inst. of Tech.) |
Assistant | Yukitaka Takemura(INTEL) / Yasunori Osana(Ryukyu Univ.) |
Paper Information | |
Registration To | Technical Committee on Reconfigurable Systems |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Parallel Calculation of Local Scores in Bayesian Network Structure Learning using FPGA |
Sub Title (in English) | |
Keyword(1) | FPGA |
Keyword(2) | Bayesian networks |
Keyword(3) | reconfigurable computing |
Keyword(4) | codesign |
1st Author's Name | Ryota Miyagi |
1st Author's Affiliation | Kyoto University(Kyoto Univ.) |
2nd Author's Name | Hideki Takase |
2nd Author's Affiliation | The University of Tokyo/JST PRESTO(U. Tokyo/JST) |
Date | 2021-09-10 |
Paper # | RECONF2021-22 |
Volume (vol) | vol.121 |
Number (no) | RECONF-175 |
Page | pp.pp.30-35(RECONF), |
#Pages | 6 |
Date of Issue | 2021-09-03 (RECONF) |