基于FPGA的稀疏网络关键节点计算的硬件加速方法研究  

Node Importance Analysis in Complex Networks Based on Hardware Computing

作　　者：史圣卿[1] 陈凯[2] 汪玉[1] 罗嵘[1] 

机构地区：[1]清华大学电子工程系清华信息科学与技术国家实验室(筹),北京100084 [2]海南省通信管理局,海口570206

出　　处：《电子与信息学报》2011年第10期2536-2540,共5页Journal of Electronics & Information Technology

摘　　要：随着互联网、生物医学及社交网络等复杂网络研究的深入,如何寻找其等效图中关键节点越来越重要。中介中心度作为衡量图中节点重要性的主要指标,其单点的计算复杂度高达O(N3),因而成为关键节点计算问题的难点。该文在对传统的中介中心度快速算法进行分析之后,提出了一种适用于硬件设计的改进算法。同时,基于算法中各点独立、以及相邻计算间无数据依赖的特点,该文利用改进算法实现了一个流水线结构的8计算单元并行计算系统,并在FPGA上完成了硬件系统的设计和验证。通过对比8核CPU软件系统的计算时间,该文的硬件计算系统实现了4.31倍的加速比。Betweenness centrality is a widely used indicator to measure the node importance in complex network s, but it is computationally-expensive to calculate betweenness centrality. In this paper, analysis on the traditional betweenness centrality algorithms is completed and a novel algorithm is proposed to meet the hardware design features. Based on this algorithm, parallel computing system is implemented on FPGA with task level coarse grained parallelism and pipeline based fine grained parallelism. The experimental results show that the FPGA based implementation achieves up to 4.31 times speedup compared with an 8-core CPU implementation.

关 键 词：FPGA 中介中心度 硬件计算 复杂网络 图 

分 类 号：TN402[电子电信—微电子学与固体电子学]