稀疏模型推理加速在美团推荐系统中的实践

如果无法正常显示，请先停止浏览器的去广告插件。

1. 稀疏模型推理加速在美团推荐系统中的实践王敬宇北京邮电大学计算机学院（国家级示范软件学院）网络与交换技术全国重点实验室 2023年11月

2. 个人及团队简介王敬宇北京邮电大学教授/博导、万物有灵战队负责人北京市青年英才、南京市紫金山英才、华为智库专家、IEEE/CIC Senior Member ➢ 依托平台：网络与交换技术全国重点实验室-网络智能研究中心，国重主任张平院士，国家杰青廖建新教授，团队入选“创新团队”及“创新研究群体” ➢ 研究领域：网络智能化（知识定义意图网络、智能运维）、机器学习系统（模型编译、加速与分布化）和人机交互（语义理解、手势控制） ➢ 科研项目：主持国家自然科学基金重点项目，国家973计划课题、国家自然科学基金面上项目、北京市自然科学基金、中国移动/华为公司/国家电网等产业化项目20余项，所研发的系统在中国移动、国家电网、CNCERT等实现规模化应用。 ➢ 成果奖励：顶会AAAI 2023杰出论文奖，IEEE System Journal最佳论文奖，团队成员获得SIGCOMM 2022唯一最佳论文奖（亚洲首次），荣获中国通信学会科学技术奖一等奖2项，全球AITrans、ACM MM、SemEval、ICCV挑战赛冠军 ➢ 成果发表：发表IEEE/ACM期刊和CCF高水平论文200余篇，包括ToN、JSAC、 NSDI、CVPR、ACL等CCF A类论文，出版《智慧服务云网络》，ITU-T、ETSI ENI、TMF、CCSA等组织参与标准化10余项，6GANA TG5（智能管控）主席。 2

3. 1 目录 CONTENTS 稀疏模型部署的技术挑战 2 美团推荐推理的现状分析 3 对美团推荐系统的加速实践 4 未来展望与总结

4. 01 稀疏模型部署的技术挑战

5. 机器学习系统MLSys的重要性 ML Systems instead of ML algorithms? How to make algorithms work with other parts to solve real-world problems？ 5

6. 机器学习系统编程模型的演进如何设计易用且高性能的API接口，一直是系统设计者首要解决的问题。为了支持在不同应用中高效开发机器学习算法，人们设计和实现了机器学习框架。 6

7. 机器学习模型转换不同的训练框架都定义了自己模型的数据结构，需要将它们转换到统一的数据结构上，需要解决训练模型到推理模型的转换，将训练好的模型部署到运行环境中进行推理。 7

8. 机器学习模型编译模型部署需要考虑模型推理的时延、功耗、内存占用等指标对整个系统的影响，通过各种编译器（如TVM），生成对模型和硬件最适合的机器代码。 8

9. 算子编译与调度执行对于一个张量算子，存在许多逻辑上等效的实现，但于线程、内存重用、流水线和其他硬件因素的差异，性能有很大差距，且需要大量的手动调整，无法跨硬件设备移植。 9

10. 基于计算图的机器学习框架机器学习系统设计者需要一个通用的数据结构来理解、表达和执行机器学习模型，基于计算图的机器学习框架应运而生，提高机器学习框架推理复杂模型的效率。 10

11. 深度学习框架的模型算子库 • 深度学习框架依靠计算图的中间表示来实现优化，例如自动微分和动态内存管理。但是，计算图级别的优化通常过于高级，无法处理特定硬件后端的算子级转换。 • 即使在当前受支持的硬件上，开发深度学习框架和模型也受到库中优化算子集合的限制，从而产生了不受支持算子的优化（例如计算图优化和算子融合）。 11

12. 目标：提高模型推理的速度和自动化程度希望在引擎层，以系统化的方式提供计算图算力密度的评估机制，以及更多通用的算子融合与替换等策略，提高GPU模型优化过程中的自动化程度。时延约50ms，加速直接影响着用户数！大体上每快10%的结果输出速度，就能多留存10%的用户。 • 目前GPU性能没有很好的充分利用，希望能提出更全面的方案，能够进一步发挥 GPU平台的推理加速潜力，并且具有很好的通用性和迁移性。 • 在目前已有的在线推荐类模型上获得比手工优化策略更通用的优化策略，甚至更优的加速表现，对高并发低延迟场景业务，实现深度学习推理服务加速。 12

13. 当前产业/学术界的解决思路当前的解决思路：合并算子，减少GPU kernel数量该方向学术界代表性的团队，有Stanford大学的Matei Zaharia教授团队，MIT的Song Han实验室以及国内微软亚研院。这些团队开辟了该领域的研究，计算图级别优化将计算图中的算子视为基本单元，并在计算图级别执行优化，而无需更改算子的内部实现。计算图级别的常见优化包括布局优化、算子融合、常数折叠、自动批处理、自动生成图替换等。比如SOSP 2019 的TASO，OSDI 2020的Rammer，KDD2022的LION，OSDI 2022的REEF等。 13

14. 挑战：算子粒度过小，造成I/O损耗较大 • 问题：模型中算子粒度过小，导致GPU在高并 • 难点：手工的方法适应范围窄，且规则的发场景下，kernel launch以及kernel在卡上方式也比较少。模型中使用的custom op IO的损耗十分明显。此问题在离线试验环境以往往并未被主流优化工具，这使得TVM等及压测环境下已经验证出来，目前主要的思路推理加速工具难以对整个模型进行加速，是通过手工或者规则的方法减少kernel数量。造成模型的对应图结构零碎，效率不高。 14

15. 02 美团推荐推理的现状分析刨析问题-加速思路

16. 美团推荐模型执行流程 ❑ 推荐系统执行效率对业务收益至关重要用户请求用户请求 … 召回精排粗排重排 CTR 用户请求用户请求大量并发几十毫秒 CPM = ??? ∗ ??? 业务超时，返回空结果，平台收益下降 16

17. 美团推荐场景的稀疏模型从Embedding表中读取ID列表索引对应的数据，这类模型有着更低的计算密度和更大的模型规模，现有深度学习框架并没有针对稀疏模型有很好的优化。召回 RPC 排序 ? Id,Sex… 精准结果收益高正常用户请求稀疏特征神经网络 CPU 特征表 PoI RPC 稀疏特征 … GPU 特征表拼接，求和稠密特征内容数据库快速筛选用户感兴趣内容超时精准预测用户感兴趣内容空结果收益低 17

18. 推荐模型上线流程三个阶段模型训练编译优化运行调度 ❑ 训练完成后的模型性能不佳，难以满足线上部署要求。 CPU Kernel launch 1 10? s Kernel launch 2 10? s Kernel 1 4? s Kernel launch 3 10? s Kernel 2 4? s Kernel launch 4 10? s Kernel 3 4? s … Kernel 4 4? s … GPU 大量微小算子导致运行硬件利用率低下 18

19. 推荐模型上线流程三个阶段模型训练编译优化运行调度 ❑ 模型编译优化技术可大大提升推理效率且不影响模型精度。移除推理无关分支融合相邻算子 19

20. 推荐模型上线流程三个阶段模型训练编译优化调度优化 ❑ 调度优化可以减少推理时间，提高硬件利用率单Stream H2D Compute H2D RPC 纯GPU D2H Compute GPU推理 D2H 加速多Stream H2D Compute D2H H2D Compute 分流 RPC Batch 分桶 CPU推理 D2H GPU推理 Timeline 多流并行执行 CPU、GPU分流 20

21. 推荐模型上线流程与相关开源框架模型训练编译优化运行调度 • 大量微小算子 • 内存占用过高 • 算子实现不佳 ☹️ 线上难以直接部署 ? • 融合相邻小算子 • 移除推理无关分支 • 生成高效算子实现推理效率大幅提升 • 算子运行时调度 • 自动隐藏通信开销 ?? 进一步加速推理性能 21

22. 美团现网解决方案-现状 1 编译时优化手工优化手写算子替换 Embedding 优化图结构分析 2 自动编译 TF-TVM 编译优化常量折叠无效节点消除 PCIe传输优化流量调度 CPU/GPU分桶性能测试输出一致性校验组Batch 传输优化输入合并结果评估运行时调度执行系统计算图调度多级参数存储硬件资源线程池 CUDA Stream 22

23. 美团现网解决方案-分析 1 编译时优化未考虑模型设备信息 ❑ 算子的执行速度和具体设备强相关手工优化自动编译 CPU 手写算子替换 TF-TVM 编译优化 GPU Embeding 优化图结构分析 Op Execution Kernel launch Op Execution 常量折叠无效节点消除 PCIe传输优化结果评估 ❑ 跨设备数据传输同样影响模型执行 H2D 性能测试输出一致性校验 D2H Host Device 23

24. 美团现网解决方案-分析 ❑ 推荐模型计算图有大量分支结构 2 运行时调度流量调度未考虑计算图并行度 CPU/GPU分桶组Batch 传输优化输入合并 ❑ 推荐模型算子占用硬件资源较少 Grid Size 数量比例 [0,56] 23240 95.1% (56, +∞] 1216 4.9% 24636 100% 总和 • • 56为A30推理卡中流多处理器的数量共26个模型执行系统计算图调度多级参数存储硬件资源线程池 CUDA Stream 24

25. 模型推理加速的技术路线目标：提升高并发场景下大规模推荐模型系统的推理服务效率研究内容1：推荐模型的异构设备推理（编译优化）算子评估通信开销端到端测试研究内容1-1：耗时建模研究内容1-2：异构执行实现理论研究内容2：推荐模型的线上推理调度（运行调度）调度策略研究内容2-1：调度算法研究内容2-2：并发执行负载估计高性能硬件执行 25

26. 03 对美团推荐系统的加速实践编译优化—调度优化

27. 编译优化-动机：推荐模型推理的设备异构加速 ❑ 美团推荐系统常常会包含接收稠密输入和稀疏输入的模块，模块中不同算子对于资源的依赖度不同，为每个算子寻找最优的目标设备是推理加速领域至关重要的问题。预测结果推理总时间 ? = ? ??? + ? ????? + ? ??? 跨设备 GPU CPU 计算时间传输时间计算时间 Softmax … ✓计算密集 ? ??? ✓访存密集 Matmal … … [? 0 , ? 1 , … , ? ? ] 稠密输入 … ? ? ? ? ? ? [? 0 , ? 1 , … , ? ? ] 稀疏输入推荐模型结构示意图 ? ? Matmal ? ??? 算子在异构设备上运算 27

28. 编译优化-动机：推荐模型推理的设备异构加速 ❑ 某些GPU算子需要依赖大量由CPU算子产生的数据作为输入，启动时需要进行大量从CPU到GPU数据传输，即H2D通信。仅考虑算子执行速度来分配设备是不够的。 ? = ? ??? + ? ????? + ? ??? 大量H2D通信 28

29. 编译优化-相关工作：DNN的算子摆放 ❑ DNN 的自动化算子摆放是优化 DNN 推理加速的一关键问题。同构设备间异构设备间在已有的计算设备、通信环境、DNN结构等限制条件下建模寻找最优的执行策略设备2 CPU，GPU对不同的算子计算各有优势将Embedding层放置到CPU计算 NP-hard Embedding 稠密向量负责访存密集型设备1 设备3 PipeDream [1] 不支持图结构DNN 通用性稀疏输入 Balance IOS [2] 计算复杂度O( 计算复杂度 ? ? +? ?? ) × 负责 Convolution = MatMul 计算密集型 [1] D. Narayanan, A. Harlap, et al. Pipedream: generalized pipeline parallelism for dnn training. SOSP, 2019. [2] Yang Y, Phothilimtha P M, Wang Y R, et al. IOS: Inter-operation Scheduler for CNN Accelerating. MLSys, 2021 29

30. 编译优化-算法：推荐模型推理的设备异构加速 ❑ 基于推荐模型计算图，构建推理时延对应拓展图，寻找最优设备摆放策略。 ? 3 ? ??? 1 ? ??? 2 ? ??? ? ????? = ? ? ? , ? ? 4 ? ??? ? ? 2 1 ? ????? ? 1 1 ? ??? ? 4 ? 3 推荐模型计算图 + ? ??, ? ? ??? = ? ?, ? ? + ? ?, ? ? ? = ? ??? + ? ????? + ? ??? = ∑? ? , ? ∈ ? ? 4 ? 3 ? 2 ? ??? = ? ??, ? 2 ? ????? ? 1 ? + ? ? ? , ? ? 3 ? ??? 计算图对应扩展图 2 ? ??? 4 ? ??? ? 找到最优设备摆放策略 ⇓ 找到扩展图对应最小割（复杂度O(n 3 ）） 30

31. 编译优化-实现：推荐模型推理的设备异构加速 ❑ 基于美团现有的 CuFuncOp 进行改进，移除 TVM Runtime，避免异构推理中产生的额外跨设备通信开销。 TensorFlow CPU H2D TVMEngineOP GPU GPU D2H CPU TVM Runtime CPU H2D GPU D2H CPU GPU TVMEngineOp 作为 TF 内部的算子不支持输入输出tensor，拆解TVM Runtime计算图，使用 TF 分别执行 TVM 编译出的 CPU 算子和 GPU 算子。 TensorFlow CPU TVMFuncOp (CPU Op) GPU CPU … 移除 TVM … TVMEngineOp GPU CuFuncOP (GPU Op) 31

32. 编译优化-结论：推荐模型推理的设备异构加速 ❑ TVM子图测试结果：为了评估算法本身的表现，我们在TVM Runtime进行算法测试。相对于纯GPU执行，我们的算法平均提升8.72%。模型TVM子图原方案预测值优化后预测值原方案运行值优化后运行值实际加速比 ddgg2_0_1.pb 1381.52 1272.04 1417.39 1222.10 15.98% ddgg3_0_1.pb 1357.82 1298.93 1414.96 1320.98 7.11% ddgg4_0_1.pb 3408.64 3304.33 3523.09 3386.22 4.04% ddgg5_0_1.pb 2570.30 2634.94 2771.80 2638.88 5.04% ddgg6_0_1.pb 1989.12 1973.74 1913.14 1902.29 0.57% ddgg7_0_0.pb 450.00 435.00 481.00 470.00 2.34% ddgg7_0_1.pb 175.81 156.65 184.40 164.43 12.14% ddgg8_0_1.pb 5007.63 4829.25 5186.85 4233.55 22.52% Avg speedup 测试机器： CPU: Intel 8352Y GPU: Nvidia T4 8.72% 指标说明：预测值：算法根据算子的执行时间和数据传输时间给出的预测推理时间。运行值：实际运行计算图统计得到的真实推理时间 32

33. 编译优化-结果：推荐模型推理的设备异构加速 ❑ Tensorflow端到端测试结果：我们测试了数十个现网模型，并在TensorFlow全图场景上的端到端测试。对比原来的TVMEngineOP方案，我们优化之后可以观察到 mean和p99指标分别平均提升11.20%、19.10%。推荐模型 ddgg1 ddgg2 ddgg3 ddgg4 ddgg5 ddgg6 ddgg7 ddgg8 ddgg9 ddgg10 ddgg11 测试机器： CPU: Intel 8352Y GPU: Nvidia A30 优化前执行时间(ms) mean 9.472 4.654 9.574 8.17 7.097 6.991 8.225 3.216 3.403 5.767 3.595 p99 10.39 5.316 12.676 11.44 9.639 10.155 11.207 6.438 5.273 9.609 6.534 优化后执行时间(ms) mean p99 mean 22.41% 7.349 8.274 10.08% 4.185 4.868 19.70% 7.688 9.188 5.36% 7.732 10.92 9.14% 6.448 7.483 7.57% 6.462 8.718 20.06% 6.575 8.868 7.03% 2.99 4.653 12.11% 2.991 4.649 7.77% 5.319 8.008 1.47% 3.542 4.221 指标说明： mean：平均执行时间。 p99: 前99%请求完成时的执行时间。加速比 p99 20.37% 8.43% 27.52% 4.55% 22.37% 14.15% 20.87% 27.73% 11.83% 16.66% 35.40% 33

34. 编译优化-分析：推荐模型推理的设备异构加速 ❑ 减少数据传输开销以及合理摆放处理算子的设备，显著降低推荐模型的执行时间。 ⚫ CPU (图左) 在处理小算子时比 GPU (图右) 更有优势。 ⚫ 合理选择执行算子的目标设备, 减少大量的数据拷贝开销。 CPU Input Input 1 Input 2 Input 3 Input 4 Input 5 Input 6 Input 7 TVMFuncOp GPU CuFuncOp 数据拷贝单输入 Op放GPU，加快计算速度 … Input n 多输入 Op放CPU，减少数据传输 CuFuncOp 34

35. 调度优化-动机：推荐模型的线上推理调度 ❑ 面对并发请求时，每个请求分别采用串行的方式将GPU算子逐个发射到同一 CUDA Stream上，导致请求执行时间增加。如何充分利用GPU计算图的并行度，并对多个请求的算子进行综合调度，成为优化线上服务系统的重要问题。用户请求执行流程 35

36. 调度优化-动机：推荐模型的线上推理调度可并行 ❑ 调度算法应该充分利用计算图并行度和GPU多流处理能力 ∑ ? ? ? T 平均 = 请求个数 5个请求同时到达 GPU计算图 GPU ……… 所有请求同一个流单流平均执行时间:26 +多流 GPU 每个请求单独一个流多流平均执行时间: 8 +调度 GPU 每个请求分布在多个流请求1 请求2 请求3 请求4 请求5 多流复用平均执行时间: 6.2 时间 36

37. 调度优化-算法：推荐模型的线上推理调度 ❑ 基于计算图和请求优先级的GPU多流复用算法多流复用系统 StreamManager 规则：1. 优先选择具有最高优先级的算子来执行 2. 根据算子属性以及GPU负载情况，分配最优流 ?????????? u = calc (???? ? , ????? u , ?????? u , ?????? u , ) ???? u = 1.0 + ෍ ?∈?(?) 1 GPU 1 3 4 2 5 6 2 3 4 请求2 N u = {v ∈ ?|(u, ?) ∈ ?} T0 5 算子执行顺序请求1 ???? ? , ???????? ? T1 T2 T3 算子C Stream 0 6 Stream 1 Stream 2 算子A 算子B 最优stream分配 37

38. 调度优化-实现：推荐模型的线上推理调度 ❑ GPU线程发射机制优化：可并行的GPU算子在不同的线程上进行发射，提高并行度单线程发射GPU算子多线程并行发射GPU算子 38

39. 调度优化-结果：推荐模型的线上推理调度 ❑ 在美团现网环境，高并发场景下（平均51k QPM），相对于现网使用的方案，我们基于算子级别调度的推理优化方案，有了平均11.56%的提升。 ddgg_model_1 单流（ ms ） 5.80 ddgg_model_2 5.92 38.92 62.6 5.16 37.54 64.6 12.84% ddgg_model_3 5.70 38.78 62.0 5.12 36.83 63.3 10.18% ddgg_model_4 6.78 14.01 37.3 6.42 13.40 36.5 5.31% ddgg_model_5 23.22 39.41 24.10 20.16 19.13 26.50 13.18% ddgg_model_6 2.82 38.88 44.6 2.70 36.27 44.8 4.26% ddgg_model_7 2.80 38.51 44.4 2.70 35.87 44.4 3.57% ddgg_model_8 9.82 39.32 49.2 8.30 39.04 51.8 15.48% ddgg_model_9 18.24 52.25 30.4 16.30 54.50 33.6 10.64% ddgg_model_10 10.98 39.30 47.7 8.12 39.18 51.8 26.05% 37.83 46.40 34.97 48.19 11.56% 模型平均值 GPU 占用率 QPM （ % ）（ k/min ） 38.88 61.7 测试机器： CPU: Intel 8352Y 多流复用（ ms ） 4.98 GPU: Nvidia A30 GPU 占用率 QPM （ % ）（ k/min ） 37.91 64.6 优化比例 14.14% 39

40. 调度优化-分析：推荐模型的线上推理调度 ❑ 充分利用CPU和GPU计算资源，且通过算子级别调度，使得更多属于不同任务的算子并行执行，减少不必要的等待，提高在高并发场景下的整体性能。 ⚫ 多流并行执行Kernel, 减少了模型执行时间多流复用，66微秒单流， 78微秒 ⚫ 处理并发请求，请求完成时间更短处理一批并发请求（450个）的完成时间开始时间（s) 结束时间(s) 持续时间(s) 平均执行时间（ms) 单流 8.75682s 10.3923 1.635 3.63 多流调度 8.33595 9.5239 1.18795 2.63 40

41. 04 未来展望与总结大模型化

42. 展望：大模型时代，关注点再次回到运行效率大模型召回与排序交互控制冷启动推荐系统推荐解释跨领域推荐利用大模型进行排序推荐 Prefill 阶段：对prompt(上下文)进行解析 Decode 阶段：自回归生成输出优化方案: 流水线并行 Tensor并行优化方向：扩展并行维度,提高GPU利用率计算密集型 GPU上SMs 使用情况仅在batch + attention head 维度上并行访存密集型扩展并行维度到 key/value序列计算任务拆分 running idle 42

43. 总结：从拖拉机自动变身成超级跑车已成功部署美团现网的推荐模型推荐加速10%，留存更多用户！修复TVM的设备分配逻辑，PR已经合并进主分支 [Bugfix] [Relay] Insertion of "device_copy" CallNode to Resolve Device Conflict on Unconstrained Nodes https://github.com/apache/tvm/pull/15090 合作论文已经发表于SPAA 2023（CCF-B）顶会论文不仅是自动驾驶，还能自动变型！ 43

44. NIRC 网络智能研究中心 NETWORK INTELLIGENCE RESEARCH CENTER 感谢关注期待讨论交流合作网络智能研究中心NIRC公众号联系人：王敬宇 wangjingyu@bupt.edu.cn