基于FPGA的稀疏网络关键节点计算的硬件加速方法研究
史圣卿*① 陈凯② 汪玉① 罗嵘①
① (清华大学电子工程系清华信息科学与技术国家实验室(筹) 北京 100084) ② (海南省通信管理局 海口 570206)
Node Importance Analysis in Complex Networks Based on Hardware Computing
Shi Sheng-qing① Chen Kai② Wang Yu① Luo Rong①
① (TNList, Dept. of Electronic Engineering, Tsinghua University, Beijing 100084, China)② (Hainan Communications Administration, Haikou 570206, China)
摘要 随着互联网、生物医学及社交网络等复杂网络研究的深入，如何寻找其等效图中关键节点越来越重要。中介中心度作为衡量图中节点重要性的主要指标，其单点的计算复杂度高达O (N 3 )，因而成为关键节点计算问题的难点。该文在对传统的中介中心度快速算法进行分析之后，提出了一种适用于硬件设计的改进算法。同时，基于算法中各点独立、以及相邻计算间无数据依赖的特点，该文利用改进算法实现了一个流水线结构的8计算单元并行计算系统，并在FPGA上完成了硬件系统的设计和验证。通过对比8核CPU软件系统的计算时间，该文的硬件计算系统实现了4.31倍的加速比。
关键词 ：
FPGA ,
中介中心度 ,
硬件计算 ,
复杂网络 ,
图
Abstract ：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.
Key words ：
FPGA
Betweenness centrality
Hardware computing
Complex networks
Graphs
收稿日期: 2011-04-14
通讯作者:
史圣卿
E-mail: shisq04@mails.tsinghua.edu.cn
引用本文:
史圣卿, 陈凯, 汪玉, 罗嵘. 基于FPGA的稀疏网络关键节点计算的硬件加速方法研究[J]. 电子与信息学报, 2011, 33(10): 2536-2540.
Shi Sheng-Qing, Chen Kai, Wang Yu, Luo Rong. Node Importance Analysis in Complex Networks Based on Hardware Computing. , 2011, 33(10): 2536-2540.
链接本文:
http://jeit.ie.ac.cn/CN/10.3724/SP.J.1146.2011.00363 或 http://jeit.ie.ac.cn/CN/Y2011/V33/I10/2536
[1]
肖斌,姜彦君,李伟生,王国胤. 基于离散Tchebichef变换的多聚焦图像融合方法
[2]
王陈园,吴斌,王宏琦. 基于形状先验的建筑物几何参数提取方法
[3]
孙士洁,赵怀慈,李波,郝明国,吕进锋. 利用低秩先验的噪声模糊图像盲去卷积
[4]
刘功申,孟魁,郭弘毅,苏波,李建华. 基于贡献函数的重叠社区划分算法
[5]
许群,刘少斌,王云香,宋立众,曹洪伟. 基于印刷振子和微带贴片的双极化天线单元研究
[6]
乔雪,彭晨,段贺,张钰尧. 基于共享特征相对属性的零样本图像分类
[7]
江淮,赵惠昌,汉敏,张淑宁. 基于扩展方位NLCS的斜视TOPSAR成像算法
[8]
王敏,赵金宇,陈涛,崔博川,高扬. 基于能量函数的极值中值滤波星图去噪算法
[9]
马英然,彭延军. 一种融合曲线演化与模糊C均值聚类算法的快速图像分割模型
[10]
陈强,徐军,牛四杰. 基于随机森林的频谱域光学相干层析技术的图像视网膜神经纤维层分割
[11]
刘彩霞,李凌书,汤红波,王晓雷,卢干强. 基于子图同构的vEPC虚拟网络分层协同映射算法
[12]
杨真真,杨震, 李雷,金正猛. Alpha稳态噪声下基于Meridian范数的全变分图像去噪算法
[13]
刘小青,许进. 4-正则图着色的Kempe等价性
[14]
耿爱辉,万春明,李毅,张云峰, 曹立华,冯强. 基于分层差分表达理论的图像视觉增强
[15]
张涛,唐振民. 一种基于非负低秩稀疏图的半监督学习改进算法
2011, Vol. 33 
