【阿姆斯特丹博士论文】GPU图算法性能分析与预测，227页pdf

2023 年 4 月 10 日 专知

本文研究了输入图的结构与图处理算法GPU (Graphical Processing Unit)并行化策略性能之间的关系 。

加速器，特别是图形处理器(gpu)，已经成为高性能计算(HPC)系统的主要组成部分。因此，分析、理解和预测GPU代码性能的能力对于有效使用这些HPC系统至关重要。

图算法广泛应用于许多科学领域，但如何将图处理算法映射到gpu上却鲜为人知。本文证明了输入图的结构对不同并行化策略的性能有显著影响。用分析模型来预测图的最佳并行化策略是不可行的。本文提出一个使用PageRank和广度优先搜索(BFS)的案例研究，表明可以通过使用二叉决策树(BDT)模型来预测给定图的适当并行化策略来加快它们的性能。

此外，我们制作了一个软件流水线和测量数据集，其他人可以使用这些数据来重现或扩展我们的工作。

我们可以使用图形处理单元(GPU)来提高图处理的性能吗?这个看似简单的问题，正是本文工作的出发点 。然而，在我们考虑这个问题之前，让我们首先考虑一下其中的假设。为什么我们关心图并处理它们?我们为什么关心GPU?为什么要把它们结合起来呢?图是用于描述离散对象之间关系的灵活抽象，使其非常适合建模复杂的结构和/或关系。因此，图被广泛应用于不同的领域，如语言学、物理学、化学、生物学、生物信息学和社会科学。它们的实用性使图成为科学和商业中许多计算问题的核心。随着我们将更多流程和数据数字化，人们想要处理的图形的数量和大小将继续增长。Graph5001排名的增长和活跃就说明了这一点。在可预见的未来，对图处理的需求可能会继续增长。

图处理在这方面并不是唯一的;每个领域对计算能力的需求都在增长。对处理能力不断增长的需求带来了GPU，在过去的15年里，它每美元提供的计算量最多。现代商用GPU的设计-具有大规模、细粒度的并行性和高带宽内存-使它们非常适合作为加速器。现代GPU提供了比大多数传统中央处理器(CPU)和通用多核(GPMCs)架构更好的计算吞吐量(按美元和/或瓦特计算)。对于增加的计算需求，无论是购买价格还是每瓦的计算量，它们都是最具成本效益的解决方案。TOP5002的排名清楚地表明了这一点，其中大多数超级计算机都具有GPU加速器。简而言之，图处理很重要，因为许多实际计算问题都依赖于它。GPU很重要，因为它们是满足日益增长的计算能力需求的最具成本效益的方法，特别是对于大规模并行计算任务。理论上，图处理应该从GPU加速中获益良多，因为图处理算法的特点是可以并行化的大量独立操作和高内存强度[61]。然而，正如本杰明·布鲁斯特所说:“理论上，理论和实践没有区别，而实践却有区别。”“[88]。

第2章概述了图形、GPGPU编程和gpu上的图形处理。为本文的后续讨论提供必要的背景资料 。最重要的是，本文更详细地概述了现代GPU中存在的设计权衡，以及这些权衡如何限制我们对图处理的实现选择。第3章在第17页讨论了经验计算机科学的再现性困难，重点是图处理中的困难。本文介绍了发表在[89]中的软件工具链，我们构建了该工具链，用于收集图算法的性能数据，对这些结果进行数据分析，并根据经验数据评估模型。在第4章中，我们将讨论相邻迭代可能的并行化策略，以及如何使用相邻迭代来实现PageRank和BFS算法。我们使用第17页第3章中的工具链来量化不同并行化策略对PageRank(发表在[92,93])和BFS(发表在[94])性能的影响。第5章第67页介绍了我们基于进化计算的图生成器，发表在[95]。我们构建这个生成器作为概念验证，以为我们的实验生成输入图。然而，由于工程时间的实际限制，我们最终放弃了这种方法，而选择使用真实的数据集。第6章介绍了发表在[94]中的分析工作量模型，用于描述第41页第4章中的并行化策略。这些分析模型不足以准确预测这些算法在GPU上的并行性能。在第7章中，我们展示了如何使用第3章中的工具链来创建二叉决策树(BDT)模型，该模型可以让我们预测给定输入图的算法的最佳实现，发表在[92,93]。此外，还证明了可以通过在遍历期间使用BDT模型动态切换实现来加快BFS遍历。第111页的第8章分析了我们的BDT模型跨数据集和GPU架构的可移植性，发表在[90]中。分析表明，所提出实现的性能特征在GPU架构和数据集上基本稳定。