1. 论文基本信息

1.1. 标题

EdgeShard: Efficient LLM Inference via Collaborative Edge Computing

1.2. 作者

Mingjin Zhang, Jiannong Cao, Fellow, IEEE, Xiaoming Shen, Zeyang Cui

1.3. 发表期刊/会议

预印本 (arXiv preprint)

1.4. 发表年份

2024年5月23日 (Published at (UTC)：2024-05-23T09:46:22.000Z)

1.5. 摘要

大型语言模型 (Large Language Models, LLMs) 在自然语言处理和内容生成领域展现出巨大潜力。然而，当前的 LLMs 高度依赖云计算，导致延迟过长、带宽成本高昂以及隐私问题。边缘计算 (Edge Computing) 有望通过将 LLMs 部署在更接近数据源的边缘设备上来解决这些问题。一些工作尝试利用模型量化 (model quantization) 来减小模型尺寸以适应资源受限的边缘设备，但这通常会导致精度损失。另一些工作使用云边协作 (cloud-edge collaboration)，但其性能受限于不稳定的网络连接。

在这项工作中，作者利用协作边缘计算 (Collaborative Edge Computing, CEC) 来促进边缘设备和云服务器之间的协作，共同执行高效的 LLM 推理。作者提出了一个通用的框架 EdgeShard，用于将 LLM 模型分片并部署到分布式设备上。为实现高效的 LLM 推理，作者将自适应的设备选择和模型分片问题进行公式化，并设计了一种高效的动态规划算法来分别优化推理延迟 (inference latency) 和吞吐量 (throughput)。在异构物理原型上对 Llama2 系列模型的实验表明，EdgeShard 相比基线方法实现了高达 50% 的延迟降低和 2 倍的吞吐量提升。

1.6. 原文链接

原文链接: https://arxiv.org/abs/2405.14371v1 PDF 链接: https://arxiv.org/pdf/2405.14371v1.pdf

2. 整体概括

2.1. 研究背景与动机

LLMs 虽然能力强大，但其在应用中面临的核心挑战是其庞大的计算量和内存需求。这使得它们主要依赖于强大的云计算基础设施。这种对云计算的重度依赖带来了几个关键问题：

1. 高延迟 (Prolonged Latency): 对于机器人控制、导航等实时应用，数据必须传输到云端处理后再返回，导致响应时间过长，无法满足即时性需求。

2. 高带宽成本 (High Bandwidth Cost): 传输海量数据（文本、视频、图像、IoT传感数据等）到云数据中心会消耗大量网络带宽，给网络架构带来巨大压力。

3. 隐私问题 (Privacy Concerns): 处理医疗、金融等敏感数据以及个人数据（如手机上的文本输入和照片）时，将其传输到云端进行处理存在显著的隐私泄露风险。

   边缘计算 (Edge Computing) 被视为解决这些挑战的潜在方案，它通过在网络边缘部署 LLMs（例如在边缘服务器、边缘网关和移动电话等边缘设备上），使计算更接近数据源。然而，边缘设备通常资源受限，无法直接承载大型 LLMs。现有的一些解决方案也存在不足：

• 模型量化 (Model Quantization): 尝试通过降低模型精度来减小模型尺寸，使其适应边缘设备的内存限制。但这种方法往往会导致精度损失 (accuracy loss)。

• 云边协作 (Cloud-Edge Collaboration): 将 LLMs 划分为两部分，一部分卸载到云端强大的服务器上。但边缘设备与云服务器之间的网络连接通常不稳定且延迟高，影响性能。

  为了克服这些挑战，本研究的切入点在于利用协作边缘计算 (Collaborative Edge Computing, CEC) 的概念。该研究动机是希望通过整合地理分布式边缘设备和云服务器的计算资源，创建一个共享的资源池，以实现 LLMs 的高效、低延迟、高吞吐量的推理，同时解决隐私和带宽成本问题。

2.2. 核心贡献/主要发现

本论文 EdgeShard 的核心贡献主要体现在以下三个方面：

1. 提出通用 LLM 推理框架 EdgeShard: 首次提出了一个通用的框架，用于在协作边缘计算环境中部署 LLMs，该框架支持异构边缘设备和云服务器之间的协作推理。
2. 数学公式化与优化算法:
   • 将设备选择和 LLM 分片问题数学化，以优化推理延迟和吞吐量。
   • 设计了高效的动态规划算法，分别解决最小化推理延迟和最大化推理吞吐量的问题。
3. 实验验证与性能提升:
   • 在由 Llama2 系列模型组成的物理测试平台上进行了广泛实验。
   • 实验结果表明，EdgeShard 显著优于现有的基线方法，实现了高达 50% 的延迟降低和 2 倍的吞吐量提升。
   • EdgeShard 能够有效解决 Llama2-70B 等大型模型在单边缘设备或简单云边协作下因内存不足 (OOM) 而无法部署的问题。

3. 预备知识与相关工作

3.1. 基础概念

为了充分理解 EdgeShard 框架，初学者需要了解以下几个核心概念：

3.1.1. 大型语言模型 (LLMs)

大型语言模型 (Large Language Models, LLMs) 是指参数量庞大（通常数十亿到数千亿）的深度学习模型，主要基于 Transformer 架构 (Transformer Architecture)。它们通过在海量文本数据上进行训练，学习语言的复杂模式和上下文关系，从而能够生成连贯、语境恰当的文本。LLMs 通常采用 解码器 (Decoder) 结构，这意味着它们擅长根据给定的输入（提示词）逐步生成后续的文本序列。

3.1.2. 边缘计算 (Edge Computing)

边缘计算 (Edge Computing) 是一种分布式计算范式，它将计算和数据存储能力从集中式云数据中心推向网络的边缘，即更接近数据生成源头和用户的物理位置。这样做的主要目的是减少数据传输到远端云服务器所需的延迟，降低网络带宽消耗，并提升数据隐私和安全性。边缘设备可以是智能手机、IoT 网关、边缘服务器等。

3.1.3. 协作边缘计算 (Collaborative Edge Computing, CEC)

协作边缘计算 (Collaborative Edge Computing, CEC) 是边缘计算的一种高级形式，它不仅将计算推向边缘，还强调在地理分布式、异构的边缘设备和云服务器之间进行资源共享和任务协作。与传统的云边垂直协作不同，CEC 包含了边缘设备之间的水平协作，形成一个共享的资源池。这有助于更有效地利用碎片化的边缘计算资源，扩大服务覆盖范围，并优化整体性能。

3.1.4. 模型量化 (Model Quantization)

模型量化 (Model Quantization) 是一种模型压缩技术，旨在通过降低模型参数（权重）和/或激活值（中间计算结果）的数值精度（例如从 32 位浮点数降到 8 位或 4 位整数）来减小模型尺寸和计算复杂度。这使得大型模型能够部署在内存和计算能力受限的设备（如边缘设备）上。然而，量化往往会引入精度损失，影响模型的性能。

3.1.5. LLM 推理的自回归性质 (Autoregressive Nature of LLM Inference)

LLM 推理 (LLM Inference)，特别是生成式 LLMs 的推理过程，具有自回归 (Autoregressive) 的特点。这意味着模型在生成一个 词元 (token) 后，会将这个新生成的 词元 加入到输入序列中，作为生成下一个 词元 的依据。这个过程是迭代的、顺序的，直到生成结束 词元 (End-Of-Sequence, EOS) 或达到最大长度。 LLM 推理通常分为两个阶段：

1. 预处理阶段 (Prompt Processing Phase) / Prefill: 模型接收完整的输入提示词（prompt），一次性处理所有输入 词元，并计算出所有 词元 的 键值缓存 (Key-Value Cache, KV Cache)。这个阶段通常计算量较大，因为需要处理所有输入 词元。
2. 自回归生成阶段 (Autoregressive Generation Phase): 模型基于当前的输入（包括原始提示词和已生成的 词元），逐个生成新的 词元。每生成一个 词元，它就会被添加到输入序列中，用于下一轮的生成。

3.1.6. 键值缓存 (Key-Value Caching, KV Cache)

在 Transformer 模型的自注意力机制中，模型会计算查询 (Query)、键 (Key) 和值 (Value) 矩阵。在自回归生成过程中，为了避免重复计算历史 词元 的键和值，LLMs 会将这些 键值对 (Key-Value Pairs) 存储起来，形成 KV 缓存 (KV Cache)。在生成下一个 词元 时，模型可以直接从 KV Cache 中获取之前 词元 的键值，从而大幅减少计算量，加速推理过程。然而，KV Cache 会显著增加模型的内存消耗。

3.1.7. 模型分片 (Model Sharding) / 模型并行 (Model Parallelism)

模型分片 (Model Sharding) 或 模型并行 (Model Parallelism) 是一种分布式训练和推理技术，用于处理单个设备无法容纳的超大型模型。其核心思想是将模型的不同部分（例如不同的层或层的不同子结构）分配到不同的计算设备上。在推理时，数据会按顺序流经这些分片，每个设备只负责处理其分配到的模型部分。

3.1.8. 流水线并行 (Pipeline Parallelism)

流水线并行 (Pipeline Parallelism) 是模型并行的一种特殊形式，旨在提高分布式系统中设备利用率和吞吐量。它将模型的连续层分配到不同的设备上，形成一个“流水线”。与简单的顺序执行不同，流水线并行允许不同设备同时处理不同批次（或微批次）的数据。例如，当第一个设备完成第一个微批次的处理并将其结果发送给第二个设备时，它可以立即开始处理第二个微批次的任务，而无需等待整个模型的所有层都处理完第一个微批次。这减少了设备空闲时间，提高了整体吞吐量。

3.2. 前人工作

3.2.1. 云端 LLM 并行化

在云计算环境中，为了训练和推理超大规模 LLMs，研究人员开发了多种并行化技术。

• Gpipe [17]: 引入了微批次 (micro-batching) 和流水线调度 (pipeline scheduling) 来实现模型并行，有效地利用多个 GPU 训练大型神经网络。它通过将模型层划分到不同的 GPU 上，并在这些 GPU 之间以流水线方式传递激活值来减少空闲时间。

• PipeDream [18]: 进一步优化了流水线并行，提出了更灵活的调度策略，可以处理模型的权重更新和激活值传递，同时减少了 流水线气泡 (pipeline bubbles)（即设备空闲时间），提升了效率。

  与本文的区别: 这些云端方案通常假设拥有同构的强大 GPU 资源和高带宽（如 InfiniBand、Nvlinks，带宽可达 600 GB/s）的网络连接。而 EdgeShard 面对的是异构的边缘设备和低带宽（数十 Kbps 到 1000 Mbps）的网络环境，云端方案直接应用于边缘场景效率低下。

3.2.2. 边缘 LLM 量化

针对边缘设备资源受限的问题，模型量化是主流方法。

• GPTQ [8]: 针对 GPT 等生成式预训练 Transformer 模型，提出了高精度的后训练量化方法，将数百亿参数的模型量化到 3-4 比特，主要关注权重 (weight-only quantization)。

• Lin 等人 [10] 和 AWQ: 通过优化通道缩放 (channel scaling) 来保留重要的权重，减少量化误差。

• SmoothQuant [11] 和 Agile-Quant [7]: 不仅量化模型权重，还量化模型激活值 (activations)，进一步减少模型大小和计算量。

• Edgeqat [12]: 结合了熵和分布引导的量化感知训练，加速边缘设备上的轻量级 LLMs。

  与本文的区别: 尽管量化可以减小模型尺寸，但往往会导致精度损失。对于 Llama2-70B 这样极大的模型，即使是 4 比特量化（35GB），也可能超出大多数边缘设备的内存容量。EdgeShard 通过模型分片和多设备协作，可以在不损失精度的情况下部署大型 LLMs。

3.2.3. 云边协作

一些工作尝试结合云和边缘的优势，将 LLM 计算任务进行分发。

• Wang 等人 [13]: 通过在云服务器和边缘设备之间分发计算来提高吞吐量，并利用残差激活值的低秩特性减少云边通信开销。

• Chen 等人 [14]: 利用边缘设备的地理位置信息，在协作的云边 LLM 服务中实现个性化的提示词补全。

  与本文的区别: 这些传统云边协作方案通常将 LLM 简单划分为两部分（一部分在云，一部分在边缘），但边缘设备与中心云之间的网络延迟通常较高且不稳定，这会成为瓶颈。EdgeShard 则提出了一个更通用的框架，允许在多个异构边缘设备和云服务器之间进行自适应分片和设备选择，并考虑了设备间的横向协作。

3.3. 技术演进

LLM 部署的技术演进大致经历了以下阶段：

1. 云端集中部署: 早期 LLMs 主要部署在云端强大的数据中心，享受集中的计算资源和高速互联网络。
2. 边缘设备部署尝试: 随着边缘计算兴起，研究人员开始探索将 LLMs 部署到边缘设备，但受限于资源。
3. 模型压缩技术 (如量化): 为了适应边缘设备的内存和计算限制，模型量化等压缩技术成为主流，但存在精度损失的权衡。
4. 云边协作部署: 结合云端和边缘的优势，将部分计算卸载到云端，但受限于云边网络连接。
5. 协作边缘计算 (本文): EdgeShard 代表了这一演进的最新方向，它超越了简单的云边二元协作，倡导在多个异构边缘设备和云服务器之间进行精细化、自适应的协同分片和调度，以更全面地解决 LLM 部署的性能、隐私和成本问题。

3.4. 差异化分析

EdgeShard 与现有方法的根本区别和创新点在于：

• 泛化性: 提出的是一个通用框架，不仅限于云与单边缘设备的二元协作，而是支持多个异构边缘设备和云服务器的协作。
• 自适应优化: 能够根据设备的异构计算能力、内存限制和网络带宽，自适应地选择参与设备和执行细粒度的模型层级分片。
• 优化目标: 明确地将最小化推理延迟和最大化吞吐量作为优化目标，并设计了专门的动态规划算法来解决这些问题。
• 性能权衡: 在不牺牲模型精度的情况下，通过协作分片来解决大型 LLMs 的内存墙问题，同时在各种网络条件下都能实现显著的性能提升。

4. 方法论

本节将详细阐述 EdgeShard 框架的方法论，包括其核心思想、系统模型、以及用于优化推理延迟和吞吐量的动态规划算法。

4.1. 方法原理

EdgeShard 的核心思想是利用协作边缘计算 (Collaborative Edge Computing, CEC) 的优势，将一个大型语言模型 (LLM) 划分为多个分片 (shards)，并将这些分片智能地部署到由异构边缘设备和云服务器组成的分布式计算网络中。通过这种方式，EdgeShard 旨在克服单个边缘设备的资源限制，同时避免传统云边协作中因网络不稳定导致的性能瓶颈，最终目标是最小化 LLM 推理的延迟 (latency) 或最大化其吞吐量 (throughput)。

整个框架分为三个主要阶段：

1. 性能分析 (Profiling): 这是一个离线步骤，用于收集每个 LLM 层在不同设备上的执行时间、激活大小、内存消耗，以及设备的内存预算和设备间的网络带宽。这些数据是后续调度优化的基础。
2. 调度优化 (Scheduling Optimization): 在此阶段，调度器利用性能分析数据，生成一个最优的部署策略。该策略决定了哪些设备将参与协作、LLM 如何被分层分片，以及每个分片分配给哪个设备。优化目标可以是最小化延迟或最大化吞吐量。
3. 协作推理 (Collaborative Inference): 一旦部署策略确定，选定的设备将按照该策略进行协作推理。EdgeShard 支持两种主要的协作推理模式：顺序推理 (Sequential Inference) 和 流水线并行推理 (Pipeline Parallel Inference)。

4.2. 系统模型

LLM 通常采用分层架构 (layered architecture)，包括嵌入层、多个解码器层和输出层。模型的参数大小和激活值（即某层的输出）因层而异。

• 我们假设 LLM 包含 $N$ 层。

• $O_i$ 表示第 $i$ 层的激活值大小，其中 $0 \le i \le N-1$。

• $Req_i$ 表示第 $i$ 层的内存消耗。

• 网络包含 $M$ 个计算设备（边缘设备和云服务器）。

• 设备具有异构的计算和内存能力。设备 $j$ 的内存预算为 $Mem_j$。

• 任意两个设备 $k$ 和 $j$ 之间的带宽为 $B_{k,j}$。

• 输入令牌驻留在源节点，无通用性损失，我们设源节点为节点 0。

  以下是原文 TABLE II 中使用的符号列表：

  Symbol	Descriptions
  $X_{i,j}$	binary variable, whether layer i of a model is allocated to device j
  $t_{comp}^{i,j}$	computation time of layer i on device j
  $t_{comp}^{i \to m,j}$	computation time of layer i to layer m on device j
  $t_{comm}^{i-1,k,j}$	communication time to transmit activations of layer i-1 from device k to device j
  `DP(i, j)`	minimal total execution time of the first i layers if layer i is allocated to device j
  `g(i, S, k)`	processing time of the slowest node to process the first i layers with device set S

4.3. 优化 LLM 推理延迟

4.3.1. 问题公式

为了最小化 LLM 推理延迟，我们首先定义模型的分配策略和相关的计算与通信成本。

• 分配策略: 我们使用一个二进制变量 $X_{i,j}$ 来表示 LLM 的分配策略。如果模型的第 $i$ 层被分配给节点 $j$，则 $X_{i,j}=1$，否则 $X_{i,j}=0$。每层模型只能分配给一个节点，因此有以下约束： $$\sum_{j=0}^{M-1} X_{i,j} = 1, \quad \forall i$$
• 计算时间: $t_{comp}^{i,j}$ 表示第 $i$ 层在设备 $j$ 上的计算时间。
• 通信时间: $t_{comm}^{i-1,k,j}$ 表示将第 i-1 层的激活值从设备 $k$ 传输到设备 $j$ 所需的通信时间。如果第 i-1 层和第 $i$ 层在同一个设备上，则通信时间为零。通信时间由第 i-1 层的输出大小 $O_{i-1}$ 和设备 $k$ 与设备 $j$ 之间的带宽 $B_{k,j}$ 决定： $$t_{comm}^{i-1,k,j} = \begin{cases} \frac{O_{i-1}}{B_{k,j}}, & \text{if } k \neq j \\ 0, & \text{otherwise}. \end{cases}$$
• 总推理时间: 整个 LLM 的总推理时间 $T_{tol}$ 可以通过以下公式计算，它包括所有层的计算时间和层间通信时间： $$T_{tol} = \sum_{i=0}^{N-1} \sum_{j=0}^{M-1} X_{i,j} \cdot t_{comp}^{i,j} + \sum_{i=1}^{N-1} \sum_{j=0}^{M-1} \sum_{k=0}^{M-1} X_{i-1,k} \cdot X_{i,j} \cdot t_{comm}^{i-1,k,j}$$ 其中，第一项是所有层在各自设备上的计算时间总和，第二项是所有层间可能发生的通信时间总和。
• 优化目标: 最小化总推理时间 $T_{tol}$： $\min T_{tol}$
• 约束条件:
  • 隐私约束 (Privacy Constraint): LLM 的第一层必须始终分配给源节点（节点 0），以避免原始输入数据在设备间传输。 $X_{0,0} = 1$
  • 内存约束 (Memory Constraint): 分配给任何设备 $j$ 的所有层所需的内存总量不能超过该设备的内存预算 $Mem_j$。 $$\sum_{i=0}^{N-1} X_{i,j} \cdot Req_i \leq Mem_j$$

4.3.2. 解决方案 (动态规划算法)

为了最小化推理延迟，作者设计了一个动态规划 (Dynamic Programming, DP) 算法。其核心思想是，前 $i$ 层的最小执行时间可以通过前 i-1 层的最优解构建，这表明问题具有最优子结构性质 (optimal substructure property)。

• DP 状态定义: DP(i, j) 表示在第 $i$ 层分配给节点 $j$ 时，前 $i$ 层的最小总执行时间。
• 状态转移方程: DP(i, j) 的计算取决于前一层 i-1 被分配给哪个节点 $k$。我们需要遍历所有可能的节点 $k$ 来承载第 i-1 层，并选择使得总执行时间最小的那个。同时，考虑到 LLM 的自回归性质，生成的 词元 (token) 需要返回源节点进行下一轮迭代。因此，对于最后一层 N-1，通信时间不仅包括从 N-2 层到 N-1 层的传输，还包括从 N-1 层传输到源节点 0 的时间。 $$DP(i, j) = \begin{cases} \min_{k=0, \dots, M-1} \left( DP(i-1, k) + t_{comp}^{i,j} + t_{comm}^{i-1,k,j} \right), & \text{if } i < N-1 \\ \min_{k=0, \dots, M-1} \left( DP(i-1, k) + t_{comp}^{i,j} + t_{comm}^{i-1,k,j} + t_{comm}^{N-1,j,0} \right), & \text{if } i = N-1 \end{cases}$$ 其中 $DP(i-1, k)$ 表示前 i-1 层分配给设备 $k$ 时的最小执行时间。
• 初始化: 根据隐私约束，第一层（第 0 层）必须分配给节点 0。 $DP(0, 0) = t_{comp}^{0,0}$
• 最终结果: 填充完 DP 表后，最小的总执行时间为最后一层所有节点中 DP 值的最小值： $$\min_{j=0, \dots, M-1} (DP(N-1, j))$$ 通过回溯 (backtracking) 存储的路径信息，可以得到每个层的最优节点分配策略。

以下是原文中用于最小化推理延迟的算法 Algo. 1 的伪代码：

Algorithm 1: Joint device selection and LLM partition for optimizing latency

Input: A LLM model; Computing device $M$; Profiled traces; bandwidth $B_{k,j}$ Output: the device selection and LLM partition strategy $R$

// initialization 1 Initialize DP table $DP(i, j) = \text{INF}$, and choice table $choice(i, j) = \text{NULL}$ to record the strategy; 2 Enforce first layer to be allocated to node 0 by $DP(0, 0) = t_{comp}^{0,0}$ and $choice(0, 0) = 0$;

// fill in the DP table 3 for $i = 1$ to $N - 1$ do 4 for $j = 0$ to $M - 1$ do 5 if $\text{Mem}_j < Req_i$ then // Note: Original text has $\text{Mem}_j \leq Req_i$, which implies if memory is exactly equal, it cannot hold. Assuming it should be capacity $Mem_j$ >= $Req_i$, so if $Mem_j$ < $Req_i$ then continue. 6 Continue; 7 end 8 else 9 for $k = 0$ to $M - 1$ do 10 Calculate the total execution time by Eq. (6) and assign it to $t_{total}$: 11 if $t_{total} \le DP(i, j)$ then 12 Update DP(i, j) by assigning $DP(i, j) = t_{total}$; 13 Update memory $Mem_j$; // This line is unusual for DP, might be conceptual or indicating cumulative memory check. For pure DP, memory check is usually at the end of path or aggregated. Assuming it means temporary update for the current path or conceptual. Re-reading, it's likely a conceptual representation for checking if current $Mem_j$ can still hold layers if layer $i$ is assigned to $j$, not modifying actual $Mem_j$ for subsequent layers in this DP iteration. The memory constraint is formally defined in Eq. (5) as a sum. The pseudo-code might be oversimplified here. Let's interpret it as checking the cumulative memory for the selected path up to layer $i$ on device $j$. However, given DP(i,j) is only for layer $i$ on device $j$, the cumulative memory check for device $j$ across all layers assigned to it on the chosen path should be handled implicitly by the DP(i-1,k) choice or a separate memory tracking mechanism. For strict interpretation of the given algorithm, it implies that $Mem_j$ is dynamically tracked within the loop. 14 Record allocation plan $choice(i, j) = k$; 15 end 16 end 17 end 18 end 19 end

// backtrace for allocation strategy 20 Initialize optimal strategy $R$. 21 Find the last selected node $N_{last} = \text{argmin}_j (DP(N-1, j))$. 22 Add $N_{last}$ to $R$. 23 for $i = N - 1$ to 0 do 24 Find the previous node $N_{last} = choice(i, N_{last})$; 25 Add $N_{last}$ to $R$. 26 end 27 Reverse $R$; 28 return $R$;

算法解释:

1. 初始化 (Lines 1-2): DP 表和 choice 表被初始化。DP(i, j) 存储到达第 $i$ 层并将其分配给设备 $j$ 的最小时间。choice(i, j) 存储了前一层 i-1 被分配到的设备 $k$，以便回溯。根据隐私约束，第 0 层必须在节点 0 上，因此 $DP(0, 0)$ 被初始化为第 0 层在节点 0 上的计算时间。
2. 填充 DP 表 (Lines 3-19):
   • 外层循环遍历从第 1 层到第 N-1 层 ( $i$ )。
   • 中层循环遍历所有可能的设备 ( $j$ ) 来承载当前层 $i$。
   • 首先检查设备 $j$ 是否有足够的内存来承载当前层 $i$ ($Mem_j < Req_i$)。这里的 $Req_i$ 应该是指当前层 $i$ 自身的内存需求。然而，内存约束公式 (5) 是累积的。在 DP 过程中，正确的内存检查应该是跟踪 $j$ 上已分配层的累积内存。鉴于伪代码的简洁性，此处 $Mem_j < Req_i$ 可能是一个简化的检查，或者 $Mem_j$ 在实际实现中是动态更新的，代表设备 $j$ 的剩余内存，或者这是一个错误，正确的内存检查应该更复杂地嵌入在 $t_{total}$ 的计算中，或在回溯后进行验证。
   • 内层循环遍历所有可能的设备 ( $k$ ) 来承载前一层 i-1。
   • 计算将第 i-1 层在设备 $k$ 上的处理结果加上当前层 $i$ 在设备 $j$ 上的计算和通信时间，得到总执行时间 $t_{total}$。
   • 如果 $t_{total}$ 小于当前 DP(i, j) 的值，则更新 DP(i, j) 为 $t_{total}$，并记录 choice(i, j) 为 $k$。
3. 回溯策略 (Lines 20-28):

   • 找到最后一层 N-1 在所有设备上 DP 值的最小值，确定最终的节点 $N_{last}$。

   • 从 $N_{last}$ 开始，利用 choice 表从后往前回溯，逐层确定每个层应该分配到的设备，从而构建出完整的模型分片和分配策略 $R$。

     计算复杂度 (Computational Complexity): 该算法的计算复杂度为 $O(N \times M \times M)$，其中 $N$ 是 LLM 的层数，$M$ 是网络中设备的数量。

4.4. 优化 LLM 推理吞吐量

4.4.1. 问题公式

为了优化吞吐量，我们采用流水线并行 (pipeline parallelism) 的思想来减少设备空闲时间。在这种模式下，不同的设备可以同时处理不同的微批次 (micro-batches)。为了最大化吞吐量，我们旨在最小化最慢设备的延迟 (latency of the slowest device)。

• 设备 $j$ 的最大延迟: 对于选定的设备集 $S$，设备 $j \in S$ 的最大延迟 $T_{latency}^j$ 是其计算时间和通信时间中的最大值。这里，$t_{comp}^{i \to m,j}$ 表示层 $i$ 到层 $m$ 在设备 $j$ 上的计算时间。 $$T_{latency}^j = \max \left\{ \begin{array}{l l} t_{comp}^{i \to m,j} \\ t_{comm}^{i-1,k,j} \end{array} \right.$$ 这个公式的含义是在流水线并行中，一个设备在一个时间片内可能进行计算，也可能进行通信，其瓶颈在于这两个操作中最耗时的一个。
• 优化目标: 理想情况下，最大化吞吐量等价于最小化所有选定设备中最大延迟的那个设备所经历的延迟。 $$\min \{ T_{latency}^j \mid j \in S \}$$
• 约束条件:
  • 内存约束 (Memory Constraint): 分配给设备 $j$ 的从层 $i$ 到层 $m$ 的模型分片所需的内存总量不能超过设备 $j$ 的内存预算。 $Req_{i \to m} \leq Mem_j$
  • 隐私约束 (Privacy Constraint): 类似于延迟优化，第一层必须分配给源节点 0。 $$g(1, \{0\}, 0) = t_{comp}^{0,0}$$ 这里，$g(1, \{0\}, 0)$ 表示处理第一层（层 0）时，使用设备集合 $\{0\}$ 且最后一个使用的节点是 0 时的时间，即第 0 层在节点 0 上的计算时间。

4.4.2. 解决方案 (动态规划算法)

类似于延迟优化，吞吐量最大化问题也具有最优子结构性质，因此可以使用动态规划解决。

• DP 状态定义: g(m, S', j) 表示在处理前 $m$ 层时，使用了设备集 $S'$，且设备 $j$ 是最后使用的节点时的最小最大延迟。其中 $0 \le i < m \le N-1$，$S$ 是前一个状态使用的设备集，$S' = S \cup \{j\}$。

• 状态转移方程: g(m, S', j) 由前一个状态 g(i, S, k) 决定，即前 $i$ 层由设备集 $S$ 处理，且 $k$ 是最后一个使用的节点。同时，考虑将从层 $i$ 到层 $m$ 的分片分配给新设备 $j$ 的计算和通信时间。 $$g(m, S', j) = \min_{0 \le i < m \le N-1} \max \left\{ \begin{array}{l l} g(i, S, k) \\ t_{comm}^{i-1,k,j} \\ t_{comp}^{i \to m,j} \end{array} \right.$$ 这个方程的直观含义是，在扩展流水线时，新的最大延迟将是之前阶段的最大延迟 g(i, S, k) 与当前新加入设备 $j$ 的计算时间 $t_{comp}^{i \to m,j}$ 以及它与前一个设备 $k$ 之间通信时间 $t_{comm}^{i-1,k,j}$ 三者中的最大值。

• 最终结果: 最终的最优吞吐量 $T_{throu}^{opt}$ 对应于 $g(N-1, S', j)$ 的最小值，其中 $S'$ 是所有可能的设备子集。

  以下是原文中用于最大化推理吞吐量的算法 Algo. 2 的伪代码：

Algorithm 2: Joint device selection and LLM partition for optimizing throughput

Input: A LLM model; Computing devices $M$; Profiled traces; bandwidth $B_{k,j}$ Output: the device selection and LLM partition strategy $R$

// initialization 1 Initialize DP table $g(i, S, k) = \text{INF}$, and choice table $choice(m, S, j) = \text{NULL}$ to record the strategy; 2 Enforce first layer to be allocated to node 0 by $g(1, \{0\}, 0) = t_{comp}^{0,0}$ and $choice(1, \{0\}, 0) = (0, 0, 0)$; // Note: The description for $g(1, {0}, 0)$ matches the privacy constraint $g(1,1,0)$ where 1 is used as a placeholder for {0}.

// fill in DP table 3 for $i = 1$ to $N - 1$ do // Current ending layer of previous segment 4 for each subset $S \subseteq M$ do // Previous set of devices 5 for last node $k \in S$ do // Last device in the previous segment 6 for $m = i + 1$ to $N - 1$ do // Current ending layer of the new segment 7 for $j \in M \setminus S$ do // New device to add, not in previous set 8 if $\sum_{l=i}^{m} Req_l > \text{Mem}_j$ then // Check cumulative memory for the segment [i, m] on device j 9 Continue; 10 end 11 else 12 Get $S'$ by adding node $j$ to the selected device set $S$; 13 Calculate current maximum execution time $T_{max}$ via Eq. (11) for the maximum execution time in all stages; 14 end 15 if $T_{max} \le g(m, S', j)$ then 16 $g(m, S', j) = T_{max}$; 17 Record the current strategy $choice(m, S', j) = (i, j, k)$; 18 end 19 end 20 end 21 end 22 end 23 end

// backtrace for optimal allocation 24 Initialize optimal strategy $R$; 25 Find selected device set $S$ and the last selected node $N_{last}$ by $S, N_{last} = \text{argmin}_{S,k} (g(N-1, S, k))$; 26 Initialize layer $= N - 1$; 27 while layer $> 0$ do 28 $(i, j, k) = choice(layer, S, N_{last})$; // Retrieve previous layer, new device (j, should be prev_N_last), prev_prev_N_last (k) 29 Add $(i \to layer, j)$ to $R$; // Record the segment from layer i to layer as performed on device j 30 Update layer, $S$ and $N_{last}$; // Set current layer to i, update S and N_last based on choice. 31 end 32 return $R$;

算法解释:

1. 初始化 (Lines 1-2): $g$ 表和 choice 表被初始化。g(i, S, k) 存储了前 $i$ 层由设备集 $S$ 处理，且 $k$ 为最后一个设备时的最小最大延迟。隐私约束体现在 $g(1, {0}, 0)$ 的初始化。
2. 填充 DP 表 (Lines 3-23):
   • 外层循环 $i$ 遍历前一个分段的结束层。
   • 循环遍历所有可能的设备子集 $S$ 和其中的最后一个设备 $k$。
   • 循环 $m$ 遍历当前分段的结束层。
   • 循环 $j$ 遍历所有未在 $S$ 中的设备，作为当前分段的新设备。
   • 检查将层 $i$ 到层 $m$ 的分片分配给设备 $j$ 是否满足内存约束。这里 $\sum_{l=i}^{m} Req_l$ 明确表示了当前分段 [i, m] 的累积内存需求。
   • 计算当前分段的最大执行时间 $T_{max}$ (使用公式 (11))。
   • 如果 $T_{max}$ 小于 g(m, S', j) 的当前值，则更新 $g$ 表并记录 choice。
3. 回溯策略 (Lines 24-32):

   • 找到 $g(N-1, S, k)$ 的最小值，确定最终的设备集 $S$ 和最后一个设备 $N_{last}$。

   • 通过 choice 表从后往前回溯，逐段确定模型的分配策略 $R$。

     计算复杂度 (Computational Complexity): 该算法的计算复杂度为 $O(N^2 \times 2^M \times M^2)$，其中 $N$ 是 LLM 的层数，$M$ 是网络中设备的数量。由于涉及设备子集 $2^M$，此算法在设备数量 $M$ 较大时复杂度很高，但对于论文中 $M=15$ 的场景，仍是可行的。

4.5. 流水线执行优化 (Pipeline Execution Optimization)

在 LLM 推理中，由于其自回归 (autoregressive) 性质（当前 词元 (token) 的计算依赖于所有之前的 词元），传统的流水线并行容易产生气泡 (bubbles)，即设备空闲时间。这是因为下一个微批次的数据无法立即开始处理，必须等待前一个微批次完成当前 词元 的生成。

4.5.1. EdgeShard-Bubbles (传统流水线)

传统流水线如图 5(a) 所示，每个设备在完成其分配到的批次或微批次的计算后，都需要等待整个 LLM 完成一个 词元 的生成，才能开始处理下一个 词元 的任务。这导致了设备在等待上游或下游数据时的空闲状态，即“气泡”。

4.5.2. EdgeShard-Nobubbles (无气泡优化)

为了近似理想情况并提高资源利用率，EdgeShard 提出了 EdgeShard-Nobubbles 策略。如图 5(b) 所示，该策略允许立即生成 词元，而无需等待迭代中所有微批次的结束。具体来说，当第一个微批次的预处理阶段 (prefill stage) (P1) 在设备 1 上结束后，设备 1 会立即开始执行第一个微批次的** 词元 生成 (token generation)** (G1A)。当 G1A 结束后，设备 1 立即进入下一个 词元 生成迭代 (G1B)。

这种机制通过缓解设备的空闲时间来减少流水线中的气泡，从而预期能够显著提高吞吐量。从图 5 的对比可以看出，在相同时间内，EdgeShard-Nobubbles 能够生成更多的 词元。

以下是原文中展示气泡和无气泡流水线执行策略的图像：

该图像是一张实验平台的照片，展示了多个异构边缘设备和云服务器的实际硬件部署，图中设备通过蓝色网线互联，展示了论文中EdgeShard系统的测试环境。

token generation of a micro-batch without waiting for other micro-batches.

5. 实验设置

本节详细描述了 EdgeShard 框架的实验设置，包括所使用的测试平台、基准模型、对比基线方法以及评估指标。

5.1. 数据集

• 模型: 实验使用了 Llama2 系列模型 [2]，包括 Llama2-7B、Llama2-13B 和 Llama2-70B。Llama2 是 Meta 于 2023 年 7 月发布的开源大型语言模型，代表了 AI 和 NLP 领域的先进水平。
• 任务: 采用文本生成 (text generation) 任务来测试性能。
• 数据源: 使用了来自 HuggingFace 的 WikiText-2 数据集 [21]。
• 样本配置: 从数据集中抽取了一个子集，其中输入 词元 (tokens) 的长度为 32，并生成 96 个 词元。
• 精度: 所有实验均使用全精度模型推理 (full-precision model inference)，这意味着没有使用量化技术，以避免精度损失对结果的影响。

5.2. 评估指标

论文中使用了两种核心指标来评估 EdgeShard 的性能：

5.2.1. 延迟 (Latency)

• 概念定义: 延迟 (Latency) 通常指从发出请求到接收到第一个响应 词元 或完成所有 词元 生成所需的时间。在此文中，作者使用 Average Latency: milliseconds/token，即平均每个 词元 的生成时间，来衡量模型的响应速度和效率。数值越低表示性能越好。
• 数学公式: 虽然原文没有直接给出 平均每词元延迟 的数学公式，但其普遍定义为： $$\text{Latency (ms/token)} = \frac{\text{Total Inference Time (ms)}}{\text{Number of Tokens Generated}}$$ 其中，Total Inference Time 是指从输入第一个 词元 到最后一个 词元 生成完毕的总时间。
• 符号解释:
  • $\text{Total Inference Time (ms)}$：完成整个推理过程所需的总时间，以毫秒为单位。
  • $\text{Number of Tokens Generated}$：在推理过程中模型生成的 词元 总数量。

5.2.2. 吞吐量 (Throughput)

• 概念定义: 吞吐量 (Throughput) 表示系统在单位时间内能够处理或生成的 词元 数量。作者使用 Throughput: tokens/second，即每秒生成的 词元 数，来衡量系统处理请求的能力。数值越高表示系统处理能力越强。
• 数学公式: $$\text{Throughput (tokens/second)} = \frac{\text{Number of Tokens Generated}}{\text{Total Inference Time (seconds)}}$$
• 符号解释:
  • $\text{Number of Tokens Generated}$：在推理过程中模型生成的 词元 总数量。
  • $\text{Total Inference Time (seconds)}$：完成整个推理过程所需的总时间，以秒为单位。

5.3. 对比基线

EdgeShard 的性能与以下几种基线方法进行了比较：

• Edge-Solo: 在这种情况下，LLMs 完整地部署在单个边缘设备上，不进行模型分片或与其他设备协作。
• Cloud-Edge-Even: 在这种情况下，LLMs 被平均地分成两部分（均匀分片）。其中一半分配给边缘设备，另一半分配给云服务器。
• Cloud-Edge-Opt: 在这种情况下，LLMs 也被分成两片，一片分配给边缘设备，另一片分配给云服务器。与 Cloud-Edge-Even 不同的是，这里的模型分片策略是使用本文提出的动态规划算法进行优化的，但算法的输入设备仅限于两个（一个边缘设备和一个云服务器）。
  • 备注: 论文中明确指出，不将纯云端 (cloud-only) 作为基线，因为纯云端部署会涉及输入 词元 传输到云服务器，可能导致隐私问题。

5.4. 测试平台

实验搭建了一个由多种异构边缘设备和云服务器组成的物理测试平台，以模拟协作边缘计算环境。

• 设备配置:

  • Jetson AGX Orin: 32GB 内存，3.33 TFLOPS AI 性能。
  • Jetson Orin NX: 16GB 内存，1.88 TFLOPS AI 性能。
  • RTX 3090: 24GB 内存，36 TFLOPS AI 性能（作为云服务器）。

• 设备数量: 共使用了 15 台设备，包括 12 台 Jetson AGX Orin、2 台 Jetson Orin NX 和 1 台 RTX 3090 云服务器。

• 网络连接: 这些设备通过路由器和交换机连接。任意两个设备之间的默认带宽为 1000Mbps。

• 网络模拟: 使用 Linux TC 工具 [20] 来模拟不同的网络带宽和设备间的通信延迟。

  以下是原文中展示异构物理设备规格的表格：

  Category	Device	Memory	AI Performance
  Edge Device	Jetson AGX Orin	32GB	3.33 TFLOPS
  Edge Device	Jetson Orin NX	16GB	1.88 TFLOPS
  Cloud Server	RTX 3090	24GB	36 TFLOPS

以下是原文中展示实验平台的图片：

该图像是图表，展示了网络带宽对协同LLM推理延迟的影响，包括Llama2-7B、Llama2-13B和Llama2-70B三个模型在不同带宽下的延迟变化情况，比较了多种部署方案的性能。

Fig. 6. Our testbed has heterogeneous edge devices and cloud server. Their specifications are shown in Table III.

6. 实验结果与分析

本节将详细分析 EdgeShard 在不同实验设置下的性能表现，并与基线方法进行对比。

6.1. 核心结果分析

6.1.1. 总体评估

实验将 AGX Orin 设置为源节点，源节点与云服务器之间的带宽设定为 1Mbps。其他计算设备之间的带宽设置为 50Mbps，并有 20% 的方差。为了测试吞吐量，批量大小 (batch size) 设置为参与设备所能支持的最大值。

以下是原文 TABLE IV 的结果，展示了 LLM 推理的延迟（毫秒/ 词元）和吞吐量（词元 /秒）表现：

观察与分析：

1. EdgeShard 解决内存溢出 (OOM) 问题: 对于 Llama2-70B 模型，其内存需求约为 280GB，远超单个边缘设备或简单的云边协作的内存容量。Edge-Solo、Cloud-Edge-Even 和 Cloud-Edge-Opt 在 Llama2-13B (OOM for Edge-Solo) 和 Llama2-70B (all baselines OOM) 上均出现内存不足 (OOM) 问题，无法进行部署。EdgeShard 通过将大型模型分片并分配到多个设备，成功实现了 Llama2-70B 的协作推理（延迟 3086.43ms，吞吐量 1.25 词元/秒），验证了其部署超大型模型的能力。
2. EdgeShard 显著优于基线方法:
   • 延迟: 对于 Llama2-7B 模型，EdgeShard 实现了 75.88ms 的延迟，比 Edge-Solo 和 Cloud-Edge-Opt 快约 1.85 倍 (140.34/75.88 $\approx$ 1.85)，比 Cloud-Edge-Even 快约 3 倍 (227.35/75.88 $\approx$ 3)。对于 Llama2-13B 模型，EdgeShard 延迟为 173.43ms，比 Cloud-Edge-Even (319.44ms) 低 45.7%，比 Cloud-Edge-Opt (243.45ms) 低 28.8%。
   • 吞吐量: 对于 Llama2-7B 模型，EdgeShard 吞吐量达到 52.45 词元/秒（最大批量大小 8），是 Edge-Solo 和 Cloud-Edge-Opt 的约 2.2 倍 (52.45/24.36 $\approx$ 2.15)，是 Cloud-Edge-Even 的约 7 倍 (52.45/7.56 $\approx$ 6.94)。对于 Llama2-13B 模型，EdgeShard 吞吐量为 10.45 词元/秒，比 Cloud-Edge-Even (4.68) 和 Cloud-Edge-Opt (4.74) 高约 2.2 倍。
3. 低带宽下 Cloud-Edge-Opt 的行为: 对于 Llama2-7B，Cloud-Edge-Opt 的性能（延迟 140.34ms，吞吐量 24.36 词元/秒）与 Edge-Solo 完全相同。这是因为在源节点与云服务器之间带宽限制在 1Mbps 的情况下，通信成本过高。因此，Cloud-Edge-Opt 的优化策略会退化为将整个模型部署在本地边缘设备上，以避免高昂的跨设备通信开销，表现与 Edge-Solo 一致。

6.1.2. 带宽影响

实验将源节点设置为 AGX Orin，并改变云服务器与源节点之间的带宽，从 1Mbps 到 50Mbps。

以下是原文图 7，展示了网络带宽对协作 LLMs 推理延迟的影响：

该图像是图8，展示了带宽对协作型LLM推理吞吐量的影响。图中三个子图分别对应Llama2-7B、Llama2-13B和Llama2-70B模型，横轴为带宽(Mbps)，纵轴为吞吐量(tokens/s)，显示了EdgeShard相比其他方法在不同带宽下的吞吐量变化趋势。

Fig. 7. Impact of Network Bandwidth to Latency of Collaborative LLMs inference

以下是原文图 8，展示了网络带宽对协作 LLMs 推理吞吐量的影响：

该图像是图表，展示了图9中不同方法在Llama2-7B模型上的延迟和吞吐量性能对比。上图为延迟(ms)，下图为吞吐量(tokens/s)，不同颜色代表两种设备（AGX Orin与Orin NX），部分方法出现OOM（内存溢出）情况。

Fig. 8. Impact of Bandwidth to Throughput of Collaborative LLMs Inference

观察与分析：

1. 延迟方面 (图 7):

   • 除了 Edge-Solo（其性能不依赖于云边带宽），其他三种协作方法（Cloud-Edge-Even、Cloud-Edge-Opt 和 EdgeShard）的延迟都随着带宽的增加而降低。这是因为带宽增加减少了数据传输时间。
   • 当云源带宽从 1Mbps 增加到 10Mbps 时，协作方法的延迟显著降低；但从 10Mbps 到 50Mbps，延迟变化不大。这表明带宽在 10Mbps 左右达到饱和，计算时间成为瓶颈。
   • 当带宽大于 10Mbps 时，云边协作方法（Cloud-Edge-Even、Cloud-Edge-Opt）性能优于 Edge-Solo，因为它们引入了强大的云服务器进行计算加速。
   • 当带宽为 1Mbps 时，Cloud-Edge-Even 性能比 Edge-Solo 更差，因为高通信成本抵消了云服务器的优势。此时 Cloud-Edge-Opt 会选择本地执行，与 Edge-Solo 性能相同。
   • EdgeShard 与 Cloud-Edge-Opt 的关系: 当带宽大于 10Mbps 时，EdgeShard 和 Cloud-Edge-Opt 的延迟几乎相同。这是因为 EdgeShard 在这种情况下会生成与 Cloud-Edge-Opt 相同的模型分片和分配策略（即主要利用云服务器进行加速），因此性能趋同。这表明 Cloud-Edge-Opt 可以看作是 EdgeShard 的一个特例。
   • Llama2-70B 的比较: 对于 Llama2-70B，EdgeShard 优于其变体 EdgeShard-Even（模型均匀分片到所有参与设备）。这强调了 EdgeShard 自适应分片策略在异构资源（云服务器与边缘设备）环境中的优势。

2. 吞吐量方面 (图 8):

   • 对于 Llama2-7B 模型，吞吐量的变化模式与延迟相似。
   • Llama2-13B 的特殊表现: 当带宽为 10Mbps 时，EdgeShard 的吞吐量比 Cloud-Edge-Opt 高约 2 倍，并未表现出趋近。这主要是因为 Cloud-Edge-Opt 在这种情况下，由于 RTX 3090 和源节点 AGX Orin 的内存消耗高达 95% 和 98%，只能支持最大批量大小为 4，无法为 KV 缓存 提供足够的内存。而 EdgeShard 涉及多个边缘设备，显著降低了单个设备的内存消耗，从而允许更大的批量大小（在本例中为 8），带来了更高的吞吐量。
   • 当带宽高于 10Mbps 时，EdgeShard 在 Llama2-7B 上的性能与 Cloud-Edge-Opt 趋近，表明其采用了相似的部署策略。
   • 对于 Llama2-70B，EdgeShard 相比 EdgeShard-Even 吞吐量略有提升，EdgeShard-Even 保持稳定吞吐量，因为它采用均匀分片策略，不随带宽变化。

6.1.3. 源节点影响

实验测试了源节点（AGX Orin vs Orin NX）对推理延迟和吞吐量的影响，源节点与云服务器之间的带宽设置为 1Mbps。

以下是原文图 9，展示了源节点对延迟和吞吐量的影响：

该图像是图表，展示了Llama2-7B和Llama2-13B模型在不同方法下的吞吐量比较。图中分别以蓝色和橙色条形区分EdgeShard-no-bubble与EdgeShard-bubble两种方案，显现EdgeShard方案在吞吐量上显著优于Cloud-Edge方法。

Fig. 9. Impact of Source Node

观察与分析：

1. Orin NX 作为源节点时的 OOM 问题: 当 Orin NX 作为源节点时，Edge-Solo 和 Cloud-Edge-Even 方法均遭遇 OOM 错误。这是因为 Orin NX 的内存相对较小（16GB），无法容纳 Llama2-7B 模型的完整版本，甚至无法容纳其一半。
2. Cloud-Edge-Opt 的性能差异: 在 Cloud-Edge-Opt 方法下，源节点为 AGX Orin 与 Orin NX 之间的延迟差距约为 60ms。这是由于 Cloud-Edge-Opt 倾向于将更多的模型层放置在源节点上（尤其是在带宽受限的 1Mbps 情况下），而 AGX Orin 的计算能力远强于 Orin NX，因此性能差异显著。
3. EdgeShard 的性能差异: 在 EdgeShard 方法下，源节点为 AGX Orin 与 Orin NX 之间的延迟差距仅约 5ms。这表明 EdgeShard 能够更好地利用网络中的其他设备。即使源节点计算能力较弱（如 Orin NX），EdgeShard 也能通过涉及更多设备并减少在源节点上的模型层数，有效弥补源节点的计算能力差距，从而减小源节点异构性带来的影响。
4. 吞吐量方面: 类似现象也出现在吞吐量上。在 Cloud-Edge-Opt 方法下，AGX Orin 作为源节点的吞吐量比 Orin NX 高 6 倍；而在 EdgeShard 方法下，这个差距缩小到 2 倍。这再次证明了 EdgeShard 能够充分利用网络中的所有计算资源来优化整体性能。

6.1.4. 流水线执行策略影响

实验评估了两种流水线执行策略 (EdgeShard-Bubble 和 EdgeShard-Nobubbles) 的效果，云服务器与源节点之间的带宽设置为 1Mbps。

以下是原文图 10，展示了流水线执行策略对性能的影响：

该图像是图2的示意图，展示了LLM推理的自回归性质。图中用不同颜色区域区分了预处理(prefill)和自回归生成过程，自回归阶段利用KV缓存实现逐步生成词语。

Fig. 2. LLM inference has an autoregressive nature. 注：这里原文的图像标题为 Figure 10，但图片文件名为 images/2.jpg，且其内容与文字描述（吞吐量对比）不符，而是展示了LLM推理的自回归性质。图10的正确图片在images/10.jpg中，描述为Llama2-7B和Llama2-13B模型在不同方法下的吞吐量比较。

正确引用图 10：

该图像是图表，展示了Llama2-7B和Llama2-13B模型在不同方法下的吞吐量比较。图中分别以蓝色和橙色条形区分EdgeShard-no-bubble与EdgeShard-bubble两种方案，显现EdgeShard方案在吞吐量上显著优于Cloud-Edge方法。

10.Impact of Pipeline Execution Strategy

观察与分析：

1. EdgeShard-Nobubbles 优于 EdgeShard-Bubble: 对于所有适用的方法，EdgeShard-Nobubbles 的性能均优于 EdgeShard-Bubble。
   • Llama2-7B: EdgeShard-Nobubbles 在 Cloud-Edge-Even 上吞吐量提升约 0.36 词元/秒，在 EdgeShard 上吞吐量提升约 6.96 词元/秒。
   • Cloud-Edge-Opt: 在带宽为 1Mbps 的情况下，Cloud-Edge-Opt 选择了本地执行，因此没有流水线执行，两种策略的吞吐量相同。
   • Llama2-13B: EdgeShard-Nobubbles 在 Cloud-Edge-Even 上吞吐量提升约 1.69 词元/秒，在 Cloud-Edge-Opt 上提升约 1.89 词元/秒，在 EdgeShard 上提升约 5.21 词元/秒。
2. 原因分析: EdgeShard-Nobubbles 通过允许立即生成 词元 而无需等待所有微批次在一个迭代中完成，有效地减少了设备的空闲时间，从而提高了吞吐量。这证实了其在缓解流水线气泡方面的有效性。

7. 总结与思考

7.1. 结论总结

本研究提出了 EdgeShard 框架，旨在实现在协作边缘计算环境中对大型语言模型 (LLMs) 的高效部署和分布式推理。通过将设备选择和模型分片问题公式化，并设计动态规划算法来分别优化推理延迟和吞吐量，EdgeShard 成功应对了 LLMs 在边缘部署中面临的内存限制、高延迟、高带宽成本和隐私问题。

实验结果表明，EdgeShard 能够根据异构网络条件自适应地确定 LLM 的分片和部署策略，从而优化推理性能。它显著优于多种基线方法，实现了高达 50% 的延迟降低和 2 倍的吞吐量提升。尤其重要的是，EdgeShard 能够部署 Llama2-70B 等超大型模型，而这些模型在单边缘设备或简单云边协作下会遭遇内存溢出 (OOM)。

论文强调，EdgeShard 并非旨在取代基于云的 LLM 推理，而是通过利用无处不在的计算设备，提供一种灵活和自适应的 LLM 服务方法。实验还揭示了 EdgeShard 在云带宽不足时能够超越传统云边协作方法，并在云带宽充足时能实现与之相当的部署策略和性能。这项工作为协作边缘计算环境中的 LLM 部署开辟了新的研究方向。

7.2. 局限性与未来工作

作者在论文中指出了 EdgeShard 存在的一些局限性，并提出了未来的研究方向：

1. 激励机制 (Incentive Mechanisms):
   • 局限性: EdgeShard 假设设备可以协作进行推理。在智能家居或智能工厂等场景中，设备可能由同一利益相关者拥有，协作相对容易。然而，如果设备属于不同的利益相关者，他们可能不愿意共享计算资源。
   • 未来工作: 需要研究设计合适的激励机制，以奖励资源共享，从而促进更广泛的设备协作。
2. 批量大小感知优化 (Batch Size Aware Optimization):
   • 局限性: 较大的批量大小会增加内存使用，进而影响推理吞吐量。尽管实验表明通过分片可以减少单个设备的内存使用，从而允许更大的批量大小并提高吞吐量，但当前设计的动态规划算法并未直接将批量大小的影响纳入其优化考虑。
   • 未来工作: 未来的研究可以探索如何将批量大小作为动态规划算法中的一个优化变量，从而进一步提升性能。

7.3. 个人启发与批判

7.3.1. 个人启发

• 协作边缘计算的巨大潜力: EdgeShard 证明了 CEC 在解决 LLM 部署挑战方面的巨大潜力。通过整合异构、分布式的边缘设备和云服务器资源，可以在不牺牲模型精度的情况下，实现 LLM 的高效推理，这对于实时应用、隐私敏感场景和带宽受限环境至关重要。这为未来 AI 在边缘的普及提供了新的思路。
• 异构性管理的重要性: 边缘计算环境的本质是异构性。EdgeShard 的成功在于其能够自适应地管理这些异构的计算和网络资源，而不是简单地假设同构环境。这表明在设计边缘 AI 解决方案时，将资源异构性作为核心考量至关重要。
• 动态规划在资源调度中的有效性: 论文将复杂的设备选择和模型分片问题巧妙地建模为动态规划问题，并设计了有效的算法。这启发了在其他分布式系统资源调度和任务分配问题中应用类似优化方法的可能性。
• 多目标优化的权衡: EdgeShard 同时考虑了延迟和吞吐量两个核心性能指标，并提供了相应的优化算法。这展示了在实际系统中，往往需要进行多目标优化和权衡。
• EdgeShard-Nobubbles 的实用价值: 对流水线气泡的优化 (EdgeShard-Nobubbles) 是一个非常实用的改进。在 LLM 自回归推理的背景下，最大限度地减少设备空闲时间对于提高吞吐量至关重要，该策略提供了一个有效的解决方案。

7.3.2. 批判与潜在改进

• 吞吐量算法复杂度: Algo. 2 的计算复杂度为 $O(N^2 \times 2^M \times M^2)$。虽然对于论文中 $M=15$ 个设备的测试平台是可行的，但如果 $M$ 显著增加，例如在未来大规模 CEC 网络中，该算法的指数级复杂度将成为瓶颈。未来的研究可能需要探索近似算法、启发式算法或基于学习的调度方法来处理更大规模的设备集。
• 实时动态性挑战: 论文中的 Profiling 是一个离线步骤，并且动态规划算法是在调度优化阶段一次性生成部署策略。然而，实际的边缘网络环境是高度动态变化的，包括设备可用性、网络带宽波动、任务负载变化等。当前的框架可能难以实时适应这些动态变化。未来可以探索在线调度、周期性重调度或基于强化学习的自适应调度策略。
• 内存约束的细化: 在 Algo. 1 的伪代码中，内存检查 $Mem_j < Req_i$ 显得有些过于简化。虽然 $Req_i$ 指的是单层内存需求，但公式 (5) 表明内存约束是累积的。在实际实现中，动态规划的每个状态都需要维护分配给该设备的所有层的累积内存使用情况，以确保在路径的每一步都满足内存限制。如果伪代码没有完全体现这一点，可能在实际实现上会更复杂。
• 隐私保护的深入探讨: 论文提到了隐私担忧是推动边缘部署的动机之一，并且通过将第一层固定在源节点以避免原始输入传输。然而，对于模型分片本身，中间激活值在设备间的传输是否会泄露敏感信息，以及如何进一步保障分布式推理过程中的数据隐私和模型隐私，这些方面可以进行更深入的探讨和机制设计。
• 批量大小和 KV 缓存的更精细管理: 批量大小对 KV 缓存 的内存需求有显著影响。虽然实验中提到了 EdgeShard 通过分散内存需求来支持更大的批量，但未来的工作可以将其更显式地集成到优化问题中。例如，动态规划算法可以尝试共同优化分片策略和每个设备的批量大小，以实现整体最优。
• 模型异构性: 论文主要关注不同设备上的同一 LLM 的分片。如果未来需要支持不同大小、不同架构的 LLMs 在同一 CEC 环境中并发运行，那么调度问题将变得更加复杂。
• 可靠性和容错性: 分布式系统面临设备故障和网络中断的风险。EdgeShard 框架目前似乎未明确考虑这些情况下的可靠性和容错机制。未来的工作应探索如何使 EdgeShard 在不稳定的边缘环境中更加鲁棒。