An FPGA Accelerator of Bayesian Network Structure Learning
Using Parallel Calculation of Local Scores∗∗∗

Ryota Miyagi Hideki Takase∗
Kyoto University ∗∗The University of Tokyo
Bayesian Networks

Log-Gamma Function Calculation▶ Probabilistic graphical model that encodes conditional independence relations
among random variables using DAG.
▶ Application in various ﬁelds (e.g. medical diagnosis, ﬁnancial analysis, genetic
phylogenetic analysis, gene sequence analysis, etc.)

Each local score calculation requires log-gamma function of given value.

Structure Learning▶ Learning DAG structure of BN from data▶ However, optimal structure learning is NP-hard and time-consuming.
PSCX

D

1000001010100

1000

10

Pollution

Smoker

XRay
Pollution

Dyspnoea

SmokerCancerDyspnoea

Pollution

SmokerCancer1...

XRay

Dyspnoeas(D, G) = LocalScore(x1, ∅, D)+ LocalScore(x2, ∅, D)+ LocalScore(x3, ∅, D)+ LocalScore(x4, {x1, x2}, D)+ LocalScore(x5, {x1, x2}, D)+ LocalScore(x6, {x3, x4}, D)

XRay

Evaluationx3

x1xx22x4xx55x6

Research Objective and Our Approach
Research Objective
Accelerate local score calculation for large BNs structure learning with
▶ Domain-speciﬁc dataﬂow architecture using FPGAs▶ Parallelization by utilizing FPGA resources▶ Scalable implementation for FPGA clusters
Our Approach
Each local score calculation depends on the entire dataset.
It is impossible to store a vast dataset for each local score calculation module.
However, storing it in one place will cause memory contention.
→ Dataﬂow architecture with FPGAArchitecture
We place parallel calculation modules according to FPGA resources.
The dataset is stored in one place and streamed to each module.
Each module counts data supporting each target substructure concurrently.
▶ High degree of data and pipeline parallelism with few memory resources▶ Scalability : performance improves as FPGA resources increase
Calculation Flow
(1) Each count-up module identiﬁes the target local score as a query.
(2) Iterate the following three steps for all combinations of parent variable values.
(2-a) Counts the data supporting each target substructure from the streaming data concurrently.
(2-b) Calculate the term for each local score in the calc-term pipeline based on counted numbers.
(2-c) Add each term calculated in the calc-term pipeline to each partial sum.

(3) Return the calculated local scores as an answer.
Global Memory
Query[chunk][P]Environment▶ Intel Xeon W-2265 / 64GB / Ubuntu 18.04 / Xilinx Alveo U50▶ BN with 30 binary random variables▶ Accelerator is designed in C/C++ using Vitis 2020.2▶ SW: single-core software execution▶ HW(P = 1024): using accelerator with parallelism 1024
▶ HW(P = 2048): using accelerator with parallelism 2048

▶ Calculating local scores in advance simpliﬁes the evaluation of the entire graph.
▶ However, The time to calculate a huge number of local scores is critical.

Data[N]

Pipeline▶ Despite the Lanczos approximation, the ﬂoating-point log-gamma function
calculation module still consumes many DSP resources in FPGAs.
▶ Therefore, each parallel calculation module shares the pipelined log-gammafunction calculation module to save DSP resources.
→ The upper limit of parallelism breaks free from DSP resource constraints.

CancerLocal Scores▶ Structure learning is reduced to a combinatorial optimization that maximizes
the log marginal likelihood score of the entire graph.
▶ The entire graph score is decomposed into local scores.

Hostmemory
via PCIe

Lanczos Approximation▶ Calculate the log-gamma function numerically with High accuracy▶ Consist of only the constants and elementary functions→ Ideal for FPGAs to calculate the log-gamma function

Answer[chunk][P](2-a)

Synthesis Results▶ Few BRAMs and DSPs, but many LUTs
Resource
LUT
LUTRAM
Available
870016402016
P=1024 324129
16861
Usage12417
P=2048 476544
37.26
4.19
P=1024
Utilization(%)
P=2048
54.77
3.02

FF
1740032
441186656236
25.36
37.71

BRAM
1344
213
200
15.85
14.88

DSP
5940
490
490
8.25
8.25

Performance Evaluation of the Accelerator▶ HW accelerates the calculations, thus enabling too time-consuming
calculations for software (N/A: terminated after 18,000 s).
▶ Comparison of HWs proves that the performance improves as the FPGA
resources increase.
Nm
SWHW(P=1024) HW(P=2048)
5 130.059
1.824
1.667
14.27012.987
6 949.879
1000 7 5930.838
93.12584.612
8N/A
510.549463.556
9N/A
2378.568
2158.771
5 1268.540
7.552
5.010
6 9175.792
60.08039.712
10000 7N/A
394.153260.2128N/A
2166.1521429.310
9N/A
10104.604
6665.651
N: data size, m: number of parent variables.
Conclusion and Future Work
Conclusion▶ Calculate local scores in parallel using dataﬂow architecture with FPGA.
▶ Extract high parallelism with few memory resources by streaming the dataset.
▶ Scalability : performance improves as FPGA resources increase
Future Work▶ Practical evaluation on FPGA cluster, such as ESSPER by RIKEN(1)query:0

count-up

count_cache:0

calc-term(2-b)

query:1
count_cache:1

query:P-1...

count_cache:P-1

calc-term module

(2-b)

(2-c)
add-term

ls_term:0

ls_term:1

local_score:0

local_score:1

ls_term:P-1...

local_score:P-1(3)

Ryota Miyagi / Hideki Takase

HPC Asia 2022