摘要
随着数字经济在全球的推进以及人工智能等技术的快速发展，我们已然处于全球数据飞速增长的大数据时代。其中以图为代表的非结构化数据更是以65％的增长率持续增长。图因为拥有丰富和强大的数据表达能力，被广泛地用于表征数据属性和事物关系。现实场景的图数据中通常含有丰富的信息和价值。面对海量且增长迅速的图数据，如何在有效时间内从图数据中挖掘出有价值的信息是一项挑战性巨大的工作。 图计算作为大规模数据分析的代表性应用之一，能够有效挖掘非结构化图数据中的潜在价值。基于矩阵运算的图计算因为拥有扎实的数学理论基础和高性能，近年来更是得到学术界和工业界的广泛关注。但是由于图数据本身和图算法存在以下特点:①图数据具有高度稀疏性，造成了图算法执行时的随机性和较差的局部性;②图数据的规模庞大，并且顶点的度数服从幂律分布，容易造成图算法执行时的负载不均衡，以上特征给传统通用处理器架构带来了严峻的挑战。因此为图计算设计专用的加速器结构成为了近年来热门的研究方向之一。 目前已有的图计算加速器工作主要集中在使用应用专用集成电路(Applica-tion Specific Integrated Circuit,ASIC)、内存计算(Processing in Memory,PIM)架构和现场可编程逻辑门阵列(Field Programmable Gate Array,FPGA)等主流硬件平台的特征来优化图计算应用的执行。尽管现有工作已对图计算应用加速取得了一些成果，但各主流硬件平台都还面临着以下问题:①基于ASIC平台的数据通路固定缺乏灵活性，新型存储技术不成熟;②细粒度的可重构架构FPGA的配置开销过大，片上资源有限;③在粗粒度可重构架构(Coarse Grained Recon-figurable Architecture,CGRA)上执行高度稀疏不规则图应用效率低下;④现有绝大部分工作都是基于以顶点为中心的图计算应用开展的量化分析和优化，针对基于矩阵运算的图计算应用开展的系统性量化分析和优化仍然有待挖掘。针对上述问题，本文从以下三个研究点出发，基于粗粒度可重构架构对基于矩阵运算的图计算应用展开优化。 ①基于矩阵运算的图计算应用瓶颈量化分析:第一个研究点针对图计算应用，尤其是对基于矩阵运算的图计算应用的执行特征进行系统性量化分析，从而指出其性能瓶颈和潜在优化方向。大量的实验分析表明，基于矩阵运算的图计算应用对硬件灵活性需求极大，核心原因是不同图算法中的核心矩阵算子具有差异较大的计算和访存特征，同时发现基于CGRA的图计算加速器以全卸载方式时执行存在需要耗时且频繁的数据传输，硬件利用率低下等问题。因此从以上两个方面进行优化对图计算加速具有十分重要的意义。该研究点通过对基于矩阵运算的图计算应用量化分析，深入探究了其软硬件加速的机遇，能够有效指导后续的专用加速结构的优化设计。 ②基于输入感知的指令共享图计算加速结构:第二个研究点针对基于矩阵运算的图计算应用对硬件灵活性需求高和图数据高度稀疏的问题，基于可灵活配置的CGRA提出了一个基于输入感知的指令共享图计算加速结构MatGraph。本研究从图算法的核心矩阵算子中抽象定义精简指令来灵活支持各种各样的图算法，以此应对图计算应用对计算硬件灵活性需求高的挑战。同时通过本研究提出的基于输入感知的指令过滤和稀疏去除机制，MatGraph可以感知不同输入来去除输入极高稀疏性带来的冗余指令计算和访存，让计算单元之间可以高效地共享同一套指令。此外，本研究还设计了多模式的片上存储部件以应对访存硬件灵活性需求高的挑战，它可以根据不同输入的特征灵活选择最合理高效的片上存储部件，从而实现了从计算和访存两方面提升图计算应用的整体性能。实验表明，与最先进的CPU和GPGPU上的解决方案相比,MatGraph分别实现了 9.35倍、2.28倍的性能提升和11.17倍、7.15倍的能效提升。与最先进的图计算加速器Graphicionado相比，MatGraph还实现了 1.59倍的性能提升和1.61倍的能效提升。 ③基于动态调度的图计算异构加速结构:第三个研究点针对现有大多数图计算加速器采用全卸载方式执行时存在耗时的频繁数据传输和低硬件利用率等问题，设计了一个基于动态调度的图计算异构加速结构HetGraph。该结构通过共享内存的CPU和CGRA异构协同执行解耦的图计算模型，从而避免了频繁的跨内存数据传输，提升了整体硬件利用率。此外，通过在HetGraph上设计稀疏去除策略和动态调度策略实现基于共享内存的CPU-CGRA之间的负载均衡，进一步提升了异构系统的整体执行效率。实验表明，与最先进的CPU和GPGPU上的解决方案相比，HetGraph平均实现了 9.42倍、2.45倍的性能提升和9.80倍、7.70倍的能效提升。与最先进的图计算加速器Graphicionado相比，HetGraph也实现了 1.42倍的性能提升和1.06倍的能效提升。
NETL