面向众核体系结构的宽度优先搜索算法研究

论文摘要

宽度优先搜索（Breadth-first Search,简称BFS）是一种基础的图形算法,是众多算法的核心组件,在大量领域中得到广泛应用,如网络安全、医学信息、数据挖掘、社交网络、语义网等等。宽度优先搜索算法还是一种典型的数据密集型应用,Graph 500即使用其对超级计算机处理数据密集型应用的能力进行排名。近年来,得益于较低的功耗和较高的性价比,众核体系结构的加速器在高性能计算领域得到广泛应用。MIC（Many Integreated Core）作为最新的众核体系结构协处理器,相对于其它加速器来说,具有和传统并行编程模型兼容的优势。随着采用CPU+MIC的“天河二号”登上Top 500榜首,MIC在高性能计算领域得到广泛重视。宽度优先搜索算法的并行实现具有数据竞争较严重、问题不规则和访存局部性差等特点,而MIC具有大量线程和宽向量处理能力且每线程的平均缓存较小,因而要充分发挥MIC硬件的优势高效实现宽度优先搜索,将面临线程间竞争开销较大,向量部件利用率不高,缓存利用率差等问题。本文即面向这些问题,研究利用MIC高效实现宽度优先搜索算法,主要取得了如下成果:1)设计并实现了自上向下和自下向上相结合的混合BFS算法。该算法根据图形的特点,在不同的搜索层使用不同的搜索策略,能够结合两种搜索策略的优势,性能分别为自上向下和自下向上策略的3.21和2.15倍。2)提出了一种面向MIC优化的多线程BFS算法。该算法以混合BFS算法为基础,通过减少数据竞争,消除原子操作,并采用动静相结合的线程调度方式,能够很好地利用MIC提供的大量线程处理能力。3)提出了一种使用宽向量部件进一步加速BFS的方法。该方法在自上向下搜索部分采用SIMD指令同时扫描顶点的邻居,在自下向上搜索部分采用SIMD指令并行查找未访问的顶点,能够进一步加速BFS算法,最高加速比达到1.85。4)设计并实现了CPU和MIC协同计算的异构混合BFS算法。该算法以混合BFS算法为基础,在搜索层中任务较多时采用CPU和MIC协同计算,通过比例可调的任务划分方法以及重叠计算的通信设计,解决了协同计算中任务不均衡和通信开销较大的问题,相对于CPU的加速比达到1.4倍左右。实验结果表明,本文在MIC中实现的BFS算法性能约为GPU的5.31倍;CPU+MIC异构混合算法的最高加速比达到1.46倍。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 面向共享内存体系结构的研究
• 1.2.2 面向分布内存体系结构的研究
• 1.2.3 面向GPU的研究
• 1.2.4 面向其它平台的研究
• 1.3 研究内容和主要贡献
• 1.4 本文组织结构
• 第二章 BFS算法与众核体系结构
• 2.1 宽度优先搜索算法分析
• 2.1.1 图形结构的特点
• 2.1.2 图形的生成与算法评估
• 2.1.3 图形的存储与表示
• 2.1.4 层间同步BFS算法
• 2.1.5 并行BFS算法的主要特点
• 2.2 MIC体系结构特点分析
• 2.2.1 MIC体系结构介绍
• 2.2.2 MIC编程模型介绍
• 2.2.3 MIC中的SIMD指令
• 2.2.4 MIC体系结构的主要特点
• 2.3 面临的挑战
• 2.4 总结
• 第三章 BFS算法的多核实现技术
• 3.1 自上向下搜索算法
• 3.1.1 并行策略
• 3.1.2 数据结构
• 3.1.3 冲突处理
• 3.1.4 实现技术
• 3.1.5 适用情况
• 3.2 自下向上搜索算法
• 3.2.1 并行策略
• 3.2.2 数据结构
• 3.2.3 实现技术
• 3.2.4 适用情况
• 3.3 混合搜索算法
• 3.3.1 算法框架
• 3.3.2 图的存储
• 3.3.3 数据结构
• 3.3.4 切换时机
• 3.4 实验与性能分析
• 3.4.1 实验环境
• 3.4.2 自上向下搜索实验
• 3.4.3 自下向上搜索实验
• 3.4.4 混合搜索实验
• 3.5 总结
• 第四章 BFS算法的众核优化实现技术
• 4.1 多线程优化实现
• 4.1.1 多线程实现方法
• 4.1.2 减少数据竞争的优化
• 4.1.3 无原子操作方法
• 4.1.4 线程调度与绑定
• 4.2 SIMD优化
• 4.2.1 自上向下搜索SIMD的使用
• 4.2.2 自下向上搜索SIMD的使用
• 4.2.3 混合搜索中SIMD的使用
• 4.3 实验与性能分析
• 4.3.1 实验环境
• 4.3.2 实验结果
• 4.3.3 性能比较
• 4.4 总结
• 第五章 BFS算法的异构混合实现技术
• 5.1 算法思想
• 5.2 算法设计
• 5.2.1 算法框架
• 5.2.2 任务划分
• 5.2.3 通信设计
• 5.3 实现技术
• 5.3.1 基于编译指导命令的实现技术
• 5.3.2 基于底层通信接口的实现技术
• 5.3.3 算法实现
• 5.4 算法分析
• 5.4.1 存储量分析
• 5.4.2 通信量分析
• 5.5 实验与性能分析
• 5.5.1 实验环境
• 5.5.2 任务划分实验
• 5.5.3 综合实验
• 5.6 总结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果