GPU局部感知线程调度潜力研究

### GPU局部感知线程调度潜力研究 #### 1. 引言 在过去十年里，图形处理单元（GPU）成为了非图形计算的热门平台。借助OpenCL和CUDA等语言，程序员能够在计算领域，如线性代数、图像处理和分子科学中使用这些大规模并行架构。随着这类加速器的日益流行，编程、可维护性和可移植性问题变得至关重要。 尽管加速器编程模型在一定程度上解决了这些问题，但程序员仍需针对GPU的内存合并、线程束大小、核心数量和片上内存等方面对代码进行调优。为应对即将到来的内存墙问题，近期的GPU配备了软件管理的片上内存（暂存器）和硬件管理的片上内存（缓存）。对于使用通用内存的集成解决方案，片外内存带宽稀缺，因此高效使用片上内存对于发挥GPU的全部潜力至关重要。 许多GPU程序是内存带宽密集型的，例如在一组基准测试中，31个程序里有18个是这种类型。缓存优化的具体示例包括稀疏矩阵向量乘法的缓存分块（速度提升5倍）和模板计算的循环分块（速度提升3倍）。因此，GPU程序员会进行内存合并以最大化片外吞吐量，或进行分块以改善数据局部性。此外，程序员还需确定线程到线程块的分配，这会影响调度自由度和缓存性能。 使用CUDA和OpenCL等编程模型时，程序员会创建大量独立线程来执行单个程序代码（内核）。然而，像GPU这样的微处理器并未充分利用这种独立性所带来的空间和时间数据局部性潜力。因此，我们提出了局部感知线程调度，即根据内核的内存访问情况改变线程、线程束和线程块的调度。 这项工作并非旨在提高已优化（如合并、分块）代码的性能，而是受非优化程序代码以及局部感知线程调度的性能潜力所驱动。这有助于提高可编程性，而可编程性与以下几个指标密切相关： - 可移植性：程序代码在针对不同微处理器时的通用性。 - 生产力：设计和维护程序代码所需的时间。 - 性能：程序的速度或能源效率。 虽然这项工作主要关注GPU，但这些想法同样适用于以单程序多数据（SPMD）方式编程的其他基于缓存的处理器。本工作表明，局部感知线程调度可以显著提高GPU的可编程性，主要贡献如下： - 第5节：识别并量化了GPU多级局部感知线程调度在几个非优化基准测试中的潜力。 - 第6节：进一步评估了两个示例内核，确定了线程调度对缓存和内存银行局部性等方面的影响。 #### 2. 背景 本节简要介绍GPU架构及其执行模型，更多背景信息可在CUDA编程指南中找到。本文以NVIDIA的Fermi架构为例，该架构最多有16个核心（也称为流式多处理器或计算单元）。每个核心包含32个处理元素（或CUDA核心）和一个64KB的片上可配置内存，它结合了暂存器和L1数据缓存（16/48KB或48/16KB）。所有核心共享一个更大的L2缓存（最大768KB）。 CUDA和OpenCL编程模型允许程序员指定在不同数据上多次执行的小程序（内核）。每个内核实例（在CUDA术语中是线程，在OpenCL术语中是工作项）都有自己独特的标识符。此外，程序员会将所有线程划分为固定大小的块（在CUDA术语中是线程块，在OpenCL术语中是工作组）。块内的线程共享片上本地内存并可以同步，但块之间无法同步。 在Fermi GPU中，一个线程块会被完整映射到一个核心上。来自一个或多个线程块的线程可以在单个核心上形成一组活动线程。对于Fermi GPU，这组活动线程最多限制为8个线程块或1536个线程，以先达到的限制为准。这样一组活动线程会以多线程方式作为线程束（NVIDIA）或波前（AMD）并发执行。在Fermi中，一个线程束是一组32个线程，它们以类似单指令多数据（SIMD）的方式在单个核心上执行，将工作负载分配到处理元素上。 #### 3. 相关工作 早期的工作已经对非GPU微处理器的局部感知线程调度进行了研究。例如，Philbin等人将单核心处理器的局部感知线程调度问题进行了形式化。Tam等人根据数据局部性对多线程多核处理器的线程进行分组，并引入了线程相似度的度量。此外，Ding和Zhong提出了一个基于重用距离来估计局部性的模型。但这些方法不能直接应用于GPU，因为它们没有考虑到线程可扩展性、缓存大小、线程 - 线程束 - 块层次结构以及活动线程数量等方面。 近期关于GPU的工作研究了调度较少活动线程以改善缓存行为的潜力。Kayiran等人提出了一种计算/内存强度启发式方法来选择活动线程数量。Rogers等人提出了一种硬件方法，即根据丢失的局部性计数器在运行时调整活动线程数量。然而，这些工作仅考虑了减少活动线程数量，并未研究线程调度。 当前GPU的调度研究主要集中在发散控制流而非数据局部性方面。通过动态地将线程重新分组为线程束，可以将遵循相同执行路径的线程调度在一起。例如，在内存访问合并的背景下讨论了动态线程束形成。近期的工作则侧重于两级线程束调度以减少内存延迟的影响。虽然我们不涉及控制流，但理想的调度器应同时考虑数据局部性和控制流这两个方面。 #### 4. 实验设置 本工作的实验使用GPGPU - Sim 3.2.1进行，采用GeForce GTX580配置（Fermi），具有16KB的L1缓存（128字节缓存行）和768KB的L2缓存。GTX580有16个单指令多线程（SIMT）核心（或SM），总共512个CUDA核心