论文部分内容阅读
近年来,人类生活中产生的数据规模急剧增长,因此也催动了大数据、云计算等技术的发展与成熟。数据可以划分为结构化数据、半结构化数据以及非结构化数据,图数据作为半结构化数据的典型代表,如何有效处理大规模图数据成为目前学术领域和工业领域的研究热点和难点。由于图数据的天然不规则特性导致基于通用处理器的图计算系统在处理大规模图数据时表现出较差的计算效率和访存效率,而基于硬件平台定制图计算加速器成为提高图数据处理效率的途径之一。本文首先分析和评估了基于通用处理器的单机图计算系统,分析了基于通用处理器的单机图计算系统的计算效率和访存效率,比较了同步计算方式与异步计算方式的收敛速度,描述了异构图计算加速器的性能模型;进一步地,本文设计了异步高能效图计算加速器Domino和可扩展的图计算加速器OmniGraph,并以加速器的设计为基础构建异构图计算系统Jakiro。本文主要工作和创新点如下:(1)针对基于通用处理器的单机图计算系统,本文设计了单机图计算系统的分析评估框架,该框架可对基于通用处理器的单机图计算系统进行分析与评估,评估的角度包括性能、数据局部性、CPU利用率等指标,分析和评估的结论能够作为用户根据自身应用的特征和数据集特征选择合适图计算系统的参考指南;(2)分析了基于通用处理器的单机图计算系统的计算效率和访存效率,描述了异构图计算加速器的性能模型,在分析的基础上设计了基于FPGA的异步高能效图计算加速器Domino,Domino分别采用线性更新策略和二分更新策略进行异步控制。实验结果表明,Domino相对于Intel Core2 Processors能够获得1.47x～7.84x加速比,相对于Intel Core i7 Processors能够获得0.47x～2.52x加速比,并且能够获得2.03x～10.08x能效比;(3)本文设计了可扩展的图计算加速器OmniGraph,OmniGraph能够根据图数据的规模选择对应的图计算引擎,并且优化了片外图数据的布局方式。实验结果表明,MGPE(Medium-scale Graph Processing Engine)计算引擎相对于 Intel Core2 Processors 能够获得 1.03x～8.13x 加速比;(4)本文基于图计算加速器的设计,构建了基于硬件加速器的异构图计算系统Jakiro,设计了异构图计算系统Jakiro的层次化架构并且实现了相应的应用程序接口函数、描述了基于Jakiro的StreamEdges-Reduce-Update编程模型。本文设计的异步高能效图计算加速器相比于单机图计算系统GraphChi有着良好的加速比,并且有着更低的功耗、能耗开销;此外,在基于硬件加速器的异构图计算系统Jakiro的编程模型中,用户可以直接调用相应的接口函数来使用底层设计好的加速器。