Parallel Calculation of Local Scores in Bayesian Network Structure Learning using FPGA

• Item type: Symposium(1)
• 公開日: 2022-01-28
• タイトル: Parallel Calculation of Local Scores in Bayesian Network Structure Learning using FPGA
• タイトル / 言語: en
• タイトル: Parallel Calculation of Local Scores in Bayesian Network Structure Learning using FPGA
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Kyoto University
• 著者所属: University of Tokyo
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): University of Tokyo
• 著者名: Ryota, Miyagi; Hideki, Takase
• 著者名(英): Ryota, Miyagi; Hideki, Takase
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A Bayesian network (BN) is a directed acyclic graph that represents the relationships among variables in datasets. Because learning an optimal BN structure is generally NP-hard, scalability is typically limited depending on the amount of available memory. This study proposes a novel scalable method for learning an optimal BN structure using a field-programmable gate array (FPGA). To reduce the amount of required memory, the approach limits the size of the parent set to calculate local scores and does not store the results. Therefore, the proposed method has an advantage over previous dynamic programming algorithms in terms of memory efficiency because these existing algorithms store all exponentially sized local scores. Furthermore, we propose an accelerator for local scores calculation by iteratively processing elements in parallel. When it was 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 drastically with increasing FPGA resources. Moreover, structure learning with the accelerator was performed up to 3.5 times faster than structure learning with the single-core implementation.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A Bayesian network (BN) is a directed acyclic graph that represents the relationships among variables in datasets. Because learning an optimal BN structure is generally NP-hard, scalability is typically limited depending on the amount of available memory. This study proposes a novel scalable method for learning an optimal BN structure using a field-programmable gate array (FPGA). To reduce the amount of required memory, the approach limits the size of the parent set to calculate local scores and does not store the results. Therefore, the proposed method has an advantage over previous dynamic programming algorithms in terms of memory efficiency because these existing algorithms store all exponentially sized local scores. Furthermore, we propose an accelerator for local scores calculation by iteratively processing elements in parallel. When it was 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 drastically with increasing FPGA resources. Moreover, structure learning with the accelerator was performed up to 3.5 times faster than structure learning with the single-core implementation.
• 書誌情報: Proceedings of Asia Pacific Conference on Robot IoT System Development and Platform; 巻 2021, p. 69-74, 発行日 2022-01-28
• 出版者 / 言語: ja
• 出版者: 情報処理学会