A Hardware Accelerator For Node Importance Computation In Brain Network Analysis

Brain network research (BNA) using magnetic resonance imaging (MRI) is anew hot topic in biomedical field. Researchers study the functional connectivity ofthe human brain by mapping the brain network into a graph and analyzing the keyfigures in the network. With the rapid growth in the size of network and the numberof samples, computating time becomes bottleneck of the brain network research. Allpairs shortest path (APSP) and betweenness centrality are the most complexalgorithms in analyzing the brain network. In this paper, a FPGA–based hardwareacceleration platform for APSP and betweenness centrality is presented.At first, Breadth-first search (BFS) algorithm is chosen for APSP because of itshigh efficiency. After performance analysis and parallel levels exploration of the BFSalgorithm, a parallel computing system is implemented on FPGA with task levelcoarse grained parallelism and pipeline based fine grained parallelism.Secondly, the traditional algorithm for betweenness centraliy is not appropriatefor hardware implemention. In this paper, a novel algorithm is presented andhardware system architecture is proposed. The betweenness centrality computingsystem design is based on IP reuse method that an entire BFS computing system iscontained in the system with betweenness calculating units connect with the BFSunits.At last, the experimental results show that the FPGA implementationsachieve3.16X (BFS) and3.61X (Betweenness centrality) speedup comparedwith an8-core CPU implementation. Experiments also show that using thehardware systems calculating APSP and betweenness for brain network canachieve4.88X (BFS) and4.98X (Betweenness centrality) speedup.