VELTAIR

Liu, Zihan, et al. "VELTAIR: towards high-performance multi-tenant deep learning services via adaptive compilation and scheduling." Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2022.

https://dl.acm.org/doi/abs/10.1145/3503222.3507752

Introduction

Liu, Zihan, et al. "VELTAIR: towards high-performance multi-tenant deep learning services via adaptive compilation and scheduling." Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2022.

干扰级别下的代码版本。
- 易受干扰 vs 抗干扰的代码
- 在 parallelism 和 locality 的权衡空间的 Pareto 边界上。
- 提出 single pass 编译策略 —— 编译出适合于不同干扰压力级别的实现版本
调度粒度：
- 模型调度 —— 低效率资源利用；
- 层级调度 —— 频繁资源冲突。
- 提出 layer-block 粒度调度，动态阈值 —— 尽可能低冲突、高利用率

Motivation and Challenges for Multi-tenant DNNs

pass

Optimization Space Analysis

2 optimization knobs：调度粒度 & 编译策略

QoS satisfaction rate： QoS 目标内完成的请求

优化空间定义

调度粒度：分配资源和调度的 entity 的大小。多层为单位的新调度粒度 —— 层块（layer block）
编译策略：code generation options。

调度粒度分析

比较：分层调度、模型调度和层块调度。

模型调度的低效率：不同层具有不同的 scalability trend。

层级调度的低效率：频繁调度冲突

编译策略分析

为了确定目标层在给定干扰水平下的最佳代码实现，我们启动了一个产生所需干扰水平的背景层。比较了四种不同实现方式在不同干扰水平下的性能。具体来说，这四种实现方式分别对应于在零、低、中、高干扰水平下搜索到的最佳实现方式。

具体来说，我们选择十个干扰级别，并确定每个级别上性能最佳的版本，这导致每层总共有十个实现版本。需要五个代码版本才能将性能损失保持在 10% 以内（对比 10 个代码版本），但大多数（即超过 80%）层只需要三个代码版本。

Detailed Design of VELTAIR

编译器的关键新颖之处是单遍多版本搜索算法。

Veltair运行时调度器动态形成层块作为调度单元，平衡了核心使用效率和调度冲突率。

通过监控系统负载和干扰压力，它自适应地选择最佳的代码版本和调度粒度

单遍静态多版本编译器

并行性-局部性权衡。

parallelism = loop unrolling factor \(\times\) parallelization factor
locality = tiling/blocking size

重干扰优化版本通常更喜欢高并行性和小块大小，而轻干扰优化版本则相反。

具有较高局部性（较大的块大小）的生成代码在轻干扰（易受干扰）下表现更好，而具有较高并行性的生成代码在重干扰（耐干扰）下表现更好。

为了利用大局部性，一层需要使用更多的片上存储器，例如CPU中的LLC，它们是多个CPU核之间的共享资源。然而，当共享资源（根据我们的观察，L3 缓存和相应的带宽）出现争用时，该层的性能会迅速下降。为了减轻争用的影响，该层可以限制其局部性并使用更多并行性来弥补其性能损失。

TVM Ansor
过滤掉不能满足 QoS 的样本（FLOPs）
𝐸𝑥𝑡𝑟𝑎𝑐𝑡𝐷𝑜𝑚𝑖𝑛𝑎𝑛𝑡 函数，帕累托边界

基于动态阈值的层块形成

为了通过层块调度来降低调度冲突率，我们首先确定最有可能触发冲突的层。为了识别这些容易发生冲突的层，我们计算每层在其 QoS 目标内完成所需的 CPU 核心数量。

我们将分层核心数与模型平均值进行比较，并将 CPU 核心数要求远高于平均值的层识别为容易发生冲突的层。

Input: 𝑙𝑎𝑦𝑒𝑟𝑠[𝑁], 𝑖𝑚𝑝𝑙𝑠, 𝑡ℎ𝑟𝑒𝑠
Output: 𝐿𝑎𝑦𝑒𝑟_𝐵𝑙𝑜𝑐𝑘
function Finding1stPivot(𝑙𝑎𝑦𝑒𝑟𝑠, 𝑖𝑚𝑝𝑙𝑠, 𝑡ℎ𝑟𝑒𝑠)
    𝑠𝑝𝑙𝑖𝑡𝑡𝑖𝑛𝑔_𝑝𝑖𝑣𝑜𝑡 ← 0
    𝐴𝑣𝑔_𝐶 ←𝐶𝑜𝑟𝑒@𝑀𝑜𝑑𝑒𝑙 𝐺𝑟𝑎𝑛𝑢𝑙𝑎𝑟𝑖𝑡𝑦(𝑙𝑎𝑦𝑒𝑟𝑠)
    for _𝑙 in 𝑙𝑎𝑦𝑒𝑟𝑠[1 : 𝑁] do
        if 𝐶𝑜𝑟𝑒(𝑖𝑚𝑝𝑙𝑠[_𝑙]) ≥ 𝑡ℎ𝑟𝑒𝑠 +𝐴𝑣𝑔_𝐶 then
            𝑠𝑝𝑙𝑖𝑡𝑡𝑖𝑛𝑔_𝑝𝑖𝑣𝑜𝑡 ← _𝑙
            break
        end if
    end for
    return 𝑠𝑝𝑙𝑖𝑡𝑡𝑖𝑛𝑔_𝑝𝑖𝑣𝑜𝑡
end function
function FormingLBs(𝑙𝑎𝑦𝑒𝑟𝑠)
    𝐿𝑎𝑦𝑒𝑟_𝐵𝑙𝑜𝑐𝑘 ← [],𝑏𝑒𝑔𝑖𝑛 ← 0
    while 𝑙𝑎𝑦𝑒𝑟𝑠.𝑙𝑒𝑛𝑔𝑡ℎ() ≠ 0 do
        𝑠𝑝 ←𝐹𝑖𝑛𝑑𝑖𝑛𝑔1𝑠𝑡𝑃𝑖𝑣𝑜𝑡(𝑙𝑎𝑦𝑒𝑟𝑠,𝑖𝑚𝑝𝑙𝑠,𝑡ℎ𝑟𝑒𝑠)
        𝐿𝑎𝑦𝑒𝑟_𝐵𝑙𝑜𝑐𝑘.𝑝𝑢𝑠ℎ_𝑏𝑎𝑐𝑘(𝑙𝑎𝑦𝑒𝑟𝑠[𝑏𝑒𝑔𝑖𝑛 : 𝑠𝑝])
        𝑙𝑎𝑦𝑒𝑟𝑠 ← 𝑙𝑎𝑦𝑒𝑟𝑠[𝑠𝑝 + 1 :]
        𝑏𝑒𝑔𝑖𝑛 ← 𝑠𝑝 + 1
    end while
    return 𝐿𝑎𝑦𝑒𝑟_𝐵𝑙𝑜𝑐𝑘𝑠
end function

运行时调度程序

为了弄清楚哪些性能计数器决定干扰水平，我们对收集的性能计数器进行主成分分析（PCA），包括L3缓存未命中率、L3访问、每周期指令（IPC）、浮点运算等。

我们选择L3丢失率和L3访问来构建简单的线性干扰模型。使用这个简单的线性模型，我们可以在运行时以低成本导出干扰压力水平。

Evaluation

工作负载：泊松分布。对于混合工作负载，每个任务的频率设置为 QoS 的反比。

为了获得稳定实验结果，关闭 SMT（ simultaneous multi-threading），DVFS（dynamic voltage and frequency scaling ）。

评价指标：95%任务 QoS 满足的 QPS，平均延迟，CPU 使用效率。

baseline 选择：Planaria（空间多任务），PERMA（时间多任务，抢占）

Veltair 配置：

Veltair-AS：仅具有自适应调度。
Veltair-AC：仅具有自适应编译。
Veltair-FULL：同时启用自适应调度和自适应编译。

QPS 提升

对比 Planaria，在低、中、重工作负载上，Veltair-FULL 获得了 71%、62%、44% 的提升，Mix 平均 68%。

Veltair-AC 比 Veltair-AS 有更好的提升。

基于时间多任务的 PERMA 比空间多任务的 Planaria 差。

请求执行延迟

与独占执行延迟比较。以确定 Veltair 的优化空间。Veltair-AC 执行延迟是独占的 1.17 倍，而 Veltair-Full 是 1.1 倍。

CPU Efficiency

层级调度可达到最小的平均 core 使用率。Veltair 与最小相比，小于 10%。但模型调度的达到 47%。

灵敏度和开销分析

灵敏度：

研究性能提升随版本数量增加的改变。4 种版本后，性能提升达到饱和。
不同层版本计数。只有 3% 的层需要五个版本。

调度开销：

运行时层块形成：复杂度 O(N)
干扰 proxy：基于线性模型

复杂度低，每个 DNN 模型的总体开销<0.1ms。

数据执行的 task co-location

multi-tenant DL 服务

DL 编译器