Paella: Low-latency Model Serving with Software-defined GPU Scheduling

* 精简概括

*.1 What

Paella，是一个用于在共享 GPU 上进行低延迟机器学习推断的轻量级框架

实现了调度器的软件化，这允许 Paella 服务平台根据任意性能/公平性指标精确地调度每个 CUDA 内核

*.2 Why

模型服务平台在提供低延迟方面仍然存在问题，特别是当 GPU 被强烈共享并且模型表现出高分散性时

模型服务平台与以下两个方面的交互存在显著的低效性：

发出请求的客户端：包括序列化、反序列化、调度、分派等的开销
分派给请求的 GPU 执行逻辑：
目前 GPU 的调度导致，在给定时刻可以调度的内容在很大程度上取决于内核提交的顺序、GPU 的当前资源利用情况以及 GPU 的特性/配置。
- 会有 HoL blocking
- 对应用程序度量的无知，忽略了重要的应用程序级目标。最佳调度策略在不同的微架构之间不同，使得好的内核提交顺序成为一个不断变化的目标

*.3 How

一个 compiler-library-scheduler co-design，抽象了 GPU 任务提交流水线，实现了完全绕过 GPU 硬件调度器的功能，打开了对 GPU 调度决策的全面、可扩展和可移植控制的大门
- Paella 使用轻量级、自动化的编译器，基于 TVM 构建，用于 instruments kernels，在 kernel 运行时展示关于 GPU SMs 的详细信息，包括占用率和利用率
- 利用这种关于 GPU 利用率的细粒度信息，Paella 调度程序可以将内核保持，在 Host 端，Paella 拦截所有 CUDA 调用并模拟 GPU 的调度职责，直到它能够保证它们可以很快/立即被放置
- 它可以基于可配置的端到端度量值做出仔细、精确的调度决策
一种用于请求提交和结果检索的服务架构和混合中断/轮询协议，最小化延迟和资源开销
- 包括一系列经过优化的通信通道，促进了系统的所有组件之间的低延迟和低开销的协调
- Paella 通过利用共享内存队列来实现零拷贝、无需内核的通信

0 Abstract

Model serving systems 在共享 GPU 上的 multiplexing machine learning inference 中发挥着巨大的作用

提出：

模型编译器 model compiler
本地客户端 local clients
调度器 scheduler

以绕过内置 GPU 调度器并实现对内核执行顺序的软件控制

这样做可以使用任意调度算法，并在推断的关键路径上减少系统开销

1 Introduction

模型服务系统，使多个用户和模型能够共享 GPU 基础设施。通常位于模型执行引擎之上，并与客户端应用程序分开，这些系统负责接收传入请求、选择模型/配置、进行调度，最终将模型执行分派给底层执行引擎。

模型服务系统（model serving system）：如 NVIDIA’s Triton, Clipper, and Clockwork
模型执行引擎（model execution engine）：如 Tensorflow, PyTorch, JAX

模型服务平台在提供低延迟方面仍然存在问题，特别是当 GPU 被强烈共享并且模型表现出高分散性时

模型服务平台与以下两个方面的交互存在显著的低效性：

发出请求的客户端：包括序列化、反序列化、调度、分派等的开销
分派给请求的 GPU 执行逻辑：基于 FIFO 的调度策略会频繁出现 Head-of-Line blocking

Paella，是一个用于在共享 GPU 上进行低延迟机器学习推断的轻量级框架。

Paella 是一个请求提交接口、模型调度器和模型执行逻辑的共同设计，主要设计目标是实现对调度及其相关任务的精细控制，它们共同确保了在推断请求处理的所有阶段都实现了高利用率和最小延迟：提交作业、调度其组成的 CUDA 任务以及返回结果

支持 Paella 的精细控制的两个关键创新点：

轻量级且自动化的 TVM 编译器工具：通过对 GPU 及其可用资源的详细实时视图，Paella 实现了调度器的软件化，这允许 Paella 服务平台根据任意性能/公平性指标精确地调度每个 CUDA 内核
各个上述组件之间的一系列专门通信通道：

它在调度和分派方面仅利用单个 CPU 核心

2 Background and Motivation

这篇文章认为，为了实现 low end-to-end application latency，服务框架需要与周围组件更紧密地集成，并对其调度和操作进行更精细的控制

2.1 GPUs and Mismatched Scheduling Policies

GPU 是一个 PCIe 设备，由多个流多处理器（SMs）组成，每个 SM 包含功能单元、寄存器阵列和 L1 缓存。

一个 SM 可以同时运行多个用户上下文

一旦将一个 thread block 放置在一个 SM 上，所需的资源，包括寄存器、共享内存以及块和线程的插槽，将在该块的持续时间内静态分配.

Blocks can then be grouped into a grid to form a kernel

kernel 是应用程序通常与 GPU 进行交互的粒度。典型的应用程序级任务/模型将包括多个 kernel，通常按顺序执行

GPU 包含若干的硬件队列，用于接收 kernel launches 并考虑它们进行调度。这些队列 FIFO

目前 GPU 的调度导致，在给定时刻可以调度的内容在很大程度上取决于内核提交的顺序、GPU 的当前资源利用情况以及 GPU 的特性/配置。

会有 HoL blocking
对应用程序度量的无知，忽略了重要的应用程序级目标。最佳调度策略在不同的微架构之间不同，使得好的内核提交顺序成为一个不断变化的目标

2.2 Framework Overheads

典型的开销，会在每个推理请求上产生，来源于诸如序列化/反序列化、批处理以及服务级调度和队列管理等任务

当 GPU 受到严重争用时，这些开销可以叠加

3 Design Overview

Paella 两项创新：

一个 compiler-library-scheduler co-design，抽象了 GPU 任务提交流水线，实现了完全绕过 GPU 硬件调度器的功能，打开了对 GPU 调度决策的全面、可扩展和可移植控制的大门
- Paella 使用轻量级、自动化的编译器，快速高效地跟踪已安排的 kernel 以及它们的位置
- 利用这种关于 GPU 利用率的细粒度信息，Paella 调度程序可以将内核保持，直到它能够保证它们可以很快/立即被放置
- 它可以基于可配置的端到端度量值做出仔细、精确的调度决策
一种用于请求提交和结果检索的服务架构和混合中断/轮询协议，最小化延迟和资源开销
- 包括一系列经过优化的通信通道，促进了系统的所有组件之间的低延迟和低开销的协调

Paella 系统组成：

一个 compiler，基于 TVM 构建，用于 instruments kernels，在 kernel 运行时展示关于 GPU SMs 的详细信息，包括占用率和利用率
A client library and communication protocol：使用混合的进程间通信系统来发出请求和响应，以产生最小的延迟开销
Paella dispatcher：接受请求并监视 GPU 资源使用情况，以便做出细粒度的调度决策

工作流程 Workflow

用户使用 Paella 的编译器编译模型
本地客户端（或 RPC 服务器）通过将原始输入向共享内存队列写入来提交推理请求给 Paella
调度程序使用有关 GPU 当前占用和利用率的基准知识来调度和部署每个客户端推理请求的所有组成内核
在作业的最后一个内核完成之前，调度程序将使用简单的 IPC 套接字通知客户端应用程序即将完成作业
在客户端接收到基于中断的通知后，它才会开始轮询结果

4 Transforming CUDA Kernels and Jobs

Paella 通过修改推断任务来 delay their release to the CUDA runtime ，实现了软件定义的 GPU 调度

Paella 通过透明地转换现有 CUDA 作业的设备和主机代码来实现这一目标

4.1 Device 端资源跟踪

在构建 model 的 kernels 时，Paella 编译器插入 instrumentation 来细粒度地暴露 GPU 硬件调度程序的效果.

4.1.1 Execution configuration information

每个 kernel 要使用的资源是静态的（static），所以，在 the launch of the kernel 之前，Paella 可以了解：Grid size，Block size, Shared memory, Register count

4.1.2 Device-side instrumentation

Paella 使用 source-level instrument 和 fast runtime communication to both the dispatcher and the client of the inference request，来追踪：

哪些 block 已经被调度
被调度到哪些 SM 上

具体来说，Paella 编译器将自动 instrument kernel 去从正在运行的 block 中导出以下信息：

Block start：指示该 block 已被调度到一个 SM 上
SM identifier：该 block 被放到了哪个 SM 上
Kernel indentifier：一个唯一的 ID，帮助 dispatcher 区分同一 kernel 的不同执行
Block end：指示该块已经成功完成，其输出已经被写入，其资源很快被释放

kernel 两次写入队列（host-device 共享内存队列）：一次在内核开始时，一次在内核结束时。对于两者，每个块的一个指定线程负责生成通知，通知 Paella dispatcher 块刚刚被放置或刚刚完成。

4.2 Host 端的 CUDA 仿真

在 Host 端，Paella 拦截所有 CUDA 调用并模拟 GPU 的调度职责。

Paella 通过以下操作来实现这个功能：

将所有相关的 CUDA 库函数包装在一个 stub 中
自动地将用户代码中的调用替换为 Paella 的版本

所以，每当一个 kernel 或者 memory copy 本应提交给 CUDA runtime，Paella 会将它们添加到一个等待列表（waitlist）中，直到 GPU 准备好处理它们

4.2.1 Kernel waitlist

由 Paella dispatcher 维护，代替了 CUDA streams 和 hardware queues 的功能。

waitlist 跟踪当前可调度（active）的 kernel 集合和依赖于其他操作完成的 kernel 集合（inactive）

4.2.2 Coroutines

这部分其实看得不是特别清除，主要是对于 CUDA 线程池和协程了解不多

在传统的 CUDA 编程中，为了执行来自不同用户的 GPU 请求，通常会创建一个线程池，每个请求都在一个独立的线程中执行。

这样做会导致：可能会产生大量线程，因此会导致CPU利用率和上下文切换开销的问题

Paella 采用了协程（Coroutines）的方式，实现了协作式多任务处理

使用这种架构，Paella 只需要一个线程；但是，可以通过将作业分片到不同线程来并行化

4.2.3 ‘Almost finished’ notification

Paella 向作业添加了一个注释，指示该作业及其输出将很快就绪

该注释的目标是在不浪费不必要的周期的情况下提前唤醒客户端，以便捕捉到已完成的通知

5 The Paella Dispatcher

Paella 调度程序运行在一个专用的 CPU 核心上，负责接收推断请求、分派内核并管理客户端与 GPU 之间的通信。

Paella 通过利用共享内存队列来实现零拷贝、无需内核的通信。为此，每个客户端在建立与调度程序的连接时会获得一个共享内存区域。

5.1 The Client → Paella Channel

用户将一个新的 job definitions 提交给 Paella service，通过提交已编译的共享库和一个辅助执行的适配器类。

之后，客户端按照以下方式提交请求给 Paella：

  
req_id = paella.predict('model_name', len, io_ptr, options);

model_name 是指事先经过仪器化和加载的模型；
io_ptr 是一个指向共享内存缓冲区的指针;
返回值 req_id 用于区分不同作业的结果.

这个接口避免了数据的编组或解组，这是当今许多服务系统中的主要开销来源。

疑惑：
下面这行话不懂，共享内存究竟是为了执行什么功能？
从前面可以看到，shared-memory queue 是用来：
通知 Paella dispatcher 块刚刚被放置或刚刚完成
实现零拷贝、无需内核的通信
每个客户端在建立与调度程序的连接时会获得一个共享内存区域

调度程序以轮询方式遍历每个共享内存队列，以接收客户端推断请求.

可支持远程推断

5.2 The Paella↔GPU Channel

5.2.1 Dispatching kernels

当时机成熟时，Paella 会直接使用内核的原始执行配置和参数启动内核

尽管最近的 GPU 试图确保流在彼此之间是异步的，但如果流的数量超过硬件队列的数量，仍然可能出现虚假依赖和 HoL 阻塞。因此，Paella 还会覆盖 cudaStreamCreate 函数以返回一个虚拟流，该虚拟流将在内核启动时替换为可用的 CUDA 流

5.2.2 Polling the instrumented statistics

轮询仪器化的统计信息

调度程序将不断轮询 GPU 上的 notifQ，以读取仪器化统计信息，并以精细的粒度跟踪 GPU 的当前占用情况。

notifQ 是单向的，使用共享内存实现。它包含两种类型的事件，即放置（placements）和完成（completions），每个事件都伴随着内核的唯一 ID 和 SM ID，并用于更新当前 GPU 资源利用情况

5.2.3 Ensuring efficiency

发现，对仪器化及其通信进行重度优化对于性能至关重要，所以，优化有：

疑惑：
第二点没看明白，是共享一个通知队列的意思吗？

将通知实现为无锁队列（lock-free queue）
Paella 对于每个调度程序线程使用单个 notifQ，减少了调度程序轮询的位置
为了减小队列的大小，对启动和结束通知进行批处理，以使每个通知表示多达 16 个线程块的组的启动/结束

5.3 The GPU → Client Channel

阻塞的读取调用利用了一种混合机制进行进程间通信。最初，客户端会在 Unix 套接字上监听第 4.2.3 节介绍的唤醒信号。只有在此之后，客户端才会开始轮询完成事件。

6 Scheduling Strategy

利用仪器化内核和服务平台之间高效的通信通道，Paella 将调度从 GPU 设备中移出，移到 Paella 调度程序中，从而实现了灵活且可扩展的调度方法

因为 Paella 尽最大努力减小 GPU 硬件队列的占用率，调度程序中的任何计算开销都有可能影响关键路径的延迟.

Paella 的默认调度程序通过一个简单但有效的算法来解决这个挑战，该算法考虑了以下因素：

剩余时间：Paella 实现了一种基于最短剩余处理时间（SRPT）的调度策略，采用了估计的方法，给出了一个估计公式
公平性：借鉴了以前工作中对赤字计数器（deficit counters）的使用
充分利用：GPU 和调度程序之间存在一些通信延迟。为了确保 GPU 始终处于饱和状态，Paella 将提交可配置的 𝐵 个块，超出其完全利用率

剩余时间和赤字计数器用红黑树来维护，红黑树是一种自平衡的二叉搜索树，它可以高效地支持插入、删除和查找操作。

这里对于赤字红黑树的处理值得记录一下：
原本一个 job 的 kernel 被执行后，这个 job 的赤字率应该减少 $1-\frac{1}{#jobs}$，其他 job 的赤字路应该增加 $\frac{1}{#jobs}$，这将会使得更新操作为 $O(n)$ 级别。所以采用将 job 的赤字率减一，将阈值减少 $\frac{1}{#jobs}$，双重下溢时需要 $O(𝑛)$ 重置

# 概念学习

#.1 model serving

模型服务（Model Serving）是指将机器学习（ML）或深度学习（DL）模型部署并提供给应用程序或系统的过程。

是将训练好的模型投入实际生产环境并使其能够接受输入数据并生成预测或推断的关键步骤

模型服务通常包括以下关键方面：部署，接口，扩展性，监控和管理，安全性

#.2 Head-of-Line Blocking

它发生在数据包或请求按照它们到达的顺序排队并等待处理时。当一个数据包或请求在队列中被阻塞时，它会阻止后续的数据包或请求继续前进，即使后续的数据包或请求本身没有问题或不受阻塞。

文章提到了 GPU 执行逻辑中的不有效的基于 FIFO 的调度策略容易导致 Head-of-Line Blocking，这意味着一些请求可能会在队列中受阻，阻止后续请求的处理，即使后续请求的处理并不受制约。

#.3 critical-path inference tasks

“Critical-path inference tasks” 指的是在计算机科学和机器学习领域中的一类任务，这些任务对延迟（latency）非常敏感，并且通常需要在用户请求的关键路径上执行。

#.4 关于 GPU

GPU 是一个 PCIe 设备，由多个流多处理器（SMs）组成，每个 SM 包含功能单元、寄存器阵列和 L1 缓存。

一个 SM 可以同时运行多个用户上下文

一旦将一个 thread block 放置在一个 SM 上，所需的资源，包括寄存器、共享内存以及块和线程的插槽，将在该块的持续时间内静态分配.

Blocks can then be grouped into a grid to form a kernel

所有在同一个 warp 中的线程会同时执行，执行相同的指令，但是可能会对不同的数据进行操作

每个 block 可以包含多个 warps

一个 SM 在同一时间只能执行一个 warp

每个SM有一个或多个 warp 调度器。当一个 warp 等待数据或因其他原因被阻塞时，调度器可以迅速切换到另一个 warp，以保持 ALU 的忙碌。这种机制被称为 SIMT（Single Instruction, Multiple Threads）。
如果一个 SM 的资源被耗尽，它可能无法分配更多的线程块，即使它有足够的 warp 调度能力

kernel 是应用程序通常与 GPU 进行交互的粒度。典型的应用程序级任务/模型将包括多个 kernel，通常按顺序执行

CUDA stream：是一系列顺序执行的指令，包括数据拷贝和内核指令。同一个 stream 中的操作顺序执行，不同 stream 中的操作可以并发执行

疑惑：
默认流（Default Stream）上的操作会不会与其他流上的操作并行执行

默认流（Default Stream）上的操作是串行执行的，~~且不会与其他流上的操作并行执行~~
阻塞流（Blocking Stream）在执行某些操作时会阻止主机 CPU 的执行，直到这些操作完成
自定义流

CUDA streams 实际上是映射到硬件队列（hardware queue）上的

#.5 Multi-Instance GPU (MIG)

用户可以设置具有强隔离性能的多个虚拟 GPU

MIG 允许一个物理 GPU 被分割成多个独立的虚拟 GPU 实例，每个实例都具有自己的计算资源和内存。这些虚拟 GPU 实例可以独立分配给不同的任务、工作负载或用户，从而提供更多的并行性和资源隔离。

#.6 在 GPU 上执行的 kernel 会经历哪几个阶段

启动阶段（Launch）：应用程序通过 API 调用指示 GPU 开始执行特定的 kernel
提交到流（Submission to Stream）：stream 是一个序列化的命令队列，其中的命令按照提交的顺序执行
设备调度（Device Scheduling）：GPU 有一个设备级别的调度器，负责从所有活动 stream 的队列中选择命令来执行
Block 调度：负责分配 block 到 SMs 的是全局调度器（或称为 GigaThread 调度器）。它会查看每个 SM 的状态和可用资源，然后决定将哪个 block 分配给哪个 SM
Warp 调度：block 中的线程会组织为 warp 进行调度，SM 内部有一个或多个 warp调度器，这些 warp 会被派发到处理单元上执行
执行阶段

#.7 Coroutine 协程

Coroutine 是一种可以与其他 Coroutine 或 Subroutine（子程序）交叉运行的程序

一段 Coroutine 也会存在一个返回语句（通常叫做 yield），一旦执行到此语句，Coroutine 就会保存上下文并且将控制权交出（睡眠），此时调用这段 Coroutine 的 whatever-routine 就会『拿到 CPU 的控制权』，并且得到 yield 出来的变量，一旦时机成熟，刚才睡眠的 Coroutine 就又可以原地复苏，从刚才暂停下来的 yield 语句继续向下执行，直到 return 才彻底结束。

#. 8 lock-free queue

是一种多线程编程中的数据结构，用于在多个线程之间安全地传递数据，而无需使用传统的互斥锁（mutex）或信号量等同步机制。

无锁队列的设计旨在最小化线程之间的竞争和等待，以提高并行性和性能.

这是通过使用一些高级的原子操作和内存屏障来实现的

Paper Reading Paella