面向图搜索的流加速部件片上数据通路的设计、实现及性能优化

发布时间：2017-08-04 17:29

  本文关键词：面向图搜索的流加速部件片上数据通路的设计、实现及性能优化

  更多相关文章： 大数据 图搜索 流加速部件 数据通路

【摘要】：近年来,信息社会的飞速发展引发了数据规模的爆炸式增长,大数据问题逐渐引起了研究者的广泛关注。然而,大数据问题表现出与传统科学计算问题不同的负载特性,使得通用处理器面临严峻挑战。图问题是大数据中的典型问题,在分析大数据集中数据对象间的关系中扮演着重要角色,尤其是以BFS算法为代表的图搜索算法,更是广泛存在于社交网络、人工智能等众多领域。考虑到流处理器高性能、高效能等特点,探索基于流体系结构解决图搜索大数据问题具有重要的意义。因此,本课题以特定的流加速部件为研究平台,面向图搜索大数据问题,研究其片上数据通路的设计和优化。针对该流加速部件,本文在深入分析其执行图搜索算法时负载特性的基础上,重点研究了其片上数据通路的设计与优化,主要从以下四个方面展开研究:第一,针对已有流处理器中的SRF数据通路,分析其在解决图搜索问题时多线程访问SRF激烈竞争的不足,提出了多体多控制器的SRF结构,增加SRF的并行度,并基于AXI协议实现了SRF中的体与处理器中的核之间的交叉互连。该数据通路能够均衡处理多线程访问SRF的请求,且具有较好的吞吐带宽,有效适应了处理器核对SRF的细粒度访问。第二,通过深入分析该流加速部件在执行图搜索算法时访问SRF的负载特性,进一步优化SRF数据通路,提出了处理器核私有SRF中的体方法,避免了它们之间复杂的交叉互连,提升了流加速部件的整体性能。第三,分析已有流处理器中的访存数据通路,针对其不适合多线程细粒度访存的问题,设计了基于消息包的高并发、低延迟的访存数据通路,该方法不仅能够均衡处理各线程的访存请求,而且也具有较好的访存带宽和延迟,满足了多线程处理图搜索问题的需求。第四,针对图搜索算法中共享数据一致性的问题,首先探索了通过加解锁SPM来维护一致性的方法,但发现该方法会导致访问SPM的激烈冲突。然后,进一步研究了多线程执行图搜索算法时访问共享数据的特性,提出了在访存数据通路中加入事务型访存的机制,通过原子性操作内存中的共享数据来保护其一致性,避免了频繁访问SPM的冲突。同时,也设计了该模块高效并发的访存接口。该方法有效减小了多线程竞争访问共享数据的阻塞时间,提高了线程间的并行性,增加了内存的带宽利用率,使得该流加速部件的整体性能得到提升。
【关键词】：大数据 图搜索 流加速部件 数据通路
【学位授予单位】：国防科学技术大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP332
【目录】：

• 摘要9-10
• ABSTRACT10-12
• 第一章 绪论12-20
• 1.1 课题研究背景12-14
• 1.1.1 大数据问题对传统处理器的挑战12
• 1.1.2 图搜索成为研究大数据问题的热点之一12-13
• 1.1.3 面向图搜索的流加速部件13-14
• 1.2 相关研究工作14-18
• 1.2.1 Imagine中的数据通路14-15
• 1.2.2 Cell中的数据通路15-16
• 1.2.3 传统处理器中的数据通路16-18
• 1.3 课题的研究内容与创新18
• 1.4 论文结构18-20
• 第二章 面向图搜索的流加速部件20-30
• 2.1 图搜索20-23
• 2.1.1 串行BFS算法20-21
• 2.1.2 并行BFS算法21-22
• 2.1.3 图搜索的规模22-23
• 2.2 流加速部件23-29
• 2.2.1 基于流体系结构的指令集23-24
• 2.2.2 多节点并行系统的结构24-25
• 2.2.3 流处理器核25-26
• 2.2.4 单节点的结构框架26-29
• 2.3 小结29-30
• 第三章 SRF数据通路的设计和优化30-48
• 3.1 问题描述30-32
• 3.1.1 SRF的功能需求30-31
• 3.1.2 已有设计的分析31-32
• 3.2 SRF数据通路的设计32-44
• 3.2.1 设计方案32-39
• 3.2.2 数据测试39-43
• 3.2.3 性能分析43-44
• 3.3 SRF数据通路的优化44-47
• 3.3.1 优化方案44-45
• 3.3.2 数据测试45-46
• 3.3.3 性能分析46-47
• 3.4 小结47-48
• 第四章 访存数据通路的设计与优化48-65
• 4.1 问题描述48-50
• 4.1.1 访存的功能需求48
• 4.1.2 已有设计的分析48-50
• 4.2 访存数据通路的设计50-58
• 4.2.1 设计方案50-55
• 4.2.2 数据测试55-56
• 4.2.3 性能分析56-58
• 4.3 访存数据通路的优化58-64
• 4.3.1 优化方案58-62
• 4.3.2 数据测试62-63
• 4.3.3 性能分析63-64
• 4.4 小结64-65
• 第五章 结束语65-68
• 5.1 工作总结65-66
• 5.2 研究展望66-68
• 致谢68-70
• 参考文献70-74
• 作者在学期间取得的学术成果74

【相似文献】

中国期刊全文数据库 前10条

1 李东海;任艳庆;马光胜;;定点数据通路的等价验证[J];小型微型计算机系统;2009年03期

2 杨志;马光胜;张曙;;基于多项式符号代数方法的高层次数据通路的等价验证[J];计算机研究与发展;2009年03期

3 周屹;杨洋;范德会;;基于多项式符号代数的数据通路模型[J];黑龙江工程学院学报(自然科学版);2009年04期

4 张连华;;数据通路组成与故障分析实验项目开发[J];科学之友;2011年07期

5 赵冰,黑勇,仇玉林;一种新型异步数据通路性能分析方法[J];固体电子学研究与进展;2004年03期

6 李东海;马光胜;胡靖;;高层次数据通路的等价性验证方法[J];哈尔滨工程大学学报;2008年06期

7 吴俊华;李东海;马光胜;李光顺;;基于模拟的定点算术数据通路等价性验证[J];吉林大学学报(工学版);2009年05期

8 黄少滨,冯彬,马光胜;基于演化程序的数据通路综合算法研究[J];哈尔滨工程大学学报;2002年03期

9 郭斌林,童家榕;一种适于数据通路应用的高性能可编程逻辑单元[J];电子学报;2002年02期

10 蒋富瑞;关于“面版显示”的研究和实践[J];山东大学学报(自然科学版);1980年03期

中国重要会议论文全文数据库 前2条

1 刘成;张磊;韩银和;李晓维;;一种基于数据通路挽救的高可靠片上互联网络设计[A];第六届中国测试学术会议论文集[C];2010年

2 段勃;王文迪;张春明;李想;;一种基于数据通路重构的运算加速平台[A];第十五届计算机工程与工艺年会暨第一届微处理器技术论坛论文集（A辑）[C];2011年

中国博士学位论文全文数据库 前1条

1 肖继学;基于累加器的DSP数据通路的内建自测试技术的研究[D];电子科技大学;2007年

中国硕士学位论文全文数据库 前10条

1 武桂林;PCIe2.0 MAC层数据通路与PCS层设计[D];中国科学技术大学;2016年

2 王雅琴;规整电路的半自动物理实现与优化[D];国防科学技术大学;2015年

3 李军飞;面向图搜索的流加速部件片上数据通路的设计、实现及性能优化[D];国防科学技术大学;2014年

4 王燕;J2ME安全数据通路关键技术研究与实现[D];国防科学技术大学;2005年

5 朱霞;P1750A处理器数据通路设计[D];西北工业大学;2001年

6 范靖;DSP处理器数据通路设计[D];西北工业大学;2001年

7 田斌;功耗限制下RTL数据通路低费用测试方法研究[D];湖南大学;2011年

8 冯彬;高速ASIC设计新理论中的高层次综合算法及软件研究[D];哈尔滨工程大学;2002年

9 向奔;一种DSP数据通路的设计实现[D];上海交通大学;2008年

10 向奔;一种DSP数据通路的设计实现[D];上海交通大学;2009年

，

本文编号：620858