《Parallel Computing》:A critical-warp and cache-locality-aware warp scheduling policy for GPGPU
编辑推荐:
摘要图形处理单元(GPU)由于其大规模并行架构,已成为通用图形处理器(GPGPU)工作负载的主要加速器。在单指令多线程(SIMT)执行模型下,线程被组织成固定大小的 Warp,并以锁步方式执行。因此,Warp 调度在决定整体系统吞吐量方面起着关键作用。然而,现有的调度策略难以
摘要
图形处理单元(GPU)由于其大规模并行架构,已成为通用图形处理器(GPGPU)工作负载的主要加速器。在单指令多线程(SIMT)执行模型下,线程被组织成固定大小的 Warp,并以锁步方式执行。因此,Warp 调度在决定整体系统吞吐量方面起着关键作用。然而,现有的调度策略难以高效处理关键 Warp,即那些主导应用程序完成时间的 Warp。同时,单一静态调度策略往往不足以适应现代工作负载多样化的内存访问和执行特性。本文首先提出了一种关键性感知松散轮询(C_LRR)调度器。通过在运行时识别关键 Warp 并提高其调度优先级,C_LRR 在保持轮询调度公平性的同时,加速了进度滞后 Warp 的执行。在 C_LRR 的基础上,本文进一步引入了一种缓存局部性感知机制,并开发了一种缓存感知关键 Warp 调度策略(CACWSP)。CACWSP 根据观察到的 L1 数据缓存重用行为,自适应地在贪婪 - 然后 - 最老(GTO)调度器和 C_LRR 调度器之间切换,从而同时提高缓存利用率和 Warp 级并行性。使用 GPGPU-Sim 在 Rodinia 基准测试套件和具有代表性的卷积神经网络(CNN)推理工作负载上进行的周期精确模拟表明,CACWSP 与最先进的 CAWS 调度器相比,平均性能提升了 10.64%,同时在多样化的 CNN 推理任务中保持了稳定的执行效率。
引言
图形处理单元(GPU)最初的设计目的是减轻中央处理单元(CPU)的负担并处理与图像相关的计算任务。如今,得益于 GPU 的大规模并行计算能力,研究人员将这些设备应用于通用计算任务,如流体动力学、数据挖掘等 [1], [2], [3]。用于这些目的的 GPU 被称为通用图形处理器(GPGPU)。GPGPU 计算技术的发展产生了深远影响;在密集并行计算和高精度算术中,GPGPU 的性能可以是 CPU 的数十倍到数百倍 [4], [5]。
在 GPGPU 执行期间,连续的线程被组织成 Warp,作为 SIMT 执行模型下的基本调度单位。在一个 Warp 内,多个线程接收共同的指令流,同时操作不同的数据元素,从而实现大规模线程级并行 [6]。然而,当发生控制流发散时,例如在 if-else 分支中,在传统 SIMT 执行模型下,同一 Warp 内的不同执行路径无法同时执行。相反,这些路径必须串行处理,导致非活动分支通道的资源暂时闲置,并降低了有效指令吞吐量 [7]。
当 Warp 由于线程发散(例如条件分支)或访问延迟而停顿时,GPGPU 中的 Warp 调度器会立即执行上下文切换,交换出被阻塞的 Warp 并选择一个就绪的 Warp 进行发射,从而利用其他 Warp 的有效指令来掩盖被挂起 Warp 的停顿延迟。该机制掩盖了停顿 Warp 的延迟,从而显著减少了计算单元的闲置时间,提高了整体资源利用率 [8], [9]。然而,如果当前流多处理器(SM)缺乏足够数量的就绪 Warp,调度器无法及时填补延迟差距,导致整体任务执行效率急剧下降。使用广度优先搜索(bfs)算法的案例研究表明,最快和最慢 Warp 之间的执行时间差超过 50% [10];研究人员发现,GPU 的延迟隐藏能力仍有显著提升空间。
目前,两种主导的 Warp 调度算法是松散轮询(LRR)和贪婪 - 然后 - 最老(GTO)[11]。LRR 为每个 Warp 分配相等的优先级,并逐周期在它们之间轮换,这通常导致大量 Warp 同时遇到长延迟事件;相比之下,GTO 优先处理最老的 Warp,并继续执行它直到其停顿后才切换。除了这两种截然不同的调度算法外,研究人员表明,明智地使用数据局部性可以产生显著的性能增益。局部性分为两类:Warp 间局部性——由一个 Warp 首次引用,随后被另一个 Warp 重用的数据;Warp 内局部性——由一个 Warp 首次引用,随后被同一 Warp 重用的数据。现有研究表明,单一调度器无法匹配所有程序阶段的特性;因此,研究人员正致力于设计能够在运行时动态演化、实时适应不同程序阶段需求的调度算法 [2]。
不同的调度算法以不同的方式贡献于延迟隐藏,而程序特性反过来决定每种算法的有效性。当算法与程序阶段不匹配时,计算资源利用率下降,整体 GPGPU 性能受损。因此,为每个程序阶段选择合适的调度算法可以有效减少发散等待时间并增强延迟隐藏能力。
为了缓解由进度滞后的关键 Warp 引起的延迟,本文提出了一种关键性感知的 Warp 调度机制,用于管理 GPU 上的共享计算和内存资源。所提出的机制加速了较慢的 Warp,减少了并行 Warp 之间的执行时间方差,并根据主导的缓存局部性特性动态选择合适的调度策略。具体而言,所提出的框架由三个主要组件组成。首先,关键性预测逻辑(CPL)监控每个 Warp 的运行时执行行为,并识别进度滞后的关键 Warp。其次,C_LRR 利用 CPL 结果优先处理这些 Warp,并为它们提供更早的发射机会,同时保持轮询调度的公平性。第三,缓存局部性代理采样 L1D 缓存访问行为,并根据观察到的局部性特性动态选择合适的调度策略。
CACWSP 的设计理念是通过监控 Warp PC 跟踪特性和 L1D 缓存局部性来动态管理计算资源和调度器,从而加速关键 Warp 的执行。与现有调度算法相比,所提出的算法同时考虑了 Warp 之间的执行时间方差和 L1D 缓存的局部性特性,从而减少了同步开销。
章节摘要
背景与动机
本节讨论了 GPGPU 的相关背景和本文的动机。
方法
基于第 2 节的分析,我们提出了一种 GPU 微架构增强方案,旨在通过三个核心机制减少由线程同步引起的闲置时间并提高整体效率。
图 5 概述了我们提出的针对缓存局部性感知线程调度优化的 GPU 架构。
- 步骤 1
执行从 L1 指令缓存提供指令流开始,该指令流由指令获取单元获取并由指令解码器解码。该
评估
在本节中,我们详细介绍了实验设置和所使用的基准测试,并展示了本文提出的算法在各种现实世界测试程序上的性能。
相关工作
先前的研究广泛探讨了数据局部性如何促进 GPGPU 性能,并为不同类型的局部性提出了多种优化方案。DEVASHREE [30] 引入了 PAVER,一种基于图的线程块调度框架。该框架在即时编译(JIT)时捕获 CTA(协作线程数组)间的数据共享信息,并通过最小生成树(MST)和 K 路划分算法将线程块重新组织为局部性感知组,从而提高片上数据重用。ADITYA
结论
本研究针对 GPGPU 执行中由分支发散引起的性能退化、由进度滞后 Warp 引起的延迟以及缓存局部性利用不足的问题。所提出的方法首先在运行时识别进度滞后的关键 Warp,并从具有最高运行时关键性的 Warp 开始调度。然后,它实时监控缓存局部性,并根据观察到的局部性特性在 GTO 和 C_LRR 之间动态切换。以此方式,
CRediT 作者贡献声明
Juan Fang: 写作 – 审阅与编辑,监督,项目管理,资金获取,概念构思。 Yubin He: 写作 – 原稿,可视化,软件,方法学,调查,形式化分析,数据整理。 Jingming Guo: 写作 – 原稿,软件,数据整理。
利益冲突声明
作者声明他们不存在已知的竞争性经济利益或个人关系,这些利益或关系可能被认为影响了本论文报告的工作。
致谢
本工作得到了 国家自然科学基金(61202076)和 北京市自然科学基金(4262021)以及其它政府赞助机构的支持。
Juan Fang|Yubin He|Jingming Guo