论文部分内容阅读
图是一种表达能力很强的数据结构,它可以表示现实世界中对象和对象之间的关系,如城市与城市间的道路连接、人之间的血缘关系。许多问题都可以用图表示再通过图算法解决。图和图算法在社交网络、基因分析等领域有着广泛应用,随着图数据规模的高速增长,如何高效处理图数据已经成为研究热点。广度优先搜索(Breadth-first search,BFS)算法是一种具有代表性的图搜索算法,Graph500测试程序使用它来评测计算机系统运行大数据应用的能力,研究它的优化技术可以为其它图算法的优化提供借鉴。为了研究BFS算法在Xeon Phi众核处理器上的优化技术,本文在新一代Xeon Phi众核处理器(KNL)上结合硬件特性对广度优先搜索算法进行优化。主要研究工作和成果如下:1.提出了一种针对KNL的片上网络对BFS算法进行优化的方法。KNL与前几代产品不同,它的处理器核通过二维片上网络进行互联,该网络具有多种不同工作模式。本文提出了针对该网络对BFS算法进行优化的方法,有效提高了BFS算法的性能。2.设计实现了一个针对KNL的特点深度优化的混合BFS算法。在针对片上网络进行优化的基础上,还从两个方面对混合BFS算法进行进一步优化:a.向量化搜索。KNL众核处理器所配备的高级向量指令集扩展提供了一次处理512bit数据的能力。为充分利用BFS算法的并行性,提出在广度优先搜索算法的自底向上搜索阶段使用向量指令并行搜索边表,进一步发掘并行性;b.对输入数据进行预处理以减少工作量。对图的顶点进行重新编号删除孤立顶点,减小位图数据结构的大小,减少了搜索时遍历位图的工作量;对邻接点列表进行排序,减少了边检查次数。实验结果表明,本文提出的针对片上网络进行优化的方法可以有效提高BFS算法的性能。在此基础上结合硬件特性进行深度优化的混合BFS算法具有优秀的性能,可以作为其它图算法的组成模块,具有实用价值。