简要

现象：数据中心的深度学习推荐系统具有许多独特的工作负载特征和系统需求——模型多样性、云规模的系统异构行和时变负载模式。这些都需要特定于应用程序的解决方案来提高执行效率。

问题：

  1. 模型多样性：推荐模型的迅速发展，以支持新的用例，并实现更高的预测精度。这种不同算法结构导致了不同的性能瓶颈。最先进的推荐模型的计算和内存强度可以变化1~2个数量级。

    image-20230315095222834

  2. 云规模的系统异构：各种各样的系统架构可以在数据中心中共存，其原因如下：

    1. 系统升级会周期性的发生，不同微架构的服务器一代又一代地出现
    2. 特定领域的加速器越来越多地部署在数据中心，以最大化执行效率

  3. 时变负载模式：查询到达服从泊松分布，查询大小呈明显的重尾分布。动态变化的条件要求调度程序在不同级别运行，以快速适应和响应负载变化。

  4. 最优调度鞠策高度依赖于模型和硬件，并且需要一个有效的搜索机制来充分探索所有SLA（服务级协议）目标在模型并行、操作员并行和数据并行维度上的大调度空间。但现有的任务调度器设计缺乏遍历整个并行空间的能力。

方案：

Herules——heterogeneity-aware recommendation using latency- and energy-conscious scheduler—tailor-designed for at-scale neural recommendation inferences.（用于大规模神经推荐推理的使用为低延迟和节能调度量身设计的异构注意推荐）

其有两个阶段：

  1. 脱机分析阶段：Hercules详尽地探索了任务调度的并行空间，并未工作负载/服务器类型对的所有排列派生了一个效率元组
  2. 在线分析阶段：Hercules在集群及使用效率元组进行异构感知发放，解决约束优化问题最大限度地降低数据中心资源成本。

贡献：

  1. 将广大的设计空间转化为一个约束优化问题，提出一个有效的搜索方法，其能为异构注意的集群调度进行有效地探索并行空间，并识别最优的执行方案。
  2. 与最先进的SLA感知调度程序相比，本文为任务调度确定了未探索的并行空间，实现了1.03x到9x的延迟受限的吞吐量改进。
  3. Herucles可以实现高达47.7%的集群容量和23.7%预置电源节省最先进的贪婪调度器，使得集群资源效率变得更高。

Insights

  1. 对于进一步促进延迟限制吞吐量（QPS）和能源效率（QPS-per-Watt）方面，在模型调度上的并行维度和工作流不平衡的底层探索仍然有显著的提升空间（观测到同样是20个线程，一核20线程和2核，每核10线程的性能表现不一样，后者可以取得更高的执行效率。还观测到当worker的数量增加时，CPU存在的idle时间会变长）
  2. GPU这样的加速器受益于模型共存和查询融合的并发探索，与最先进的调度器相比，实现了7.87倍的吞吐量和3.36倍的能源效率提升，但是由于内存容量优先，他们无法容纳大型模型。（观测是使用三个不同的推荐模型，使用三种不同的策略(无模型共存无查询融合，单模型共存，模型共存+查询融合)进行评测，使用了模型共存+查询融合策略的推荐模型都取得了最好的表现）
  3. 尽管具有异构感知能力，但当多个工作负载竞争相同的服务器类型时，最先进的贪婪调度器无法正确分配服务器，导致次优的解决方案

Hercules设计

总览

image-20230317190538673

Hercules由两个主要的stage组成：离线分析和在线服务

离线分析：最大化单个服务器上推荐工作负载执行的效率，并为所有工作负载/服务器类型对记录一个效率元组

在线服务：将离线分析的记录输入到集群调度器中，用于调度集群

GmG_m：将推荐模型形成一个计算图，这个计算图就是GmG_m

SLAmSLA_m：GmG_m对应的SLA延迟目标

ThT_h：GmG_m的服务器候选集

在离线分析中，首先为每个GmG_m和ThT_h对，执行HW-aware Model Partition(图9，a的左上角)使其满足大型推荐模型在硬件上的内存容量约束，然后执行SLA-aware task scheduling exploration(图9，绿色框，第一行，第二个)，以获取在满足SLA延迟目标上的最大延迟限制吞吐量。然后以表格的形式(像图9b)记录延迟限制吞吐量QPSm,hQPS_{m,h}和测量的峰值功率Powerm,hPower_{m,h}。这些记录对每个工作负载的可用服务器体系结构进行定量分类。

在线服务时，首先通过运行SLA- & Power-aware task scheduling exploration(图9，a的蓝色框下面那个)来执行初始化设置，以确保使用实时查询进行准确的分析。这里他必须满足两个条件(图9，a的蓝色框上面那个)：SLA延迟目标SLAmSLA_m以及功率开销要在功率预算Powerm,hPower_{m,h}之内。在离线分析中记录的效率元组也会实时更新，以衡量实时查询负载的性能QPSm,hQPS_{m,h}。

通过定量工作负载分类，将集群提供描述为一个全局资源成本最小化目标的约束优化问题。动态分配适当数量的最佳匹配服务器，以满足传入的每日负载。

梯度引导的任务调度探索

在单个服务器上的推荐推理需要满足三个约束：硬件资源，SLA延迟，满足功率预算。Hercules执行硬件注意模型分区使其满足内存容量，并进行满足SLA延迟和功率预算的并行空间探索。

硬件注意模型分区和流水线

image-20230317194633208

本文观察到95的模型内存占用适用于在稀疏网络GsG_s的embedding表上，而密集网络GdG_d的则只有几MB，于是，如图10的a所示，本文提出了局部注意的embedding分区方法去识别hot embedding实例，并通过访问频率去排序他们，形成hot embedding表。hot embedding表的数量又每个线程的容量预算(内存容量和模型共存)决定。原始的模型GmG_m将被分为3个部分：密集网络GdG_d，拥有整个embedding表的稀疏网络GsG_s，拥有hot embedding表的Gs.hotG_{s.hot}。

这里先要介绍两种调度：

  1. 基于模型的调度：如图10的b所示，他将CPU资源划分为密集线程和稀疏线程，将没有操作依赖的稀疏网络GsG_s放入到稀疏线程中，有操作依赖的密集网络放入到密集线程中。
  2. 稀疏-密集(S-D)流水线调度：如图10c所示，将稀疏网络GsG_s放入到host端(可以简单认为是CPU)，把密集网络GdG_d放入到加速器端(可以简单认为就是GPU)

而Hercules使用的是交替执行两种调度的方法，如图9d所示，将热稀疏网络和密集网络Gs.hot+GdG_{s.hot}+G_d放入到加速器端，然后host端则是放稀疏网络GSG_S，这个GsG_s是不携带Gs.hotG_{s.hot}部分的。（集合基于模型调度的稀疏线程和密集线程，同时结合S-D流水线调度的host端和加速器端）。

基于梯度的搜索

整个并行空间为Psp(M+D+O)P_{sp}(M+D+O)，其中MM是每个线程的共存数，OO是每个线程的核心数，DD是batch size。结合所有的并行维度，他等价于Psp(O)×Psp(M+D)P_{sp}(O)\times P_{sp}(M+D)。其中Psp(O)P_{sp}(O)表示一个线程可以分配的核心数，因此只用探索Psp(M+D)P_{sp}(M+D)的维度即可。

对于一个线程使用i个核心数的情况Psp(O)[i]P_{sp}(O)[i]而言,Psp(M+D)P_{sp}(M+D)从最少共存数和最少batch size开始，每次更新有三个选择：

  1. 增加共存数
  2. 增加batch size
  3. 同时增加共存数和batch size

通过这三种方式生成候选三个候选节点，然后计算三个候选点相对于其实点的尾延迟和吞吐量的梯度，分别表示为∇ Latency [1:3]\nabla \text { Latency }[1: 3] 和∇QPS⁡[1:3]\nabla \operatorname{QPS}[1: 3]。并且要考虑到候选点必须满足用户设置的SLA延迟LL和功率PP的限制。当所有三个候选配置的吞吐结果都比当前配置低时，搜索将停止，并且报告这个配置在当前一个线程使用i个核心数Psp(O)[i]P_{sp}(O)[i]是最优的配置。接着就可以遍历下一个情况Psp(O)[i+1]P_{sp}(O)[i+1]。然后再比较Psp(O)[i]P_{sp}(O)[i]和Psp(O)[i+1]P_{sp}(O)[i+1]之间更优的选择，作为最终的选择。

伪代码如下：

算法1：基于梯度的搜索

数据：SLA延迟目标LL，功率预算PP

结果：调度配置

初始化：batch size， 线程的数量

  1. for (op-parallelism) in Psp(O)P_{sp}(O) do:
  2. #P(M+D)空间搜索
  3. while do
    1. # 三个候选
    2. ∇ Latency [1:3]\nabla \text { Latency }[1: 3] = $ \text { Latency }[1: 3] - \text{Latency}_{t-1}$
    3. ∇QPS⁡[1:3]=QPS⁡[1:3]−QPSt−1\nabla \operatorname{QPS}[1: 3]=\operatorname{QPS}[1: 3]-QPS_{t-1}
    4. if (max(∇QPS⁡>0\nabla \operatorname{QPS}>0) and (Latency<LLatency<L) and (Power<PPower < P)) then
      1. # 吞吐量提升
      2. 使用提升最大的候选点进行配置更新
    5. else
      1. 结束搜索
    6. end
  4. end
  5. if 操作并行的配置下吞吐量减少 then
    1. 结束并返回最好的配置信息
  6. end
  7. end

面向目标的集群调度优化

由于最先进的贪婪调度器在定量分配竞争最佳匹配服务器的优先级方面存在缺陷，因此需要一个数值优化目标来保证全局集群资源成本最小化。本文将这个问题描述为一个约束优化问题，优化目标是找到N1:H,1:M(t)N_{1:H,1:M}(t)的值（公式1），使得整个功率预算最小。Nh,m(t)N_{h, m}(t)是分配给工作负载GmG_m的服务器类型ThT_h的数量，RR是获得率。QPSh,mQ P S_{h, m}和$ Power_{h, m}是工作负载是工作负载G_m运行在服务器运行在服务器T_h$上的限制延迟吞吐量和限制功率预算。

这里有两个约束需要满足：

  1. 对于所有的工作负载G1:MG_{1: M}，分配给工作负载GmG_m的服务器数量必须满足工作流在时间tt的收入加载 load⁡m(t)\operatorname{load}_m(t)（公式2）。
  2. 激活的服务器数量不能超过容量限制(公式3)，其中NhN_h可使用的ThT_h服务器的数量。

 公式1：Minimize ∑m=1M(∑h=1H(Nh,m(t)× Power h,m)), subject to ∀m∈[1.M],公式2：∑h=1H(Nh,m(t)×QPSh,m)⩾load⁡m(t)(1+R%),∀h∈[1..H],公式3：∑m=1MNh,m(t)⩽Nh\begin{gathered} \text { 公式1：Minimize } \sum_{m=1}^M\left(\sum_{h=1}^H\left(N_{h, m}(t) \times \text { Power }_{h, m}\right)\right), \text { subject to } \\ \forall m \in[1 . M], \text{公式2：}\sum_{h=1}^H\left(N_{h, m}(t) \times Q P S_{h, m}\right) \geqslant \operatorname{load}_m(t)(1+R \%), \\ \forall h \in[1 . . H], \text{公式3：}\sum_{m=1}^M N_{h, m}(t) \leqslant N_h \end{gathered}

在图9c中，集群管理器为所有的服务器ThT_h和工作负载GmG_m对保留最优的限制延迟QPS和功率预算元组，并且知道对于所有工作负载在当前时间t内的load1:M(t)load_{1:M}(t)。在运行最优的解决方案 N1:H,1:M(t)N_{1: H, 1: M}(t)后，集群管理器能够激活/释放服务器，并决定那个工作负载在激活的服务器上执行。动态供应以粗略的时间间隔(10秒为分钟)执行，以摊销工作负载设置时间的开销(10秒为秒)。设置超额供应率R以处理此时间间隔内的负载增量。R是通过分析时间间隔长度内的历史负载变化来估计的。