EdgeShard: Efficient LLM Inference via Collaborative Edge Computing
计 算 机 与 大 数 据 学 院 EdgeShard: Efficient LLM Inference via Collaborative Edge Computing EdgeShard: 通 过 协 同 边 缘 计 算 实 现 高 效 LLM 推 理 论 文 出 处 ： arXiv 发 表 时 间 ： 2024-05-23 作 者 ： Zhang Mingjin, Cao Jiannong, Shen Xiaoming, Cui zeyang 作 者 单 位 ： 香 港 理 工 大 学 汇 报 人 ： 常 情 阔 日 期 ： 2024-10-24
摘要
计 算 机 与 大 数 据 学 院 摘 要 背 景 ： 大 型 语 言 模 型 （ LLMs ） 在 自 然 语 言 处 理 和 内 容 生 成 方 面 展 现 出 了 巨 大 的 潜 力 。 然 而 ， 当 前 的 LLMs 严 重 依 赖 云 计 算 ， 导 致 延 迟 时 间 长 、 带 宽 成 本 高 以 及 隐 私 问 题 。 边 缘 计 算 有 望 通 过 在 靠 近 数 据 源 的 边 缘 设 备 上 部 署 LLMs 来 解 决 这 些 问 题 。 作 者 提 出 ： 使 用 边 端 协 作 的 方 式 来 促 进 边 缘 设 备 和 云 服 务 器 之 间 的 工 作 ， 以 联 合 执 行 高 效 的 LLM 推 理 。 即 ： EdgeShard 框 架 。 它 将 LLM 模 型 划 分 为 碎 片 并 部 署 在 分 布 式 设 备 上 。 EdgeShard 框 架 作 用 ： 是 将 LLM 模 型 划 分 为 碎 片 并 部 署 在 分 布 式 设 备 上 。 为 了 实 现 高 效 的 LLM 推 理 ， 我 们 提 出 了 一 个 自 适 应 的 设 备 选 择 和 模 型 分 区 问 题 ， 并 设 计 了 一 种 有 效 的 动 态 规 划 算 法 来 分 别 优 化 推 理 延 迟 和 吞 吐 量 。 在 异 构 物 理 原 型 上 的 Llama2 串 行 模 型 实 验 表 明 ， EdgeShard 相 比 基 线 方 法 最 多 可 以 减 少 50% 的 延 迟 ， 并 将 吞 吐 量 提 高 2 倍 。
引言
计 算 机 与 大 数 据 学 院 引 言 已 有 工 作 ： 1. 试 图 利 用 模 型 量 化 来 减 小 模 型 大 小 ， 以 适 应 资 源 受 限 的 边 缘 设 备 ， 但 这 样 会 导 致 准 确 性 下 降 。 2. 采 用 云 - 边 协 作 ， 但 可 能 受 到 不 稳 定 网 络 连 接 的 影 响 。 作 者 工 作 特 色 ： 1. 主 要 处 理 异 构 环 境 下 的 自 适 应 设 备 和 模 型 分 区 任 务 。 2. 使 用 了 动 态 规 划 算 法 来 计 算 推 理 延 迟 和 吞 吐 量 。 3. 使 用 与 序 列 化 处 理 的 过 程 不 同 的 流 水 线 并 行 推 理 方 式 。 【 Gpipe 机 制 】 4. 提 出 了 空 泡 的 方 式 来 优 化 流 水 线 并 行 处 理 。 【 但 未 讲 清 楚 ， 只 是 一 笔 带 过 】
背景知识
计 算 机 与 大 数 据 学 院 背 景 知 识 命 名 ： • 用 户 端 计 算 设 备 ： 终 端 ； • 网 关 等 边 缘 服 务 器 【 Edge Service 】 ： 边 端 ； • 云 服 务 器 【 Cloud Service 】 ： 云 端 。 • 模 型 划 分 【 model partition 】 ： 模 型 分 区 。 大 语 言 模 型 【 LLM ： large language model 】 组 成 ： • 一 个 嵌 入 层 ： 将 输 入 的 自 然 语 言 转 换 为 计 算 机 可 以 处 理 的 语 言 编 码 • 多 个 解 码 器 层 ： 包 括 自 注 意 机 制 、 前 馈 网 络 和 层 归 一 化 组 件 。 作 用 ： 依 据 输 入 的 数 据 生 成 下 面 的 回 答 。 • 一 个 输 出 层 ： 根 据 解 码 层 输 出 的 回 答 ， 映 射 到 词 汇 表 中 。 形 成 人 类 可 以 看 的 懂 的 回 答 。
框架结构----考虑在一个具有异构设备和带宽连接的通用协作边缘网络
计 算 机 与 大 数 据 学 院 框 架 结 构 ---- 考 虑 在 一 个 具 有 异 构 设 备 和 带 宽 连 接 的 通 用 协 作 边 缘 网 络 Device and Modle Profile Inference Task Scheduling Collaborative inference 预 处 理 阶 段 生 成 调 度 策 略 阶 段 模 型 部 署 和 推 理 阶 段
框架结构：预处理阶段
计 算 机 与 大 数 据 学 院 框 架 结 构 ： 预 处 理 阶 段 初 始 化 信 息 【 可 以 离 线 操 作 】 ： 模 型 的 每 一 层 在 各 个 设 备 的 执 行 时 间 ： • 执 行 时 间 采 用 预 填 充 阶 段 【 嵌 入 层 】 和 自 回 归 阶 段 【 多 个 解 码 层 】 生 成 一 个 token 所 需 的 时 间 ， 然 后 取 平 均 值 。 模 型 的 每 一 层 在 各 个 设 备 的 输 出 数 据 大 小 和 内 存 消 耗 的 大 小 。 每 一 个 设 备 的 可 用 内 存 大 小 和 各 个 设 备 之 间 的 带 宽 。 注 意 ： 因 为 一 台 设 备 的 内 存 可 能 不 足 以 存 储 一 个 模 型 ， 以 至 于 无 法 通 过 前 期 处 理 得 到 所 需 的 信 息 ， 故 而 文 章 采 用 了 动 态 内 存 加 载 的 技 术 【 dynamic model loading technology 】 。
框架结构----考虑在一个具有异构设备和带宽连接的通用协作边缘网络
计 算 机 与 大 数 据 学 院 框 架 结 构 ---- 考 虑 在 一 个 具 有 异 构 设 备 和 带 宽 连 接 的 通 用 协 作 边 缘 网 络 Device and Modle Profile Inference Task Scheduling Collaborative inference 预 处 理 阶 段 生 成 调 度 策 略 阶 段 模 型 部 署 和 推 理 阶 段
框架结构：生成调度策略阶段
计 算 机 与 大 数 据 学 院 框 架 结 构 ： 生 成 调 度 策 略 阶 段 生 成 调 度 策 略 的 目 标 ： 最 小 延 迟 或 者 最 大 吞 吐 量 。 针 对 延 迟 的 动 态 规 划 算 法 一 ： 输 入 ： 模 型 初 始 化 信 息 、 各 个 设 备 的 计 算 能 力 和 相 连 设 备 之 间 的 相 连 带 宽 。 输 出 ： 模 型 分 割 之 后 ， 各 个 模 型 层 部 署 的 策 略 。 针 对 吞 吐 量 的 动 态 规 划 算 法 二 ： 输 入 ： 模 型 初 始 化 信 息 、 各 个 设 备 的 计 算 能 力 和 相 连 设 备 之 间 的 相 连 带 宽 。 输 出 ： 模 型 分 割 之 后 ， 各 个 模 型 层 部 署 的 策 略 。
针对延迟的动态规划算法
计 算 机 与 大 数 据 学 院 针 对 延 迟 的 动 态 规 划 算 法 符 号 描 述 ： 总 延 迟 ： 延 迟 分 为 两 部 分 ： 计 算 延 迟 和 数 据 传 输 延 迟 其 中 X i,j 是 一 个 二 元 变 量 【 binary variable 】 如 果 第 i 层 部 署 在 第 j 个 设 备 上 ， 则 为 1 ， 反 之 为 0 。 总 目 标 ：
针对延迟的动态规划算法
计 算 机 与 大 数 据 学 院 针 对 延 迟 的 动 态 规 划 算 法 计 算 延 迟 的 最 优 子 结 构 ： DP(i,j) 表 示 模 型 的 第 i 层 分 配 给 第 j 台 设 备 的 情 况 下 ， 前 i 层 （ 包 括 第 i 层 ） 的 最 小 执 行 时 间 。 两 种 情 况 ： 分 别 是 最 后 一 层 和 非 最 后 一 层 ， 因 为 最 后 一 层 的 输 出 得 返 回 源 节 点 。 第 0 层 指 定 在 源 节 点 处 理 ：
针对吞吐量的动态规划算法
计 算 机 与 大 数 据 学 院 针 对 吞 吐 量 的 动 态 规 划 算 法 解 释 ： g(i, S, k) 代 表 在 设 备 集 S 中 处 理 模 型 前 i 层 【 first i layers 】 的 最 小 时 间 ， 并 且 最 后 一 个 被 使 用 的 节 点 是 k 。 公 式 13 表 示 模 型 第 0 层 ， 只 在 第 0 个 设 备 （ 即 源 节 点 ） 处 理 。 计 算 吞 吐 量 的 最 优 子 结 构 限 制 条 件 ：
框架结构----考虑在一个具有异构设备和带宽连接的通用协作边缘网络
计 算 机 与 大 数 据 学 院 框 架 结 构 ---- 考 虑 在 一 个 具 有 异 构 设 备 和 带 宽 连 接 的 通 用 协 作 边 缘 网 络 Device and Modle Profile Inference Task Scheduling Collaborative inference 预 处 理 阶 段 生 成 调 度 策 略 阶 段 模 型 部 署 和 推 理 阶 段
模型部署和推理阶段
计 算 机 与 大 数 据 学 院 模 型 部 署 和 推 理 阶 段 使 用 Gpipe 机 制 实 现 流 水 线 并 行 推 理 ： Gpipe ： 将 多 个 网 络 层 合 并 为 batch ， 然 后 batch 里 面 有 属 于 batch 的 所 有 层 的 权 重 ， 和 前 向 函 数 ， 然 后 利 用 自 动 符 号 微 分 技 术 ， 将 这 些 前 向 函 数 代 表 的 过 程 ， 整 合 为 一 个 过 程 。 从 而 能 够 同 时 计 算 多 个 layer 。 具 体 来 讲 ： 不 同 于 单 阶 段 计 算 LLM 应 用 ， 基 于 解 码 器 的 LLM 应 用 具 有 自 回 归 性 质 ， 其 中 会 有 多 个 token 需 要 生 成 ， 然 而 当 前 token 的 计 算 依 赖 于 所 有 的 先 前 token 。 所 以 在 获 取 先 前 生 成 的 token 之 前 ， 当 前 token 的 计 算 无 法 开 始 ， 这 会 导 致 管 道 执 行 的 瓶 颈 。 // 单 阶 段 计 算 应 用 可 以 理 解 为 一 个 函 数 ， 一 次 输 入 ， 一 次 输 出 。 // 而 自 回 归 性 质 可 以 理 解 为 多 层 函 数 ， 每 层 函 数 ， 都 会 利 用 其 上 一 层 函 数 的 输 出 以 及 原 始 输 入 。 提 出 空 泡 机 制 来 优 化 流 水 线 并 行 处 理 ： 因 为 流 水 线 处 理 时 ， 会 出 现 任 务 的 不 同 阶 段 处 理 速 度 不 同 的 情 况 ， 故 而 会 出 现 等 待 任 务 的 某 一 阶 段 的 情 况 。 等 待 的 过 程 ， 作 者 称 为 空 泡 。 然 后 作 者 提 出 EdgeShard-NoBubble 以 处 理 该 种 情 况 。 具 体 NoBubble 是 怎 么 做 的 ？ 作 者 没 讲 。
实验部分
计 算 机 与 大 数 据 学 院 实 验 部 分 物 理 配 置 ： 12 台 Jetson AGX Orin 、 2 台 Jetson Orin NX 、 1 台 RTX 3090 。 这 些 设 备 用 路 由 器 和 交 换 机 连 接 。 每 两 台 相 连 设 备 之 间 的 带 宽 都 是 1000Mbps 。 使 用 Linux TC tool 来 调 控 网 络 带 宽 ， 以 控 制 设 备 之 间 的 通 信 延 迟 。 模 型 ： Llama2-7B, Llama2-13B, Llama2-70B 四 种 模 型 分 区 方 式 ： Edge-Sole ： 部 署 在 本 地 的 边 端 服 务 器 。 Cloud-Edge-Even ： 将 模 型 平 均 的 分 配 给 边 端 和 云 端 。 Cloud-Edge-Opt ： 采 用 EdgeShard 的 模 型 分 区 策 略 ， 但 是 所 使 用 的 设 备 仅 有 两 台 。 （ 边 端 设 备 和 云 端 设 备 ） EdgeShard ： 测 试 指 标 ： 延 迟 和 吞 吐 量 没 有 采 用 只 使 用 云 端 服 务 器 的 基 准 实 验 ， 因 为 这 会 导 致 隐 私 问 题 。
实验部分----指定带宽
计 算 机 与 大 数 据 学 院 实 验 部 分 ---- 指 定 带 宽 带 宽 配 置 ： 边 端 节 点 和 云 端 之 间 的 带 宽 使 1Mbps 。 其 他 计 算 设 备 之 间 的 带 宽 设 置 为 50Mbps ， 误 差 为 20% 即 40Mbps - 60Mbps 。 OOM 即 （ out-of-memory ） ， 放 不 下 ， 运 行 不 了 。
实验部分----带宽变化
计 算 机 与 大 数 据 学 院 实 验 部 分 ---- 带 宽 变 化 边 端 节 点 和 云 端 带 宽 变 化 范 围 ： 1Mbps -> 50Mbps 延 迟 ：
实验部分----带宽变化
计 算 机 与 大 数 据 学 院 实 验 部 分 ---- 带 宽 变 化 吞 吐 量 ： 有 一 点 值 得 尤 其 注 意 ： Llama2-13B 模 型 中 ， 在 带 宽 为 10M 时 ， EdgeShard 的 吞 吐 量 突 然 剧 增 。 是 因 为 此 时 的 异 构 网 络 中 ， 可 以 使 用 更 大 的 批 次 -8 。 而 其 他 的 因 为 没 有 更 大 的 KV 空 间 ， 所 以 只 能 采 用 -4 。 可 以 理 解 为 运 算 节 点 因 为 很 多 ， 计 算 负 载 小 ， 所 以 可 以 使 用 较 少 数 量 的 大 batch 。 而 其 他 的 因 为 节 点 少 ， 每 个 计 节 点 的 计 算 负 载 大 ， 故 而 不 能 使 用 大 batch 。 还 有 一 点 值 得 注 意 ： 发 现 随 着 带 宽 的 增 加 ， EdgeShard 和 Cloud-Edge-Opt 的 表 现 逐 渐 趋 于 一 样 。 文 章 说 ： 这 是 因 为 当 带 宽 高 于 10Mbps 时 ， EdgeShard 倾 向 于 采 用 和 Cloud-Edge-Opt 相 同 的 分 区 策 略 。 具 体 为 什 么 ， 也 没 说 。 Llama2-70B 模 型 的 测 试 图 中 ， label ： EdgeShard-Even 应 该 改 为 ： Cloud-Edge-Even 。
实验部分----边端节点配置不同
计 算 机 与 大 数 据 学 院 实 验 部 分 ---- 边 端 节 点 配 置 不 同 分 别 使 用 AGX Orin 和 Orin NX 在 Latency 指 标 图 中 ， 之 所 以 在 EdgeShard 分 区 方 式 下 ， 不 同 的 源 节 点 配 置 不 同 ， 而 性 能 差 不 多 ， 是 因 为 EdgeShard 会 倾 向 于 将 更 少 的 模 型 层 放 在 源 节 点 。 故 而 对 源 节 点 的 配 置 要 求 不 高 。 也 就 是 说 ， 不 是 蓝 色 高 了 ， 而 是 黄 色 的 低 了 。 在 ThroughPut 指 标 图 中 ， 之 所 以 EdgeShard 的 分 区 策 略 对 模 型 吞 吐 量 性 能 的 提 升 没 有 Cloud-Edge-Opt 分 区 策 略 的 提 升 能 力 强 ， 是 因 为 EdgeShard 可 以 充 分 利 用 网 络 中 的 计 算 资 源 。 也 就 是 说 ， 不 是 蓝 色 的 低 了 ， 而 是 黄 色 部 分 在 EdgeShard 的 影 响 下 的 高 了 。 也 就 是 说 ， EdgeShard 可 以 在 源 节 点 较 低 配 置 的 情 况 下 ， 也 能 发 挥 出 较 好 的 性 能 。 个 人 认 为 ： 这 里 应 该 是 最 有 意 义 的 部 分 ， 因 为 它 可 以 让 较 低 配 置 的 边 端 节 点 也 能 发 挥 出 较 好 的 性 能 。
谢谢！
计 算 机 与 大 数 据 学 院 谢 谢 ！