1. 论文基本信息

1.1. 标题

NanoFlow：面向最优大语言模型服务吞吐量的路径 (NanoFlow: Towards Optimal Large Language Model Serving Throughput)

1.2. 作者

该论文由华盛顿大学 (University of Washington) 的多位研究人员，以及清华大学 (Tsinghua University) 和加州大学伯克利分校 (University of California, Berkeley) 的合作者共同完成。主要作者包括 Kan Zhu、Yufei Gao、Yilong Zhao 等。

1.3. 发表期刊/会议

该论文发表于 arXiv 预印本平台。考虑到其研究内容的重要性及作者团队的学术背景，预计将在顶级计算机系统或机器学习会议上发表。

1.4. 发表年份

2024年

1.5. 摘要

大型语言模型 (LLM) 服务的巨大需求推动了对全球规模服务系统的发展，其中数万个图形处理器 (GPU) 持续为数亿用户提供服务。因此，吞吐量 (throughput) 已成为决定服务系统性能的关键指标。由于模型规模庞大和自注意力机制 (self-attention) 的内存密集特性，LLM 服务通常被认为是内存受限 (memory-bound)。然而，通过详细分析，本文揭示，尽管存在内存密集型组件，但对于大多数常见的工作负载和LLM而言，端到端 (end-to-end) 的LLM服务实际上是计算受限 (compute-bound) 的。遗憾的是，大多数现有服务引擎未能实现最佳计算利用率 (compute utilization)，原因在于构成LLM服务的异构操作——计算、内存、网络——在单个设备内部是顺序执行的。

本文提出了 NanoFlow，一个新颖的服务框架，它利用设备内并行 (intra-device parallelism)，在单个设备内重叠 (overlap) 异构资源的使用。NanoFlow 将输入拆分为更小的纳米批次 (nano-batches)，并复制操作以独立处理每个部分，从而实现重叠。NanoFlow 自动识别纳米批次的数量、大小、顺序和 GPU 资源分配，以最小化执行时间，同时考虑并发操作的干扰 (interference)。本文在 LLaMA-2-70B、Mixtral 8x7B、LLaMA-3-8B 等流行模型上评估了 NanoFlow 的端到端服务吞吐量。在实际工作负载下，NanoFlow 比最先进的服务系统提供了 1.91 倍的吞吐量提升，在流行模型上达到了最佳吞吐量的 50% 到 72%。

1.6. 原文链接

原文链接: https://arxiv.org/abs/2408.12757 PDF 链接: https://arxiv.org/pdf/2408.12757v2.pdf

2. 整体概括

2.1. 研究背景与动机

当前，基于 Transformer 架构的 大型语言模型 (Large Language Models, LLMs)，如 ChatGPT、GPT-4 等，已成为聊天机器人、搜索引擎和办公软件等应用的核心驱动力。这些 LLM 的广泛应用导致了对行星级服务系统 (planet-scale serving systems) 的巨大需求，这些系统需要数万个 GPU 持续为数亿用户提供服务。在这种背景下，如何最大限度地利用有限的硬件资源，特别是 GPU，以满足海量用户请求，成为了一个至关重要的问题。其中，吞吐量 (throughput)，即每秒处理的令牌 (tokens) 数量，是衡量 LLM 服务系统性能的关键指标，直接影响着服务成本。

传统观点认为，LLM 服务由于其巨大的模型规模（例如 GPT-3 拥有 1750 亿参数，需要多个 A100 GPU 存储权重）以及 自注意力机制 (self-attention mechanism) 对内存的密集需求（KV-cache 的大小会随上下文长度 context length 的增加而呈二次方增长，甚至超过模型权重本身），因此通常被认为是内存受限 (memory-bound) 的。这意味着系统的瓶颈在于内存带宽 (memory bandwidth) 或容量。

然而，本文的作者通过深入分析发现，这一传统假设并不完全成立。尽管 自注意力机制 (self-attention mechanism) 确实是内存密集型的，但从端到端 (end-to-end) 的角度来看，对于大多数常见的工作负载和 LLM，整个服务过程实际上是计算受限 (compute-bound) 的。这意味着 GPU 的计算能力，而非内存带宽，成为了系统性能的瓶颈。

现有的 LLM 服务引擎在实践中未能充分利用 GPU 的计算资源。核心问题在于，构成 LLM 服务的各种异构操作——包括计算密集型 (compute-bound) 操作（如矩阵乘法 GEMMs）、内存密集型 (memory-bound) 操作（如 KV-cache 访问）和网络密集型 (network-bound) 操作（如并行通信）——在单个 GPU 设备内部是顺序执行的。这种顺序执行导致了大量的 管道空闲 (pipeline bubbles)，即在某个操作执行时，其他资源（如计算单元、内存控制器或网络接口）处于空闲状态，从而导致整体 计算利用率 (compute utilization) 偏低。

因此，论文的动机在于解决 LLM 服务中存在的 计算利用率 (compute utilization) 低下的问题，打破异构操作顺序执行的限制，通过 设备内并行 (intra-device parallelism) 的方式，在单个 GPU 内部实现这些异构操作的重叠执行，从而最大限度地提升 LLM 服务的吞吐量。

2.2. 核心贡献/主要发现

本文的核心贡献可以总结为以下几点：

1. 重新定义 LLM 服务瓶颈： 论文通过详细的分析和实证验证，推翻了 LLM 服务通常是内存受限 (memory-bound) 的传统假设，明确指出对于大多数常见的工作负载和 LLM，端到端服务是计算受限 (compute-bound) 的。这为后续的优化指明了方向。

2. 提出 NanoFlow 框架： 引入了一个新颖的 LLM 服务框架 NanoFlow，其核心思想是利用 设备内并行 (intra-device parallelism)，通过将输入批次拆分为更小的 纳米批次 (nano-batches)，并重叠执行这些 纳米批次 (nano-batches) 上的异构操作，从而提高 GPU 资源的利用率。

3. 设计 自动化管道搜索 (auto-search) 引擎： NanoFlow 包含一个 自动化管道搜索 (auto-search) 引擎，该引擎能够自动识别 纳米批次 (nano-batches) 的数量、大小、执行顺序以及 GPU 资源分配，以最小化执行时间。该引擎通过两阶段逼近法，在考虑并发操作干扰 (interference) 的情况下，有效探索了巨大的搜索空间。

4. 实现高效的 LLM 服务运行时： NanoFlow 提供了一个端到端 LLM 服务运行时系统，用于高效地执行优化后的 纳米批次 (nano-batches) 管道。这包括异步调度 (asynchronous scheduling)、批次形成 (batch formation) 和 KV-cache 管理 (KV-cache management)（如 SSD 卸载）。

5. 显著的性能提升： 在 LLaMA-2-70B、Mixtral 8x7B 等流行模型和实际工作负载下，NanoFlow 相较于 最先进 (state-of-the-art) 的服务系统（如 vLLM、DeepSpeed-FastGen 和 TensorRT-LLM）实现了平均 1.91 倍的吞吐量提升，达到了理论最优吞吐量的 50% 到 72%。在其他模型上，平均吞吐量增益达到 2.66 倍。

   这些发现和贡献共同为 LLM 服务系统提供了一个新的优化范式，即从关注内存优化转向更精细化的 设备内并行 (intra-device parallelism) 计算资源管理，从而显著提升了 LLM 服务的效率和成本效益。

3. 预备知识与相关工作

3.1. 基础概念

为了更好地理解 NanoFlow，我们需要了解 LLM 推理过程、其中的关键操作类型以及当前 LLM 服务中常用的并行化技术。

3.1.1. LLM 推理工作流

现代 LLM，如 GPT-4、LLaMA 和 Mistral，大多基于 仅解码器 (decoder-only) 的 Transformer 架构。其推理过程通常分为两个阶段：

• 预填充阶段 (Prefill Phase)： 处理用户的全部输入提示 (input prompt)。例如，用户输入一个长问题，这个阶段会一次性处理这个问题中的所有令牌。这个阶段的主要任务是计算所有输入令牌的隐藏状态，并填充 KV-cache。

• 解码阶段 (Decode Phase)： 逐个生成输出令牌。在预填充阶段结束后，模型会进入解码阶段，每次生成一个新令牌，并将其添加到 KV-cache 中，然后基于新的 KV-cache 和上一个生成的令牌继续生成下一个令牌，直到生成结束令牌 EOS token 或达到最大生成长度。

  这两种阶段都使用相似的推理工作流，如图1所示。当接收到推理请求后，输入会经过相同的解码器层 (decoder layers) 来生成后续令牌。

  该图像是示意图，展示了在大语言模型（LLM）服务中，预填充请求和解码请求的处理流程。图中标出了不同操作，包括注意力操作、计算绑定、内存绑定和网络绑定操作，分别用黄色、绿色和蓝色区域表示。可见，图示详细地展示了各个组件的运作流程及其相互关系，为理解NanoFlow框架在优化LLM服务中的作用提供了直观参考。

描述: 该图像是示意图，展示了在大语言模型（LLM）服务中，预填充请求和解码请求的处理流程。图中标出了不同操作，包括注意力操作、计算绑定、内存绑定和网络绑定操作，分别用黄色、绿色和蓝色区域表示。可见，图示详细地展示了各个组件的运作流程及其相互关系，为理解NanoFlow框架在优化LLM服务中的作用提供了直观参考。 来源: 1.jpg

在一个解码器层中，关键操作包括：

• 注意力阶段 (Attention Stage)：

  1. 输入与权重矩阵 $W_Q$, $W_K$, $W_V$ 相乘，生成查询 (Query, $Q$)、键 (Key, $K$) 和值 (Value, $V$)。
  2. Key 和 Value 会被连接到现有的 KV-cache 中。
  3. Query 与现有 Keys 相乘并归一化，以评估当前令牌与所有先前令牌之间的相似度。
  4. 这种相似度用于计算 Value 的加权平均值，聚合上下文信息。
  5. 结果通过线性变换 $W_O$ 进行 O-投影 (O-projection)，然后进行层归一化操作 (layer normalization)。 为了帮助初学者理解，这里补充 自注意力机制 (self-attention mechanism) 的核心计算公式： $$\mathrm{Attention}(Q, K, V) = \mathrm{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right)V$$ 其中：
  • $Q$ (Query)、$K$ (Key)、$V$ (Value) 分别是查询、键、值矩阵，它们通过输入与模型权重 $W_Q, W_K, W_V$ 线性投影得到。
  • $Q K^T$ 计算查询与键之间的相似度。
  • $\sqrt{d_k}$ 是一个缩放因子，用于防止点积结果过大，其中 $d_k$ 是键向量的维度。
  • $\mathrm{softmax}$ 函数将相似度转换为概率分布。
  • Value 矩阵与这些概率分布相乘，得到加权平均值，即注意力输出。
  • $\mathrm{Attention}(Q, K, V)$ 的输出再经过 $W_O$ 进行 O-投影 (O-projection)。

• 前馈网络阶段 (Feed Forward Network Stage)：

  1. 激活值分别与 $W_{up}$ 和 $W_{gate}$ 相乘，生成 $o_u$ 和 $o_g$。
  2. $o_g$ 通过激活函数（例如 SiLU）处理。
  3. 结果与 $o_u$ 进行逐元素乘法。
  4. 最后应用 $W_{down}$ 作为 下投影 (Down-projection)，生成输出，作为下一个层的输入。

3.1.2. KV-cache

KV-cache (Key-Value cache) 是 LLM 推理中的一个关键优化技术。在 Transformer 的解码阶段，每个新生成的令牌都需要计算它与所有先前令牌之间的注意力。如果没有 KV-cache，每次生成新令牌时，都需要重新计算所有先前令牌的 Key 和 Value 向量，这会导致计算量和内存访问量的巨大浪费。KV-cache 通过缓存之前计算的 Key 和 Value 向量，使得在生成新令牌时只需计算当前令牌的 Key 和 Value，然后将其与缓存中的 Key 和 Value 连接起来，从而大大加速了解码过程。

3.1.3. 操作特性

根据推理过程中操作的特性，可以将其分为四类：

• 密集操作 (Dense operations)： 包括 KQV 生成 (Query, Key, Value)、O-投影 (O-projection)、Up、Gate 和 Down-投影 (Down-projection)。这些操作涉及激活值与模型权重的乘法，本质上是 通用矩阵乘法 (General Matrix Multiplications, GEMMs)。在预填充阶段，新请求的所有令牌形成一个大批次进行这些密集操作；在解码阶段，批处理解码 (batched decoding) 聚合所有解码请求的激活值进行密集操作。由于预填充和解码阶段共享权重矩阵，它们的激活值可以合并以进一步利用批处理效应 (batching effect)，从而分摊权重加载成本。因此，密集操作通常是计算受限 (compute-bound) 的。
• 注意力操作 (Attention operations)： Transformer 通过注意力机制捕获令牌关系。在预填充阶段，所有输入令牌同时处理，使其计算受限 (compute-bound)。然而，在解码阶段，模型每次迭代生成一个令牌，需要从 KV-cache 加载缓存的 $K$ 和 $V$ 向量，这使得解码注意力操作通常是内存受限 (memory-bound) 的。
• 网络操作 (Network operations)： 包括 AllGather (AG) 和 AllReduce (AR) 等集合通信操作。这些操作通常在多 GPU 或多节点并行场景下用于同步数据，它们是网络受限 (network-bound) 的，需要高带宽互连（如 NVLink）。
• 其他操作 (Other operations)： Transformer 架构中的其余操作，如层归一化 (layer norms)、位置嵌入 (position embeddings) 等，由于其运行时间相对于密集操作和注意力操作较短，被归为其他操作。

3.1.4. LLM 规模化服务

对于大型模型，单个 GPU 的内存容量和计算能力往往不足。因此，需要多个 GPU 提供足够的资源来高效地服务 LLM。现有工作主要利用以下几种并行范式：

• 张量并行 (Tensor Parallelism)： 将每个权重矩阵拆分到不同的 GPU 上。例如，一个大矩阵 $W$ 可以被拆分为 $W_1, W_2, \ldots, W_N$，分别存储在 $N$ 个 GPU 上。每次操作时，每个 GPU 只处理其存储的那部分权重。为了保持计算的正确性，在操作完成后，通常需要进行集合通信 (collective communications)（如 AllGather 或 AllReduce）来同步结果。这种方法可以扩展计算能力，避免权重复制。
• 流水线并行 (Pipeline Parallelism)： 将模型按层拆分为多个阶段 (stages)，每个 GPU 只负责模型的一部分层。与张量并行中所有设备处理相同批次数据不同，流水线并行中的设备处理不同 微批次 (micro-batches) 的数据，这些 微批次 (micro-batches) 沿着流水线依次通过各个阶段。 在实践中，这两种并行范式通常结合使用。例如，在节点内部，GPU 之间通常使用张量并行来实现更大的批次大小；而在节点之间，则使用流水线并行来进一步扩展集群规模。

3.2. 前人工作

LLM 服务优化是一个活跃的研究领域，许多工作从不同粒度上提升吞吐量。

• 请求级优化： Orca [53] 提出了请求级连续批处理 (request-level continuous batching)，在每次迭代中填充正在进行的批次，以最大化批次大小。DistServe [59] 和 Splitwise [32] 探索了阶段级调度 (phase-level scheduling)，将预填充和解码阶段分离到不同的集群中。DeepSpeed-FastGen [13] 和 Sarathi-Serve [2] 提出了分块预填充 (chunked prefill) 策略，将预填充请求拆分为多个小块，并与解码请求一起批处理，以提高整体利用率。
• 操作级优化： 其他工作通过优化特定操作来解决推理效率低下问题，例如 PagedAttention [17] 用于高效 KV-cache 管理，以及 量化 (quantization) 方法 [19, 44, 55] 减少模型大小和计算量。
• 设备内并行和操作级并行： Rammer [20] 探索了通过将操作重新映射到不同功能单元来实现 操作内并行 (intra-operation parallelism)。Unity [50] 研究了并行化和操作的等价代数转换的结合。ASPEN [30] 和 Welder [37] 通过构建和编译瓦片级数据图 (tile-level data graph) 打破了操作之间的界限。

3.3. 技术演进与差异化分析

LLM 服务技术经历了从简单推理到复杂优化调度的演变。早期关注点主要在如何将大型模型部署到有限硬件上（如模型并行化），随后转向如何提高 GPU 内存利用率（如 PagedAttention），以及如何通过批处理（如 continuous batching）来提高 GPU 的宏观利用率。

本文 NanoFlow 的工作处于这一技术演进的前沿，其核心区别和创新点在于：

• 对瓶颈的重新认知： 不同于以往普遍认为的内存受限，NanoFlow 明确指出并实证了当前 LLM 服务在大多数情况下是计算受限 (compute-bound) 的。这一认知转变是其所有后续优化的基础。

• 精细化的 设备内并行 (intra-device parallelism)： 现有的批处理和调度方法通常在请求级别或阶段级别进行，而 NanoFlow 将粒度下沉到 纳米批次 (nano-batches) 和操作级别。它首次提出了在单个设备内部，通过重叠具有不同资源需求的异构操作（计算密集型、内存密集型、网络密集型）来实现并行。这是与以往工作最显著的区别。

• 智能的 自动化管道搜索 (auto-search)： 针对 设备内并行 (intra-device parallelism) 带来的复杂调度问题，NanoFlow 引入了一个 自动化管道搜索 (auto-search) 引擎，能够自动优化 纳米批次 (nano-batches) 的参数和调度，并考虑了内核间的性能干扰。这避免了手动调优的巨大工作量，并能适应不同的模型和硬件。

• 通用性和适应性： NanoFlow 不依赖于特定的操作实现，而是通过 内核分析 (kernel profiling) 和 干扰建模 (interference modeling) 来适应新的操作实现。这使得它能够轻松采纳新的优化技术（如新的量化方法），并广泛应用于各种 LLM 模型和架构，包括 Mixture-of-Experts (MoE) 模型。

  简而言之，NanoFlow 通过将 LLM 服务优化的关注点从宏观的请求/阶段调度，提升到微观的 设备内异构操作并行 (intra-device heterogeneous operation parallelism)，并辅以智能自动化调度，从而有效解决了 GPU 计算资源利用率低下的核心问题。

4. 方法论

NanoFlow 的核心目标是最大化 LLM 服务吞吐量，通过利用 设备内并行 (intra-device parallelism) 来重叠 GPU 内部的异构操作。其设计包含两个关键组件：自动化管道搜索 (auto-search) 引擎和 LLM 服务运行时系统。

4.1. 自动化管道搜索 (Automated Pipeline Search)

自动化管道搜索 (auto-search) 引擎是 NanoFlow 的核心，它负责为 纳米批次 (nano-batches) 自动计算一个优化的执行管道。由于模型和硬件的多样性，决定每个 纳米操作 (nano-operation) 的资源分配、启动内核 (kernels) 和调度具有挑战性。NanoFlow 通过两阶段逼近法，利用 混合整数线性规划 (Mixed Integer Linear Programming, MILP) 来减少搜索空间，找到一个平衡效率和准确性的解决方案。

4.1.1. 内核分析与干扰建模 (Kernel Profiling and Interference Modeling)

理解不同操作的性能特性是 自动化管道搜索 (auto-search) 的基础。NanoFlow 首先对 GEMM 内核（用于计算密集型操作，如 KQV 生成）、GEMV 内核（用于内存密集型操作，如解码注意力 decode-attention）和网络内核（用于网络密集型操作，如 AllReduce (AR) 和 AllGather (AG)）进行分析。

1. 确定最大密集批次大小 (Determining the maximum dense batch size)： 给定特定的模型架构和用户输入统计数据，NanoFlow 首先计算能够适应 GPU 内存的最大密集批次大小 (dense batch size)。例如，对于服务 LLaMA-2 70B 的 $8 \times \mathrm { A100 }$ GPU，最大密集批次大小可能为 2048。这个值作为 auto-search 的输入，并设定了分析中形状的上限。

2. 分析无干扰内核 (Profiling interference-free kernels)： NanoFlow 接下来确定内核在无干扰 (interference-free) 情况下的执行时间，即每个操作单独使用 GPU 时的性能。NanoFlow 会对离散的输入批次大小（从 128 到最大密集批次大小，以 128 的倍数递增，因为 128 是 GEMM 平铺 (tiling) 的硬件友好形状）进行内核分析。它探索所有可能的内核实现，改变线程块 (thread blocks) 数量、warp 数量和瓦片大小 (tile size) 等参数，以找出执行时间最短的实现。分析结果是一个从（内核、批次大小）到其最佳实现的映射。

3. 分析带干扰内核 (Profiling kernels with interference)： 理想情况下，我们希望能够独立地为每个 纳米操作 (nano-operation) 分配单个 GPU 计算、内存和网络带宽的比例资源 (fractional allocation)。我们将这个比例称为 $R_{physical}$。然而，当两个或更多内核在设备上并行执行时，它们的运行速度会比单独运行时慢，这被称为内核干扰 (kernel interference)。内核干扰是由于内核竞争 GPU 硬件资源（如执行单元、缓存）造成的。由于 NVIDIA GPU 不提供对计算、内存和网络带宽的精确控制，我们无法直接控制 $R_{physical}$。

   NanoFlow 通过使用 GEMM 性能作为 $R_{physical}$ 的代理 $R$，并对成对内核干扰 (pairwise kernel interference) 进行建模。由于计算密集型操作占主导地位，并且 NanoFlow 的目标是优化计算，因此 $R$ 被定义为以 GEMM 为中心的方式。 具体来说，当一个计算内核 A 和另一个内核 B 重叠时，NanoFlow 通过测量实际性能来分析成对内核干扰模式。例如，如果重叠时内核 A 的性能是其单独运行时最佳性能的 40%，那么我们定义 $R_A = 0.4$。然后，我们假设重叠内核获得了剩余资源，因此设置 $R_B = 1 - R_A = 0.6$。 接着，通过测量当 $R_A$ 资源分配给计算内核 A 时，非计算内核 B 的性能损失来建模干扰。当 A 和 B 重叠时，我们将 A 和 B 的性能归一化到它们单独运行时达到峰值性能时的表现。我们将这个归一化值称为 $P$。对于计算内核 A，根据定义 $P_A$ 等价于 $R_A$；而 $P_B$ 则捕获了当 $R_A$ 资源分配给计算内核时，内存或网络的利用率。 直观地，这个过程建立了 $R$（计算利用率）与 $P$（内存或网络利用率）之间的兑换率。整体内核干扰模型可以捕获在一个表格中，例如表3，它将 $R$ 映射到每种内核类型的 $P$。

   分析不同内核组合之间的映射 $R$ 到 $P$ 仍然具有挑战性，因为可能的内核组合数量巨大。尽管每个操作可能只有几百个内核实现，但重叠内核的不同实现之间的组合会呈指数级扩展分析空间，导致数百万种可能的配置，使得穷举探索不可行。 NanoFlow 通过限制 GEMV 和网络内核的线程块数量在 8 到 128 之间（以 8 为步长），来减少分析空间，因为 128 个块足以使其性能饱和。它还排除了效率较低的 GEMM 内核，这些内核在使用更多线程块时执行时间更长。NanoFlow 专注于成对干扰分析——计算-内存和计算-网络——而不是同时检查三种内核类型，并假设成对干扰分析得到的 $R$ 到 $P$ 映射在重叠三种内核时仍然成立。

   以下是原文 Figure 5 的结果：

   该图像是图表，展示了不同模型在每个 GPU 每秒的 token 吞吐量。NanoFlow 在多个工作负载条件下的表现超过了所有基线模型，验证了其在 LLaMA-2-70B 模型上的高效性。最优吞吐量为 1857 tokens/s。

   描述: 该图像是图表，展示了GEMM和GEMV内核之间的干扰特性。x轴对应于独特的GEMM-GEMV实现对，y轴表示GEMM和GEMV内核的标准化性能 $P$。图中显示不同的优先级策略对性能的影响，特别是当GEMM被优先时，性能显著提升。 来源: 5.jpg

   图5展示了 NanoFlow 在 A100 GPU 上对 GEMM-GEMV 内核对的分析结果（经过简化后约 100 对），其中 GEMM 形状为 $(M, N, K) = (384, 4096, 4096)$，GEMV 批次大小 384，序列长度 1024。这些对按 GEMM 性能降序排列。例如，归一化性能 0.8 意味着内核的执行时间是其最快实现的 $1/0.8$ 倍。 对 GEMM 干扰更大但 GEMV 性能更差的对（图5中灰色部分）被丢弃。这个过程识别出在各种 GEMM-GEMV 性能权衡点上表现最佳的内核组合。 利用干扰分析结果，auto-search 生成一个资源映射表（表3）。该表量化了 GEMV 和网络内核的性能 ($P$) 作为资源利用率 ($R$) 的函数。例如，如图5中虚线红色所示，实现 0.3 的 GEMV 性能需要牺牲 0.2 的 GEMM 性能（从 1 到 0.8）。这意味着 0.2 的 GEMM 性能被交换为 0.3 的 GEMV 性能，表明 $R_{\mathrm{GEMV}} = 0.2$ 对应于 $P_{\mathrm{GEMV}} = 0.3$。 对评估的 LLM 模型中所有 GEMM 形状和 64 种批次大小组合的敏感性分析表明，$R$ 到 $P$ 的映射是一致的，标准差在平均值的 5% 以内。因此，表3可以用于后续 auto-search 分析中所有 GEMV 和网络内核实现的 $R$ 到 $P$ 映射。

   以下是原文 Table 3 的结果：

   Operations	Resource Utilization (R)
   	0	0.1	0.2	..	0.8	0.9	1
   GEMM (by definition)	0	0.1	0.2		0.8	0.9	1
   GEMV	0	0.2	0.3		0.85	0.95	1
   Network	0	0.3	0.5		0.9	1	1

   表3：GEMV 和网络内核在不同资源利用率 $R$ 下的性能 $P$。

4.1.2. 自动化搜索 (auto-search) 阶段I：管道结构搜索 (Pipeline Structure Search)

在第一阶段，auto-search 接收密集批次大小 (dense batch size)、操作依赖关系（由给定模型架构的 PyTorch 实现定义）以及无干扰内核的分析结果作为输入。然后，它使用 混合整数线性规划 (MILP) 输出每个 纳米操作 (nano-operation) 的数量、批次大小和执行顺序。阶段 I 不考虑内核之间的干扰，以简化问题，干扰问题由阶段 II 处理。MILP 问题受以下约束：

• 优化目标 (Optimization objective)： MILP 的主要目标是消除计算操作的 管道空闲 (pipeline bubbles)（如图4中标记为“WASTED”的部分），以最小化执行时间。

  以下是原文 Figure 4 的结果：

  该图像是示意图，展示了NanoFlow框架中不同层次的计算过程和资源分配情况。图中标注了各组件的响应性（R值），例如Prefill Attention和多个DecAttn部分，体现了如何优化大语言模型的处理效率。

  描述: 该图像是示意图，展示了在特定层次中，各个组件及其相互关系。图中包括了独立操作如 KQV、DecAttn、Prefill Attention 和多个“WASTED”部分，突出显示了资源的使用情况与潜在的浪费。箭头指示了数据流向和操作顺序，强调了各组件在执行过程中的角色。整体上，这幅图有助于理解 LLM 的计算流程及其效率问题。 来源: 4.jpg

• 纳米操作数量约束 (Constraints on the number of nano-operations)： 为了重叠资源，每个操作至少需要拆分为两个 纳米操作 (nano-operations)，每个操作在独立的 纳米批次 (nano-batch) 上运行。由于拆分为 纳米操作 (nano-operations) 会降低批处理效应 (batching effect)，因此 纳米操作 (nano-operations) 的数量应最小化。因此，auto-search 从将所有操作拆分为两个 纳米操作 (nano-operations) 开始搜索，并制定 MILP 问题以确定 纳米操作 (nano-operations) 的批次大小、执行时间和顺序。如果临时最佳解决方案存在计算空闲，auto-search 会增加空闲附近操作的 纳米操作 (nano-operations) 数量，以提高资源利用率，直到 MILP 无法产生更好的解决方案。

• 批次大小和执行时间约束 (Constraints on batch sizes and execution times)： auto-search 强制批次大小从 128 到密集批次大小中选择，并使用在 §4.1.1 中计算的给定批次大小的 纳米操作 (nano-operation) 的无干扰执行时间。

• 依赖关系约束 (Constraints on dependencies)： 纳米操作 (nano-operations) 的依赖关系由它们的父操作（存在于基线实现中，例如 PyTorch）和它们的输入批次决定。仅当它们的父操作具有依赖关系（例如，O-投影 (O-projection) 依赖于注意力操作）并且它们的输入批次相交（例如，范围 0-255 和 128-383）时，两个 纳米操作 (nano-operations) 才具有依赖关系。

• 重叠约束 (Constraints on overlapping)： 受相同资源（例如计算）约束的重叠内核对利用率没有帮助，因此 auto-search 限制管道仅重叠受不同资源约束的操作。

• 操作转换约束 (Constraints on operation transformations)： 某些网络集合操作具有性能特性和依赖关系不同的等效转换。例如，AllGather (AG) 可以通过不同的权重分区方法转换为 AllReduce (AR) [39, 57]。NanoFlow 探索所有这些替代转换，并搜索最短的管道设计。

  由于搜索空间巨大，搜索最佳管道可能需要数小时甚至数天。然而，通过优先搜索可行解决方案而不是寻找可证明的最佳解决方案，可以在大约 10 分钟内找到一个实用的管道。

4.1.3. 自动化搜索 (auto-search) 阶段II：优化管道 (Refining the Pipeline)

第一阶段导出的管道没有考虑内核干扰，这对于实际部署来说是不切实际的。在第二阶段，auto-search 通过考虑干扰导致的内核减速来优化此管道。此阶段制定了一个单独的 MILP 问题，其中 纳米操作 (nano-operations) 的数量、批次大小和排序约束保持不变（即第一阶段的输出）。auto-search 探索对单个 纳米操作 (nano-operations) 的各种资源利用率 ($R$) 分配，并使用在 §4.1.1 中推导的表3将 $R$ 映射到 $P$。特定的资源利用率 $R$ 直接对应于在 §4.1.1 中确定的内核实现。第二阶段的目标同样是最小化管道执行时间。

• GPU 资源利用率约束 (Constraints on GPU resource utilization)： 如 §4.1.1 中所述，并发内核的总 GPU 资源利用率 $R$ 应该竞争总共 1.0。因此，auto-search 强制任何给定时间 $R$ 的总和小于或等于 1.0。

• 执行时间约束 (Constrains on execution times)： 给定 纳米操作 (nano-operation) 的资源利用率 $R$，auto-search 使用 $D_{best} / P$ 计算操作的执行时间，其中 $D_{best}$ 表示无干扰情况下的最佳执行时间，$P$ 使用表3推导。

  auto-search 仅在模型架构或工作负载（输入长度、输出长度）发生显著变化时执行。与长时间的部署时间相比，搜索时间可以忽略不计。

4.1.4. 示例管道 (Example Pipelines)

• 70B 管道 (70B pipeline)： 作者将 auto-search 应用于 70B 规模的模型，包括 LLaMA-2 70B、LLaMA-3 70B、Qwen2.5-72B 和 Deepseek-67B。尽管这些模型之间存在细微差异（例如 LLaMA-3 70B 的词汇表更大，Deepseek-67B 的层数和隐藏维度不同，Qwen2.5-72B 引入了偏置），但这些调整并未显著改变性能特性，因此产生了相似的调度。 以下是原文 Figure 6 的结果：

  该图像是图表，展示了不同请求速率下的延迟比较，包括 vLLM、DeepSpeed-FastGen、TensorRT-LLM 和 NanoFlow 四种方法，其中 NanoFlow 的延迟在较高请求速率下保持更优表现。具体而言，y 轴表示标准化延迟（毫秒/令牌），x 轴表示每秒请求数（req/s）。

  描述: 该图像是示意图，展示了NanoFlow框架中不同层次的计算过程和资源分配情况。图中标注了各组件的响应性（R值），例如Prefill Attention和多个DecAttn部分，体现了如何优化大语言模型的处理效率。 来源: 6.jpg 图6展示了 LLaMA-2 70B 的 NanoFlow 生成管道示例。由于在解码层开始时（即 KQV 生成）计算、内存和网络三种资源重叠，auto-search 最终使用 4 个 纳米操作 (nano-operations) 来减少 管道空闲 (pipeline bubbles)。其中，解码注意力 decode attention 操作的资源利用率为 0.4（即减少 40% 的 GEMM 性能），并达到最大解码注意力性能的 80%。对于管道的其余部分，GEMM 操作被优先处理，仅使用两个 纳米操作 (nano-operations)。

• 8B 管道 (8B pipeline)： 8B 模型（例如 Llama3-8B）由于可以完全放入单个 GPU 中，因此不需要网络操作。auto-search 将所有操作拆分为两个 纳米操作 (nano-operations)，其中解码注意力 decode attention 与 Up Gate Down 投影重叠。

• MoE 管道 (MoE pipeline)： 与 70B 模型相比，MoE (Mixture-of-Experts) 模型具有不同的隐藏维度和层数。由于专家之间的不平衡，NanoFlow 对 MoE 使用 张量并行 (tensor parallelism)，其中 FFN (Feed-Forward Network) 使用 分组 GEMM (grouped-GEMM) 实现。FFN 还涉及额外的门控路由操作 (gate routing operation)。auto-search 对 MoE 模型的工作方式类似，并自动生成高效的管道。

4.2. NanoFlow 运行时 (NanoFlow Runtime)

NanoFlow 运行时系统负责执行 auto-search 生成的优化管道，主要包括异步调度 (asynchronous scheduling) 和 KV-cache 管理 (KV-cache management)。

4.2.1. 请求调度 (Request Scheduling)

1. 批次形成 (Batch formation)： NanoFlow 假设自动扩缩容 (auto-scaling)、工作负载平衡 (workload balancing) 和优先级感知路由 (priority-aware routing) 由外部控制平面管理。NanoFlow 实例假设有大量请求，并以相同的优先级处理每个请求。当请求不充足时，控制平面应减少 NanoFlow 实例的数量，以保持足够的每个实例批次大小。值得注意的是，虽然 $B_{dense}$（即 GEMM 的令牌批次大小）可达数千（例如，1 个预填充请求的 2048 个令牌和 256 个解码令牌），但这代表了预填充和解码令牌的组合。因此，请求批次大小（例如，1 个预填充请求和 256 个解码请求）通常在数百个级别，这在现实世界的大规模服务中很容易实现。 在形成批次时，NanoFlow 优先处理未完成的解码请求，并以令牌粒度对预填充请求进行分块，遵循 SarathiServe [3] 的方法，以精确填充预选的最佳性能密集批次的剩余容量。这有效地减少了尾延迟 (tail latency)，因为密集操作在每次迭代中以一致的批次大小执行。 最初，全局批次仅包含预填充请求（处于预填充阶段的请求）。当这些请求完成预填充阶段时，它们在批次内转换为解码请求，并引入新的预填充请求以维持固定的令牌批次大小。随着解码请求的增加，预填充令牌预算减少，导致预填充请求变慢。当解码请求开始完成时，这又释放了更多预填充令牌的空间，加速了预填充。因此，解码请求和预填充请求的数量将趋于稳定。 为了优化 GPU 内存使用并避免内存不足，NanoFlow 根据用户请求的状态预测未来的峰值内存使用。NanoFlow 跟踪每个请求的已解码令牌数，使用平均解码长度估计完成时间，并仅在预测内存使用量保持在 GPU 限制内时才预填充新请求。如果 GPU 内存不足，NanoFlow 会将请求卸载到 CPU，并在内存可用时重新加载，而无需重新计算。

2. 异步调度 (Asynchronous scheduling)： 批次形成，包括估计内存使用、调度新请求、终止已完成请求以及调整 PagedAttention [17] 的页表，在 CPU 侧会消耗不可忽略的时间。在大多数服务框架中，只有在 GPU 执行完一次迭代后，CPU 上的调度器才能检测到 EOS token，从批次中移除已完成的请求，并用新请求重新填充批次。然而，在此期间 GPU 处于未充分利用状态。为避免这种浪费，NanoFlow 在 GPU 执行的同时异步调度批次形成。在任何迭代 $i$ 中，NanoFlow 在当前迭代结束前形成下一迭代的批次。这意味着 NanoFlow 无法检测到在迭代 $i$ 生成的 EOS token。在启动迭代 $i+1$ 后，NanoFlow 形成迭代 $i+2$ 的批次，检测来自迭代 $i$ 的 EOS token，并移除已完成的请求。幸运的是，由于典型工作负载的平均解码长度超过 100（参见表4），一个额外解码令牌的开销可以忽略不计（<1%），这相对于隐藏批次形成开销的好处来说是值得的。

4.2.2. KV-cache 管理 (KV-cache Management)

为了高效服务多轮对话 (multi-round conversations) 应用，NanoFlow 将正在运行请求的 KV-cache 卸载到由主机 CPU 内存和 SSD 组成的层次化缓存 (hierarchical cache) 中，并在新一轮对话到来时加载先前一轮的 KV-cache。

1. 同步卸载 (Simultaneous offloading)： NanoFlow 不会等待请求完成，而是在每个 Transformer 层中 KQV 生成之后，将令牌的 KV-cache 直接卸载，然后再将其追加到 KV-cache 中。KQV 生成输出的 KV 向量自然是连续的，并且由于 NanoFlow 的密集批次保持稳定，卸载数据的大小在迭代之间是平衡的。因此，主机和 GPU 保存着相同一份正在进行的请求的 KV-cache 副本。为了最小化卸载开销，NanoFlow 在 FFN 中计算密集型操作期间执行设备到主机的复制——一个 GPU 发起的复制操作，它使用少量 GPU 资源。此外，NanoFlow 通过 NUMA 感知线程绑定 (NUMA-aware thread-binding) 减少了卸载时间。

2. 主机 KV-cache 管理 (Host KV-cache management)： NanoFlow 使用 最近最少使用 (Least Recently Used, LRU) 策略来管理 CPU 内存和 SSD 的层次化缓存。例如，当 CPU 达到内存限制时，KV-cache 会被逐出到 SSD；当请求的下一轮对话到来时，它会从 CPU 或 SSD 检索，以启动加载过程。

3. KV-cache 加载和分散 (KV-cache loading and scattering)： NanoFlow 使用 PagedAttention [17]，因此 KV-cache 的页面以碎片化的方式驻留在 GPU 内存中。为了避免复制到碎片化的 GPU 页面目的地，NanoFlow 首先将数据复制到 GPU 上的一个连续空间，然后将页面分散到其目的地。这实现了 $7 - 10 \times$ 的主机到设备复制的更高带宽。

5. 实验设置

5.1. 数据集

为了全面评估 NanoFlow 的性能，实验采用了多个真实世界的数据集，以模拟不同类型的用户查询行为。

以下是原文 Table 4 的结果：

表4：采样数据集中输入和输出长度的平均值和标准差。

• Splitwise [32]： 这是从 Microsoft 的真实生产环境中收集到的对话记录，总计约 20000 个请求。它代表了实际部署中可能遇到的复杂对话模式。从表4可以看出，其平均输入长度相对较长 (1155)，且标准差较大 (1109)，表明输入长度变化很大，这对于 LLM 服务系统来说是一个挑战。

• LMSYS-Chat-1M [56]： 这是一个大规模数据集，包含来自 25 个不同 LLM 的 100 万条真实世界对话。它提供了广泛的对话场景，有助于评估系统在多样化工作负载下的性能。其平均输入长度较短 (102)，但输出长度与 Splitwise 相当 (222)。

• ShareGPT [1]： 这是一个从 ShareGPT API 收集的对话数据集。它也反映了用户与 LLM 交互的真实情况。其平均输入长度和输出长度介于 Splitwise 和 LMSYS-Chat 之间。

  实验使用了 Splitwise 的完整轨迹，并从 ShareGPT 和 LMSYS-Chat-1M 中随机采样了 50,000 个请求进行评估。选择这些数据集旨在覆盖不同输入/输出长度分布和复杂度的实际工作负载，以全面验证 NanoFlow 在各种场景下的性能。

5.2. 评估指标

论文使用了以下几个关键指标来评估 NanoFlow 及其对比基线的性能：

5.2.1. 吞吐量 (Throughput)

• 概念定义： 吞吐量是衡量服务系统处理请求效率的核心指标。在 LLM 服务中，它量化了系统每秒能够处理的令牌总数，包括输入提示的令牌和模型生成的输出令牌。更高的吞吐量意味着在单位时间内完成更多的工作，从而降低服务成本。
• 数学公式： $$\mathrm{Throughput} = \frac{\text{Total tokens processed}}{\text{Total execution time}}$$
• 符号解释：
  • $\text{Total tokens processed}$：在给定时间段内，系统处理的输入令牌和输出令牌的总和。
  • $\text{Total execution time}$：处理这些令牌所花费的总时间。

5.2.2. 最优吞吐量 (Optimal Throughput)

• 概念定义： 最优吞吐量 是一个理论上限，表示在 GPU 计算资源完全饱和利用的情况下，系统能够达到的最高吞吐量。由于论文分析指出 LLM 服务通常是计算受限 (compute-bound) 的，因此 最优吞吐量 仅取决于 GPU 的计算能力和模型的参数量。
• 数学公式： $$\mathrm{Throughput_{optimal}} = \frac{Compute}{2 P_{Model}}$$
• 符号解释：
  • $\mathrm{Throughput_{optimal}}$：理论上可达到的最优吞吐量 (tokens/s/GPU)。
  • Compute：GPU 的聚合计算能力 (GFLOP/s)。
  • $P_{Model}$：模型的参数数量。
  • 2：在 GEMM 计算中，每个浮点数乘法通常伴随着一个浮点数加法，因此一个 FLOP 被定义为一次乘加操作，而一个 GEMM 的操作数是 $2 B_{Dense} N_w K_w$，因此参数前面乘以 2。

5.2.3. 归一化延迟 (Normalized Latency)

• 概念定义： 归一化延迟衡量了每个请求的端到端响应时间与生成令牌数量之间的比值，即平均每个输出令牌的延迟。这个指标有助于评估系统在不同输出长度下的用户体验，并设定 服务水平目标 (Service Level Objective, SLO)。
• 数学公式： $$\mathrm{Normalized Latency} = \frac{\text{End-to-end request latency}}{\text{Output length in tokens}}$$
• 符号解释：

  • $\text{End-to-end request latency}$：从请求开始到所有输出令牌生成完成的总时间。

  • $\text{Output length in tokens}$：该请求实际生成的输出令牌数量。

    此外，论文还关注 99th-percentile latency（99% 分位数延迟），这是一个衡量尾延迟 (tail latency) 的指标，确保绝大多数用户都能获得良好的体验。服务水平目标 (SLO) 被设定为 200ms 的平均归一化延迟。

5.3. 对比基线

为了全面评估 NanoFlow 的性能，论文将其与以下三个 最先进 (state-of-the-art) 的 LLM 服务框架进行了比较：

• vLLM [17, 52]： vLLM 是一个广泛使用的 LLM 服务系统，以其高吞吐量而闻名。它通过实现 PagedAttention 来提高 GPU 内存利用率，从而允许更大的批次处理。此外，vLLM 还采用了 分块预填充 (chunked prefill) 技术，以进一步提高 GPU 利用率。这些优化使得 vLLM 在处理大量请求时表现出色。

• DeepSpeed-FastGen [13, 23]： DeepSpeed-FastGen 是由 Microsoft 开发的一个服务框架。它的一个关键特性是能够动态地将预填充请求与解码请求组合，以确保引擎在高吞吐量状态下运行。通过调整 max-ragged-batch-size 参数，可以优化批次大小以达到最高吞吐量。

• TensorRT-LLM [26, 27]： TensorRT-LLM 是基于 NVIDIA TensorRT SDK 构建的高性能 LLM 推理引擎。它专注于通过 NVIDIA 的底层优化技术来加速推理。在实验中，max-num-tokens 参数通过计算 GPU 内存中 KV-cache 的最大容量来设置。此外，在编译时启用了 Paged KV-cache 和动态批处理 (dynamic batching) 优化。

这些基线都代表了当前 LLM 服务领域中领先的优化策略，与它们进行比较能够充分展现 NanoFlow 的竞争优势。

5.4. 硬件设置

实验在一台配备 $8 \times \mathrm { A100 }$ 80GB SXM GPU 的服务器上进行，这些 GPU 之间通过 NVLink 互连。这种配置是当前数据中心高性能计算的标准，能够为 LLM 服务提供强大的计算和通信能力。 所有模型均使用 FP16 (半精度浮点数) 权重和激活进行推理，这在数据中心规模的推理中是标准做法，因为它可以在保持足够精度的同时节省内存并加速计算。

6. 实验结果与分析

6.1. 核心结果分析

6.1.1. 吞吐量 (Throughput) 比较

论文首先评估了 NanoFlow 在 LLaMA-2-70B 模型上的离线吞吐量 (offline throughput)，以模拟基准测试、信息提取、数据整理和表单处理等用例。 实验中，输入（提示令牌）和输出（生成令牌）的长度从数据集中采样，并增加了固定长度的额外实验。NanoFlow 实例（对于 LLaMA-2-70B，密集批次大小为 2048）的总吞吐量定义为输入和输出令牌总数除以执行时间。 最优吞吐量 (optimal throughput) 是通过公式5计算得出的，其中 Compute 峰值容量通过 最先进 (state-of-the-art) GEMM 供应商库 CUTLASS 测量，令牌批次大小为 2048。由于 最优吞吐量 与用户查询统计数据无关，对于所有实验，计算出的 最优吞吐量 均为 1857 tokens/s/GPU。

以下是原文 Figure 7 的结果：

该图像是图表，展示了NanoFlow与其他方法（如Non-overlap、Nanobatch-only和NanoFlow-offload）在不同输入输出配置下的每GPU密钥通过率（tokens/s）。结果显示，NanoFlow在多种配置下均表现出最佳的吞吐量，验证了其高效性。

描述: 该图像是图表，展示了不同模型在每个 GPU 每秒的 token 吞吐量。NanoFlow 在多个工作负载条件下的表现超过了所有基线模型，验证了其在 LLaMA-2-70B 模型上的高效性。最优吞吐量为 1857 tokens/s。 来源: 7.jpg

图7展示了 NanoFlow 实例与基线系统在不同设置下的吞吐量比较。

• 总体优势： NanoFlow 在所有设置下都具有最高的吞吐量，并且在最佳情况下能够达到理论 最优吞吐量 的 68.5%。
• 固定长度工作负载： 对于固定长度的输入和输出，NanoFlow 的离线吞吐量平均比 vLLM 高 2.62 倍，比 DeepSpeed-FastGen 高 2.78 倍，比 TensorRT-LLM 高 1.73 倍。
• 实际工作负载（从数据集中采样）： 当输入和输出长度从数据集中采样时，NanoFlow 的吞吐量平均比 vLLM 高 4.18 倍，比 DeepSpeed-FastGen 高 3.45 倍，比 TensorRT-LLM 高 1.91 倍。 这些结果强有力地验证了 NanoFlow 通过 设备内并行 (intra-device parallelism) 和 纳米批次 (nano-batches) 重叠异构操作的有效性，使其能够显著超越现有 最先进 (state-of-the-art) 系统。

6.1.2. 延迟 (Latency) 比较

延迟评估模拟了请求到达间隔服从指数分布的情况。生成了 5 分钟的请求轨迹，覆盖不同的请求速率。归一化延迟 (normalized latency) 通过将端到端请求延迟除以输出令牌长度来计算，然后对所有请求取平均值。服务水平目标 (SLO) 设定为平均归一化延迟 200ms。

以下是原文 Figure 8 的结果：

该图像是资源使用情况的示意图，包括两种模式下的计算、内存和网络使用百分比。左侧(a)展示了非重叠管道的资源使用情况，右侧(b)展示了NanoFlow的资源使用情况。可见，NanoFlow在资源使用上更为高效。

描述: 该图像是图表，展示了不同请求速率下的延迟比较，包括 vLLM、DeepSpeed-FastGen、TensorRT-LLM 和 NanoFlow 四种方法，其中 NanoFlow 的延迟在较高请求速率下保持更优表现。具体而言，y 轴表示标准化延迟（毫秒/令牌），x 轴表示每秒请求数（req/s）。 来源: 8.jpg

图8展示了 NanoFlow 实例与基线系统在不同请求速率下的归一化延迟。

• 低请求速率下： 在较低的请求速率下，NanoFlow 实例的延迟与 TensorRT-LLM 相当，但略高。这主要是因为 NanoFlow 旨在面向吞吐量的场景，因此采用了较大的密集批次大小，这可能导致在请求稀疏时略微增加单个请求的等待时间。
• 高请求速率下： NanoFlow 实例能够维持比所有其他基线系统更高的请求速率，同时仍满足 200ms 的延迟 SLO。例如，对于 LMSys-Chat-1M 数据集，NanoFlow 实例在 200ms 归一化延迟约束下，能够处理比 TensorRT-LLM 高 1.64 倍的请求速率。
• 尾延迟： NanoFlow 实例的 99th-percentile latency（99% 分位数延迟）在接近最大吞吐量时仅为平均延迟的 1.07 倍。这表明 NanoFlow 在尾延迟方面表现良好，因为它使用恒定的密集批次大小，有助于减少极端延迟波动。

6.1.3. 消融研究 (Ablation Study)

消融研究旨在量化 NanoFlow 中各项技术（包括 纳米批次 (nano-batching)、纳米操作 (nano-operation) 重叠和 KV-cache 卸载）的开销和效益。

以下是原文 Figure 9 的结果：

该图像是一个柱状图，展示了NanoFlow与vLLM在不同模型上的每GPU标准化吞吐量对比。NanoFlow在多个模型中显著提高了吞吐量，最高可达最佳吞吐量的$78.5\%$，而vLLM的性能相对较低。

描述: 该图像是图表，展示了NanoFlow与其他方法（如Non-overlap、Nanobatch-only和NanoFlow-offload）在不同输入输出配置下的每GPU密钥通过率（tokens/s）。结果显示，NanoFlow在多种配置下均表现出最佳的吞吐量，验证了其高效性。 来源: 9.jpg

图9展示了消融研究的结果：

• 纳米批次 (nano-batching) 开销： 单独将请求拆分为 纳米批次 (nano-batches)（Nanobatch-only 基线），但不进行重叠操作，会导致性能下降 13.2%。这表明 纳米批次 (nano-batches) 本身会引入一定的开销，例如调度开销或批处理效应的损失。
• 重叠的效益：
  • 网络密集型内核重叠： 对于仅预填充工作负载（输入 512，输出 0），NanoFlow 通过重叠网络密集型内核，实现了 1.07 倍的加速。
  • 网络和内存密集型内核重叠： 对于解码密集型工作负载（输入 512，输出 1024），NanoFlow 通过重叠网络和内存密集型内核，实现了 1.17 倍的加速。 这证明了 纳米操作 (nano-operation) 重叠是 NanoFlow 性能提升的关键驱动因素，能够有效抵消 纳米批次 (nano-batching) 引入的开销。
• KV-cache 卸载的开销与效益： 启用 KV-cache 卸载会导致管道速度降低 3.0%，这主要是由于 KV-cache 移动引起的内核干扰。然而，对于多轮 LMSYS-Chat 工作负载，卸载可以减少 3.02 倍的计算量。这表明尽管卸载有微小的性能开销，但对于需要长期 KV-cache 存储和复用的场景，其带来的计算节省和内存管理效益是显著的。

6.1.4. 资源使用模式 (Resource Usage Pattern)

论文通过资源利用率图展示了 NanoFlow 的有效性。

以下是原文 Figure 10 的结果：

该图像是一个热力图，展示了不同模型和设备配置下的计算与网络边界性能。数据表明，LLM 模型在多 GPU 器件上的计算效率表现不一，右侧的颜色映射指示计算与网络边界的相对状态。此图可用于分析和比较各模型在不同资源配置下的表现。

描述: 该图像是资源使用情况的示意图，包括两种模式下的计算、内存和网络使用百分比。左侧(a)展示了非重叠管道的资源使用情况，右侧(b)展示了NanoFlow的资源使用情况。可见，NanoFlow在资源使用上更为高效。 来源: 10.jpg

图10对比了非重叠基线和 NanoFlow 实例的资源使用模式。

• 非重叠基线： 非重叠基线按顺序执行操作，在给定时间点主要只使用一种资源。这导致了大量的资源空闲，尤其是在计算资源方面。
• NanoFlow 实例： NanoFlow 实例能够并发利用多种资源，并实现了平均 68.5% 的计算利用率。尽管由于内核干扰，NanoFlow 提供的计算利用率低于理论最优值，但它显著高于非重叠基线。这直观地展示了 NanoFlow 通过 设备内并行 (intra-device parallelism) 有效减少 管道空闲 (pipeline bubbles)，从而提高 GPU 整体利用率的能力。

6.1.5. 在其他 LLM 上的性能 (Performance on Other LLMs)

为了证明 NanoFlow 的通用性，论文还评估了其在其他流行 LLM 上的吞吐量表现。实验使用固定长度的输入（1024）和输出（512），并在 $8 \times \mathrm { A100 }$ 80GB SXM GPU 上进行，除了 LLaMA-3-8B（运行在单个 A100 80GB SXM GPU 上）。

以下是原文 Figure 11 的结果：

该图像是一个热力图，展示了不同模型在不同配置下的计算时间和内存使用情况。颜色越向黄色靠近，说明工作负载越计算密集，而越向绿色则表示内存密集型。数据包括LLaMA-3 8B（1xGPU）、Mistral 8x7B（8xGPU）等的性能比较。

描述: 该图像是一个柱状图，展示了NanoFlow与vLLM在不同模型上的每GPU标准化吞吐量对比。NanoFlow在多个模型中显著提高了吞吐量，最高可达最佳吞量$78.5\%$，而vLLM的性能相对较低。 来源: 11.jpg

图11总结了 NanoFlow 在其他模型上的性能：

• 通用性： NanoFlow 能够将这些模型的吞吐量提升到 最优吞吐量 的 50% 到 72% 之间。
• 相比 vLLM 的增益： NanoFlow 相较于 vLLM 平均实现了 2.66 倍的吞吐量增益。 这些结果表明，NanoFlow 提出的 设备内并行 (intra-device parallelism) 方法和 自动化管道搜索 (auto-search) 引擎对于各种 LLM 模型和架构（包括 Mixture-of-Experts (MoE)）都具有广泛的适用性和显著的性能提升。

6.2. 成本模型验证 (Validation of the Cost Model)

论文在 LLaMA-2 70B 服务（使用 8 块 NVIDIA A100 GPU，密集批次大小为 2048 请求）上验证了其成本模型。通过计算每个操作的 GFLOPs、内存移动和网络流量（表2），并结合硬件规格，计算了 $T_{compute}$、$T_{mem}$ 和 $T_{net}$。最长估计时间 $T_{op} = \operatorname*{max}(T_{compute}, T_{mem}, T_{net})$ 表示最受限的资源。

以下是原文 Table 2 的结果：

表2：成本模型估计与实际测量操作运行时间的比较。

• 对齐性： 对于大多数操作，$T_{op}$ 与分析结果吻合。
• 异常： 预填充注意力 Prefill Attention (PfAttn) 是一个例外，其真实测量时间更大，原因在于相关内核的启动开销主导了总时间。
• 总和： 所有操作的 $T_{compute}$、$T_{mem}$ 和 $T_{net}$ 总和表明计算是最大的受限资源（114.17 ms），这与成本模型的发现一致。

6.3. LLM 服务工作负载分类 (Classification of LLM Serving Workloads)

论文通过比较迭代的内存、计算和网络延迟来对 LLM 服务工作负载进行分类。

6.3.1. 计算与网络时间比 (Compute vs. Network Time Ratio)

首先比较网络时间 $T_{Net}$ (公式3) 和计算时间 $T_{Compute}$ (公式2)。 $$\frac{T_{Net}}{T_{Compute}} = \frac{2 D_{model} L}{P_{model}} \frac{N_{GPU} Compute}{NetBW/S_{type}}$$ 其中：

• $D_{model}$：隐藏层维度大小。

• $L$：层数。

• $P_{model}$：模型参数数量。

• $N_{GPU}$：GPU 数量。

• Compute：GPU 聚合计算能力 (GFLOP/s)。

• NetBW：GPU 互连带宽 (GB/s)。

• $S_{type}$：模型参数数据类型的大小 (Bytes)。

  注意到 $P_{model} \approx 12 D_{model}^2 L$，因此 $\frac{2 D_{model} L}{P_{model}} \approx \frac{1}{6 D_{model}}$。对于需要多个 GPU 的模型，$D_{model}$ 通常大于 4096，使得 $\frac{2 D_{model} L}{P_{model}}$ 项小于 $1 \times 10^{-5}$。由于数据中心 GPU 之间的高带宽互连（例如 NVLink [25]），$\frac{N_{GPU} Compute}{NetBW/S_{type}}$ 的比率通常在 $1 \times 10^4$ 到 $1 \times 10^5$ 之间。因此，整体比率通常小于 1，表明网络不是瓶颈。

以下是原文 Figure 2 的结果：

该图像是示意图，展示了在特定层次中，各个组件及其相互关系。图中包括了独立操作如 KQV、DecAttn、Prefill Attention 和多个“WASTED”部分，突出显示了资源的使用情况与潜在的浪费。箭头指示了数据流向和操作顺序，强调了各组件在执行过程中的角色。整体上，这幅图有助于理解 LLM 的计算流程及其效率问题。

描述: 该图像是一个热力图，展示了不同模型和设备配置下的计算与网络边界性能。数据表明，LLM 模型在多 GPU 器件上的计算效率表现不一，右侧的颜色映射指示计算与网络边界的相对状态。此图可用于分析和比较各模型在不同资源配置下的表现。 来源: 2.jpg

图2展示了不同 LLM 模型在不同 GPU 数量下的 计算与网络时间比。颜色越接近蓝色表示工作负载越网络受限。图中大部分区域颜色偏黄，表明计算时间大于网络时间。对于大型模型和数据中心 GPU，计算耗时通常多于网络耗时。

6.3.2. 计算与内存时间比 (Compute vs. Memory Time Ratio)

接下来比较内存时间 $T_{Mem}$ (公式1) 和计算时间 $T_{Compute}$ (公式2)，以最终确定工作负载的特性，即以下比值： $$T_R = \frac{T_{Mem}}{T_{Compute}} \approx \frac{Compute}{MemBW} \frac{MemSize}{P_{model}} \frac{1}{2B_{dense}}$$ 其中：

• $T_R$：内存时间与计算时间的比值。

• MemBW (GB/s)：聚合 GPU 内存带宽。

• MemSize (GB)：聚合 GPU 内存容量。

• $B_{dense}$：密集操作的批次大小。

  现代模型广泛采用 分组查询注意力 (Grouped Query Attention, GQA)，例如 LLaMA-3 [48]。在 GQA 中，多个注意力头共享一个 KV-cache，这意味着在相同内存容量下，批次可以包含更多请求。因此，$B_{dense}$ 趋于更大。例如，在 $8 \times \mathrm { A100 }$ GPU 上服务 LLaMA-2 70B 时，解码请求的最大批次大小可达 1024。结合批次中的预填充令牌，$B_{dense}$ 可以达到 2048，而相同大小的非 GQA 模型只能达到 $B_{dense} = 256$。因此，比值 $T_R$ 小于 1，计算成为主要瓶颈。此外，现代模型倾向于具有越来越大的模型规模 $P_{model}$，这使得 $T_R$ 进一步降至 1 以下。

以下是原文 Figure 3 的结果：

该图像是图表，展示了GEMM和GEMV内核之间的干扰特性。x轴对应于独特的GEMM-GEMV实现对，y轴表示GEMM和GEMV内核的标准化性能 $P$。图中显示不同的优先级策略对性能的影响，特别是当GEMM被优先时，性能显著提升。

描述: 该图像是一个热力图，展示了不同模型在不同配置下的计算时间和内存使用情况。颜色越向黄色靠近，说明工作负载越计算密集，而越向绿色则表示内存密集型。数据包括LLaMA-3 8B（1xGPU）、Mistral 8x7B（8xGPU）等的性能比较。 来源: 3.jpg

图3展示了五个代表性模型的 $T_R$ 值：LLaMA-3 8B (1x A100)、Mistral 8x7B (8x A100)、LLaMA-2 70B (8x A100)、LLaMA-3 70B (8x A100) 和 Qwen-2 72B (8x A100)。热力图显示，许多工作负载（Splitwise [32]、LMSYS-Chat-1M [56]、ShareGPT [1] 以及固定长度输入和输出）都是统一的计算受限 (compute-bound)，除了在 LLaMA-3 8B 模型上进行长解码（512-1024）工作负载时，$T_R$ 约为 1。

总结而言，成本模型表明现代 LLM 服务工作负载主要在计算受限 (compute-bound) 状态下运行。这一结论通过实证验证得到了支持。

6.4. 其他 LLM 上的性能 (Performance on Other LLMs)

为了展示 NanoFlow 的泛化能力和高效性，论文对其在除 LLaMA-2-70B 之外的其他流行 LLM 上的吞吐量进行了评估。这些评估均在输入长度为 1024，输出长度为 512 的固定长度工作负载下进行。所有实验都在 $8 \times \mathrm { A100 }$ 80GB SXM GPU 上完成，除了 LLaMA-3-8B 模型，它是在单个 A100 80GB SXM GPU 上运行的。

以下是原文 Figure 11 的结果：

该图像是一个热力图，展示了不同模型在不同配置下的计算时间和内存使用情况。颜色越向黄色靠近，说明工作负载越计算密集，而越向绿色则表示内存密集型。数据包括LLaMA-3 8B（1xGPU）、Mistral 8x7B（8xGPU）等的性能比较。

描述: 该图像是一个柱状图，展示了NanoFlow与vLLM在不同模型上的每GPU标准化吞吐量对比。NanoFlow在多个模型中显著提高了吞吐量，最高可达最佳吞吐量的$78.5\%$，而vLLM的性能相对较低。 来源: 11.jpg

图11展示了 NanoFlow 实例在不同模型上的每 GPU 每秒令牌吞吐量性能。

• 接近最优吞吐量： NanoFlow 在这些模型上实现了 最优吞吐量 的 50% 到 72%。这表明 NanoFlow 的 自动化管道搜索 (auto-search) 引擎能够有效地为不同架构的 LLM 模型生成高效的管道，使其接近理论性能上限。
• 相对于 vLLM 的显著增益： 相较于 vLLM，NanoFlow 在所有评估的模型上都显著提高了吞吐量。平均而言，NanoFlow 实现了 2.66 倍的吞吐量增益。 这些结果再次证明了 NanoFlow 方法的鲁棒性和有效性，不仅对主要评估的 LLaMA-2-70B 模型有效，而且能够推广到更广泛的 LLM 模型家族，包括 Mixture-of-Experts (MoE) 模型，从而为不同类型的 LLM 提供高效的服务。

7. 总结与思考

7.1. 结论总结

本研究对 LLM 服务中不同操作的特性进行了深入分析，揭示了现代 LLM 服务工作负载在大多数情况下是计算受限 (compute-bound) 的本质，而非传统认为的内存受限。论文指出，现有 LLM 服务系统由于计算密集型、内存密集型和网络密集型操作在单个 GPU 内顺序执行，导致 GPU 计算资源利用率低下，从而限制了吞吐量。

为解决这一问题，论文提出了 NanoFlow，一个新颖的端到端 LLM 服务系统。NanoFlow 的核心创新在于利用 设备内并行 (intra-device parallelism)，通过将输入拆分为更小的 纳米批次 (nano-batches)，并重叠执行具有异构资源需求的 纳米操作 (nano-operations)。NanoFlow 包含一个 自动化管道搜索 (auto-search) 引擎，该引擎能够智能地确定 纳米批次 (nano-batches) 的数量、大小、顺序和 GPU 资源分配，同时考虑并发操作的性能干扰，以最小化执行时间。

实验结果表明，NanoFlow 在 LLaMA-2-70B 等主流模型和实际工作负载下，相较于 最先进 (state-of-the-art) 的服务系统实现了平均 1.91 倍的吞吐量提升，达到了理论 最优吞吐量 的 50% 至 72%。此外，NanoFlow 还能在更高的请求速率下满足 服务水平目标 (SLO)，并对其他 LLM 模型（包括 MoE 模型）表现出良好的泛化能力，平均吞吐量增益达到 2.66 倍。这些证据强有力地证明了 NanoFlow 在显著提高 LLM 服务吞吐量方面的有效性和优越性。

7.2. 局限性与未来工作

论文中指出了一些 NanoFlow 的潜在局限性，并可以推断出一些未来的研究方向：

• 内核干扰建模的复杂性： NanoFlow 采用成对内核干扰 (pairwise kernel interference) 建模，并假设这种成对关系在重叠三个内核时仍然成立。然而，实际的内核干扰模式可能更为复杂且难以预测，尤其是在多个异构操作并发执行时。更精细、更准确的多内核干扰建模将是一个挑战。
• 自动化搜索 (auto-search) 的近似性： auto-search 引擎旨在在合理的时间内找到一个“实用”的管道，而非“可证明最优”的解决方案。虽然其在效率和准确性之间取得了平衡，但理论上仍存在进一步优化的空间，例如探索更复杂的优化算法或结合强化学习 (Reinforcement Learning) 来动态调整策略。
• 工作负载假设： NanoFlow 的批次形成策略假设有“大量请求”的场景。在请求量较少或波动较大的边缘部署场景中，其性能可能会受到影响。未来的工作可以探索如何在请求稀疏或流量模式不确定的情况下，更好地适应并维护高 GPU 利用率。
• KV-cache 卸载的开销： 尽管 KV-cache 卸载在多轮对话中带来了显著的计算节省，但其本身引入了 3.0% 的性能开销。如何进一步优化卸载机制，减少设备到主机的数据传输对 GPU 执行的干扰，仍有改进空间。
• 硬件支持的潜力： 论文提到 NVIDIA GPU 不提供对计算、内存和网络带宽的精确控制，这使得 R_physical 的直接控制成为挑战。如果未来的 GPU 硬件能够提供更细粒度的资源管理接口，将可能进一步简化 设备内并行 (intra-device parallelism) 的实现，并提升优化效果。
• 模型架构的演进： LLM 架构仍在快速发展，例如新的注意力机制、更复杂的混合专家模型 (Mixture-of-Experts, MoE) 等。NanoFlow 需要持续适应这些新架构的特性，并确保其 自动化搜索 (auto-search) 能够有效地发现最优管道。

7.3. 个人启发与批判

这篇论文对 LLM 服务领域提供了重要的见解和创新。

• 对瓶颈的重新认知至关重要： 最令我启发的是，论文首先通过严谨的分析和实证，推翻了领域内的普遍假设，即 LLM 服务是内存受限的，并明确指出它是计算受限的。这一底层认知是所有后续优化策略的基石。这提醒我们在解决复杂系统问题时，首先要准确识别真正的瓶颈，而不是盲目地遵循传统观念。
• 精细化 设备内并行 (intra-device parallelism) 的潜力： NanoFlow 提出的 纳米批次 (nano-batches) 和异构操作重叠的思想，将并行优化的粒度从宏观（请求、阶段）下沉到微观（设备内操作），这提供了一个新的视角来挖掘 GPU 内部的并行性。这种方法不仅限于 LLM，理论上可以推广到任何包含异构计算、内存和网络操作的 深度学习 (Deep Learning) 工作负载中，特别是那些瓶颈在 GPU 计算但存在资源空闲的场景。
• 自动化管道搜索 (auto-search) 的实用性： 面对 设备内并行 (intra-device parallelism) 带来的巨大调度复杂性，NanoFlow 的 自动化管道搜索 (auto-search) 引擎是一个非常实用的解决方案。它避免了手动调优的繁琐和低效，使得优化方案能够自适应不同的模型、硬件和工作负载。这种将复杂优化问题转化为可求解的 MILP，并通过分阶段近似来提高效率的方法，值得在其他系统优化问题中借鉴。

批判性思考：

• 通用性与开销的平衡： 尽管 NanoFlow 提供了显著的吞吐量提升，但其 纳米批次 (nano-batches) 本身带来了 13.2% 的开销。这意味着对于计算利用率已经很高或异构操作不那么明显的模型或场景，NanoFlow 的收益可能不如论文中所示的那么显著。如何在不同场景下动态调整 纳米批次 (nano-batches) 的粒度和重叠策略，以实现最佳的开销与收益平衡，是一个值得深入研究的方向。

• MILP 的可扩展性： 尽管 auto-search 通过两阶段和近似技术降低了 MILP 的搜索时间，但随着 LLM 架构的日益复杂和 GPU 资源配置的多样化，MILP 问题的规模可能会继续扩大。MILP 求解器的性能和可扩展性可能会成为未来的一个瓶颈。探索结合机器学习、强化学习或其他启发式搜索方法，以实现更高效、更通用的调度策略，可能会是一个有前景的方向。

• 实际部署的复杂性： NanoFlow 的实现涉及对 CUDA 内核的精细控制、KV-cache 的异步卸载以及复杂的批次调度。这使得其在实际生产环境中的部署、维护和调试具有一定的复杂性。如何将这些底层优化封装成更易于使用和集成的接口，降低其使用门槛，是其走向广泛应用的关键。

  总的来说，NanoFlow 不仅提供了一个高性能的 LLM 服务解决方案，更重要的是，它改变了我们对 LLM 服务瓶颈的认知，并提出了一个通用的 设备内并行 (intra-device parallelism) 优化范式，这对于未来的 深度学习 (Deep Learning) 系统设计具有重要的指导意义。