A Performance Model For Gpu Architectures: Analysis And Design Of Fundamental Algorithms
A Performance Model For Gpu Architectures: Analysis And Design Of Fundamental Algorithms
复制标题
GPU架构的性能模型：基本算法的分析与设计
DOI：
10.15803/ijnc.5.1_26
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ben Karsin
中科院分区：
文献类型：
--
作者：
Ben Karsin
在过去的十年中，“众核”架构已成为解决计算难题的关键资源。这些系统依靠数百或数千个简单的计算核心来实现高计算吞吐量。然而，它们与传统CPU的不同使得现有的算法和模型不适用。因此，开发人员依靠一组启发式方法和依赖于硬件的经验规则来开发多核系统（例如 GPU）的算法。本论文试图通过提出同步并行吞吐量（SPT）模型来解决这个问题，这是一种通用性能模型，旨在捕获对多核架构上算法性能影响最大的因素。该模型重点关注两个经常造成性能瓶颈的因素：内存延迟和同步开销。我们使用一系列测量硬件参数（例如内存访问延迟和峰值带宽）的微基准在三个独立的现代 GPU 平台上实例化 SPT 模型。我们进一步展示了多重性如何通过隐藏延迟和提高整体吞吐量来影响性能。我们将三个基本问题作为本文的案例研究：一般矩阵-矩阵乘法、搜索和排序。使用我们的 SPT 模型，我们分析了矩阵乘法算法的最先进的库实现，并表明我们的模型可以在我们的 GPU 平台上生成平均误差为 5% 的运行时估计。然后，我们在 GPU 内存层次结构的两个级别的上下文中考虑批量前驱搜索问题。在慢速全局内存中，我们证明了 SPT 模型的准确性，而在快速共享内存中，我们确定内存访问模式会造成性能瓶颈，从而降低性能。我们开发了一种新的搜索算法，可以改进访问模式并将 GPU 的性能提高高达 293%。最后，我们通过分析两种最先进的算法来研究 GPU 上基于比较的排序，并使用我们的 SPT 模型确定它们都存在抑制性能的瓶颈。考虑到这些瓶颈，我们开发了 GPU-MMS，即 GPU 高效的多路合并排序算法，并证明它在对随机输入进行排序时比现有算法的高度优化库实现平均高出 21%，在最坏情况输入排列时比现有算法高出 67%。这些案例研究证明了 SPT 模型在分析和开发 GPU 高效算法方面的准确性和适用性。
Over the past decade, “many-core” architectures have become a crucial resources for solving computationally challenging problems. These systems rely on hundreds or thousands of simple compute cores to achieve high computational throughput. However, their divergence from traditional CPUs makes existing algorithms and models inapplicable. Thus, developers rely on a set of heuristics and hardware-dependent rules of thumb to develop algorithms for many-core systems, such as GPUs. This dissertation attempts to remedy this by presenting the Synchronous Parallel Throughput (SPT) model, a general performance model that aims to capture the factors that most impact algorithm performance on many-core architectures. The model focuses on two factors that often create performance bottlenecks: memory latency and synchronization overhead. We instantiate the SPT model on three separate modern GPU platforms using a series of microbenchmarks that measure hardware parameters such as memory access latency and peak bandwidth. We further show how multiplicity affects performance by hiding latencies and increasing overall throughput. We consider three fundamental problems as case studies in this dissertation: general matrix-matrix multiplication, searching, and sorting. Using our SPT model, we analyze a state-of-the-art library implementation of a matrix multiplication algorithm and show that our model can generate runtime estimates with an average error of 5% across our GPU platforms. We then consider the problem of batched predecessor search in the context of two levels of the GPU memory hierarchy. In slow, global memory, we demonstrate the accuracy of the SPT model, while in fast, shared memory, we determine that the memory access patterns create a performance bottleneck that degrades performance. We develop a new searching algorithm that improves the access pattern and increases performance by up to 293% on our GPUs. Finally, we look at comparison-based sorting on GPUs by analyzing two state-of-the-art algorithms and, using our SPT model, determine that they each suffer from bottlenecks that stifle performance. With these bottlenecks in mind, we develop GPU-MMS, our GPU-efficient multiway mergesort algorithm, and demonstrate that it outperforms highly optimized library implementations of existing algorithms by an average of 21% when sorting random inputs and up to 67% on worst-case input permutations. These case studies demonstrate both the accuracy and applicability of the SPT model for analyzing and developing GPU-efficient algorithms.
影响因子：
8.7
作者：
Lin, Feng;Wang, Gang;Yao, Xin
通讯作者：
Yao, Xin