BFS算法与众核处理器的适应性研究

发布时间：2018-04-13 17:08

  本文选题：广度优先搜索算法 + 众核处理器　； 参考：《计算机研究与发展》2015年05期

【摘要】：以图计算为代表的数据密集型应用获得越来越广泛的关注,而传统的高性能计算机处理这类应用的效率较低.面向未来高性能计算机体系结构要有效支持数据密集型计算,深入研究以广度优先搜索(breadth-first search,BFS)算法为代表的图计算的典型特征,设计实现轻量级启发式切换BFS算法,该算法通过基本搜索方式的自动切换,避免冗余内存访问,提高搜索效率;针对BFS算法的离散随机数据访问特征以及众核处理器执行机制,建立面向BFS算法的众核处理器体系结构分析模型;全面、深入研究了BFS算法在典型众核处理器上的运行特征和性能变化趋势.测试结果表明:Cache命中率、内存带宽、流水线利用效率等相关参数均处于较低水平,无法完全满足BFS算法的需求,因此需要能够支持大量离散随机访问和简单执行机制的新型众核处理器体系结构.
[Abstract]:In order to support data - intensive computing , the traditional high - performance computer architecture can effectively support the data - intensive computing . In order to avoid redundant memory access and improve the search efficiency , this paper studies the operating characteristics and performance trends of the BFS algorithm . The results show that the cache hit rate , memory bandwidth , pipeline utilization efficiency and so on are all at a low level . The results show that the cache hit rate , memory bandwidth , pipeline utilization efficiency and other related parameters can not meet the requirements of the BFS algorithm completely . Therefore , a new type of core processor architecture capable of supporting a large number of discrete random access and simple execution mechanism is required .

【作者单位】： 数学工程与先进计算国家重点实验室;
【基金】：国家“八六三”高技术研究发展计划基金项目(2013AA010105)
【分类号】：TP332

【相似文献】

相关期刊论文 前10条

1 Robert Cravotta;;可配置处理器应用日趋红火[J];电子设计技术;2003年11期

2 刘磊;邹候文;唐屹;;一种可编程安全处理器体系结构的研究与实现[J];广州大学学报(自然科学版);2006年04期

3 张铮;赵荣彩;颜峻;邰铭;陈科;;网络处理器体系结构和应用综述[J];信息工程大学学报;2006年04期

4 张怡,孙志刚;基于IPSec的下一代高性能安全处理器的体系结构[J];国防科技大学学报;2003年02期

5 岳虹;戴葵;王志英;;一种面向数字信号处理的嵌入式处理器体系结构设计[J];计算机工程与科学;2006年10期

6 许珊琳;;适合嵌入应用的嵌入式处理器[J];中国集成电路;2009年02期

7 张磊;王颖;陈云霁;徐志伟;张立新;;可重塑处理器:用户可定义的加速器中处理器架构[J];网络新媒体技术;2012年06期

8 Robert Cravotta;;一个处理器能兼顾控制与信号处理吗?[J];电子设计技术;2002年07期

9 朱丹;李暾;郭阳;李思昆;;微处理器体系结构级测试程序自动生成技术[J];软件学报;2005年12期

10 ;高性能处理器云集市场[J];每周电脑报;1997年15期

相关会议论文 前3条

1 宋绯;刘晓宁;;DSP/MCU结构的新型处理器[A];第九届全国青年通信学术会议论文集[C];2004年

2 赵秋平;杨灿群;王锋;;LBM算法在Cell处理器上的实现和优化[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

3 周巍;孙冰;战立明;吕建华;王国仁;于戈;;基于DOM模型的XML查询处理器的设计与实现[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

相关重要报纸文章 前10条

1 ;处理器上演多核大戏[N];计算机世界;2005年

2 心元;PC“心脏”的搏击[N];计算机世界;2004年

3 清华大学微处理器与SoC技 术研究中心 王海霞 汪东升;颠覆传统理念[N];计算机世界;2005年

4 清华大学微处理器与SoC技术研究 中心 汪东升 王海霞 张悠慧 李兆麟;CMP 开启处理器效能时代[N];计算机世界;2005年

5 江苏 netfan;体现速度与性能[N];电脑报;2004年

6 四川 王毅;变革进行时[N];电脑报;2004年

7 清华大学微处理器与SoC技术研究中心 汪东升;多核技术天地广阔[N];计算机世界;2006年

8 本报记者 李献 王皓;2002年服务器四大景观[N];计算机世界;2003年

9 ;MontaVista Linux 2．1跨平台[N];中国计算机报;2002年

10 ;CPU技术进步牛气冲天[N];计算机世界;2004年

相关博士学位论文 前10条

1 魏继增;可配置可扩展处理器关键问题研究[D];天津大学;2010年

2 霍文捷;嵌入式处理器安全运行机制的研究与设计[D];华中科技大学;2010年

3 从明;类数据流驱动的分片式处理器体系结构[D];中国科学技术大学;2009年

4 徐光;分片式流处理器体系结构[D];中国科学技术大学;2010年

5 李勇;异步数据触发微处理器体系结构关键技术研究与实现[D];国防科学技术大学;2007年

6 任永青;逻辑核动态可重构的众核处理器体系结构[D];中国科学技术大学;2010年

7 黎铁军;嵌入式流媒体处理器体系结构技术研究[D];国防科学技术大学;2005年

8 黄海林;高可靠处理器体系结构研究[D];中国科学院研究生院（计算技术研究所）;2006年

9 刘光辉;高效处理器容错技术研究与实现[D];国防科学技术大学;2013年

10 温璞;面向科学计算的PIM体系结构技术研究[D];国防科学技术大学;2007年

相关硕士学位论文 前10条

1 曾斌;分片式处理器体系结构上的超块优化技术[D];中国科学技术大学;2009年

2 黄冕;X处理器存储一致性模型的研究与实现[D];国防科学技术大学;2008年

3 赵灿明;分片式处理器上激进执行模型分析[D];中国科学技术大学;2009年

4 刘晋汾;处理器描述语言的研究与应用[D];解放军信息工程大学;2011年

5 刘子扬;基于虚拟计算群的众核处理器动态在线任务调度算法研究[D];上海交通大学;2013年

6 邸志雄;多核包处理器数据控制总线技术研究[D];西安电子科技大学;2010年

7 方红霞;基于指令的处理器时延测试产生方法[D];中国科学院研究生院（计算技术研究所）;2005年

8 黎宝峰;嵌入式DSP处理器的设计与验证[D];湖南大学;2003年

9 钟松延;可配置可扩展处理器编译器设计[D];天津大学;2012年

10 董亚卓;循环阵列处理器体系结构的关键技术研究与实现[D];国防科学技术大学;2004年

，

本文编号：1745421