论文部分内容阅读
大规模图计算分析已经成为目前众多数据分析应用的重要组成部分。图(Graph)作为最基本的抽象数据结构之一,常常被用来表示不同个体间的关系。现在它已经成为许多应用领域的数据表示方式,例如网页搜索排名、社交网络、医药研究、遗传学、传染病学等。GPU已经成为大规模并行计算的主流平台,它可以比多核处理器使用更少的能耗但获取更高的性能。许多面向图计算应用的软件编程框架模型已经开始使用GPU加速图计算算法的性能。本文针对使用GPU平台加速图计算算法存在的负载不平衡和控制流分歧(Control Divergence)等问题,研究分析了图计算算法在GPU上运行时遇到的指令执行和存储访问瓶颈问题,并从GPU体系结构的角度出发,设计并实现了相应的硬件体系结构解决方案,有效解决了图计算应用负载不平衡、数据缓存空间利用率低、高延迟的数据访问等问题,从而提高了GPU执行图计算算法的性能,满足未来解决大规模图计算问题的需求。本文取得的研究成果如下:1.提出并设计实现了一种动态的多粒度GPU数据缓存管理机制。使用GPU并行加速图计算算法存在着诸如存储访问分歧(Memory Divergence)、细粒度数据存储访问以及片上数据缓存空间利用率低等问题,导致GPU无法充分发挥出其应有的计算性能。本文针对图计算算法存储访问请求的数据大小与GPU片上一级数据缓存的缓存块大小之间不匹配的矛盾,提出了动态的多粒度数据缓存管理机制,并在模拟器上设计实现了相应的硬件缓存管理单元。这项缓存管理机制可以解决由不规则存储访问导致的一级数据缓存存储空间利用率低效的问题,有效提高了具有不规则存储访问特点的应用在GPU上执行效率。实验结果表明,相比于现有的GPU一级数据缓存设计以及细粒度的缓存管理机制,所提出的数据缓存管理机制有效地提高了一级数据缓存的空间利用率以及应用程序的性能。2.提出并设计实现了一种面向图数据结构的GPU数据预取技术。虽然针对固定模式数据存储访问模式的数据预取技术已经较为成熟,但是针对不规则的数据存储访问模式的数据预取技术目前还没有找到较好的解决方法。本文通过对宽度优先搜索算法的数据结构访问模式的分析,提出了面向图数据结构的GPU数据预取技术,并在模拟器上设计实现了相应的硬件数据预取单元以及辅助的CUDA编程接口。该技术利用显式获取的图数据结构访问信息,提高了数据预取的准确性,减少了数据预取对存储带宽的消耗,有效地减少了数据访问的延迟。实验结果表明,相比于已有的GPU数据预取技术,所提出的GPU数据预取技术能够有效地提高对不规则存储访问的数据预取准确性,降低了存储访问延迟,进而使GPU执行图计算算法的性能获得巨大提升。3.提出并设计实现了一个新颖的面向图计算的高效GPU体系结构。虽然目前已经提出许多基于GPU的图计算编程框架模型,但是图计算应用的负载平衡问题无法通过软件方法彻底解决。本文针对软件实现的图计算编程框架模型进行分析,提出了一个新颖的面向图计算的高效GPU体系结构,并在模拟器上设计实现了相应的硬件结构以及CUDA编程模型。该技术消除了软件负载平衡策略进行预处理时的指令消耗,实现了SM核内线程间以及SM核间的高效负载平衡。实验结果表明,相比于软件实现的图计算编程框架模型,所提出的GPU体系结构能够有效地减少执行负载平衡的开销,高效地平衡各个计算单元间的工作负载,最终极大地提高了GPU执行图计算算法的吞吐率。