Paper Reading Gemini

* 精简概括

*.1 What

*.2 Why

*.3 How

0 Abstract

Gemini，一个用户空间运行时调度框架，以支持多租户和弹性分配。

关键思想是引入内核突发（kernel burst）的概念，它指的是一组连续的内核一起启动，而不会被同步事件中断

基于内核突发的特点，论文提出了一个低开销的事件驱动监视器和一个动态时间共享调度器来实现我们的目标。

关键词：GPU, multi-tenancy, resource allocation, performance, scheduling

1 Introduction

实现在计算和内存资源方面解决 GPU 利用率问题的有效解决方案之一是在计算任务之间实现 GPU 共享.

专有的 GPU 堆栈和内核的异步、非抢占性质使得从主机端获取必要的信息和控制来管理 GPU 变得困难.

the proprietary GPU stack and the asynchronous, non-preemptive nature of the kernel make it difficult to obtain the necessary information and control to manage GPU from the host side.

因此，大多数解决方案基于自定义 API 库、驱动程序或操作系统模块。其他需要在编译时进行优化或分析

论文旨在实现在共享 GPU 上进行细粒度的资源管理控制，同时保持 GPU 堆栈的透明性，并且不需要来自应用程序的先验知识。

Gemini，作为一个轻量级运行时库，存在于 CUDA API 接口和应用程序之间，用于监控和控制对 GPU 的内核提交，以便以时间切片方式在应用程序之间共享 GPU。

基于内核突发，论文设计了一个在用户空间中的事件驱动监视技术，以捕获和测量运行时内核执行行为，而不引入 GPU 和 CPU 之间的同步点。

实施了一个基于令牌的时间共享调度器，用于协调客户/租户之间的 GPU 使用，提供多租户和弹性分配模型。

提出了一种基于，估计的内核突发时间的，动态配额策略和令牌吊销方案，以适应动态工作负载模式

2 Problem Descriptions

2.1 目标

论文 GPU 共享的目标是通过支持弹性和多租户资源共享，来最大化 GPU 的利用率。

每个客户端（即租户）与特定的资源需求（specified resource demand）关联，该需求在最小值（request）和最大值（limit）之间根据其工作负载变化而定。需求（demand）表示客户端可以在 GPU 上执行内核的时间百分比.

Each client (i.e., tenant) is associated with a specified resource demand between a minimum value (request) and a maximum value (limit) according to their workload variations

多租户（Multi-tenancy）确保客户端被分配的 GPU 满足其 request，并且不能超过 limit

弹性分配（Elastic allocation）允许将剩余容量弹性地分配给客户端，只要分配不超过客户端的资源限制，以便最大化计算的整体 GPU 利用率。

所以，由于工作负载的变化，客户端的实际资源分配随时间而变化。但分配永远不会违反客户端指定的请求和限制。

2.2 挑战

实现细粒度和可控制的 GPU 共享是一个具有挑战性的问题，主要有以下两个原因：

黑盒 GPU 堆栈：GPU 的应用程序接口（包括库、运行时系统、驱动程序、硬件）通常对程序员不可访问。

异步和非抢占内核：GPU 和 CPU 主要异步协作，除非在 CPU 和 GPU 之间调用显式同步函数，否则软件程序无法获取内核执行的开始时间和结束时间。但是这些同步调用同时会导致 GPU 吞吐量显著下降。现代 GPU 架构不支持内核抢占。这意味着一旦在 GPU 上启动内核，它将由硬件调度器管理，操作系统无法停止或挂起其执行。

2.3 设计要求

2.3.1 多租户隔离（Multi-Tenant Isolation）

在客户端之间隔离 GPU 内核的执行时间，并确保它们的资源使用受到资源需求容量的控制。

允许用户指定作业的最大（即限制）和最小（即请求）资源使用情况。

因此，资源管理器可以在弹性使用需求下最大化资源利用率。

2.3.2 高利用率（High Utilization）

异步 GPU 内核执行，使跟踪准确的 GPU 使用状态成为具有挑战性的任务

2.3.3 低开销（Low Overhead）

内核执行通常具有微秒级的延迟。

2.3.4 工作负载自适应（Workload Adaptation）

设计了自适应资源管理算法和技术

2.3.5 软件透明性（Software Transparency）

3 Gemini

3.1 Approach Overview

设计并实施了一个运行时 GPU 共享框架，称为 Gemini.

资源隔离是通过启用基于令牌的调度架构的时间共享解决方案来确保的，并提出了一种令牌吊销方案，以避免非抢占内核超出其调度时间配额。

通过支持弹性分配来确保在隔离的 GPU 使用下具有高资源利用率

关键创新是探索了来自 GPU 程序的内核突发行为，以便开发一个用于跟踪异步和非抢占内核执行的细粒度和低开销的事件驱动监视器。

利用运行时监视器信息，开发了一个动态配额调度器。

通过 CUDA 统一内存技术支持内存超额分配，并提出了最小化统一内存的内存传输延迟的策略。

最终实现为一个轻量级的 CUDA API 挂载模块。

3.2 System Design

Gemini 由 2 个组件组成：

a frontend CUDA API hook runtime library：插入到客户端应用程序环境中
a centralized backend scheduler：用于协调客户端之间的 GPU 使用

3.2.1 frontend API hook runtime library

API hook 是一个 Linux 共享库，其路径被添加到 LD_PRELOAD Linux 环境变量中。在任何其他库之前，动态加载器将首先加载 LD_PRELOAD 中的共享库。

使用这个技巧允许 hook library 拦截应用程序的 CUDA API 调用并检索运行时信息，甚至覆盖原始的 CUDA API.

需要拦截三种类型的 CUDA API 调用：内核启动、内存管理和主机端同步

内核启动和主机端同步的 API 被拦截以捕获客户端的 GPU 使用模式，并从调度器请求计算资源的令牌。
内存管理 API 被拦截以通过 CUDA 统一内存技术支持内存超额分配

3.2.2 backend scheduler

实现了一个基于令牌的调度框架，确保 GPU 资源以时间共享的方式分配给客户端.

一个令牌表示时间片，令牌的配额是时间片的长度.

只有具有有效令牌的 API hook 才能将来自客户端的内核启动调用传递给 GPU 驱动程序进行执行。

当令牌的配额过期时，令牌将变为无效，其 hook library 必须从调度器请求一个新令牌，以供将来的内核执行使用.

令牌配额的设置对调度性能至关重要：

如果令牌配额太长，时间片中可能包含更多客户端的空闲时间，这可能会降低 GPU 利用率，因为令牌会阻止其他客户端提交内核到 GPU
如果令牌配额太短，客户端必须更频繁地从调度器请求有效令牌，这会导致 API hook 和调度器之间的同步开销更高。当令牌配额变得更短时，超额使用的机会也会增加

3.3 Kernel Burst

「内核突发」指的是一组连续的内核，它们一起启动，而不会被同步事件中断。

GPU 使用模式可以被建模为在执行和同步之间交织的一系列阶段的序列。

根据内核突发而不是单个内核启动来调度令牌和分配资源具有以下优势：

应避免在内核突发期间客户端和调度器之间的协调
跟踪内核时间所带来的开销可以显著减少
内核突发的稳定性可以帮助我们更准确地进行时间预测
通过将令牌配额设置为内核突发时间的一部分，仍然可以以更精细的时间粒度管理资源

3.4 Event-Driven Monitoring

监视机制是在 API hook 中实现的，因此，监视器只能访问 CUDA API，并在应用程序调用这些 API 时触发。

监视器的目标是从应用程序中识别内核突发，并正确记录它们的实际开始时间和结束时间以供执行。

主要挑战在于，CUDA 事件是与 CPU 异步记录的。

为了避免监视的同步开销，当应用程序自己调用同步事件时，我们将我们的监视事件附加在其后。可以检测到内核突发的结束。

为了检测内核突发的开始时间，我们只需要在完成用户同步事件或 API hook 调度事件后添加监视事件。同样，我们的监视事件可以与现有的同步点一起附加。

核心逻辑在于：
文章假定 kernel burst 是一系列 kernel launch，后面跟着同步操作。
所以在同步操作前能够插入监控的话，就能检测到 kernel burst 的结束。
但是存在一个例外是，kernel burst 因 Token 失效而被迫中止，所以当 Token 失效时，加入一个监控事件，也可以检测到 kernel burst 的结束。同时，因为在这种情况下，API hook 需要阻塞应用并且申请新的 token，所以在这里加入监控事件并不会引入额外开销。更重要的是，这样做同时可以测量到 overuse 的量。
kernel burst 的开始只有以下两种时刻：
API hook 收到了 Token，然后开始发送 kernels.
在一个同步操作后，第一个 kernel launch 指令被调用的时候。
这两种情况下，只需要在完成 user 同步或者 API hook 调度事件后加入监控，即可检测到 kernel burst 的开始。

监视器只在以下情况下调度事件：

在同步事件完成之前和之后
当当前令牌过期时
当从调度器接收到新的令牌时
当在同步事件之后调用第一个内核启动 API 时

为了在不阻塞应用程序的情况下接收我们的监视事件通知，我们的 API hook 在程序初始化期间生成一组监视线程。在主线程（即 GPU 流）上调用 cudaEventRecord 以安排同步点，而在监视线程上调用 cudaEventSynchronize 以记录内核突发时间。

3.5 Dynamic & Elastic Scheduling

后端调度器有两个主要目标：

在来自客户端的资源需求约束下，支持弹性分配并最大化 GPU 利用率
提供动态配额调度，以便根据各个客户端的工作负载模式选择适当的令牌配额

提出了一个令牌吊销方案，允许客户端主动调整调度配额，以防止 GPU 空闲并提高 GPU 利用率

3.5.1 弹性分配 Elastic Allocation

调度器按照以下四个步骤，决定哪个客户端收到下一个有效 Token。

这些步骤会在以下情况下定期执行：
之前的 Token 过期，同时有客户端在调度队列中等待
一个新的客户端需求到达，同时没有客户端持有有效的 Token

Step1. 计算分配。使用滑动窗口。

Step2. 过滤请求。已经超过资源限制的客户端的请求将不会被选择

Step3. 优先处理请求。第一优先级是满足客户端的最低资源需求。如果 GPU 上还有剩余容量，我们将继续分配资源给客户端，直到它们达到其最大资源需求

这里要注意的是，在分配到的时间片里，租户是独占 GPU 资源的。

Step4. 确定令牌配额.

3.5.2 动态配额 Dynamic Quota

允许 API hook 向调度器提供其客户端内核突发的一些统计信息。调度器使用平滑函数根据来自客户端的估计突发时间逐渐调整客户端的令牌配额.

简单来说就是根据过去的内核突发的时间估计下一次内核突发的时间，用上次令牌配额和估计时间决定下一次令牌配额。

3.5.3 令牌撤销 Token Revocation

允许客户端在配额到期之前撤销其令牌，当客户端发现剩余的配额时间不足以执行下一个内核时.

通过将内核突发时间除以在突发周期内发生的内核调用次数来粗略估算内核时间.

令牌撤销可以在两种情况下发生：

第一种情况发生在内核执行结束时剩余的配额时间少于估计的内核执行时间。在这情况下，需要插入一个监控，以便在最后一个内核执行结束时得到通知，并立即撤销令牌，以避免 GPU 空闲或过度使用。
第二种情况发生在内核启动调用到达时，剩余的配额时间少于估计的内核时间。在这种情况下，当一个 kernel 调用到达时，需要检查剩余配额时间是否足够，不够的话就需要阻塞 kernel.

令牌撤销方案有助于进一步减少来自客户端的资源超用和闲置问题。

3.6 内存共享和优化

内存在空间域内共享。

在我们的租户模型中，客户端还必须在资源规范中指定其最大内存使用量，并且其内存使用量在其执行期间不应超过其请求的限制。

我们的 GPU 共享库还必须在运行时保证内存使用约束。

与我们的计算资源调控技术类似，Gemini 拦截了所有向 CUDA 驱动程序发出的内存分配 API 调用，以跟踪每个客户端的实际内存使用情况。

内存使用可能会限制共享 GPU 上的并发客户端数量。为解决这个问题，我们建议使用统一内存技术。

通过统一内存，我们让 GPU 使用主机内存作为 GPU 内存内容的交换空间，并只在 GPU 中保留活动内存，以便 GPU 可以被更多应用程序共享。为实现这一点，Gemini 简单地将所有拦截的内存和数组分配/释放 API 替换为 cudaMallocManaged 统一内存分配 API。

Therefore, through unified memory, we let GPUs use the host memory as a swap space for the GPU memory content and only keep the active memory in GPU so that the GPU could be shared by more applications. To achieve this, Gemini simply replaces all the intercepted memory and array allocation/free APIs with the cuda-MallocManaged unified memory allocation API.

疑问：
联想那边实现的显存隔离是否支持统一内存？

又引入了，使用 cudaMemPrefetchAsync API 预取内存内容，以及通过猜测内核启动所需的内存内容或释放应用程序未使用的内存内容来减少需要预取的数据量，两种方法来减少内存传输时间。

4 Evaluations

# 概念学习

#.1 统一内存技术 unified memory

统一内存首次在 CUDA 6.0 版本中引入，用于 NVIDIA Kepler GPU 架构，为应用程序提供了一个单一的、统一的虚拟地址空间，用于访问 CPU 和 GPU 内存。受管理的内存在 CPU 和 GPU 之间共享，CUDA 驱动程序会在需要时自动透明地在 CPU 和 GPU 之间迁移数据，以满足应用程序的需求。