Microsecond-scale Preemption for Concurrent GPU-accelerated DNN Inferences
*. 精简概括
*.1 What
REEF：一个 GPU-accelerated DNN inference serving system
实现了 微秒级内核抢占（microsecond-scale kernel preemption）和 GPU 调度中的受控并发执行（controlled concurrent execution in GPU scheduling）
*.2 Why
目标：降低延迟，提高吞吐率
两种任务：
- real-time (RT) task: latency-critical task
- best-effort (BE) task: task with no hard real-time requirement
*.3 How
*.3.1 Reset-based Preemption
real-time task 应立即抢占 GPU，为了降低延迟
一个 task 启动的 kernel 会位于三个位置：host queues (HQs), device queues (DQs), compute units (CUs)，所以需要从这三个位置将已经启动的 kernel 清除掉。
Reset：抢占模块会记录最后一个传输到 device queue 的内核，然后从该内核之前的 c 个内核处恢复，c 为 device queue 的容量
*.3.2 Dynamic Kernel Padding
希望 best-effort tasks 利用 real-time tasks 的剩余 GPU 资源，提高吞吐率
首先为 real-time kernel 保留足够的 CU，然后检查 best-effort task queue，选择适合剩余 CU 的合适块，直到没有空闲的 CU 或候选任务。
0. Abstract
- 商用 GPU 缺乏 preemptive scheduling support，如今先进的方式要么必须独占 GPU，要么需要 real-time tasks 等待 best-effort tasks 完成
- real-time (RT) task: latency-critical task
- best-effort (BE) task: task with no hard real-time requirement
- 提出了 REEF：
- 是一个 GPU-accelerated DNN inference serving system
- 实现了 微秒级内核抢占（microsecond-scale kernel preemption）和 GPU 调度中的受控并发执行（controlled concurrent execution in GPU scheduling）
- 基于观察：DNN Inference 大多是幂等的（idempotent）。提出了 基于重置的内核抢占（reset-based preemption scheme）。通过主动 kill 和 restore best-effort kernels 来发射 real-time kernel.
- 由于 DNN inference 拥有变化的并行性和可预测的延迟，REFF 提出了动态内核填充机制（Dynamic kernel padding mechanism），with negligible overhead.
- 与将 GPU 专用于实时任务相比，REEF仅导致实时任务的端到端延迟增加不到2％，但整体吞吐量增加了高达 7.7 倍
- 关键词：reset-based preemption scheme，Dynamic kernel padding mechanism
1. Introduction
之前方法的缺点：
独占 GPU：不能充分利用并行性
- multiple GPU streams：延迟增大
- wait-based approach (preemption for GPU scheduling) : preemption latency 高，best-effort tasks 会 starve
REEF：
- real-time task 应立即抢占 GPU，从正在运行的 best-effort kernel
- best-effort task 应利用剩余的 GPU 资源并发执行
第一个设计，用了软件和硬件 driver 的方法。
第二个设计，提出了动态内核填充，基于观察——DNN inference 在 GPU kernel 上的运行时间是确定的和可预测的。可通过离线的分析（offline profiling），将 best-effort kernel 填充上去。扩充了 GPU 编译器。引入代理内核（proxy kernels）解决寄存器分配问题。
通过扩展 Apache TVM（一个用于深度学习的编译器）和 AMD ROCm（一个开源 GPU 计算平台）来实现了 REEF
2. Background and Motivation
2.1 GPU 加速的 DNN 的特性
DNN 由多个层组成，如 convolutional, pooling and fullyconnected layers。
对于每个到达的请求，DNN 模型的所有内核会依次执行，输入会传递给这些内核，然后将生成的输出返回给 DNN 应用程序。
Idempotence. DNN 模型中的 GPU 内核大多是幂等的，因为它们主要由几乎没有副作用的密集线性代数计算组成。同时，第 ( k ) 个内核总是使用第 ( k - 1 ) 个内核的输出和静态参数。
Massive kernels. 现代 DNN 模型通常包含数百个内核.
现代 DNN 模型通常包含数百个内核。为了应对这一情况，通常会提前提交大量内核，通常是数百个或更多，以隐藏较长的内核启动时间。此外，为了充分利用 GPU，服务系统可能会同时执行来自不同推断任务的多个内核，使用相同或不同的 DNN 模型。因此，抢占 GPU 会导致显著的性能损失（几毫秒），甚至可能与数百个内核的执行时间相媲美。
Latency predictability. 在 GPU 上单独运行时，DNN 推断中 GPU 内核的执行时间是确定性和可预测的。
Varied parallelism. DNN 推断中的 GPU 内核通常由于不同的输入规模而表现出完全不同的并行性。在执行过程中，DNN 推断的计算需求，即计算单元（CUs）的数量，是不断变化的。
2.2 目前的 GPU 调度方法
Sequential execution.
实时任务的端到端延迟可能会显著延长，因为它必须等待前面任务的完成。
整体吞吐量较差。
Block-level preemption.
由于上下文较大（例如，大量寄存器），在 GPU 上实现抢占调度是困难的。
通用 GPU 也缺乏抢占机制的硬件支持。
基于等待的方法来实现 GPU 调度的块级抢占
抢占延迟会随着抢占的内核数量增加而增加
导致 best-effort task 饥饿
Multiple GPU streams.
可以提高吞吐量，但实时任务的延迟可能会因并发任务而显著降低
延迟开销会随着并发任务的数量增加而增加
3 REEF Overview
3.1 System Architecture
2 个设计：reset-based preemption and dynamic kernel padding.
离线部分：负责编译和加载用户提供的 DNN 模型
在线部分：负责调度和提供 DNN 推断请求
DNN model preparation (offline).
REEF 扩展了模型编译器并添加了一个代码变换模块（code transformer），该模块首先验证了 DNN 模型中内核的幂等性，然后将源代码转换以协助 REEF 中的 GPU 调度。
REEF 还开发了一个内核性能分析器，用于测量模型中每个内核的计算需求和执行时间
DNN inference serving (online)
任务队列（Task Queues）：
维护一个 real-time task queue，若干个 best-effort task queues. FIFO.
每个队列都会绑定到一个 GPU stream.
提供了一个基于 RPC 的接口，用于将 inference request 传递到任务队列
调度程序（Scheduler）：
对任务队列使用 busy polling
两种执行模式：
- real-time mode: 遇到 real-time task 时
- normal mode: real-time task queue 为空时
抢占模块（Preemption module）：
在 normal mode 下，REEF 同时为多个 best-effort 队列的任务提供服务，用 multiple GPU streams
在 real-time mode 下，REEF 抢占所有正在运行的 best-effort tasks 的 GPU，然后立即发射 real-time task
设置 preemption flag = true
动态内核填充（Dynamic kernel padding, DKP）：
在 real-time mode 下，在发射 real-time kernel 前，DKP 会选择合适的 best-effort kernels 动态地将他们填充到 real-time kernel.
4 Reset-based Preemption
由于 DNN 模型中的 kernel 大多是幂等的，所以可以采用主动抢占的方式。
好处：避免了保存和恢复上下文，无需等待运行中的内核完成。
挑战：GPU 运行时还在维护的多个队列中缓冲了数百个已启动的内核，这些也需要清除
the lifetime of launched kernels in the GPU runtime and devices:
- scheduler 发射一个 task 的所有 kernels，为每个 task 指定一个 GPU stream. 进入 host queue，每个 GPU stream 都会有一个 host queue 来缓存已经发射的 kernels
- 再将 kernel 异步地传输到一个环形缓冲区，称为 device queue
- command processor 会轮询所有 device queues，来 fetch kernel 并dispatch 到计算单元 compute units
所以一个 task 发射的 kernel 会位于三个位置：host queues (HQs), device queues (DQs), compute units (CUs)
4.1 Evicting Buffered Kernels
即清除 host queues 和 device queues 中的 kernels
host queues 中的 kernels：出队并回收内存
device queues 中的 kernels：延迟清除（lazy eviction），REEF 的代码转换器在每个内核的开头注入一段代码，该代码检查抢占标志（preemption flag）以确定自己是否已被清除。当抢占标志为 true 时，内核将自愿终止。在发生抢占时，抢占模块将立即将 GPU 内存中的抢占标志设置为 true。设备队列中缓冲的内核将像往常一样被提取并分派给计算单元，但将立即自行终止。
抢占开销主要来自于：从 host queue 中回收内存，等待从 device queue 中 fetch kernel
异步内存回收（asynchronous memory reclamation）：REEF 首先通过简单地将头指针置空，然后通知 GC 线程在后台回收内存来重置 host queue
device queue 容量限制（device queue capacity restriction）：REEF 限制了 device queue 的容量，需要清除的内核减少，但正常执行时间增加，做了权衡
4.2 Killing Running Kernels
即清除 compute units 中的 kernels
REEF 对 GPU 驱动程序的内核终止功能进行了改进，可以使 commamnd peocessor kill 所有运行的 kernels，同时保留它们的运行状态在 GPU memory 中。
4.3 Restoring Preempted Tasks
由于 DNN kernel 的幂等性，可以从接近中断点的 kernel 处护肤被抢占的任务，但精确识别终端的 kernel 是几乎不可能。
REEF 采取了一种近似的方法，以确保被抢占的任务最多从中断的 kernel 之前的常熟数量 c 的内核处恢复
重置 task queue 时，抢占模块会记录最后一个传输到 device queue 的内核，然后从该内核之前的 c 个内核处恢复，c 为 device queue 的容量。
疑惑：
CUs 上会同时执行来自一个 device queue 的几个 kernel
4.4 基于闭源 GPU 的抢占
REEF-N 首先会将每个 GPU stream 封装为 virtual host queue (vHQs)，拦截和缓冲所有已经启动的内核
REEF-N 将整个 GPU runtime 视为多个 device queue，每个 GPU stream 有一个 device queue，以便 REEF-N 可以轻松重置 vHQs.
疑惑：
上一行为什么？
REEF-N 仍然采用延迟清除来重置 DQs
等待所有正在运行的 kernel 完成
5 Dynamic Kernel Padding
希望 best-effort tasks 利用 real-time tasks 的剩余 GPU 资源，但是现有方法做不到，原因为：
- 使用不用的 GPU stream 进行 real-time 和 best-effort task 不能避免相互干扰。调度延迟，inter-stream barrier
- static kernel fusion 对于 DNN inference 几百个 kernel 不现实
将 real-time 和 best-effort kernels 合并为一个，发射到一个 GPU stream
在编译时构建一个模板（称为 dkp kernel），使用函数指针在运行时填充和执行内核。
动态选择 best-effort kernels 避免与 real-time kernel 干扰。
5.1 Efficient Function Pointers
这一部分感觉有很多概念和原理要学
默认的函数指针机制在 GPU 上存在的两个关键性能问题。
有限的寄存器分配（Limited register allocation）：
GPU 程序需要多样化但固定数量的寄存器，这个数量在编译时计算并编码到模型可执行文件中。这种属性禁止在 GPU kernel 中直接使用函数指针，因为无法在静态情况下确定间接调用函数所使用的寄存器数量。
GPU 编译器的默认行为是为被调用的函数分配一个预定义的静态上限，以限制被调用函数的寄存器使用量，这可能会迫使被调用函数由于寄存器不足而将变量保存在堆栈上，导致性能不如纯粹使用寄存器的情况
昂贵的上下文保存（Expensive context saving）
REEF 引入全局函数指针。由于全局函数被视为内核入口，编译器既不应用寄存器限制，也不向它们添加上下文保存和恢复代码。
疑惑：
candidate kernel 到底是被声明为 global function 还是 device function
感觉是写成了 device function，然后修改了汇编代码，将间接函数调用替换为跳转指令
在 candidate kernel 中缺少上下文保存代码不会影响执行正确性
动态寄存器分配（Dynamic register allocation）：存在寄存器过分分配的问题。REEF 通过引入一组代理内核来解决动态寄存器分配问题。代理内核与 dkp 内核共享相同的源代码，但分配不同数量的寄存器，允许调度程序根据每个候选内核的寄存器需求动态选择合适的代理内核。10 个 CU 占用率级别，对应生成 10 个代理内核。
动态共享内存（Dynamic shared memory）：在模型编译过程中，REEF 将变量的声明从固定大小的共享内存转换为动态共享内存
5.2 Kernel Selection
提出了一种贪心的启发式方法。
它首先为 real-time kernel 保留足够的 CU，然后检查 best-effort task queue，选择适合剩余 CU 的合适块，直到没有空闲的 CU 或候选任务。所选的尽力而为块应满足以下两个规则：
- best-effort kernel 的执行时间必须比 real-time kernel 短，因为 dkp 内核的执行时间由最慢的块决定
- best-effort kernel 的 CU 占用率必须高于 real-time kernel，因为 dkp 内核的 CU 占用率由内核的最小值决定
疑惑：
第二点不理解
＃ 概念学习
#.1 idempotent 幂等
用于描述一个操作或函数，无论执行多少次，其结果都相同
DNN inference 中的 kernel 大多是幂等的，可以在不保存上下文的情况下主动 kill 和 restore best-effort kernels
#.2 DISB
DNN inference serving benchmark
#.3 ROCm
是 Radeon Open Compute 平台的缩写，它是由 AMD 开发的开源计算平台。ROCm 旨在提供一套开放标准和工具，以支持 GPU 计算和异构计算
#.4 EDF
是一种调度策略，Earliest Deadline First
这种调度策略通常用于实时系统中，其中任务需要在特定的截止时间之前完成。EDF 调度器会按照任务的截止时间来排序，优先选择最早截止时间的任务进行执行。
#.5 RPC-based interface
是指一种基于远程过程调用（Remote Procedure Call，简称 RPC）的接口或通信机制。RPC 是一种计算机通信协议，它允许一个程序在远程计算机上调用另一个程序的过程或函数，就像调用本地过程一样，而无需了解底层网络通信的细节。RPC 允许分布式系统中的不同组件或服务之间进行通信和交互。
#.6 busy polling
是一种轮询技术。
其中一个进程或线程在等待某些事件发生时不断地检查（轮询）该事件是否已经发生
由于 “busy polling” 会不断地检查条件，这可能导致资源浪费
一个优点是它可以实现低延迟的响应，因为一旦条件满足，进程或线程可以立即执行相应的操作，而不需要等待通知或唤醒
#.7 GPU stream
GPU Stream 的主要原理是将 GPU 操作划分为多个独立的流，这些流可以并行执行。
每个 GPU 流都包含一系列 GPU 操作（例如内核函数、数据传输等），这些操作按照在流中添加的顺序进行执行。不同的流可以同时执行，因此它们可以在不相互阻塞的情况下并行工作
#.8 SM, SP, Warp, Grid, Block
当一个 kernel 启动后，thread 会被分配到很多 SM 中执行。大量的 thread 可能会被分配到不同的 SM，但是同一个 block 中的 thread 必然在同一个 SM 中并行执行。
一个 SP 可以执行一个 thread
Nvidia 把 32 个 threads 组成一个 warp，warp 是调度和运行的基本单元。warp 中所有 threads 并行的执行相同的指令。warp 由 SM 的硬件 warp scheduler 负责调度，一个 SM 同一个时刻可以执行多个 warp，这取决于 warp scheduler 的数量.
Grid：由一个单独的 kernel 启动的所有线程组成一个 grid，grid 中所有线程共享 global memory。Grid 由很多 Block 组成，可以是一维二维或三维。
Block：block 由许多线程组成，同样可以有一维、二维或者三维。block 内部的多个线程可以同步（synchronize），可访问共享内存（share memory）