推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

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

更新时间:2019-08-20 08:50:21 大小:287K 上传用户:江岚查看TA发布的资源 浏览次数:78 下载积分:2分 下载次数:0 次 标签:fpga稀疏网络 出售积分赚钱 评价赚积分 ( 如何评价?) 收藏 评论(0) 举报

资料介绍

摘 要:随着互联网、生物医学及社交网络等复杂网络研究的深入,如何寻找其等效图中关键节点越来越重要。中

介中心度作为衡量图中节点重要性的主要指标,其单点的计算复杂度高达O(N3),因而成为关键节点计算问题的难

点。该文在对传统的中介中心度快速算法进行分析之后,提出了一种适用于硬件设计的改进算法。同时,基于算法

中各点独立、以及相邻计算间无数据依赖的特点,该文利用改进算法实现了一个流水线结构的8 计算单元并行计算

系统,并在FPGA 上完成了硬件系统的设计和验证。通过对比8 核CPU 软件系统的计算时间,该文的硬件计算

系统实现了4.31 倍的加速比。


部分文件列表

文件名 大小
基于FPGA的稀疏网络关键节点计算的硬件加速方法研究.pdf 287K

部分页面预览

(完整内容请下载后查看)
33 卷第 10 期  
2011 10 月  
Vol.33No.10  
Oct. 2011  
Journal of Electronics & Information Technology  
FPGA 的稀疏网络关键节点计算的硬件加速方法研究  
史圣卿*①  
(清华大学电子工程系清华信息科学与技术国家实验室() 北京 100084)  
(海南省通信管理局 海口 570206)  
摘 要随着互联网物医学及社交网络等复杂网络研究的深入何寻找其等效图中关键节点越来越重要中  
介中心度作为衡量图中节点重要性的主要指标单点的计算复杂度高达 O(N3)而成为关键节点计算问题的难  
文在对传统的中介中心度快速算法进行分析之后出了一种适用于硬件设计的改进算法于算法  
中各点独立及相邻计算间无数据依赖的特点文利用改进算法实现了一个流水线结构的 8 计算单元并行计算  
系统,并在 FPGA 上完成了硬件系统的设计和验证。通过对比 8 CPU 软件系统的计算时间,该文的硬件计算  
系统实现了 4.31 倍的加速比。  
关键词:FPGA;中介中心度;硬件计算;复杂网络;图  
中图分类号:TN402  
文献标识码: A  
文章编号:1009-5896(2011)10-2536-05  
DOI: 10.3724/SP.J.1146.2011.00363  
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)  
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  
1 引言  
O(N3)要高出一个数量级[6]。因此计算时间成为限制  
关键节点研究的主要问题,现有的对中介中心度计  
算进行加速的工作主要都是基于多核 CPU[3]和超级  
计算机[3]。基于分布式存储的超级计算机如 Cray  
MTA-2[1]可以实现较大的网络规模和较高的计算速  
度,但是其造价高昂,功耗也很大,难以普及;多  
CPU 计算中介中心度主要采用任务级并行的方  
式,难以实现更细粒度的并行,而受限于存储访问  
瓶颈[7]任务级并行的效果相比于单核 CPU 提升  
也较为有限。相比之下,FPGA 在成本、功耗和运  
算速度等方面均具有一定的优势[8]。  
图是一种基本的数据形式,大量现实世界中的  
复杂网络如互联网、道路交通、生物医学等问题都  
需要抽象成稀疏图来表达,并通过图的相关属性来  
进行分析。传统的研究主要集中在计算图中的最短  
距离[1,2]。近年来,随着基于核磁共振成像的生物医  
学网络[3]以及基于人际关系的社交网络等研究的不  
断深入[4],使得人们对于图属性的计算需求越来越  
大,关注的重点也由寻找最短距离转移到寻找图中  
的关键节点。  
中介中心度(betweenness centrality)[5]是衡量图  
中节点重要性的主要指标。相对于单点最短距离的  
计算复杂度 O(N2),单点中介中心度的计算复杂度  
本文在对传统的中介中心度快速算法进行分析  
之后先针对 FPGA 硬件存储结构较为固定的特  
点,提出了一种不需要指针点集的改进型中介中心  
度算法以适应硬件设计;然后针对算法中各源点的  
计算完全独立以及计算过程中邻近节点间无数据依  
2011-04-14 收到,2011-06-23 改回  
*通信作者:史圣卿

推荐下载

全部评论(0)

暂无评论

上传资源

更多>>

项 目 外 包