DistServe：为大语言模型服务进行prefill和decode的分解
DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving
这篇论文是北大金鑫组和阶跃星辰公司，加州大学圣地亚哥分校合作的，已经被OSDI‘24接收。主要思路是将一个推理请求的prefill和decoding分解进行batch，从而最优化goodput。
背景
处理一个端到端LLM请求甚至比百度（普通搜索引擎）慢。
大模型推理分为两个阶段prefill 和 decode。大模型相关
prefill的成果： time-to-first-token (TTFT)
Decode 的成果：time-per-output-token (TPOT)
不同的应用程序对每个指标提出了不同的要求。例如，实时聊天机器人优先考虑低TTFT来快速响应，而TPOT仅在比人类阅读速度（即250字/分钟）快时才重要。【投放大量资源给prefill】
相反，文档摘要强调低TPOT，以加快摘要生成速度。【投放大量资源给decode】
绿色的长条是prefill; 蓝色的短条是decode。
SLI： 服务质量指标（service level indicator). 大部分服务都将请求延迟,处理请求所消耗的时间——作为一个关键SLI
SLO：服务质量目标,SLI小于一个值，比如用户请求返回结果要小于1秒。
吞吐量衡量的是所有用户和请求中完成的请求或词元的数量，因此忽略了这些时延要求。我们引入了有效吞吐量（goodput），即每秒完成请求的遵守SLO（TTFT和TPOT要求）的数量，并展示了它是一个更优指标，因为它捕获了在SLO达成下的请求吞吐量——因此既考虑了成本又考虑了服务质量。
有效吞吐量（P90 TTFT < 200ms和P90 TPOT < 50ms）= 当至少90%的请求同时满足TTFT < 200ms和TPOT < 50ms时，系统可以承受的每秒最大请求速率。
rps：每秒请求 request per second
图1:将prefill和decode两个阶段拆开，会让响应速度变快。
有效吞吐量(合并) = min(3,1.6) = 1.6 RPS（每GPU）
拆开 Goodput(2P1D) = min(5.6 x 2, 10) = 10 reqs/s / 3 GPUs ≈ 3.3 reqs/s (per GPU)
每个GPU提升了两倍的有效吞吐量！
该实验表明，在没有使用任何并行策略的情况下，这种简单的解耦能产生2倍的有效吞吐量。
M/D/1 队列
一个最简单的队列模型成为M/D/1队列。
M表明到达服从Markov过程，在这个文本中，泊松过程到达服从特定的概率分布，此分布以准确表明了许多真实世界的模拟；
D表明离开是确定的并以固定的速度发生；
1表明只有一台服务器。
解决的问题/问题特点
计算中的预填充和解码阶段各具独特属性。预填充对计算资源的需求量极大，哪怕是小批次的预填充任务，甚至单个较长的预填充任务，都足以使GPU的计算能力达到饱和。与此相对，解码任务则需要更大的批大小才能充分利用计算资源，并且更容易受到GPU内存带宽限制的影响。
如果我只有一块GPU，我进行批处理。然后如果有prefill请求过来，现在的decode很容易就要延迟，就不满足TPOT了。
本来只有decode的机器，加入了一个prefill的请求，request的长度是128和1024，然后会和decode抢资源，这样延时肯定会高。
那我一般怎么满足TPOT呢，由于这种干扰，为同时满足TTFT和TPOT的SLO，系统必须过度配置资源以满足时延目标，尤其是在SLO要求严格的情况下。加钱加gpu
此外，由于合并，预填充和解码计算的并行策略（张量、流水线或数据并行）本质上是耦合的。
如前所述，由于它们的计算模式和时延目标截然不同，预填充和解码阶段的最优并行策略通常也不同。
例如，当实时吞吐量(TTFT)要求严格而总吞吐量(TPOT)要求宽松时，预填充阶段更倾向于使用张量并行(TP)来满足严格的时延目标，而解码阶段则更倾向于数据或流水线并行以提高吞吐量。
解决上述问题，最直接的想法，把prefill和decode放到不同的GPU上。
解耦造成了在预填充和解码GPU之间传输中间状态（即KV Cache）的成本。在LLM推理中，KV Cache看似是一个巨大的内存开销，而在GPU之间传输KV Cache则像是一种瓶颈。然而，我们展示的情况恰恰相反：通过适当的放置（placement），KV Cache传输开销可以有效地最小化，甚至低于一个解码步数的时间，这要归功于现在的高速网络，如NVLink和PCI-e 5.0
总结一下：
1.满足约束：TTFT 和 TPOT 施加激进的服务级别目标 (SLO)
2.目标：有效吞吐量大一点
3.格外要求：不要加钱，不要加很多gpu。
创新点/解决方案
在摘要中提到的贡献
1.分析不分离不行，提出prefill和decode分离
2.自动判别怎么分离，2p1d还是其他的分配方案
3.用真实世界的工作负载进行全面的评估
三、权衡分析
3.1 prefill实例的分析
在相同的批处理大小下，不同的输出文本长度，会对应不同的吞吐量。
增大批处理大小，一般会让prefill的吞吐量增大，但是如果batch size超过一个阈值，那么增量就不明显了。批处理大小1->30很明显，从30->100不明显，因为gpu也没那么强。
上面是实验结果，在低速率的情况下，橙色的好；在高速率的情况下，蓝色的好。
右边可以看到随着K的减小，橙色越来越浅，耗时越来越长。
下面是作者用排队论的思想进行建模，作者写这个的意义是，我这个实际的实验结果，和排队论的理论结果是吻合的。
K：对于算子内并行性，我们引入了一个加速系数K，其中1 < K < 2，反映了算子内并行性的高通信开销引起的不完美加速。
D：由于预填充长度均匀，每个请求的执行时间都记为D，保持不变。
R：假设泊松到达率为R，使用条件为RD < 1，平均TTFT（Avg_T T F T）可以通过M/D/1队列[47]以接近形式建模：
对于算子间并行（流水线并行）inter-op
对于算子内并行（数据并行，张量并行）intra-op
3.2 decode实例的分析
随着加gpu，decode阶段的表现：
如果采用inter-op，吞吐量会表现很好
如果采用intra-op, 延迟会有明显降低，这个指标表现很好
3.3 实际的问题
流水线并行处理，在每个请求token长度不一样的时候，会产生大量气泡。
KV-cache的转移开销，OPT-66B 上单个 512 个令牌请求的 KV 缓存大小约为 1.13GB。 假设平均到达率为每秒 10 个请求，我们需要传输 1.13 × 10 = 11.3 GB 数据。常用的节点内 NVLINK，其中 A100 GPU 之间的峰值带宽为 600 GB/ s，但是所有的GPU都有NVLINK吗
四、方法
给定模型、工作负载特征、延迟要求和 SLO 达到目标，DistServe 将确定 (a) 预填充和解码实例的并行策略，(b) 要部署的每种实例类型的数量，以及 （c) 如何部署 将它们放置到物理集群上。 我们将该解决方案称为展示位置。 我们的目标是找到一个能够最大化每 GPU 吞吐量的布局。
在第四节中，我们首先介绍两种放置算法：一种适用于具有高速跨节点网络的集群（第 4.1 节），另一种适用于缺乏此类基础设施的环境（第 4.2 节）； 后者引入了额外的限制。 然后，我们开发适应现实工作负载细微差别的在线调度优化（第 4.3 节）。
4.3节：
对于所有的请求，DistServe 采用简单的 FCFS 调度策略运行。然后做了三个优化：
1.减少流水线气泡：prefill处理长度为Lm=6的就gpu满了；以前是遇到一个3的，处理一下，遇到一个7的处理一下。那我可以让他批处理两个长度为3的，然后碰到长度为7的单独处理。
2.docode存在内存风险：之前prefill在请求很多处理很快，一下子扔给decode很多kv-cache，塞爆炸了；现在采用decode从prefill拉
3.定期重新规划，根据观察到的最新参数，过一段时间就动态调整；比如之前是2P2D，后面变成3P1D
4.FCFS的弊端，以及没有容错性。D严重依赖于P，毕竟P没结果D咋做。
实验
DistServe是一个用于LLM的端到端分布式服务系统，具有放置算法模块、RESTful API前端、编排层和并行执行引擎。
真实的模型和数据集。
实验设置
4个节点，32个GPU，每个节点的8个A100-GPU用NVLINK连接。
有不同类型的任务，聊天机器人，代码完成，生成摘要。设置不同的TTFT和TPOT。
vLLM：vLLM是一种在学术界和工业界广泛使用的具有代表性的LLM服务系统。它支持连续批处理以提高吞吐量，支持分页注意力[32]以减少KV缓存分配期间的内存碎片。然而，它将预填充和解码计算放在一起，以最大限度地提高整体系统吞吐量，并努力经济高效地满足延迟要求。
DeepSpeed-MII支持分块预填充，通过将长提示分解为更小的块，并与短提示组合以精确填充目标令牌预算。它减轻但不能消除由长预填充作业引起的预填充解码干扰
实验结果贴图
图8-聊天机器人
随着SLO Scale的减小，延迟要求更加严格。
图9-代码补全和生成摘要
传输时间很短
表2：DistServe性能比VLLM好，并且模拟器模拟的很准
图11说明：VLLM+和VLLM性能一样，蓝色（4.1）比橙色（4.2）略好，因为蓝色的网络配置更好。
读后感
说实话，就是做了一个prefill和decode分解。
分解看这个样子会带来性能提升；考虑一下网络开销。不是所有的GPU都有NVLINK？如果网络真的很快，serverlessLLM就不会选择传tokens重新进行prefill了，直接传KV-cache。还是说不同的业务场景（比如迁移）各有侧重。
prefill和decode构成的是一个完善的推理过程，从输入的token到输出的token；而我们的工作还是要把他作为一个 数据集/模型 的特点，扯到调度上。
参考：
https://blog.csdn.net/OneFlow_Official/article/details/138940834
