基于FPGA的图计算并行算法和体系结构研究

发布时间：2018-10-22 11:16

【摘要】：近年来,随着现场可编程门阵列(FPGA)在计算、存储和逻辑等资源方面的急剧增长,基于FPGA的可重构计算成为高性能计算领域的一个重要分支,越来越凸显其重要的研究和应用价值。图计算是大数据分析领域的一种关键应用,在大数据分析方面具有重要作用,FPGA定制计算在加速图计算方面具有巨大的潜力。然而,现有FPGA图计算存在并行算法设计、并行度开发和支持图计算规模有限等挑战。为应对这些挑战,本文对大规模图计算的FPGA实现技术进行了深入研究,本文的主要工作和创新点如下:(1)提出了面向大规模图最短路径计算的FPGA并行算法和硬件实现结构。针对现有单源路径问题的FPGA实现采用片内存储资源来保存图数据和计算结果,难以高效处理大规模图数据处理的问题,提出了基于Eager Dijkstra算法变种的FPGA并行单源最短路径算法,每次迭代从优先队列移除多个元素进行并行处理,开发了并行性。为了实现大规模优先队列的处理,提出了基于片外存储的大规模优先队列实现方法,利用片外DRAM存储器保存溢出队列元素,并设计合理策略将片外元素重新放回片内,从而保证了大规模优先队列处理的正确性。选取真实的公路网络数据进行测试,实验结果表明基于FPGA的并行单源最短路径算法和通用微处理器上的软件实现相比可以获得5倍的加速效果,并且功耗仅为通用微处理器的1/4。(2)提出了面向大规模图最小生成树计算的FPGA并行算法和硬件实现结构。针对现有最小生成树计算的FPGA实现并行度开发不够和不能处理大规模图的问题,提出了一种基于Prim算法的FPGA最小生成树并行算法。该算法选取多个起始结点并行执行Prim算法生成多个子树,当检测到子树间冲突时,停止当前子树生成,选择其它的未访问结点继续生成新的子树,当所有结点都被访问时,对所有的子树进行合并。对于单个子树的Prim计算,提出了基于线性阵列优先队列的实现方法,当优先队列溢出时,采用DRAM存储溢出队列元素,实现了大规模子树生成。选取随机生成图进行测试,实验结果表明基于FPGA的并行最小生成树算法和通用微处理器上的软件实现相比可以获得2.58倍到6.88倍的加速比。(3)提出了面向大规模图宽度优先搜索(BFS)的FPGA消息传递并行算法和硬件实现结构。针对大规模并行宽度优先搜索通信延迟大的问题,首次提出了一种新颖的基于二维消息传递阵列结构的并行宽度优先搜索算法,利用片上存储减少了处理单元之间的通信延迟。与相关工作相比,该结构显著减少了片上存储资源的消耗,并且具备良好的可扩展性,能够映射到多FPGA系统。此外,提出了一种基于片上位图存储的分布式队列实现方法,该方法避免了为判断顶点是否为当前层待搜索顶点而引入的片外访存开销。使用不同类型的图进行了测试,并与相关工作进行了比较。由于随机访存的延迟较大,单片FPGA上的BFS算法实测性能低于相关工作的性能。尽管如此,本文提出的FPGA并行BFS算法和硬件结构在理论上能够扩展到任意数量FPGA构成的计算系统。(4)提出了面向大规模图匹配的FPGA并行算法和硬件实现结构。针对现有二部图图匹配计算的FPGA实现基于片上存储保存图数据,无法高效处理大规模图匹配的问题,提出了一种二部图图匹配的并行算法,该算法每次对未指派的多个结点进行并行处理,提高了并行性,在此基础上提出了一种基于片外存储的二部图匹配并行计算体系结构,与相关FPGA实现相比,该结构可以处理更大规模的图匹配。选取随机生成图进行了测试,实验结果表明,FPGA实现优于通用处理器的实现。
[Abstract]:......
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TN791

【相似文献】

相关期刊论文 前10条

1 科卞;并行算法及其在电子系统中的应用[J];电子科技大学学报;2002年02期

2 徐云;孙广中;郑启龙;吴俊敏;陈国良;;“并行算法”课程的教学与探讨[J];教育与现代化;2008年04期

3 陈国良;孙广中;徐云;吕敏;;并行算法研究方法学[J];计算机学报;2008年09期

4 罗贵章;陈忠伟;;并行算法综述[J];计算机光盘软件与应用;2013年15期

5 谢铁柱;吴功广;;多项式几种并行算法的比较与优化[J];计算机工程与科学;1981年01期

6 李晓梅 ,胡庆丰;并行算法的发展与展望[J];计算机工程与科学;1991年03期

7 童丽,王正明,曾泳泓;自变量选择及其并行算法[J];数值计算与计算机应用;2001年03期

8 陈国良;昔日王榭堂前燕,飞入寻常百姓家浅谈并行算法[J];新电脑;2002年12期

9 李晓梅;《可扩展并行算法的设计与分析》简介[J];装备指挥技术学院学报;2003年02期

10 吴磊,芦东昕,方马;并行算法中的指针转移技术分析[J];计算机工程;2003年22期

相关会议论文 前10条

1 姚向东;;并行算法到并行结构的映射[A];中国工程物理研究院科技年报（2001）[C];2001年

2 高华;苗世光;;城市小区尺度模式并行算法研究[A];中国气象学会2006年年会“中尺度天气动力学、数值模拟和预测”分会场论文集[C];2006年

3 王志成;吴颂平;;多块结构网格并行算法研究[A];北京力学会第20届学术年会论文集[C];2014年

4 焦龙;郭亚红;纪守领;李金宝;;基于多核计算机的分子动力学并行算法的实现[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年

5 张衡;张武;;三维抛物型初边值问题的块三对角可扩展并行算法[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

6 王雷章;张爱武;刘晓萌;;三维建模中平面分割并行算法的设计与实现[A];中国系统仿真学会第五次全国会员代表大会暨2006年全国学术年会论文集[C];2006年

7 毛韶阳;李肯立;;一种基因数据的聚类并行算法研究[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

8 左墨;蔺小林;;电力系统暂态稳定并行算法的进展[A];第二届中国水利水电岩土力学与工程学术讨论会论文集（二）[C];2008年

9 樊洪明;李先庭;赵彬;任鸿泽;;有限元分布式并行算法研究[A];全国暖通空调制冷2002年学术年会论文集[C];2002年

10 侯有政;张方;;基于CUDA的动载荷频域识别的并行算法研究[A];第十届全国振动理论及应用学术会议论文集（2011）上册[C];2011年

相关重要报纸文章 前4条

1 ;并行算法研究进展[N];中国计算机报;2004年

2 新华社记者 奚启新 本报通讯员 李汛 记者 喻国英;精彩人生[N];光明日报;2005年

3 新华社记者　奚启新　本报记者　廖文根;三次选择　无怨无悔[N];人民日报;2005年

4 清华大学计算机系 薛巍;电网仿真考验高性能计算[N];计算机世界;2006年

相关博士学位论文 前10条

1 任立波;稠密颗粒两相流的CFD-DEM耦合并行算法及数值模拟[D];山东大学;2015年

2 李雪宝;太阳望远镜海量数据并行处理技术研究[D];中国科学院研究生院(云南天文台);2015年

3 马欣荣;微分动力学方程的快速与并行算法研究[D];西安电子科技大学;2015年

4 雷国庆;基于FPGA的图计算并行算法和体系结构研究[D];国防科学技术大学;2015年

5 张艳;分布并行算法设计、分析与实现[D];电子科技大学;2001年

6 杜云飞;容错并行算法的研究与分析[D];国防科学技术大学;2008年

7 潘斌;几何定理机器证明并行算法研究[D];中国科学院研究生院（成都计算机应用研究所）;2006年

8 骆志刚;典型结构大型线性方程组的分布式并行算法研究[D];中国人民解放军国防科学技术大学;2000年

9 何霞辉;基于非稳态不可压缩流的可扩张并行算法研究[D];湖南大学;2013年

10 戚晶晶;热物性反问题高效并行算法研究[D];武汉理工大学;2013年

相关硕士学位论文 前10条

1 陈权;基于分布式集群的多摄像头的目标检测和跟踪的并行算法[D];南京理工大学;2015年

2 马焕焕;一类近场动力学问题的并行算法[D];山东大学;2015年

3 朱晓丹;一种神经动力学优化系统的并行算法设计[D];大连理工大学;2015年

4 张源;新一代视频编码技术的并行算法设计与实现[D];大连理工大学;2015年

5 董蕾;基于GPU的图像压缩感知算法并行化研究[D];电子科技大学;2015年

6 蒋昭炎;基于图像的大场景三维重建并行算法研究[D];东北大学;2013年

7 冯杰;基于MIC架构的遥感图像增强类算法并行化研究[D];电子科技大学;2015年

8 郑全刚;并行生物序列算法设计与优化[D];山东大学;2016年

9 周兰花;基于异构计算的电磁仿真并行算法研究[D];湖南大学;2016年

10 李剑威;共形组合激发参数并行算法研究[D];西南石油大学;2016年

，

本文编号：2287001