面向众核体系结构的图算法并行优化技术研究

摘要

跨入新时代，计算机融入到人们生活的方方面面，随之也产生了数量巨大的数据需要处理。云计算、物联网、物理学、生物学、环境生态学等领域更需要对海量数据进行挖掘和处理，这预示着我们进入了“大数据”时代。“大数据”时代处理的数据量非常大，数据种类繁多，对数据处理提出了新的挑战。
　　图提供了非结构化数据的自然表现，是大数据的一种非常有效的表示方法。图的遍历是一种基础的图形算法在社交网络、商业分析、高性能计算等领域有广泛应用的图形算法。在单节点上图的遍历已经被研究和优化的非常完善。目前异构计算正变得越来越流行，而CPU+MIC是一种典型的异构体系结构。Intel的MIC（Many Integrated Core）是一种为高并行计算设计的众核协处理器，它拥有大约60个核心。在图的遍历方面，MIC还没有被很好的利用起来。同时图具有：小世界性、无标度性、社区结构等属性。即一部分顶点的度较小，另一部分顶点的度非常大。因此当用MIC来遍历图形时，划分到MIC各个核心的顶点的度差别会很大。经量化分析证明MIC处理并行图算法存在很严重的负载不平衡现象，这会对系统的性能造成不利影响。
　　本文将提出一种算法设计和优化技术来改善MIC上的负载不平衡现象。关于这一优化设计，它的核心思想是将度高的点和度低的点区分处理。为了实现这一思想，本文还提出一种改进的数据结构，以达到将胖节点和瘦节点区分处理的目的。通过这些优化措施，相较于未经优化的算法优化算法获得了非常高的性能提升。同时我们相信这一新颖的算法将会得到广泛的应用，特别是对拥有多个 MIC的大规模并行系统中。
　　本文主要包括以下几个方面的研究工作：
　　（1）MIC是一种超多核心架构的处理器，在处理并行图算法时存在严重的负载不均衡现象。针对这一负载不均衡现象，本文做了深入的量化分析。首先在单一节点上采用方向优化的策略在MIC上实现并行BFS算法，统计出规模是20每次BFS第三层的最大边差（处理边数最多的核的边数减去处理边数最少的核的边数）和最大边差比（处理边数最多的核的边数减去处理边数最少的核的边数除以每个核处理的平均边数）。通过对这两个参数的分析，量化地分析了MIC处理并行图算法的负载不均衡现象。
　　（2）本文主要研究如何减轻MIC上各核处理并行BFS时的负载不均衡现象。图形顶点度的差异是造成MIC负载不均衡的关键因素，因此对MIC的优化的关键是将胖节点和瘦节点区分出来处理。即选择图中度大的若干顶点组成胖节点集合，剩下的度小的顶点组成瘦节点集合。然后将胖节点均匀的分配到MIC的各个核，进行并行宽度优先搜索。再将瘦节点均匀的分配到MIC的各个核，进行并行宽度优先搜索。在进行宽度优先搜索时，采用双向搜索的优化策略。即在对胖节点和瘦节点分别进行并行BFS处理的同时，对算法进行双向搜索的优化，算法性能取得了很大提升。
　　（3）同时本文设计算法将单节点的优化方法推广到大规模并行系统上。设计采用一维和二维的图划分方法，节点间的划分方式不变，对每个节点内的MIC运用上述方法进行负载均衡优化。通过提高每个MIC的性能，提高整个系统的性能。同时采用waves通信、位图、计算和通信重叠等优化技术对算法进行优化。

目录

声明

英文缩写词对照表

第一章 绪论

1.1 研究背景

1.2 研究内容

1.3 论文主要创新点

1.4 本文组织结构

第二章 并行BFS的研究现状

2.1 图的表示与存储

2.2 并行BFS算法介绍

2.3并行BFS面向共享内存系统的研究

2.4 并行BFS面向加速器部件的研究

2.5 本章小结

第三章 量化分析MIC处理并行图算法的负载不均衡现象

3.1 Graph 500图的特点

3.2 MIC上实现并行BFS算法

3.3 量化分析面向MIC并行BFS负载不平衡现象

3.4 本章小结

第四章 负载均衡优化算法

4.1 优化算法简介

4.2 MO-CSR数据结构

4.3 LB-BFS算法

4.4 负载均衡优化效果

4.4 算法性能优化效果

4.5 LB-BFS算法的多节点应用设计

4.6 本章小结

第五章 结 束 语

5.1 工作总结

5.2 工作展望

致谢

参考文献

作者在学期间取得的学术成果