论文地址-《DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving》

代码地址- Github

摘要

• Distserve通过分解预填充和解码计算来提高大语模型（LLMS）的性能。现有的LLM服务系统可以分配两个阶段，并批量在所有用户和请求中进行预填充和解码的计算。
  • 作者发现，这种策略不仅会导致强烈的预填充干扰，而且还伴随了两个阶段的资源分配和并行计划。
  • LLM应用程序通常会强调每个阶段的个体延迟：对于预填充阶段的 “time to first token” TTFT，以及每个请求解码阶段的 “time per output token” TPOT
  • 在存在严格的延迟要求的情况下，现有系统必须优先考虑一个延迟，或者过度交付的计算资源以满足这两者。
• Distserve将预填充和解码计算分配给不同的GPU，因此消除了预填充解码的干扰。
  • 鉴于应用程序的TTFT和TPOT要求，DistServe会选择为每个阶段量身定制的资源分配和并行性策略。
  • Distserve还根据服务集群的带宽放置两个阶段，以最大程度地减少分解引起的通信。结果，Distserve可以显着改善LLM服务性能，从而在每个GPU上都可以在TTFT和TPOT约束中提供的最大速率。
• 效果
  • 作者的评估表明，与最先进的系统相比，Distserve在各种流行的LLM，应用程序和延迟要求上，可以提供7.4×更多请求或12.6倍的SLO，同时保持大于90％的请求满足延迟约束。
    
    

1 介绍

• LLM服务分为两个阶段响应用户查询。
  • 预填充阶段处理用户的提示，由一系列token组成，以在一个步骤中生成响应的第一个token。
  • 接着，解码阶段依次以多个步骤生成后续token。每个解码步骤都会根据上一步中生成的token生成一个新token，直到达到终止token。
  • 这种双阶段过程将 LLM 服务与传统服务区分开来——LLM 服务的延迟由两个关键指标唯一衡量：首次token的时间 （TTFT），即预填充阶段的持续时间，以及每个输出token的时间 （TPOT），它表示为每个请求生成token所花费的平均时间（第一个token除外）
  • 不同的应用程序对每个指标提出了不同的要求。例如，实时聊天机器人 [1] 优先考虑低 TTFT 以实现响应及时性，而 TPOT 仅在其比人类阅读速度更快（即 250 个单词/分钟）之前才保持重要性。相反，文档摘要强调低 TPOT 以更快地生成摘要。
    
    
• 由于预填充和解码阶段共享 LLM 权重和工作内存，因此现有的 LLM 服务系统通常在 GPU 上将这两个阶段放在一起，并通过跨请求批处理预填充和解码步骤来最大限度地提高整体系统吞吐量（所有用户和请求每秒生成的token）。但是，为了满足延迟要求，作者发现这些系统必须过度预置计算资源。
  • 图 1 说明了在使用现有系统为 13B LLM 提供服务时，P90 TTFT 和 TPOT 如何随着请求速率的增加而变化。在 90% 的 SLO 达到率下，单个 A100 GPU 上可实现的最大吞吐量约为每秒 1.6 个请求 （rps），该要求受到更严格的 TTFT 和 TPOT 要求的限制。
  • 当每个阶段在单独的 GPU 上独立提供时，性能会形成鲜明对比，如橙色和绿色曲线所示，预填充阶段的每 GPU 吞吐量为 5.6 rps，解码的每 GPU 吞吐量为 10 rps。理想情况下，通过分配 2 个 GPU 用于预填充和 1 个 GPU 用于解码，作者可以有效地为模型提供 10 rps 的整体吞吐量，或者每个 GPU 平均 3.3 rps，这比现有系统高 2.1 倍。

• 挑战
  • 首先，同位导致较强的预填充-解码干扰。
    • 一个预填充步骤往往要比一个解码步骤花费更长的时间。当批处理在一起时，批处理中的解码步骤被预填充步骤延迟，显著延长了它们的TPOT；类似地，加入解码步骤有助于TTFT的非平凡增加，如图2所示。
    • 即使作者单独调度它们，当它们开始竞争资源时，问题仍然存在。等待GPU执行的解码任务由于正在进行的预填充任务而导致排队延迟增加，反之亦然。一个阶段的优先调度可能导致另一个阶段的延迟需求无法满足。
  • 其次，预填充和解码计算的延迟需求和对并行方式的偏好不同。
    • 然而，配置预填充和解码耦合了它们的资源分配，并阻止执行不同的并行策略更适合满足每个阶段的特定延迟要求。

• 为了克服这些挑战，作者提出将LLM推理的预填充和解码阶段进行分解，分配给单独的GPU。
• 两个好处
  • 首先，在不同的GPU上独立运行每个相位，消除了预填充-解码干扰。
  • 其次，它允许通过定制的资源分配和模型并行策略来独立地扩展每个阶段，以满足其特定的延迟要求。
• 尽管解聚会导致GPU之间的中间状态通信，但作者表明，在现代GPU集群中，通信开销并不大( § 3.3 )，并且在适当的管理下，解聚会显著提高了每个GPU的吞吐量。
• 基于以上认识，本文通过分解预填充和解码阶段，构建了一个良好的吞吐量优化的LLM服务系统DistServe。
  • 在给定TTFT和TPOT需求的情况下，DistServe首先通过协同优化预填充和解码阶段的GPU分配和并行策略来独立地扩展每个阶段，假设服务于单个模型副本。优化可确保最大化每个GPU的优势，并根据各自的延迟要求为每个阶段分配不同数量的GPU和并行策略。
  • 然后，DistServe通过复制将此分配范围分配到多个实例，直到达到用户所需的流量率（第4节）。
  • DistServe还具有算法，根据其分配方案和群集的带宽放置预填充和解码计算，以最大程度地减少相之间中间状态的开销。
    
    

2 背景和动机

3 权衡分析

• 分解脱离了两个阶段，并允许对每个阶段的特征进行明显的分析，从而为算法设计提供了宝贵的见解。它还扩大了设计空间：现在，每个阶段都需要根据其延迟要求独立缩放和计划。
  
  

3.1 预填充实例分析

• 分解后，预填充阶段通过并行处理用户提示的所有token来生成第一个token。假设给定的到达率，作者旨在使用最少的资源来满足服务对TTFT的延迟要求。
• 批处理策略
  • 预填充步骤通常是计算密集型的。
  • 图 3（a） 显示了预填充阶段的吞吐量如何随输入长度和批次大小而变化。对于 13B 参数 LLM，处理单个 512 个token序列可以完全占满 A100 GPU。一旦 GPU 变成计算瓶颈，向批处理添加更多请求就不再能提高 GPU 效率。相反，它会按比例延长批处理的总处理时间，从而无意中延迟所有包含的请求。
  • 因此，对于预填充实例，有必要提前分析特定的 LLM 和 GPU，以确定关键输入长度阈值，表示为 Lm，超过该阈值后，预填充阶段将受计算限制。仅当计划请求的输入长度低于 Lm 时，才应考虑对更多请求进行批处理。在实践中，用户提示通常平均超过数百个 Token[8]。预填充实例的批量大小通常保持较小。

• 并行方案
  • 为了研究仅预填充实例的并行度偏好，作者在两个 A100 GPU 上使用操作间或操作内并行策略提供 66B LLM。
  • 作者在图 4（a） 中比较了不同到达速率下的平均 TTFT：运算内并行性在较低的到达速率下效率更高，而运算间并行性随着速率的增加而获得优势。
  • 解聚使预填充阶段的功能类似于 M/D/1 队列，因此作者可以使用排队理论来验证观察结果。
• 理论验证略
  
  

3.2 解码实例分析

• 与预填充实例不同，解码实例遵循不同的计算模式：它从预填充实例接收 KV 缓存和第一个输出token，并一次生成一个后续token。对于解码实例，作者的优化目标是使用最少的计算资源满足应用程序的 TPOT 要求。
• 批处理策略
  • 由于单个解码作业受带宽严重限制，因此批处理是避免低 GPU 利用率（因此每个 GPU 的吞吐量高）的关键，如图 3 （b） 所示。
  • 在预填充和解码阶段共置的现有系统中，增加解码批处理大小很困难，因为它与满足延迟目标相冲突，尤其是在请求率较高的情况下。这是因为共享 GPU 会导致预填充和解码作业之间的竞争，从而导致 TTFT 和 TPOT 之间的权衡。
  • 相反，解耦提供了一种解决方案，它允许将多个预填充实例分配给单个解码实例。这种方法允许在解码阶段在专用 GPU 上积累更大的批处理大小，而不会牺牲 TPOT。
• 并行方案
  • 解耦后，解码的批量大小可能会受到 GPU 内存容量的限制，因为有必要维护所有活动请求的 KV 缓存。使用模型并行性扩展解码实例或利用 LLM KV 缓存的高级内存管理技术，例如 Paged-Attention [32] 和 GQA [10]，可以将解码批处理大小进一步扩展到接近计算绑定的大小。
  • 作者研究了图 5 中大批量条件下不同并行度下的延迟和吞吐量如何变化：
    • 运算中并行性减少了延迟，但收益递减，这是由通信和分区后利用率降低引起的。
    • 运算间并行性几乎可以线性地扩展吞吐量。
    • 因此，当 TPOT SLO 严格时，运算中并行性对于减少 TPOT 以满足延迟目标至关重要。除此之外，运算间并行性更可取，以线性方式提高吞吐量。

• 值得注意的是，当模型可以适应单个 GPU 的内存时，除了预填充和解码实例的模型并行性之外，副本也是一个有竞争力的选项，可以线性扩展系统的速率容量。它还可以减少排队延迟。
  
  

3.3 实际问题

• 作者制定了为每个阶段选择批处理和并行的基本原则。在本节中，作者将讨论并解决在实际部署分解式预填充和解码阶段时遇到的几个挑战。
• 可变预填充长度
  • §3 在请求之间假定了统一的提示长度。在实际部署中，根据 LLM 应用程序的不同，请求的长度是不一致的。
  • 不一致性可能会导致应用操作间并行性的预填充实例出现管道气泡，因为不同长度的请求的管道阶段的执行时间会有所不同。这导致与使用 M/D/1 队列模型指示的结论略有偏差。为了解决这个问题，§4 开发了基于工作负载搜索并行性的算法，并采用调度来最小化气泡 （§4.3）。
• 通信开销
  • 将 KV 缓存从预填充实例传输到解码实例会产生显著的开销。
  • 例如，OPT-66B 上单个 512 token请求的 KV 缓存大小约为 1.13GB。假设平均到达速率为 10 rps，作者需要每秒传输 11.3GB 数据，或相当于 90Gbps 的带宽才能使开销不可见。
  • 虽然许多用于 LLM 的现代 GPU 集群都配备了 InfiniBand（例如 800 Gbps），但在跨节点带宽有限的情况下，DistServe 依赖于通常可用的节点内 NVLINK，其中 A100 GPU 之间的峰值带宽为 600 GB/s，再次使传输开销可以忽略不计。
  • 但是，此要求对预填充和解码实例的放置施加了额外的限制，作者将在下一节中考虑这些限制。
    
    

4 方法

• 作者构建 DistServe 来解决上述挑战。根据模型、工作负载特征、延迟要求和 SLO 实现目标，DistServe 将确定
  • （a） 预填充和解码实例的并行策略
  • （b） 要部署的每种实例类型的数量
  • （c） 如何将它们放置在物理集群上。作者将该解决方案称为 placement。
  • 作者的目标是找到一个能最大化每 GPU 好吞吐量的 Placement。
    
    

4.1 高节点关联性集群的放置

• 在配备 Infiniband 的高节点亲和性集群上，KV 缓存跨节点传输开销可以忽略不计，DistServe 可以不受限制地跨任意两个节点部署预填充和解码实例。作者针对此类场景提出了一种两级放置算法：
  • 首先，作者分别优化预填充和解码实例的并行配置，以实现阶段级最佳每 GPU 吞吐量
  • 然后，作者使用 Replication 来匹配整体流量速率。
• 问题
  • 鉴于工作负载具有不同的输入、输出长度和不规则的到达模式，因此为单个实例类型（例如预填充实例）找到最佳并行配置仍然具有挑战性，因为缺乏简单的分析公式来计算 SLO 实现度。
  • 因此，作者求助于构建一个模拟器来估计 SLO 实现情况，假设事先了解工作负载的到达过程以及输入和输出长度分布。虽然短期间隔无法预测，但较长时间尺度（例如，数小时或数天）的工作量模式通常是可预测的。
  • DistServe 从历史请求跟踪中拟合分配，并从分配中重新采样新跟踪作为模拟器的输入工作负载，以计算 SLO 实现。接下来，DistServe 只需枚举放置，并通过二叉搜索和模拟试验找到满足 SLO 实现目标的最大速率。
• 算法一：高节点亲和性放置算法

• 模拟器构建
  • 为了构建一个准确的模拟器，作者分别分析了预填充和解码阶段的 FLOPs 和内存访问次数，并使用延迟模型来估计推理执行时间。
  • 由于 DNN 工作负载 [23， 33] 具有高度的可预测性，该模拟器与实际分析结果非常一致，已在 §6.4 中得到验证。
    
    

4.2 低节点关联性集群的放置

• 对于大型型号，例如具有 175B 参数 ，作者甚至可能无法在 8 个 GPU 节点中托管一对预填充和解码实例。作者将其作为额外的放置约束，并将其与模型并行性进行协同优化，如算法 2 所示。
• 关键的见解是，KV 缓存传输仅发生在预填充和解码实例的相应层之间。利用操作间并行性，作者将各层分组为多个阶段，并将每个实例划分为多个段，称为实例段，每个段维护一个特定的操作间阶段。
  • 通过将同一阶段的预填充和解码段共置在单个节点中，作者强制仅通过 NVLINK 传输中间状态。
  • 在节点内部，作者为同一实例的段设置相同的并行度和资源分配。鉴于每个节点的 GPU 的典型限制（通常为 8 个），作者可以枚举一个节点内可能的配置，并使用模拟器来确定产生最佳吞吐量的配置。
• 如算法 2 中所述
  • 作者首先枚举互作并行度，以获取所有可能的实例 Segment。对于每个 Segment，作者通过调用 get_intra_node_configs 来获得所有可能的节点内并行配置。
  • 然后作者使用仿真找到最优的 A 并对其进行复制以满足目标流量速率。

4.3 在线调度

• DistServe 的运行时架构如图 6 所示
  • DistServe 使用简单的 FCFS 调度策略运行。所有传入请求都到达一个集中式控制器，然后被分派到队列最短的预填充实例进行预填充处理，然后分派到负载最少的解码实例进行解码步骤。

• 减少流水线气泡
  • 为了缓解由非统一提示长度 （§3.3） 引起的管道气泡，作者以平衡管道中所有批次的执行时间的方式安排请求。
  • 这是通过“对于 Prefill 和 Decoding 实例，Batch 中新 Token 的数量是 Batch 实际执行时间的可靠指标。”的观察来实现的。
• 对抗繁忙
  • 工作负载的突发性可能会导致大量 KV 缓存从预填充实例传输到解码实例，从而冒着解码实例内存过载的风险。
  • 为了规避这种情况，DistServe 采用“pull”方法进行 KV 缓存传输，而不是“push”方法——解码实例根据需要从预填充实例中获取 KV 缓存，使用预填充实例的 GPU 内存作为排队缓冲区。
  • 这样，预填充实例只需通过在处理提示后将 KV Cache 保留在 GPU 内存中，即可继续处理其他预填充作业。
  • 因此，每种类型的实例都按照自己的节奏运行，无需复杂的协调。
    
    
• 重新规划
  • DistServe 中的资源和并行度计划针对特定的工作负载模式进行了优化，如果工作负载模式随时间变化，该模式可能会变得次优。
  • DistServe 实施定期重新规划。工作负载分析器监控关键参数，例如请求的平均输入和输出长度、平均到达率等。如果检测到明显的模式偏移，DistServe 将根据最近的历史数据触发重新运行放置算法。
  • 开销：所提出的算法在几秒钟内运行 （§6.5），重新加载 LLM 权重可以在几分钟内完成 – 远短于实际工作负载变化发生的小时刻度。
• 抢占和容错
  • DistServe 没有实现抢占 [26] 和容错 [58] 等高级运行时策略，这些策略是对解聚的补充。
  • 尽管如此，作者还是讨论了它们如何适应 DistServe。（讨论略）
    
    

5 实现

• DistServe 是一个适用于 LLM 的端到端分布式服务系统，具有放置算法模块、RESTful API 前端、编排层和并行执行引擎。
  • 算法模块、前端和编排层使用 6.5K 行 Python 代码实现。
  • 并行执行引擎使用 8.1K 行C++/CUDA 代码。
• 各模块
  • placement algorithm 模块实现了 §4 中提到的算法和模拟器，它给出了特定模型和集群设置的放置决定 。
  • 前端支持与 OpenAI API 兼容的接口，客户端可以在其中指定采样参数，例如最大输出长度和温度。
  • 编排层管理预填和解码实例，负责请求调度、KV 缓存传输和结果下发。它利用 NCCL [6] 进行跨节点 GPU 通信，利用异步 CudaMemcpy 进行节点内通信，从而避免在传输过程中阻塞 GPU 计算。
  • 每个实例都由一个并行执行引擎提供支持，该引擎使用 Ray [35] actor 来实现 GPU worker，这些 GPU worker 以分布式方式执行 LLM 推理和管理 KV Cache。它集成了许多最新的 LLM 优化，如连续批处理 [54]、FlashAttention [20]、PagedAttention [32]。
    
    

6 评估

• 在本节中，作者在从 13B 到 175B 的不同大小的 LLM 和各种应用程序数据集（包括聊天机器人、代码完成和摘要）下评估了 DistServe。
  
  

6.1 实验设置

• 集群测试平台：在具有 4 个节点和 32 个 GPU 的集群上部署 DistServe。每个节点都有 8 个 NVIDIA SXM A100 80GB GPU 与 NVLINK 连接。跨节点带宽为 25Gbps。

• 模型和工作负载设置：OPT [56]模型系列，较新的 GPT 模型系列正在采用 GQA [10] 和 MQA [44] 等高效内存注意力机制。DistServe 在这些模型上将显示更好的性能，因为由于 KV 缓存大小的减小，传输开销较低。如表 1 所示，作者选择三个典型的 LLM 应用程序，并根据其服务目标根据经验设置 SLO。

  • Chatbot
  • Code completion
  • Summarization

• 测量指标：SLO 实现
• 基线：vLLM、DeepSpeed-MⅡ

6.2 端到端实验

• 作者将 DistServe 的端到端性能与真实应用程序数据集上的基线进行比较。
• Chatbot
  • 作者评估了 DistServe 在所有三种 OPT 模型的聊天机器人应用程序上的性能。

• Code completion 和 Summarization

6.3 延迟拆解

• 为了详细了解 DistServe 的性能，作者对 DistServe 中的请求进行了延迟细分。
  • 作者将 DistServe 中请求的处理生命周期分为五个阶段：预填队列、预填执行、传输、解码队列和解码执行。
• 如图
  • 左图：使用 DistServe 在 ShareGPT 数据集上提供 OPT-175B 时的延迟细分
  • 右图：三种 OPT 模型的 KV Cache 传输时间的 CDF 函数。

6.5 消融实验

• 作者研究了 DistServe 中两个关键创新的有效性：分解和位置搜索算法。
• 模拟器精度：作者在表 2 中研究了模拟器的准确性。对于“vLLM”和“DistServe-Low”，作者比较了模拟器和测试台上在不同速率下实际运行报告的 SLO 满足率。在所有情况下，误差都小于 2%，验证了作者模拟器的准确性。

• 结果

6.5 算法运行时间

• 图 12 显示了随着提供给单个实例的 GPU 数量 （N × M） 的增加，Alg. 1 （DistServe-Low） 和 Alg. 2 （DistServe-High） 在具有 96 个内核的 AWS m5d.metal 实例上的运行时间。
  • 结果， DistServe 可以很好地随 GPU 的数量扩展，并且与模型大小无关。
  • 随着 GPU 数量的增加，“Dist-Low” 的执行时间会比“Dist-High”的执行时间长。这是因为在 “Dist-High” 中搜索预填充和解码实例的并行策略是独立的，并且可以并行化。但对于 “Dist-Low”，由于部署的额外限制，作者需要列举预填充和解码实例所有可能的节点内并行组合。

7 讨论

8 相关工作

9 总结

作者介绍了 DistServe，这是一种新的 LLM 服务架构，可分解预填充和解码计算。DistServe 最大限度地提高了每 GPU 的吞吐量，即根据预置的每个 GPU 的 SLO 实现目标可以提供的最大请求速率，因此每个 LLM 查询的成本降低了 7.4×同时保证 SLO 的满意度。作者的研究结果证实，随着延迟成为 LLM 服务越来越重要的指标，预填充和解码解聚是承诺提高性能和服务质量保证的重要策略。