针对广度优先搜索算法的多核处理器定制优化

发布时间：2017-10-24 13:36

  本文关键词：针对广度优先搜索算法的多核处理器定制优化

  更多相关文章： 广度优先搜索 多核处理器 定制处理器

【摘要】：目前，高能耗已经严重制约了高性能计算机的发展，因此处理器体系结构的设计越来越注重性能功耗比的提升，针对关键应用进行体系结构的定制已成为技术发展趋势之一。另一方面，图数据处理的应用越来越广泛，广度优先搜索（BFS）算法作为图数据处理的基础算法之一，重要性日益凸显。 随着多核/众核处理器体系结构的发展，越来越多的处理器核心将被集成到一个芯片上。在片上多核处理器（CMP）中运行广度优先搜索算法，面临的主要挑战有：数据局部性差带来的访存延时，并行执行带来的任务间负载不均以及同步开销等。对此，本文采用软硬件协同设计的方法，提出了一个在较大规模片上多核处理器上实现高能效、可扩展的广度优先搜索的方案。1）将广度优先搜索算法访存密集部分和计算密集部分划分为两个阶段，用较多的内核或线程来执行相对较慢的访存，掩盖访存延时并实现访存与计算的并行；同时，对访存和计算两个部分分别采用不同的数据划分方法，在避免锁的同时达到较好的负载均衡性。2）针对广度优先搜索算法对处理器核心进行定制，用可快速访问的片上存储取代最后一级缓存，用于存储频繁访问的离散数据，在提高性能的同时降低了功耗。3）构建快速的片上网络实现数据在处理器核心之间的快速传输。 实验结果表明，在体系结构的支持下，经过适当的算法设计，可以在低功耗CMP上实现高效率的图数据处理。使用16个Xtensa处理器核心构建的片上多核处理器模型进行仿真测试，执行2阶段并行BFS算法，相对于Intel Xeon X5560处理器(相同的CMOS工艺)运行Graph500OpenMP基准测试程序，以10%的面积、1.6%的功耗，可以达到90%的图遍历性能，，性能功耗比提高了41.98倍。
【关键词】：广度优先搜索 多核处理器 定制处理器
【学位授予单位】：清华大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP332
【目录】：

• 摘要3-4
• Abstract4-7
• 第1章 引言7-13
• 1.1 能耗成为制约高性能计算机发展的重要因素7
• 1.2 使用定制处理器构建高性能计算机系统7-9
• 1.3 图数据处理日益重要9-10
• 1.4 大规模图数据处理对高性能计算机的挑战10-11
• 1.5 本文贡献11
• 1.6 论文结构11-13
• 第2章 相关工作介绍13-20
• 2.1 几种针对特定应用的定制处理器系统介绍13-17
• 2.1.1 Blue Gene13-14
• 2.1.2 Green Flash14-15
• 2.1.3 Anton15-16
• 2.1.4 MD Grape16-17
• 2.2 围绕广度优先搜索算法进行的研究17-19
• 2.2.1 针对多核处理器的研究17
• 2.2.2 在 Cray MTA 2 平台上的研究17-18
• 2.2.3 在 GPU 上进行图数据处理18
• 2.2.4 在 Intel MIC 平台上的研究18-19
• 2.3 本章小结19-20
• 第3章 基于 Xtensa 的定制处理器工具和环境20-33
• 3.1 Xtensa 处理器定制工具20-26
• 3.1.1 Xtensa 处理器指令集基本配置22-24
• 3.1.2 Xtensa 处理器的流水线24-25
• 3.1.3 Xtensa 处理器的存储系统25-26
• 3.2 Tensilica 指令扩展（TIE）语言介绍26-32
• 3.2.1 指令部分的扩展和定制27-30
• 3.2.2 接口部分的定制30-32
• 3.3 本章小结32-33
• 第4章 并行广度优先搜索算法设计优化33-45
• 4.1 广度优先搜索算法33-34
• 4.1.1 图数据处理的特点33-34
• 4.1.2 广度优先搜索（BFS）算法34
• 4.2 针对广度优先搜索的优化策略及算法设计34-44
• 4.2.1 算法使用的主要数据结构35
• 4.2.2 并行 BFS 算法35-37
• 4.2.3 分段并行 BFS 算法37-42
• 4.2.4 负载均衡42-44
• 4.3 本章小结44-45
• 第5章 处理器定制优化及多核互联环境45-65
• 5.1 影响算法的因素45-47
• 5.1.1 内存延迟的影响45-46
• 5.1.2 取数与计算的平衡46-47
• 5.2 多核互联仿真47-54
• 5.2.1 SystemC47-48
• 5.2.2 XTSC 工具集48-51
• 5.2.3 多核处理器的存储系统实现51-52
• 5.2.4 处理器核间互联网络实现52-54
• 5.3 处理器核心设计54-61
• 5.3.1 指令集定制55-56
• 5.3.2 存储系统定制56-58
• 5.3.3 流水线定制58-59
• 5.3.4 指令扩展（TIE）59-61
• 5.4 多核处理器性能评估61-63
• 5.5 本章小结63-65
• 第6章 总结与展望65-67
• 6.1 总结65-66
• 6.2 展望66-67
• 参考文献67-69
• 致谢69-70
• 个人简历、在学期间发表的学术论文与研究成果70

【共引文献】

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

1 黎军;张贤惠;;锂离子电池技术中的计算设计方法进展[J];科研信息化技术与应用;2012年01期

2 吴超;马路遥;黄牛;;高性能分子动力学模拟在生物大分子结构和功能研究中的应用[J];科研信息化技术与应用;2010年04期

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

1 杨矫云;大规模生物序列分析的高性能算法和模型[D];中国科学技术大学;2014年

2 吴云剑;分子动力学模拟在几类重要蛋白研究中的应用[D];吉林大学;2014年

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

1 牟丽蓉;改进的AMBER力场研究Trp-cage的折叠机理[D];华东师范大学;2014年

2 程亦超;GPU上图处理并行框架的设计与实现[D];中国科学技术大学;2015年

本文编号：1088996