Microsecond-scale Preemption for Concurrent GPU-accelerated DNN Inferences

作者：Mingcong Han1,2, Hanze Zhang1,4, Rong Chen1,2, and Haibo Chen1,3
机构：1上海交通大学并行与分布式系统研究所（SEIEE），2上海人工智能实验室，3教育部领域专用操作系统工程研究中心，4上海交通大学人工智能研究院，教育部人工智能重点实验室

A1 主要贡献

许多智能应用（如自动驾驶和虚拟现实）需要在GPU上同时运行延迟关键型（latency-critical）和尽力而为型（best-effort）的DNN推理任务，以实现实时响应和工作保持（work conserving）。然而，商用GPU缺乏高效的抢占式调度支持，现有技术要么独占GPU导致利用率低下，要么让实时任务等待尽力而为任务完成导致高延迟。

本文提出了REEF，这是首个在GPU调度中实现微秒级内核抢占和受控并发执行的GPU加速DNN推理服务系统。REEF的创新体现在两个方面：
1. 基于重置的抢占方案 (Reset-based Preemption)：基于DNN推理内核大多是幂等的（idempotent）这一观察，REEF设计了一种基于重置的抢占方案。当实时任务到达时，该方案通过主动终止并随后恢复正在运行的尽力而为内核，从而在微秒级别的时间内将实时内核调度到GPU上。
2. 动态内核填充机制 (Dynamic Kernel Padding)：鉴于DNN推理内核具有多样化的并行度和可预测的延迟，REEF提出了一种动态内核填充机制。该机制根据实时内核的资源需求，动态地选择合适的尽力而为内核来“填充”GPU的剩余资源，从而在几乎没有开销的情况下充分利用GPU。

本文的主要贡献如下：
* 深入理解GPU加速DNN推理的特性：揭示了DNN推理任务的幂等性、大量内核、延迟可预测性和并行度多样性等特点，并分析了现有GPU调度方案在应对这些特性时存在的问题（§2）。
* 新颖的基于重置的抢占方案：该方案能够在几微秒内将实时内核调度到GPU上，且抢占延迟与被抢占内核的数量无关（§4）。
* 优雅的动态内核填充机制：该机制能够动态地将尽力而为内核与实时内核结合，以充分利用GPU的大规模并行性（§5）。
* 在AMD和NVIDIA GPU上的实现与评估：通过在一个新的DNN推理服务基准（DISB）和真实世界轨迹上的评估，证明了REEF相比现有技术的优越性和有效性（§6, §7）。


图 1: (a) DNN推理（包括实时和尽力而为任务）的总体吞吐量；(b) 使用并发GPU调度（即多个GPU流）时实时任务的端到端延迟；(c) 使用抢占式GPU调度（即基于等待的抢占）时实时任务的端到端延迟；(d) 随着实时任务频率增加，尽力而为任务的吞吐量。工作负载：VGG（实时）和ResNet（尽力而为）。测试平台：一块拥有16GB内存的AMD Radeon Instinct MI50 GPU。

A3 背景知识、关键观察与设计原则

2.1 GPU加速DNN推理的特性

深度神经网络（DNN）由多个通用层（如卷积层、池化层和全连接层）的实例组成。为了在GPU上服务推理请求，预训练的DNN模型会提前加载到GPU内存中。对于每个到达的请求，DNN模型的所有内核会依次执行，并将结果返回给应用程序。


图 2: 使用类似ResNet模型的DNN推理示例。

DNN推理被用于实时（RT）任务（如障碍物和交通灯识别）和尽力而为（BE）任务（如情绪和疲劳监测）。实时任务对延迟非常敏感，而尽力而为任务没有严格的时间要求。

  • 幂等性 (Idempotence)：我们观察到DNN模型中的GPU内核大多是幂等的，因为它们几乎只包含无副作用的密集线性代数计算。这意味着无论内核是否被重试，只要输入相同，总能产生相同的输出。在DNN模型中，第k个内核总是使用第k-1个内核的输出和静态参数（如权重）作为输入。因此，DNN推理任务的执行可以从被中断内核之前的任何一个内核恢复，而不会改变推理结果。

  • 海量内核 (Massive kernels)：与传统GPU应用（如Rodinia【11, Shuai Che et al. Rodinia: A Benchmark Suite for Heterogeneous Computing. IEEE International Symposium on Workload Characterization, 2009.】最多14个内核）不同，现代DNN模型通常包含数百个内核（见表1）。为了隐藏内核启动时间，系统会提前提交大量内核。此外，为了充分利用GPU，服务系统可能会并发执行来自不同推理任务的多个内核。因此，抢占GPU的性能代价可能非常大（几毫秒），甚至与数百个内核的执行时间相当。

    Table 1: §7中评估的DNN模型中的GPU内核数量和执行时间（毫秒）。代码由TVM【15, T. Chen et al. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI’18, 2018.】生成，并在AMD Radeon Instinct MI50 GPU上运行。

  • 延迟可预测性 (Latency predictability)：我们观察到，当DNN推理中的GPU内核单独在GPU上运行时（无干扰），其执行时间是确定且可预测的。原因有二：首先，内核主要是线性代数计算，如矩阵乘法和卷积，既不包含条件分支，也没有可变循环。其次，所有内核参数（如输入和权重）和输出都是固定大小的数组。因此，这类内核的执行时间与推理请求的输入无关，可以提前测量和准确预测。实践中，我们观察到DNN模型内核执行时间的方差通常只有几微秒（见图3(a)），这一点也得到了近期文献的证实【6, Zhihao Bai et al. PipeSwitch: Fast Pipelined Context Switching for Deep Learning Applications. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】【28, A. Gujarati et al. Serving DNNs like Clockwork: Performance Predictability from the Bottom Up. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】【47, Lingxiao Ma et al. Rammer: Enabling Holistic Deep Learning Compiler Optimizations with rTasks. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】。


    图 3: (a) VGG中几个典型内核执行时间的累积分布函数（CDF），以及(b) 在拥有60个计算单元（CU）的GPU上执行VGG期间CU使用率的时间线。注意VGG中GPU内核的执行时间覆盖了从10 µs到255 µs的相当宽的范围（见图10）。

  • 并行度多样性 (Varied parallelism)：由于输入尺度的不同，DNN推理中的GPU内核通常表现出完全不同的并行度。例如，如图2所示，池化内核使用64个线程块，而softmax内核只使用1个。因此，DNN推理的计算需求，即计算单元（CU）的数量，在执行过程中是不断变化的。如图3(b)所示，VGG执行期间的CU使用率在6.7%到86.7%之间变化。因此，为了高效利用GPU，必须采用动态机制在运行时选择并执行来自不同DNN推理任务的多个内核。

2.2 现有GPU调度技术

DNN推理服务系统依赖GPU调度来满足两个可能冲突的性能目标：低延迟和工作保持。尽管GPU调度在高性能计算社区已有广泛研究，但DNN推理的独特性质带来了新的挑战。

  • 顺序执行 (Sequential execution)：大多数现有DNN服务系统（如Clockwork【28, A. Gujarati et al. Serving DNNs like Clockwork: Performance Predictability from the Bottom Up. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】）采用顺序执行以避免任务间干扰。这样每个任务可以获得最优执行延迟（如图4(a)）。然而，由于没有抢占机制，实时任务的端到端延迟可能会因等待前一个任务完成而显著增加。此外，该方案由于顺序服务推理任务，总体吞吐量较差。

  • 块级抢占 (Block-level preemption)：为了降低实时任务的延迟，需要从正在运行的尽力而为任务中抢占GPU。然而，由于上下文庞大（例如大量寄存器），在GPU上实现抢占式调度很困难，且商用GPU缺乏硬件支持。作为折衷，先前工作【8, C. Basaran and K. Kang. Supporting Preemptive Task Executions and Memory Copies in GPGPUs. In 24th Euromicro Conference on Real-Time Systems, ECRTS’12, 2012.】【90, H. Zhou, G. Tong, and Cong Liu. GPES: A Preemptive Execution System for GPGPU Computing. 21st IEEE Real-Time and Embedded Technology and Applications Symposium, 2015.】提出了基于等待的方法来实现块级抢占。实时任务仍需被动等待正在运行的块完成（如图4(b)），抢占延迟会随着被抢占内核数量的增加而增加（见图1(c)）。这对于DNN推理是不切实际的，因为需要提交大量内核。此外，高频率的实时任务可能会导致尽力而为任务饿死（见图1(d)）。

  • 多个GPU流 (Multiple GPU streams)：为了提高总体吞吐量，现代GPU库（如CUDA【52, NVIDIA. CUDA Toolkit, 2021.】和ROCm【3, AMD ROCm. AMD ROCm Platform Documentation, 2022.】）提供多个GPU流来并发执行来自独立任务的内核。运行时调度器按需从GPU流中分派内核以保持所有CU繁忙（如图4(c)）。虽然这能提高吞吐量（见图1(a)），但实时任务的延迟会因并发任务而显著恶化（见图1(b)），且延迟开销随并发任务数量增加而增加。


图 4: 一个混合工作负载的GPU任务调度示例，包含两个尽力而为任务和一个实时DNN推理任务。GPU有四个计算单元（CU）。(a)顺序执行无抢占 (b)块级抢占 (c)多GPU流并发 (d)理想调度

3 REEF 概览

3.1 系统架构

REEF的目标是提供抢占式GPU调度，以实现延迟关键型任务的实时性和尽力而为任务的工作保持性（如图4理想调度所示）。基于DNN推理内核大多是幂等的，并且存在大量具有不同并行度和可预测延迟的内核这一洞察，REEF提出了两个新颖的设计：基于重置的抢占和动态内核填充。

REEF的架构如图5所示，包括离线和在线两部分：
* DNN模型准备（离线）：DNN模型首先被编译和优化，然后加载到模型池中。REEF扩展了模型编译器（如TVM【15, T. Chen et al. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI’18, 2018.】），增加了一个代码转换模块，用于验证内核的幂等性并转换源代码以辅助调度。此外，REEF开发了一个内核分析器来测量每个内核的计算需求和执行时间。

  • DNN推理服务（在线）：REEF扩展了现有的GPU运行时（如ROCm【3, AMD ROCm. AMD ROCm Platform Documentation, 2022.】），包含四个主要组件：
    1. 任务队列 (Task Queues)：维护一个实时任务队列和多个尽力而为任务队列，每个队列绑定一个GPU流。
    2. 调度器 (Scheduler)：调度器通过忙轮询检查任务队列，并将任务分配给关联的GPU流。REEF有两种执行模式：实时模式和正常模式。
    3. 抢占模块 (Preemption module)：在正常模式下，REEF使用多个GPU流并发服务尽力而为任务。在实时模式下，抢占模块首先立即从所有正在运行的尽力而为任务中抢占GPU（§4），然后立即启动实时任务。
    4. 动态内核填充 (DKP)：在实时模式下，启动实时内核之前，DKP模块会选择合适的尽力而为内核，并动态地将它们填充到实时内核中（§5），以实现高吞吐量。


图 5: REEF的架构。虚线框中的模块位于服务DNN推理请求的关键路径上。

3.2 一个说明性示例

图6展示了REEF中调度五个DNN推理任务的时间线。
1. REEF收到前两个尽力而为请求r1和b1，系统在正常模式下运行，两个任务的内核被调度到两个不同的GPU流上并发执行。
2. 在r1和b1执行期间，一个实时请求v1到达。调度器立即切换到实时模式，GPU运行时通过终止所有正在运行的尽力而为内核（即r1和b1）来立即抢占GPU。
3. 同时，DKP模块从被恢复的任务中选择合适的内核来动态填充实时任务v1的内核。之后，填充后的内核将在GPU上单独执行。
4. v1完成后，调度器切换回正常模式。所有正在运行的和后续的尽力而为任务（即r1, b1, b2, r2）将通过两个GPU流在GPU上并发执行。


图 6: REEF中的时间线示例。这里的DNN推理任务与图4中的相同。

A2 方法细节

4 基于重置的抢占 (Reset-based Preemption)

核心思想。我们的核心思想，即基于重置的抢占，是利用DNN模型中GPU内核大多是幂等的特性，这使得主动抢占成为可能——立即终止GPU上所有正在运行的内核，并在稍后恢复它们。这样做的好处有两点：首先，它避免了保存和恢复GPU庞大的上下文（例如每个CU有256 KB的寄存器文件）【70, I. Tanasic et al. Enabling Preemptive Multiprogramming on GPUs. ACM/IEEE 41st International Symposium on Computer Architecture, 2014.】。其次，无需等待所有正在运行的内核完成，这可能需要数百微秒的时间。

面临的挑战。然而，在商用GPU上实现基于重置的抢占仍然面临新的挑战。除了在GPU上运行的内核外，还有数百个已启动的内核被缓存在GPU运行时维护的多个队列中。这对于隐藏内核启动时间并充分利用GPU的大规模并行性是必要的。但是，驱逐所有已启动的内核使得在几十微秒内抢占GPU变得异常困难。

内核生命周期。图7说明了已启动内核在GPU运行时和设备中的生命周期。首先，调度器启动一个推理任务的所有内核，并为每个任务指定一个GPU流。GPU运行时为每个GPU流维护一个称为主机队列（host queue）的链表来缓冲已启动的内核。每个主机队列都有一个后台线程，将缓冲的内核异步传输到一个称为设备队列（device queue）的环形缓冲区，该队列可由CPU和GPU同时访问。GPU的命令处理器会轮询所有设备队列以获取缓冲的内核，并最终将它们分派给计算单元。因此，一个推理任务的已启动内核可能存在于三个地方：主机队列（HQs）、设备队列（DQs）和计算单元（CUs）。为了实现即时抢占，必须驱逐这三个地方的所有内核。


图 7: REEF中为实现即时抢占而扩展的GPU运行时。

4.1 驱逐缓冲的内核 (Evicting Buffered Kernels)

主机队列和设备队列的重置。基于重置的方法需要主动从主机队列和设备队列中驱逐所有缓冲的内核。对于主机队列，重置它们很简单（图7中的➊），只需将所有缓冲的内核出队并回收内存，因为它们完全由GPU运行时控制。然而，对于设备队列，GPU运行时无法驱逐缓冲的内核，因为GPU的命令处理器可以直接从设备队列中获取内核【23, ROCm documentation. GCN Native ISA LLVM Code Generator: Kernel Dispatch, 2022.】，这会导致数据竞争和不可预测的结果。CPU也没有提供安全驱逐设备队列内核的方法。一个潜在的解决方案是通知GPU重新注册一个新的设备队列【62, ROCm Core Technology. AMD GPU kernel driver with KFD: unmap_queues_cpsch, 2022.】，但这会带来不可接受的延迟开销（在我们的测试平台上约为1毫秒）。

懒惰驱逐机制。受可驱逐内核【12, Guoyang Chen et al. EffiSha: A Software Framework for Enabling Efficient Preemptive Scheduling of GPU. 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2017.】的启发，我们提出了懒惰驱逐（lazy eviction）来重置设备队列，而无需扩展GPU运行时和硬件。REEF的代码转换器预先在每个内核的开头注入一段代码，该代码检查一个抢占标志以判断自己是否已被驱逐。当抢占标志为真时，内核将主动终止自己。因此，当抢占发生时，抢占模块会立即在GPU内存中将抢占标志设置为真（见图7中的➋）。设备队列中缓冲的内核将照常被获取并分派到CU，但会立即自我终止。

性能优化。我们最初的队列驱逐机制给抢占过程带来了不可忽略的开销，抢占单个任务需要超过500 µs。深入分析表明，开销主要来自(a)从主机队列回收内存和(b)等待从设备队列获取内核。因此，我们提出了两个优化来减轻这些开销。
* 异步内存回收 (Asynchronous memory reclamation)：为了立即从主机队列中驱逐GPU内核，REEF利用一个后台GC线程来异步回收内存。具体来说，REEF通过简单地将头指针置空来重置主机队列，然后通知GC线程在后台回收内存。
* 设备队列容量限制 (Device queue capacity restriction)：虽然懒惰驱逐可以立即终止设备队列中的内核，但这些内核仍然需要被获取和分派到CU，每个内核大约需要20 µs。因此，REEF限制设备队列的容量以实现微秒级的内核抢占。调整设备队列容量是在抢占延迟和执行时间之间进行权衡。我们根据经验在测试平台上选择设备队列容量为4，因为它足以在30 µs内重置设备队列，而对正常执行时间的开销可以忽略不计（小于0.3%）。

4.2 终止运行中的内核 (Killing Running Kernels)

利用驱动程序修改。为了避免等待运行中内核的完成，基于重置的抢占会主动终止GPU中正在运行的内核。不幸的是，GPU运行时没有提供API，GPU驱动程序也没有暴露功能来从主机端终止运行中的内核。我们观察到GPU驱动程序有能力终止CPU进程并同时杀死相关的GPU内核。这表明GPU驱动程序确实可以杀死一个未完成的内核。然而，这个功能也会回收进程和GPU内核分配的GPU内存，导致被抢占的内核必须重新加载DNN模型参数，耗时甚至达数秒。

保留内存的内核终止。为了解决这个问题，REEF修改了GPU驱动程序的内核终止功能，并将其暴露给GPU运行时的抢占模块。这个新功能会指示命令处理器杀死CU上所有正在运行的内核，但保留它们在GPU内存中的运行状态。抢占模块将在驱逐主机队列和设备队列后，使用它来杀死所有正在运行的内核（见图7中的➌）。

4.3 恢复被抢占的任务 (Restoring Preempted Tasks)

恢复点的近似。尽力而为的任务在被抢占后应该被恢复。幸运的是，DNN模型中内核的幂等性特性保证了DNN推理任务的执行可以从被中断内核之前的任何一个内核恢复。然而，精确识别被中断的内核几乎是不可能的。

恢复策略。为了解决这个问题，REEF采用了一种近似方法，确保被抢占的任务从至多比中断内核早一个常数（c）个内核的位置恢复。具体来说，抢占模块在开始重置任务队列时，首先记录传输到设备队列的最后一个内核（kl），然后从kl之前的c个内核处恢复被抢占的任务，其中c表示设备队列的容量。我们观察到命令处理器按顺序从设备队列中获取内核并运行它，这意味着中断的内核不会早于设备队列中最后一个内核（kl）之前的c个内核。REEF将冗余执行最多c+1个内核。由于c被配置得相对较小（即4），恢复开销可以忽略不计（约30 µs）。

4.4 在闭源GPU上的抢占

面临的挑战。许多商用GPU（如NVIDIA GPU）是闭源的。这给我们的基于重置的抢占方案带来了新的挑战，必须将GPU运行时视为一个黑盒。主要限制是我们无法重置CU来主动终止正在运行的内核（图7中的➌）。此外，REEF也无法直接在GPU运行时之外操作主机队列和设备队列。

REEF-N方案。我们为闭源GPU提出了一个受限版本的基于重置的抢占，称为REEF-N。
1. REEF-N首先将GPU运行时提供的通用抽象——GPU流，包装成一个虚拟主机队列（vHQs），用于拦截和缓冲所有已启动的内核。
2. 每个vHQ也有一个后台线程异步地将缓冲的内核传输到GPU运行时。
3. 之后，REEF-N将整个GPU运行时视为多个设备队列（每个GPU流一个），这样REEF可以轻松地重置vHQs来驱逐缓冲的内核，而不是直接重置物理HQs（图7中的➊）。
4. REEF-N仍然遵循懒惰驱逐来重置DQs，然后等待所有正在运行的内核完成。
5. 最后，为了模拟DQ容量限制，REEF限制了在GPU运行时中未完成内核的数量。


图 8: 使用不同方法并行服务多个内核的示例。

5 动态内核填充 (Dynamic Kernel Padding)

现有方案的局限性。为了实现高吞吐量，实时和尽力而为任务应在GPU上并发执行。然而，现有的方法都不能提供这种受控的并发执行。
* 不同GPU流：使用不同的GPU流启动实时和尽力而为任务无法避免相互干扰。如图8所示，GPU流之间的分派延迟（20–40 µs）可能会推迟实时内核的执行或限制其可用资源。
* 静态内核融合：静态内核融合【74, Guibin Wang et al. Kernel Fusion: An Effective Method for Better Power Efficiency on Multithreaded GPU. IEEE/ACM Int’l Conference on Green Computing and Communications, 2010.】可以在编译时将来自不同任务的多个内核合并成一个。然而，这需要预编译所有可能的内核组合，对于拥有数百个内核的DNN模型来说，这在实践中是不可行的，会导致内核数量爆炸和巨大的内存占用。

我们的方法：动态内核填充。受内核融合的启发，我们的方法也将实时内核和尽力而为内核组合成一个，并使用单个GPU流启动它，如图8所示。不同的是，我们在编译时构建一个模板（称为dkp内核），并在运行时使用函数指针来填充和执行内核。此外，我们动态选择尽力而为内核以避免对实时内核的干扰。

DKP内核实现。图9展示了一个dkp内核的示例。它被声明为一个全局函数（即内核入口）。候选内核函数（如dense）被声明为独立的设备函数，可以作为dkp内核的参数传递，并通过函数指针调用。dkp内核将CU分区，以并行执行一个实时候选内核（rt_kern）和一组尽力而为候选内核（be_kerns）。它首先为实时内核分配足够的CU，然后将剩余的CU分配给尽力而为内核。


图 9: REEF中动态内核填充的伪代码。

5.1 高效的函数指针 (Efficient Function Pointers)

默认函数指针的问题。在GPU上直接使用函数指针会带来两个关键性能问题：
1. 有限的寄存器分配：GPU程序的寄存器数量在编译时确定。由于无法静态确定间接调用函数使用的寄存器数量，GPU编译器会为被调用函数分配一个预定义的静态上限，这可能导致寄存器不足而将变量保存到栈上，从而降低性能。
2. 昂贵的上下文保存：GPU上的间接函数调用比CPU上昂贵得多，因为需要保存和恢复庞大的上下文（例如数十个寄存器）。

REEF的解决方案：代理内核。REEF通过引入全局函数指针作为默认函数指针机制的替代来解决上述问题。由于全局函数被视作内核入口，编译器既不限制其寄存器使用，也不为其添加上下文保存/恢复代码。我们将候选内核声明为全局函数而非设备函数，从而解决了这两个问题。然而，一个全局函数（如dkp内核）不能调用另一个全局函数。为了绕过这个限制，我们在汇编代码中用跳转指令替换间接函数调用，并手动准备候选内核的初始状态。

动态寄存器分配。即使使用了全局函数指针技术，由于过度分配（over-allocation）问题，实时内核的性能仍然不理想。为了满足不同候选内核的寄存器需求，dkp内核必须分配尽可能多的寄存器，这可能会降低CU占用率，从而增加执行时间。REEF通过引入一组代理内核（proxy kernels）来解决动态寄存器分配问题。代理内核与dkp内核共享相同的源代码，但分配不同数量的寄存器，允许调度器根据每个候选内核的寄存器需求动态选择合适的代理内核。

减少代理内核数量。为每个可能的寄存器数量生成代理内核会面临内核数量爆炸的问题。为了减少代理内核的数量，我们为所有可能的CU占用率而不是寄存器数量生成代理内核。由于引入代理内核是为了防止过度分配降低CU占用率，具有不同寄存器数量但共享相同CU占用率的代理内核实际上是冗余的。在我们的测试平台上，这使得代理内核的数量从32,768个减少到10个，而不影响候选内核的性能。

动态共享内存。除了寄存器，共享内存的过度分配也可能降低代理内核的CU占用率。幸运的是，内核可以在启动时通过设置一个属性（即“动态共享内存”）来动态分配共享内存。REEF在模型编译期间将固定大小共享内存的变量声明转换为动态共享内存，从而使代理内核使用的共享内存量可以在运行时根据候选内核的最大需求进行设置。


图 10: 五个DNN模型中内核的实测执行时间。DNN模型的详细信息见表1。

5.2 内核选择 (Kernel Selection)

选择策略。对于动态内核填充，内核选择策略对于避免对实时任务的延迟干扰至关重要。REEF提出了一种贪心启发式方法，以确保尽力而为的块只使用实时内核剩余的GPU资源（即CU）。具体来说，它首先为实时内核保留足够的CU，然后检查尽力而为任务队列，为剩余的CU选择合适的块，直到没有空闲的CU或候选任务为止。被选中的尽力而为块应满足以下两个规则：

  • 规则1：尽力而为内核的执行时间必须短于实时内核的执行时间，因为dkp内核的执行时间由最慢的块决定。我们开发了一个离线内核分析器来测量每个内核的计算需求和执行时间。
  • 规则2：尽力而为内核的CU占用率必须高于实时内核的CU占用率，因为dkp内核的CU占用率由所有内核中的最小值决定。

策略的保守性。这个内核选择策略高效（选择时间小于1 µs）且有效（实时内核延迟开销平均小于1%），但它也比较保守。例如，当尽力而为内核的执行时间通常比实时内核长时（如图10中的VGG和DenseNet），即使实时任务只使用少量CU，动态内核填充的吞吐量提升也可能微不足道。

6 实现

我们在AMD GPU上实现了REEF，因为它拥有开源平台和ISA。实现基于Apache TVM【73, Apache TVM, 2021.】和AMD ROCm【3, AMD ROCm. AMD ROCm Platform Documentation, 2022.】，大约有5,500行C++代码。此外，为了展示REEF在闭源GPU上的可行性，我们也在NVIDIA GPU上移植了REEF-N，一个受限版本的基于重置的抢占。

  • 模型编译器：REEF扩展了Apache TVM【15, T. Chen et al. TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI’18, 2018.】的代码转换器，主要进行了两处修改：(1) 注入一个抢占标志用于懒惰驱逐内核；(2) 为填充后的内核构建一组代理内核。

  • GPU运行时 (AMD)：REEF在ROCm的HIP【63, ROCm Developer Tools. Hip, 2022.】上构建了抢占模块，并向GPU运行时添加了三个新API：(1) hip_reset_hq，用于重置主机队列；(2) hip_set_stream_cap，用于限制设备队列的容量；(3) hip_reset_kern，用于通过Linux中的GPU驱动程序重置计算单元。

  • GPU运行时 (NVIDIA)：REEF-N拦截了三个与内核启动和流管理相关的CUDA API：(1) cuStreamCreate，用于创建vHQ；(2) cuKernelLaunch，用于将启动的内核缓冲在vHQ中；(3) cuStreamSynchronize，用于等待GPU运行时完成。最后，REEF-N提供了一个新API cuResetHQ来重置vHQ。

A4 实验环境与结果

实验环境

  • 硬件配置：
    • CPU: Intel Core i7-10700 (8核)
    • 内存: 16 GB DRAM
    • GPU: 1x AMD Radeon Instinct MI50 (60 CUs, 16GB HBM2内存)；1x NVIDIA V100 (用于闭源GPU评估)
  • 软件配置：
    • 操作系统: Ubuntu 18.04
    • GPU平台: AMD ROCm 4.3.0, NVIDIA CUDA 10.2
    • 深度学习编译器: Apache TVM 0.8.0
  • 数据集/模型:
    • 使用了五个代表性的DNN模型：ResNet-152 (RNET), DenseNet-201 (DNET), VGG-19 (VGG), Inception v3 (IN3), 和 DistilBert (BERT)。

  • 基准测试 (DISB)：

    • 我们构建了一个新的DNN推理服务基准（DISB），包含五个工作负载（A-E），模拟不同的负载情况，如低负载、高实时负载、高尽力而为负载、多实时任务负载和随机负载。详细信息见表2。
    • 此外，我们还使用了一个来自开源自动驾驶平台Apollo【7, Baidu. Apollo, 2022.】的真实世界轨迹作为实时工作负载。

    Table 2: DISB工作负载描述。#/model表示客户端数量及其DNN模型。[U/P]表示到达分布（均匀或泊松）。

实验结果

总体性能

我们使用DISB工作负载和真实世界轨迹比较了REEF与其他方法（SEQ：顺序执行，GPUStreams：多流并发，RT-Only：仅实时任务）的端到端延迟和总体吞吐量。

  • 结论（图 11）:
    • 低负载 (DISB A, B): REEF在保持实时任务延迟接近RT-Only（开销<1%）的同时，将总体吞吐量提升了高达1.60倍，与GPUStreams相当。而SEQ和GPUStreams都显著增加了实时任务的延迟（高达1.95倍）。
    • 高负载 (DISB C, D, E): 随着尽力而为任务的增加，SEQ和GPUStreams虽然提高了吞吐量（GPUStreams最高提升8.19倍），但也极大地牺牲了实时任务的延迟（GPUStreams最高增加3.31倍）。相比之下，REEF始终将实时任务的延迟开销控制在1.5%以内，同时吞吐量比RT-Only高出3倍以上。
    • 真实世界轨迹 (REAL): REEF实现了7.7倍的吞吐量提升，而实时任务的延迟开销不到2%。这得益于其微秒级的抢占能力，使得GPU在空闲时能高效处理尽力而为任务。


图 11: (a) 端到端实时任务延迟 和 (b) 总体吞吐量（包括实时和尽力而为任务）在不同调度方法下的比较。

DNN推理抢占性能

我们比较了REEF的基于重置的抢占和扩展后的基于等待的抢占方法的抢占延迟。

  • 结论（图 12, 13, 14）:
    • 性能优势: 基于重置的抢占比基于等待的方法快一个数量级以上（15.3倍到18.5倍）。基于等待的方法延迟随模型内核数量和执行时间线性增加，而REEF的抢占延迟保持稳定在40 µs以下，与模型特性无关。
    • 优化效果: 异步内存回收和队列容量限制两个优化将抢占延迟降低了高达92%。分析表明，重置主机队列的延迟从17 µs降至3 µs，重置设备队列的延迟从424 µs降至31 µs。
    • 队列容量权衡 (图 15a): 我们选择设备队列容量为4，这是一个在抢占延迟（约30 µs）和正常执行时间开销（可忽略）之间的最佳权衡点。
    • 任务恢复开销 (图 15b): 任务恢复时间很低（70 µs到245 µs），对总执行时间的开销平均约为2%。


图 12: 基于重置和基于等待方法的抢占延迟比较 (a) 在DISB工作负载上，以及 (b) 抢占不同DNN模型的单个推理任务时。


图 13: 抢占延迟随 (a) 已启动内核数量 和 (b) 内核执行时间的增加而变化。


图 14: (a) 抢占延迟随尽力而为客户端数量增加的变化，以及 (b) 基于重置方法有无优化的延迟分解。


图 15: (a) 抢占延迟和执行时间随设备队列容量的变化，其中[%]显示了正常执行期间的CPU利用率，以及 (b) 不同DNN模型的恢复开销，标签显示了恢复时间（µs）。

动态内核填充性能

我们评估了动态内核填充（DKP）的有效性。

  • 结论（图 16, 17, 18, 19）:
    • 延迟与吞吐量: DKP能够为实时任务提供近乎最优的延迟（平均开销仅1%），同时利用剩余资源提升尽力而为任务的吞吐量。吞吐量的提升取决于实时任务的CU使用率和是否存在执行时间更短的尽力而为内核。
    • 优化效果: 代理内核优化将DKP的执行时间开销从默认函数指针的最高503%降低到平均0.8%。在内存方面，DKP通过代理内核优化将内存占用从静态融合的超过35GB大幅降低到仅10KB。
    • 内核选择开销与准确性: 内核选择的开销极低（0.2-0.4 µs）。评估表明，超过90%的实时内核因填充而产生的额外延迟小于4 µs，证明了选择策略的准确性。


图 16: 使用不同并发执行方案的 (a) 实时任务端到端延迟 和 (b) 总体吞吐量比较。


图 17: 使用动态内核填充，在不同DNN模型组合下运行实时和尽力而为内核的平均CU使用率。


图 18: 使用不同优化的填充内核的 (a) 执行时间开销 和 (b) 内存开销比较。


图 19: (a) DISB A-E的内核选择执行时间 和 (b) 使用动态内核填充的实时内核执行时间开销的CDF。

闭源GPU评估

我们在NVIDIA V100 GPU上评估了REEF-N（受限版本）。

  • 结论（图 20）:
    • 即使没有主动终止运行中内核的功能，REEF-N在NVIDIA GPU上的抢占延迟（71-288 µs）仍比基于等待的方法快6.3倍至12.3倍。
    • 与AMD GPU上的完整REEF相比，主动终止内核的功能可以进一步将抢占延迟平均降低2.0倍。这证明了我们方法的通用性和主要思想的有效性。


图 20: 在NVIDIA和AMD GPU上使用不同抢占方案对DISB工作负载的抢占延迟比较。

A7 补充细节

8 讨论

  • 幂等性假设。REEF的基于重置的抢占依赖于DNN推理内核是幂等的假设。目前我们遇到的所有DNN推理内核都满足此特性。如果未来遇到非幂等内核，可以采用事务化方法【40, Hyeonsu Lee et al. A GPU Kernel Transactionization Scheme for Preemptive Priority Scheduling. In 2018 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS’18, 2018.】将其转换为幂等内核。由于只有尽力而为内核会被抢占，这种转换只会牺牲尽力而为内核的性能，而保证实时内核的即时执行。

  • 内核选择的限制。当前的内核选择策略是有效但保守的，其主要目标是避免对实时任务的性能干扰。一个明显的限制是尽力而为内核的执行时间必须短于被填充的实时内核，这限制了总体吞吐量的提升空间。未来的工作可以探索如何克服这一限制。此外，该策略未考虑GPU内存带宽的争用。

  • 未来的GPU API和运行时。我们的工作为未来GPU API和运行时的设计提供了启示。首先，可以提供一个精确重置计算单元（CUs）的API。其次，可以提供一个新的API，指示命令处理器丢弃已获取的内核并停止从设备队列（DQs）获取新内核，以实现硬件-软件协同的DQs重置。最后，GPU运行时可以提供一个高层API来重置GPU流。这些扩展将简化实现，并可能进一步提升性能。

9 相关工作

  • DNN推理服务系统。先前的模型服务系统【21, Weihao Cui et al. Ebird: Elastic Batch for Improving Responsiveness and Throughput of Deep Learning Services. IEEE 37th International Conference on Computer Design, 2019.】【28, A. Gujarati et al. Serving DNNs like Clockwork: Performance Predictability from the Bottom Up. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】【64, Francisco Romero et al. INFaaS: Automated Model-less Inference Serving. In USENIX Annual Technical Conference, ATC’21, 2021.】主要关注满足数十毫秒的服务水平目标（SLO），并提高数据中心应用的总体吞吐量。它们采用的非抢占式调度或批处理方案不适用于实时场景。REEF的设计与这些分布式服务系统是正交的，其关键机制可以集成到这些系统中。

  • GPU内核抢占。除了软件抢占技术，先前的工作也提出了硬件增强来支持抢占式GPU调度【44, Zhen Lin et al. Enabling Efficient Preemption for SIMT Architectures with Lightweight Context Switching. International Conference for High Performance Computing, Networking, Storage and Analysis, 2016.】【56, J. Park et al. Chimera: Collaborative Preemption for Multitasking on a Shared GPU. Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems, 2015.】【70, I. Tanasic et al. Enabling Preemptive Multiprogramming on GPUs. ACM/IEEE 41st International Symposium on Computer Architecture, 2014.】。这些方法要么需要昂贵的上下文切换，要么需要修改硬件。不同的是，我们的方法改造了现有的硬件机制，无需对GPU进行修改即可实现即时抢占。

  • GPU多任务处理。已有许多工作致力于并发执行多个GPU内核以提高吞吐量【27, Chris Gregg et al. Fine-grained resource sharing for concurrent GPGPU kernels. In 4th USENIX Workshop on Hot Topics in Parallelism, HotPar’12, 2012.】【47, Lingxiao Ma et al. Rammer: Enabling Holistic Deep Learning Compiler Optimizations with rTasks. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】【74, Guibin Wang et al. Kernel Fusion: An Effective Method for Better Power Efficiency on Multithreaded GPU. IEEE/ACM Int’l Conference on Green Computing and Communications, 2010.】。例如，Rammer【47, Lingxiao Ma et al. Rammer: Enabling Holistic Deep Learning Compiler Optimizations with rTasks. In 14th USENIX Symposium on Operating Systems Design and Implementation, OSDI’20, 2020.】使用静态内核融合，但这不适用于REEF中的动态任务调度。REEF提出的动态内核填充允许在运行时做出调度决策。其他工作【13, Quan Chen et al. Prophet: Precise QoS Prediction on Non-Preemptive Accelerators to Improve Utilization in Warehouse-Scale Computers. Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems, 2017.】【87, Wenyi Zhao et al. Themis: Predicting and Reining in Application-Level Slowdown on Spatial Multitasking GPUs. IEEE International Parallel and Distributed Processing Symposium, 2019.】通过建模预测并发内核执行的减速，但预测无法总是准确。REEF的动态内核填充通过强制并发内核只使用实时内核剩余的GPU资源来避免性能干扰。

A5 结论

本文介绍了REEF，首个用于商用GPU的DNN推理服务系统，它通过微秒级内核抢占和受控并发执行实现了实时性和工作保持性。REEF的核心创新在于：首先，通过主动终止和恢复尽力而为内核，在微秒级别内为实时内核抢占GPU；其次，通过动态地用合适的尽力而为内核填充实时内核，以极小的开销充分利用GPU。我们还构建了一个新的DNN推理服务基准（DISB）。在AMD和NVIDIA GPU上的评估证实了REEF的有效性和高效性。

A6 附录

本工件提供了REEF的源代码、详细的自述文件以及用于复现OSDI 2022论文“Microsecond-scale Preemption for Concurrent GPU-accelerated DNN Inferences”主要实验结果的脚本。REEF是首个支持微秒级内核抢占和受控并发执行的GPU加速DNN推理服务系统。我们提供了构建软件包和运行实验的说明。我们的工件在OSDI 2022的工件评估过程中获得了“Artifacts Available”、“Artifacts Functional”和“Artifacts Reproduced”徽章。我们的工件的DOI是 https://doi.org/10.5281/zenodo.6586106 。

工件仓库。所有项目源代码，包括关于如何在REEF和基准测试上构建和运行主要实验的完整说明，都可以在以下git仓库中找到：https://github.com/SJTU-IPADS/reef-artifacts/tree/osdi22-ae 。