推荐系统已成为日常生活中的重要组成部分，其通过在海量数据上训练推荐模型来学习用户偏好和物品特征，从而为电子商务^[1-3]、在线娱乐^[4-6]及社交媒体^[7-9]等领域提供个性化推荐服务，有效提升用户体验并驱动业务增长^[10-11]. 近年来，随着移动计算和互联网的快速发展，将推荐系统集成到物联网应用中以提供个性化推荐服务已成为一种发展趋势，如能源互联网中的能源管理推荐^[12-13]、健康监测中的健康建议^[14]，以及智慧旅游中的目的地智能推荐^[15]. 然而，传统基于云数据中心的推荐系统面临着双重挑战：一方面，集中式数据存储存在隐私泄露风险；另一方面，网络传输延迟可能影响服务质量^[16-19]. 为此，学术界和工业界近年来聚焦于将推荐模型的训练和部署从云数据中心迁移至边缘智能计算系统中，以在保障隐私数据安全和低延迟的前提下为物联网应用提供个性化推荐服务^[20-25]. 对于在边缘智能计算系统中部署推荐模型以提供推荐服务，文献[20]对模型推理过程中的流水线进行调度以提高吞吐量，为了降低推荐延迟，文献[21]提出了边缘推荐系统EdgeRec，其将淘宝的商品详情页访问量提高了9%. 对于在边缘智能计算系统中训练推荐模型，文献[23]利用边缘节点进行分布式参数聚合，文献[24]引入边缘节点存储隐私数据，文献[25]利用边缘节点训练推荐模型，并设计了边缘节点选择算法来优化模型准确率.

近年来，基于深度学习的推荐模型（deep learning recommendation models, DLRMs），如WDL^[26]和DFM^[27]，已成为构建推荐系统的核心技术^[28]. DLRM主要由嵌入层和多层感知机（MLP）层组成. 嵌入层是一个大规模的嵌入表，它将稀疏输入（例如用户ID和视频ID）转换为嵌入（向量）^[29-31]. 一般情况下，嵌入表的存储空间需求可达数十GB到TB，而MLP层通常只需要几MB到几百MB的存储空间^[32-33]. 因此，在训练DLRM时，一般采用参数服务器架构（PS）来处理占用大量内存的嵌入表. 具体来说，在PS架构中，使用一台或多台拥有大量内存的服务器（即参数服务器）维护全局嵌入表，在配有GPU的工作节点中缓存部分嵌入表（即嵌入缓存）. 在DLRM训练过程中，工作节点会从参数服务器拉取嵌入以及向参数服务器推送嵌入梯度，这一过程被称为嵌入传输. 在实际生产负载中，用于DLRM训练的单个训练输入样本中可涉及数千个嵌入^[34]，先前的研究和本文实验均表明，嵌入传输代价是DLRM训练过程中的瓶颈^[35]. 例如，本文使用Criteo Kaggle数据集^[36]训练WDL^[26]时，高达90%的时间用于嵌入传输，主导了整个训练周期.

本文目标是通过降低总嵌入传输代价来加速在边缘智能计算系统中训练DLRM. 对从数据加载器加载到每个工作节点的嵌入样本进行管理是减少嵌入传输代价的有效方法^[37-39]. 具体而言，利用现今常用的数据加载器中的输入样本预取功能^[40-41]，可以在当前训练迭代期间应用一个调度机制，将下一个迭代的输入嵌入样本调度到合适的工作节点上，以降低嵌入传输代价. 直觉上，调度机制应专注于提高工作节点上的缓存命中率，然而，不同于传统的文件缓存，在DLRM训练期间，工作节点会与参数服务器间进行嵌入传输，即存储在工作节点上的嵌入不是静态的，这导致缓存命中率的高低无法直接对应到总嵌入传输代价的大小，这给设计样本调度机制带来了挑战. 此外，边缘智能计算系统中的异构网络和资源受限等特点也带来了挑战. 本文将问题挑战总结如下：

1）代价组成. 本文采用不牺牲模型精度的批量同步并行方法（bulk synchronous parallel, BSP）^[42]对DLRM进行训练. 在每个训练迭代开始之前，每个工作节点的嵌入缓存中应确保存储有每个输入样本对应嵌入的最新版本. 如果嵌入的最新版本在缓存中不可用，则必须从参数服务器拉取（未命中拉取，Miss Pull）. 对于每次迭代，工作节点和参数服务器之间会按需同步嵌入梯度（更新推送，Update Push）. 此外，当达到嵌入缓存容量时，为了存储新的嵌入，须将部分嵌入替换出去，它们的梯度也需要被推送到参数服务器上（逐出推送，Evict Push）. 因此，嵌入传输代价来自Miss Pull、Update Push和Evict Push这3个操作. 所以，样本调度机制的设计应考虑上述操作带来的样本传输代价，而不是仅专注于优化命中率.

2）异构网络. 在边缘智能计算系统中训练DLRM时，工作节点与参数服务器之间的连接带宽一般显著低于云数据中心中所用网络的带宽（例如100 Gbps以太网或InfiniBand），此外，多个边缘工作节点通常通过异构网络连接到参数服务器. 例如，一些工作节点使用1 Gbps网络，而其他工作节点则通过5 Gbps网络连接到参数服务器，这导致不同节点与参数服务器间传输相同大小的嵌入的代价不同^[43-45]. 因此，对于嵌入传输代价，除了考虑Miss Pull、Update Push和Evict Push操作的数量外，还需要考虑工作节点与参数服务器之间的网络带宽.

3）资源受限. 在生产环境中，每次迭代通常涉及成千上万个嵌入样本，为这些样本做出调度决策会产生额外的资源消耗. 在边缘智能计算系统中，通常存在资源争用现象，即会有多个任务争用有限的资源^[46-47]. 所以，本文应对样本调度机制带来的额外的资源消耗进行考虑. 此外，本文专注于能及时准确地捕捉用户兴趣漂移和新兴趋势的在线DLRM训练^[33,48]，这要求调度决策必须在每次训练迭代内完成，以避免性能下降. 因此，在设计调度机制时，对调度机制的资源消耗和求解延迟的考虑是十分重要的.

先前的工作主要集中于降低在云数据中心中训练DLRM时的嵌入传输代价，未对边缘智能计算系统中的实际挑战加以考虑^[49-50]. 为解决上述实际挑战，本文提出了嵌入样本调度机制ESD，旨在将嵌入样本调度到合适的边缘工作节点上进行训练以减少总嵌入传输代价. ESD首先为每个样本计算在不同边缘工作节点上进行训练的预期传输代价，再基于预期传输代价将样本调度到合适的节点上. 为避免决策时间超过每个迭代的训练时间，同时平衡决策质量和资源消耗，本文提出了HybridDis作为ESD中的调度决策方法，它结合了资源密集型最优解法和资源高效的启发式解法. 本文主要技术贡献有3 点：

1）为在边缘智能计算系统中加速DLRM训练，本文首先形式化了DLRM训练过程中对嵌入样本进行调度以最小化总嵌入传输代价这一问题，本文是首个在边缘智能计算系统中优化嵌入传输代价的工作.

2）本文提出了ESD，一个通过计算将每个嵌入样本调度到不同工作节点上进行训练的预期代价来减少总嵌入传输代价的嵌入样本调度机制. 本文在ESD中提出了HybridDis，一个混合调度决策方法，旨在平衡决策质量和资源消耗，以应对资源受限挑战.

3 ）本文使用C++（包括CUDA）和Python语言实现了ESD原型系统，并在8个边缘工作节点上使用现实世界工作负载进行了广泛的实验评估. 评估结果显示，与LAIA^[37]相比，ESD可减少高达36.76%的嵌入传输代价，在端到端DLRM训练速度上可实现最高1.74倍加速.

1.   背景知识

针对本文的研究主题，本节将对边缘智能计算系统中的推荐模型、深度学习推荐模型系统架构和深度学习推荐模型训练过程中的嵌入传输代价的背景知识进行简要介绍.

1.1   边缘智能计算系统中的推荐模型

推荐系统现已成为电子商务和社交媒体等应用中不可或缺的一部分，其可提供个性化推荐以增强用户体验并推动业务增长^[51-52]. 通常，企业在云数据中心中对推荐模型进行训练和部署，云服务器基于所有用户数据训练模型，并在接收到推理请求时将推荐结果推送到用户的设备上. 尽管云数据中心可以提供近乎无限的计算能力，但其面临包括高资源消耗^[53]、公有网络访问依赖^[54]以及用户隐私泄漏^[55-58]等问题在内的挑战，这些问题降低了基于云数据中心训练和部署DLRM的可用度^[59]. 随着边缘计算的兴起，在边缘智能计算系统中训练和部署推荐模型成为了新兴趋势. 该模式在确保隐私保护和低延迟的前提下可为物联网应用（如能源互联网^[60]、健康监测^[61]以及智慧旅游^[15]）提供推荐服务. 例如，在能源互联网中，推荐系统可以提出能源管理解决方案并协助资源分配；在健康监测中，根据医疗历史和实时健康信息提供个性化的健康建议. 为保障数据安全，本文所用边缘工作节点和参数服务器使用隔离外部互联网的局域网进行连接. 这种方法使隐私数据保持本地化，在防止泄露的同时能够提供低延迟的推荐服务. 此外，本文专注于在线DLRM训练，在系统的初始化阶段，DLRM模型是基于由物联网设备（如摄像头和传感器）生成的历史数据上进行训练的，为了在推荐服务期间持续提供高质量的推荐，DLRM模型使用来自物联网设备的流数据在线连续训练和优化^[62-67]. 总的来说，本文聚焦于利用连接在同一局域网内的边缘工作节点和参数服务器进行在线DLRM训练，为物联网应用提供低延迟、隐私保护的个性化推荐服务.

1.2   深度学习推荐模型系统架构

深度学习推荐模型，如WDL^[26]、DFM^[27]、DCN^[68]和FLEN^[69]，将推荐决策建模为预测特定事件发生概率的问题，例如预测网络观众观看推荐内容（视频或音乐）的可能性. DLRM主要由嵌入层、特征交互层和多层感知机（MLP）层组成，如图1所示. DLRM的输入通常既包括稠密输入（如年龄和身高）也包括稀疏输入（如用户ID和音乐ID），这两种输入分别通过MLP层和嵌入层进行处理.

图  1  深度学习推荐模型系统架构

Figure  1.  Architectural of deep learning recommendation model system

下载: 全尺寸图片 幻灯片

1）嵌入层. 嵌入层实际上是由嵌入表组成的，每个嵌入表代表一个分类特征，而表中的每一行代表一个特定的ID（例如用户ID或音乐ID）. 嵌入表将每个ID转换为固定大小的向量，即嵌入，其中包含可训练的浮点数值.

2）多层感知机（MLP）层. MLP层执行多个全连接操作以处理稠密输入并处理来自特征交互层的输出. 它为单个用户-项目对提供点击率的概率，还包括了其他计算稠密型单元，如批量归一化等.

3）特征交互层. 特征交互是组合稠密特征和稀疏特征以捕捉它们之间复杂且非线性关系的过程[30]. 特征交互的输出将由后续的MLP层进行处理. 特征交互的操作包括平均、求和等.

1.3   深度学习推荐模型训练过程中的嵌入传输代价

在DLRM训练中，可在嵌入层和MLP层使用不同的通信方式. MLP层所占内存较少，可以被单个工作节点所容纳，因此，可在每个工作节点上都保留一份MLP层的副本，并使用全局规约（AllReduce）进行通信. 另一方面，嵌入层占用内存较多，可达TB级，因此将全局嵌入表存储在一个单独的工作节点上是不可行的. 为此，采用PS架构，即在拥有较多内存参数服务器中维护全局共享的嵌入表，而边缘工作节点则在其本地内存中缓存部分嵌入表，即使用PS通信^[70]. 然而，在这种设计之上应用不牺牲模型精度的批量同步并行（BSP）时，引入了高昂的嵌入传输代价^[71]. BSP训练是一种并行计算模型，它将计算组织成同步步骤，每个步骤包括局部计算、工作节点间的通信和全局同步屏障^[42]. 在每次训练迭代中，工作节点从参数服务器拉取嵌入，并根据需要将嵌入梯度推送回参数服务器. 在按照第5节所示默认设置进行的实验中，嵌入传输代价主导了训练周期，可占端到端训练时间的90%. 先前工作通过减少工作节点与参数服务器之间的嵌入传输次数^{[37,38,49,50]}或降低每次嵌入传输的代价^{[35,39,72,73]}来减少嵌入传输代价. 本文面向代价组成、异构网络和资源受限等挑战，旨在最小化边缘智能计算系统中DLRM训练期间的总嵌入传输代价，以加速DLRM训练. 本工作与前者类似，并与后者研究正交.

2.   系统模型和问题形式化

本节将介绍系统模型和问题的形式化描述. 表1列出了本文常用符号.

表  1  符号列表

Table  1.  List of symbols

符号	描述
$\mathcal{W}$	边缘工作节点集合
${\mathcal{E}}_{i}$	迭代${I}_{i}$的输入嵌入样本，${\mathcal{E}}_{i}=\{{E}_{1},{E}_{2},… ,{E}_{m\times n}\}$
${I}_{i}$	第$i$个训练迭代
$m$	每个工作节点的批量大小
${E}_{i}$	一个嵌入样本，${E}_{i}=\{{x}_{1},{x}_{2},{x}_{3},… \}$
${x}_{i}$	一个嵌入样本的ID
$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$	嵌入样本ID为${x}_{i}$对应的嵌入值（向量）
${D}_{tran}$	一个嵌入的数据量
${B}_{w}^{j}$	工作节点${w}_{j}\mathrm{和}\mathrm{参}\mathrm{数}\mathrm{服}\mathrm{务}\mathrm{器}\mathrm{间}$的网络带宽
${T}_{tran}^{j}$	工作节点${w}_{j}\mathrm{和}\mathrm{参}\mathrm{数}\mathrm{服}\mathrm{务}\mathrm{器}\mathrm{间}$传输一个嵌入的代价，${T}_{tran}^{j}=\dfrac{{D}_{tran}}{{B}_{w}^{j}}$

下载: 导出CSV 

| 显示表格

2.1   系统模型

1）边缘智能计算系统. 本文基于一个包含多个边缘GPU工作节点（简称“工作节点”）和一个参数服务器（PS）的边缘智能计算系统展开研究. 具体而言，该系统由$n$个工作节点组成，记为 $\mathcal{W}=\{{w}_{1}, {w}_{2},… ,{w}_{n}\}$. 这些工作节点通过以太网连接到参数服务器，带宽为5 Gbps或0.5 Gbps.

2）训练输入样本. 在深度学习推荐模型训练中，每个工作节点都关联一个数据加载器，其是一个负责预处理训练样本的CPU进程. 数据加载器可从本地内存、磁盘或网络流中加载训练样本. 对于每个训练迭代${I}_{t}$，数据加载器将一批输入样本划分成多个微批次分配给每个工作节点. 为了保持各工作节点之间的工作负载平衡，本文使用$m$来表示每个工作节点的批量大小. 因此，对于$n$个工作节点，每次迭代的总训练输入样本数为$m\times n$. 在$m\times n$个输入嵌入样本$\mathcal{E}$中，$\forall {E}_{i}\in \mathcal{E}$都是一个嵌入样本，其包含多个嵌入ID，即${E}_{i}=\{{x}_{1},{x}_{2},… ,\}$. ID类型的特征是对大规模类别信息的稀疏编码. 本文使用$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$来表示${x}_{i}$对应的嵌入值（向量）.

3）嵌入缓存. 当在边缘工作节点上训练DLRM时，每个工作节点存有MLP的一个副本，并在训练过程中使用全局规约进行同步. 所有的嵌入存储在参数服务器上的全局嵌入表中，而每个工作节点则缓存一部分嵌入表. 工作节点通过与PS传输嵌入来管理本地缓存，以保证本地嵌入表和全局嵌入表之间的一致性. 本文使用$r$来表示缓存比例，即缓存中的嵌入数量与总嵌入数量的比例.

4）工作节点和参数服务器间的按需同步. 在DLRM的BSP训练中，在工作节点上，每次训练迭代都需要存有所需嵌入的最新版本，为此，工作节点与参数服务器间频繁传输嵌入值和梯度. 按需同步是一种减少传输代价的方法. 具体来说，在迭代${I}_{t}$之后，不是将

所有嵌入梯度都推送到PS，而是在${I}_{t+1}$中使用按需推送. 例如，如果在迭代${I}_{t}$期间，嵌入$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$在工作节点${w}_{j}$上进行了训练，并且在${I}_{t+1}$中没有其他工作节点（${w}'\in \mathcal{W},{w}'\ne {w}_{j}$）接收到包含${x}_{i}$的样本，则工作节点${w}_{j}$不需要将嵌入$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$梯度推送PS. 相反，如果其他工作节点在${I}_{t+1}$中需要$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$，则工作节点${w}_{j}$需要将$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$推送到PS，而其他工作节点将其从PS拉取到它们的缓存中. 因此，当使用按需同步时，每个工作节点在从数据加载器接收训练样本后的每次迭代的过程如下：按需嵌入梯度推送，拉取本地缓存中不存在的最新嵌入，前向传播，反向传播，稠密参数全局规约同步.

5）模型一致性分析. 本部分将通过理论分析阐述在BSP中使用按需同步和对样本进行调度不会影响模型的准确性. 相比于普通的分布式训练，对嵌入进行调度引入了两个主要变化：特定的输入嵌入样本调度机制（相对于随机调度机制）和按需同步（相对于训练迭代后将每个嵌入的梯度都推送到参数服务器上）. 在BSP中，按需同步确保所有工作节点在即将到来的训练迭代中使用最新的嵌入，这与普通分布式训练的行为相同. 接下来证明BSP下对样本进行调度不会影响模型训练. 考虑到参数优化器遵循SGD算法^[74]，对于给定批次的 $m\times n$个训练样本，模型权重$y$的梯度计算公式如下：

其中，${\mathcal{E}}_{i}$表示该批次中的第$i$个训练样本，$L$表示损失函数. 根据式(1)，批次的梯度计算为每个训练样本的个体梯度之和. 由于个体梯度仅依赖于输入样本和当前模型权重，并且这些权重在本迭代开始前已在BSP下同步，因此将批次划分为$n$个微批次不会影响梯度结果.

对于式（2），其中，${E}_{ij}$是第$i$个微批次中的第$j$个训练样本（对于工作节点${w}_{i}$）. 因此，由调度机制生成的调度结果在整个训练过程中都保留了与BSP相同的梯度，并收敛到相同的模型.

2.2   问题形式化

本文的目标是减少推荐模型训练中的嵌入传输代价. 如图2所示，在DLRM训练中，使用按需同步时，嵌入传输的代价来自未命中拉取、更新推送和逐出推送. 在图2中，为了简单起见，本文使用数字来表示嵌入 嵌入ID 和嵌入值.

图  2  深度学习推荐模型训练过程中的Miss Pull、Update Push和Evict Push操作

Figure  2.  Miss Pull, Update Push, and Evict Push transmission operations in DLRM training

下载: 全尺寸图片 幻灯片

1）未命中拉取（miss pull）. 当从数据加载器接收到训练样本时，工作节点应该从本地缓存或 PS 中检索必要的嵌入，称为嵌入查找. 如果本次迭代所需的嵌入已在本地缓存中并且是最新版本，则无需从 PS 中拉取嵌入. 在缓存的语境中，这是缓存命中. 相反，如果所需的嵌入不在本地缓存中或者已经过期（即不是最新版本），则需要从 PS 中拉取，即导致缓存未命中. 缓存未命中会导致额外的嵌入传输代价，称为未命中拉取（Miss Pull），例如，在图2中，迭代${I}_{2}$中拉取 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{8}\right)$、$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{9}\right)$、$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{10}\right)$ 和 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{11}\right)$.

2）更新推送（update push）. 在使用按需同步时，梯度推送发生在每次迭 代的开始而不是每次迭代的结束. 对于一个工作节点，当接收到训练样本时，如果在前一次迭代中某些嵌入在其他工作节点上进行了训练，其他工作节点应将嵌入梯度更新推送到参数服务器. 例如在图2中的迭代${I}_{2}$，${w}_{3}$应将 ${x}_{9}$的嵌入梯度推送到参数服务器，以便在工作节点 ${w}_{2}$上对其进行训练.

3 ）逐出推送（Evict Push）. 除了缓存未命中导致的Miss Pull和按需同步引入的Update Push之外，当使用按需同步时，如果工作节点的缓存已满，则需要为新的嵌入留出存储空间. 在缓存替换（或逐出）期间，如果尚未同步的嵌入被替换出去，则需要将其梯度更新到PS. 这被称为Evict Push. 例如图2中迭代$I_3$将${\boldsymbol{Emb}}({\boldsymbol{x}}_5)$替换出去，需要把$x_5$的梯度推送到参数服务器上.

本文的目标是最小化所有迭代的总嵌入传输代价. 对于每次嵌入传输，本文假设每次嵌入拉取和推送的数据大小相同，用${D}_{tran}$来表示. 对于迭代${I}_{t}$，嵌入传输的数量为${T}_{num}^{t}.$ 当网络带宽为${B}_{w}$时，每个嵌入的传输代价 ${T}_{tran}=\dfrac{{D}_{tran}}{{B}_{w}}$.

问题 P:

3.   调度机制设计

本节将首先阐述ESD中输入嵌入样本调度的过程. 之后，在3.2节中介绍如何计算预期传输代价. 最后，鉴于边缘智能计算系统资源受限，介绍名为HybridDis的混合调度决策方法，该方法在资源消耗和求解质量之间进行平衡.

3.1   ESD中样本调度机制流程

图3展示了ESD中嵌入样本调度的过程. 具体来说，在训练迭代${I}_{t}$开始时，ESD根据${I}_{t+1}$ 的输入嵌入样本和每个工作节点上缓存嵌入的当前状态（是否缓存、是否为最新版本）为${I}_{t+1}$做出调度决策. 此外，基于该调度决策及各工作节点上缓存嵌入的当前状态，ESD可以生成每个工作节点在迭代${I}_{t+1}$ 中的更新推送（Update Push）计划，这一部分内容在图3中未展示. 由于本文专注于在线DLRM训练，因此${I}_{t+1}$的调度决策时间应小于等于${I}_{t}$的训练时间，以确保嵌入样本调度能够减少训练时间. 上述调度过程是在每个工作节点本地执行的，而不是由一个集中式的调度器执行，以此避免分发调度决策带来的额外开销.

图  3  ESD中的嵌入样本调度过程概览

Figure  3.  Overview of embedding samples dispatching process in ESD

下载: 全尺寸图片 幻灯片

当输入嵌入样本${E}_{i}$（${E}_{i}\in$ ${\mathcal{E}}_{i}$）在工作节点 ${w}_{j}$上进行训练时，其预期传输代价为 ${c}_{i}^{j}$，本文将嵌入样本调度到合适的工作节点上以最小化总的嵌入传输代价. 当基于预期传输代价调度嵌入样本时，决策过程会消耗边缘工作节点的资源，而这些资源是有限的并且可能受到多个任务的竞争. ESD引入了一种混合调度决策方法HybridDis，它结合了资源密集型最优算法（Opt）和启发式算法（Heu），以平衡求解质量（即总嵌入传输代价）和资源消耗. 例如，ESD($\alpha = 0.25$)表示25%的输入嵌入样本使用Opt进行调度决策，而剩余75%使用Heu. 本文分析了使用Heu时的调度误差，并使用${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}-\mathrm{m}\mathrm{i}\mathrm{n}$对输入嵌入样本进行划分，其中${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}$和$\mathrm{m}\mathrm{i}\mathrm{n}$分别代表在不同工作节点上训练同一嵌入样本 ${E}_{i}$的第二小和最小代价.

3.2   预期传输代价

本小节用于介绍如何计算预期传输代价. 由于每个工作节点上嵌入缓存的状态是可见的，并且当今的数据加载器可以为下一个迭代预取嵌入样本，可以计算将每个嵌入样本调度到每个工作节点的预期传输代价（如算法1中的第3到第9行所示）. 下面，通过一个例子来介绍预期传输代价的计算方法.

考虑在迭代${I}_{t}$开始时，开始计算下一个迭代${I}_{t+1}$的嵌入样本的预期传输代价. 如果输入嵌入样本${E}_{i}=\{{x}_{1},{x}_{2},… ,\}$被调度到工作节点 ${w}_{j}$ 进行训练，对于 ${x}_{i}$ 的嵌入值$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$，如果最新版本的$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$不在 ${w}_{j}$的缓存中，则需要执行一次Miss Pull操作，其代价为${T}_{tran}^{j}$ （第7行）. 此外，如果在迭代${I}_{t}$期间，其他工作节点上存有$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$的最新版本，在按需同步的设置下，另一个工作节点（${w}_{j'}$）需要将${x}_{i}$的梯度推送回参数服务器，因此${c}_{i}^{j}+={T}_{tran}^{j'}$，即将工作节点${w}_{j'}$把梯度推送回参数服务器的传输代价累加到${c}_{i}^{j}$上（第9行）. 这样，对于迭代${I}_{t+1}$，得到了将每个嵌入样本调度到不同工作节点的预期传输代价，并将这些预期传输代价存储在代价矩阵$\mathcal{C}$中. 对于算法1中的第6行和第8行，in表示 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$ 的最新版本在边缘工作节点的嵌入缓存中可用，而not in则表示不可用.

此外，在边缘智能计算系统中训练DLRM面临边缘工作节点与PS之间异构的网络带宽，即不同的工作节点与参数服务器间的网络带宽不同，从而导致${T}_{tran}^{j}$ 不同. 例如，在图2中的迭代${I}_{2}$ 中， ${w}_{2}$ 与PS之间的带宽为5 Gbps，而 ${w}_{3}$ 与PS之间的带宽仅为0.5 Gbps. 因此，从PS拉取 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{8}\right)$ 到 ${w}_{3}$ 的代价是从PS拉取 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{9}\right)$ 到 ${w}_{2}$ 的代价的十倍，即 ${T}_{tran}^{3}= 10 \times {T}_{tran}^{2}$.

算法1: ESD.

输入：一个迭代的输入嵌入样本$\mathcal{E}$，$\left|\mathcal{E}\right|=m\times n$，工作节点集合$\mathcal{W}$，代价矩阵$\mathcal{C}$；

输出：调度决策（$Decision$）.

① 初始化$Decision$；

② 初始化$\mathcal{C}$中所有的元素为0；

③ for each ${E}_{i}$ in $\mathcal{E}$

④ 　for each ${w}_{j}$ in $\mathcal{W}$

⑤ 　　for each ${x}_{i}$ in ${E}_{i}$

⑥ 　　　if ${x}_{i}$对应的嵌入$\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$ not in ${w}_{j}$

⑦ 　　　　${c}_{i}^{j}+={T}_{tran}^{j}$；

⑧ 　　　　if $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$ in ${w}_{j'}$

⑨ 　　　　　${c}_{i}^{j}+={T}_{tran}^{{j}'}$；

⑩$Decision$=HybridDis($\mathcal{C}$)；

⑪ return 调度决策（$Decision$）.

3.3   HybridDis

在获得代价矩阵$\mathcal{C}$之后，本小节专注于设计一种调度决策方法来得到使总嵌入传输代价最小化的调度决策.

在资源受限的边缘智能计算系统中，确保得出调度决策所需的时间短于每次迭代的训练时间是一个挑战. 本节首先明确了在CPU上顺序执行匈牙利算法（Opt）会导致求解时间过长的问题. 然后简要分析了使用CUDA编程并行化匈牙利算法的可行性. 为了平衡解决方案质量（即总嵌入传输代价）和资源消耗，本节介绍了一种资源高效的启发式方法Heu. Opt是最优解法但资源消耗高，Heu资源消耗低但求解质量差，因此，本文提出了一种结合Opt和Heu的混合调度决策方法HybridDis. 在HybridDis中，将Heu的调度误差作为分割代价矩阵的标准.

对于代价矩阵$\mathcal{C}$，可以使用匈牙利算法^[75]求解得到能最小化总嵌入传输代价的调度方案. 当每个工作节点的批量大小为$m$，工作节点数量为$n$时，代价矩阵$\mathcal{C}$的维度为$\left(m\times n\right)\times n$. 由于每个工作节点的批量大小为$m$，本文将$\mathcal{C}$的每一列扩展为$m$列，生成一个阶数为 $k$ （$k=m\times n$）的方阵$\mathcal{C}\mathcal{'}$，并将该方阵作为匈牙利算法的输入. 匈牙利算法的时间复杂度为 $O\left({k}^{3}\right)$ ^[76]. 如表2所示，当在CPU上运行匈牙利算法时，当每个工作节点的批量大小从32增加到1024时，执行时间从9毫秒增加到134.986秒，该延迟超过了每次迭代的训练时间，违反了每次求解时间不能超过训练时间的要求，即应在 ${I}_{t}$的训练时间内计算出${I}_{t+1}$ 的调度决策以避免增加端到端的训练时间. 经分析，匈牙利算法中，初始归约中的每行或每列减去最小值、初始匹配中的零元素覆盖以及矩阵调整期间的矩阵更新都可以并行化实现. 因此，本文使用CUDA并行实现了匈牙利算法，以确保调度决策的延迟保持在训练时间限制内^[76]. 表2所示的执行时间证明了这种并行化的有效性. 3.4节通过流程图的方式简要介绍了匈牙利算法，对于匈牙利算法的完整描述，请参阅[77-78].

表  2  在使用8个工作节点的情况下，不同批量大小，串行与并行实现的匈牙利算法执行时间

Table  2.  Execution Time Comparison Between Serial and Parallel Implementations of Hungarian Algorithm for Different Batch Size Per Worker when Using 8 Workers ms

每节点 批量大小	32	64	128	256	512	1024
CPU串行	9	62	528	3360	50976	134986
GPU并行	21	28	82	186	811	1385

下载: 导出CSV 

| 显示表格

尽管匈牙利算法可以提供最优调度决策以最小化每次迭代的总嵌入传输代价，但使用CUDA实现匈牙利算法会消耗有限且争用的GPU资源. 为了平衡调度决策质量和资源消耗，如算法2所示，本文提出了HybridDis，一种结合匈牙利算法（Opt）和启发式算法（Heu）的混合方法，用于将输入嵌入样本调度到边缘工作节点上. 算法2中的第9到第18行描述了启发式方法Heu. 在代价矩阵$\mathcal{C}$中，$ro{w}_{i}$ 表示将${E}_{i}$调度到$n$个工作节点的 $n$个预期嵌入代价，当该工作节点未达到其最大工作负载时，Heu贪心地将${E}_{i}$调度到预期代价最低的工作节点. 例如，如果 ${c}_{i}^{j}$是$\mathcal{C}$中$ro{w}_{i}$的最小值，则${E}_{i}$会被调度到节点${w}_{j}$上. 在本文中，为了避免不同工作节点之间的不平衡，每个工作节点处理$m$个嵌入样本，即$m$是每个工作节点的最大工作负载. 显然，这种方法不是最优的，根据定理1，最坏情况下的调度误差是 ${\mathrm{m}\mathrm{i}\mathrm{n}}_{\lfloor i/m\rfloor +1}-\mathrm{m}\mathrm{i}\mathrm{n}$，其中 ${\mathrm{m}\mathrm{i}\mathrm{n}}_{\lfloor i/m\rfloor +1}$和$\mathrm{m}\mathrm{i}\mathrm{n}$分别代表$ro{w}_{i}$中的第$\lfloor i/m\rfloor +1$小值和最小值.

为了平衡决策质量和计算效率，本文中HybridDis选取${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}-\mathrm{m}\mathrm{i}\mathrm{n}$作为划分标准. 具体来说，本文将具有较高${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}-\mathrm{m}\mathrm{i}\mathrm{n}$值（潜在调度误差）的$\alpha \times m\times n$ （$0\le \alpha \le 1$）行分配给Opt，而其余行则由Heu处理（算法2中的第2到第5行）. 这确保了潜在调度误差较大的嵌入样本由最优求解方法处理. 值得注意的是，划分标准是可替换的，可以根据具体需求进行调整. 根据实际DLRM训练场景中观察到的数据分布模式，可以使用其他指标，如${\mathrm{m}\mathrm{i}\mathrm{n}}_{3}-\mathrm{m}\mathrm{i}\mathrm{n}$、${\mathrm{m}\mathrm{i}\mathrm{n}}_{3}-{\mathrm{m}\mathrm{i}\mathrm{n}}_{2}$或行平均值.

算法2: HybridDis.

输入：一个迭代的输入嵌入样本$\mathcal{E}$，$\left|\mathcal{E}\right|=m\times n$，工作节点集合$\mathcal{W}$，最大负载$maxworkload=m$，代价矩阵$\mathcal{C}$，$\alpha$，负载列表$workload[1… n]$；

输出：$\mathcal{D}$. /*调度决策*/

① 使用0初始化负载列表$workload[1… n]$；

② 计算$\mathcal{C}$中每行的${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}-\mathrm{m}\mathrm{i}\mathrm{n}$；

③ 对$\mathcal{C}$中每行基于${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}-\mathrm{m}\mathrm{i}\mathrm{n}$进行降序排序；

④ ${\mathcal{C}}_{heu}\leftarrow \mathcal{C}$中$\left\lceil {\left|\mathcal{E}\right|\times \alpha} \right\rceil$到$\left|\mathcal{E}\right|$行；/*保留原始行号*/

⑤ ${\mathcal{C}}_{opt}\leftarrow \mathcal{C}$中0到$\left\lfloor {\left|\mathcal{E}\right|\times \alpha} \right\rfloor$行

⑥ 将${\mathcal{C}}_{opt}$中每列复制为$\left\lfloor {m\times \alpha } \right\rfloor$列；

⑦ $\mathcal{D}=$Opt(${\mathcal{C}}_{opt}$)

⑧ $maxworkload=m-\left\lfloor {m\times \alpha} \right\rfloor$

⑨ for each $ro{w}_{i}$ in ${\mathcal{C}}_{heu}$

⑩ 　　while True do

⑪ 　　　选择$ro{w}_{i}$中的最小值${c}_{i}^{j}$；

⑫ 　　　if $workload\left[j\right] < maxworkload$

⑬ 　　　　将${E}_{i}$调度到${w}_{j}$；

⑭ 　　　　将上述调度决策添加到$\mathcal{D}$；

⑮ 　　　　$workload\left[j\right]+=1$；

⑯ 　　　　break；

⑰ 　　　else

⑱ 　　　　将${c}_{i}^{j}$从$ro{w}_{i}$的可选范围删除；

⑲ return $\mathcal{D}$.

定理1 . 当使用Heu时，对于第$i$行$ro{w}_{i}$，最坏情况下的调度误差是${\mathrm{m}\mathrm{i}\mathrm{n}}_{\lfloor i/m\rfloor +1}-\mathrm{m}\mathrm{i}\mathrm{n}$，其中 ${\mathrm{m}\mathrm{i}\mathrm{n}}_{\lfloor i/m\rfloor +1}$和$\mathrm{m}\mathrm{i}\mathrm{n}$分别代表$ro{w}_{i}$中的第$\lfloor i/m\rfloor +1$小值和最小值.

证明. 在代价矩阵$\mathcal{C}$（$m\times n$行, $n$列）中, 每列代表一个节点，每节点最多可接受$m$个列（样本）被调度到自己这里来，$m$即$maxworkload$. 对于$ro{w}_{i}(0\le i\le m-1)$, 最坏误差为0，因为任意一个列都不会达到$maxworkload$. 对于$ro{w}_{i}(m\le i\le 2m-1),$ 最坏的情况如下， $ro{w}_{i}(0\le i\le m-1)$都被调度到同一个节点${w}_{{u}^{1}}$ ，而在$ro{w}_{i}(m\le i\le 2m-1)$中，最小值都是 ${c}_{i}^{{u}^{1}}$，而代表节点${w}_{{u}^{1}}$的列已经达到了$maxworkload$，那么对于$ro{w}_{i}(m\le i\le 2m-1)$, 只能选择次小值${\mathrm{m}\mathrm{i}\mathrm{n}}_{2}$. 对于$ro{w}_{i}(2m\le i\le 3m-1)$，类似地，当$ro{w}_{i}(0\le i\le m-1)$都被调度到同一个节点${w}_{{u}^{1}}$且$ro{w}_{i}(m\le i\le 2m-1)$都被调度到同一个节点${w}_{{u}^{2}}$, 而对于$ro{w}_{i}(2m\le i\le 3m-1)$，其最小值和次小值均是 ${c}_{i}^{{u}^{1}}$或${c}_{i}^{{u}^{2}}$，但${w}_{{u}^{1}}$和${w}_{{u}^{2}}$均达到了$maxworkload$，这导致$ro{w}_{i}(2m\le i\le 3m-1)$只能选择${\mathrm{m}\mathrm{i}\mathrm{n}}_{3}$，以此类推，对于$ro{w}_{i}\left(\mathrm{即}{E}_{i}\right)$，在最坏情况下的调度误差是${\mathrm{m}\mathrm{i}\mathrm{n}}_{\lfloor i/m\rfloor +1}-\mathrm{m}\mathrm{i}\mathrm{n}$，${\mathrm{m}\mathrm{i}\mathrm{n}}_{\lfloor i/m\rfloor +1}$和$\mathrm{m}\mathrm{i}\mathrm{n}$分别表示第$i$行$ro{w}_{i}$的第$\lfloor i/m\rfloor +1$小值和最小值. 证毕.

3.4   匈牙利算法求解流程

本文形式化的嵌入样本调度问题可被建模为二分图的最优匹配问题（总代价最小的匹配），即把$k$个嵌入样本分配给$n$个工作节点，并使分配的总代价最小. 由于每个工作节点的批量大小为$m$，本文将代价矩阵$\mathcal{C}$的每一列扩展为$m$列，生成一个阶数为 $k$ （$k= m\times n$）的方阵${\mathcal{C}}'$，则我们要做的是在这个矩阵${\mathcal{C}}'$中找到个数为$k$的一组独立元素（独立是指这组元素中任意2个元素不在同一行或同一列），并使这些元素的总代价最小，这组独立元素即为一个最优匹配. 文献[78]中陈述了2条定理：1）如果矩阵${\mathcal{C}}'$中最大独立0元素个数为$p$，则最少$p$条线可覆盖${\mathcal{C}}'$中所有0元素. 2）矩阵${\mathcal{C}}'$的每一行（或列）同时减去一个常数并不会影响算法最后的解. 依据这两条定理我们可以对这个问题进行变形. 通过对矩阵中的行和列减去该行或该列的最小值，可以在代价矩阵中创造出一些0元素，并且确保矩阵中元素均为非负，由定理2）可知此时问题的解不变. 根据定理1），即最大匹配等价于最小顶点覆盖，可通过该定理确定当前匹配是否为最大匹配.

因为我们需要求的是总代价最小的匹配，而此时矩阵中最小的元素是0，因此算法的思路是：通过在矩阵中不断创造新的0元素从而把最优匹配问题转化为完备匹配问题，即只把0元素作为二分图中的边，在这些边中找到完备匹配（让每个点都与一个边相连，即为所有的工作节点和嵌入样本找到一一对应的边）；那么算法最终的解一定是最优匹配（因为所有边代价均为0，总和一定是最小的）. 在本算法中，该解的形式为最大独立0的集合（个数为$k$），每个独立0即为一条匹配边.

算法流程图如图4所示. 初始阶段首先对矩阵进行行归约与列归约，即每行、每列减去该行、该列的最小值，形成一些0元素，并找到一组独立0（即一组匹配），标记为0*，需要注意的是这组独立0不一定是当前该矩阵的最大独立0集合（初始匹配）. 接下来尝试用经过0*的横线或竖线（每条线覆盖一整行、列的元素）来覆盖所有的0. 由定理1）可知，如果存在这样的线集合，则说明当前的0*集合即为当前矩阵的最大独立0集合，也即为当前二分图的最大匹配；如果不存在，则当前0*集合并非当前矩阵的最大独立0集合. 如果不能覆盖所有0，说明现在还不是最大匹配，则通过寻找增广路径的办法来增加匹配（独立0）的数量，该步骤一定会使0*的数量加1. 检查最新的0*集合，如果0*数量等于$k$，说明找到了完备匹配（即最优解），此时0*集合即为解集；如果0*数量 < $k$，则继续尝试用经过0*的横线或竖线来覆盖所有的0. 若能覆盖所有0，说明现在已经是当前二分图的最大匹配，但需要注意的是，目前还不是完备匹配. 由于当前矩阵最大独立0个数 < $k$，因此需要在矩阵中（未被覆盖的元素里）创造新的0来增加最大独立0的个数，即对未被覆盖的元素减去未被覆盖元素中的最小值，由定理2），可通过对未被覆盖的列减去该最小值，对被覆盖的行加上该最小值来实现.

图  4  匈牙利算法流程图

Figure  4.  Flow chart of Hungarian algorithm

下载: 全尺寸图片 幻灯片

4.   系统实现

本文在HET^[49]的基础上使用C++和Python实现了ESD的原型. 除了第3节中描述的设计外，ESD维护所有工作节点的缓存快照，以提供嵌入的信息. 这些缓存快照用于计算预期传输代价，并在调度结束时根据调度结果进行更新. 本文替换了HET中的数据加载器实现，ESD中的数据加载器返回嵌入样本和按需同步的嵌入ID作为稀疏输入. 为了支持不干扰训练过程的输入预取，ESD由专用线程启动，且ESD的调度决策通过共享内存传递给数据加载器 . 此外，本研究采用CUDA并行策略加速匈牙利算法，主要优化包括：1）在行列归约阶段，通过并行归约核函数并行计算每行/列的最小值，并利用线程块级并行完成矩阵减法操作；2）针对独立0元素的标记（初始匹配阶段），通过原子操作解决多线程竞争条件下的0元素标记问题，确保独立0元素标记的互斥性；3）矩阵更新时，利用并行归约定位未覆盖元素中的最小值，通过动态并行与块级分块策略优化内存访问模式，实现加减操作. 特别地，采用共享内存缓存技术优化全局内存访问模式，通过矩阵分块处理减少数据访存延迟.

5.   实验评估

本文使用如表 3所列的工作负载来评估 ESD 的性能. 与最先进的机制LAIA相比，ESD实现了至多1.74倍的加速比，并能将嵌入传输代价降低至多36.76%. 通过对每个工作节点的批量大小、缓存比例和嵌入大小进行敏感性分析，ESD始终优于基线方法. 所有实验均重复五次，取平均值作为最终结果.

5.1   实验设置

1）实验环境. 工作节点和参数服务器（PS）均配备了一颗28核心、主频为2.0 GHz的Intel Xeon Gold 6330 CPU以及64 GB（PS为500GB）的内存. 每个工作节点配备一块Nvidia 4090 GPU. 工作节点和参数服务器通过0.5 Gbps或5 Gbps的以太网连接. 所有机器运行Ubuntu 18.04，Python 3.8，CUDA 11.3，cuDNN 8.2.0，NCCL 2.8和OpenMPI 4.0.3. 实验环境中有8个边缘工作节点和1个参数服务器，其中4个工作节点通过5 Gbps以太网与参数服务器相连，另外4个则通过0.5 Gbps以太网连接与参数服务器相连. 默认情况下，嵌入大小为512，每个工作节点的批量大小为128、缓存比例为8%.

2） 基线方法. 本文将ESD与以下机制进行了比较：

HET ^[49]. HET是一个在参数服务器架构下通过跟踪嵌入版本以容忍有界陈旧性的嵌入缓存机制. 当检索嵌入时，会将本地版本与PS版本进行比较，如果差异超过阈值，则从PS拉取嵌入. 同样的方法也适用于梯度同步.

FAE ^[50]. FAE设计采用了静态缓存策略. 在训练前，缓存的嵌入会被离线分析并固定下来. 所有工作节点在FAE中缓存相同的嵌入，并使用全局规约同步所有缓存的嵌入.

LAIA^[37]. LAIA旨在多个云端工作节点之间调度嵌入. LAIA计算一个分数来量化每个输入样本与工作节点之间的相关性，并将每个输入分配给得分最高的工作节点.

HET和FAE通过牺牲一定的模型准确性来减少嵌入传输代价. 在本文的实验中，HET和FAE中采用批量同步并行. 在本节中，ESD是一个更通用的说法，无论$\alpha$为何值，均可以称为ESD. 具体来说，ESD($\alpha = 1$)、ESD($\alpha =0.5$)、ESD($\alpha =0.25$)、ESD($\alpha =0.125$)和ESD($\alpha =0$)分别代表具有不同$\alpha$值的机制. 这里的$\alpha$指的是HybridDis混合决策方法中Opt（匈牙利算法）和Heu（启发式算法）的分配比例. 不同的$\alpha$值反映了在求解质量和资源消耗之间不同的权衡策略. 例如，ESD($\alpha =1$)意味着完全采用Opt方法，而ESD($\alpha =0$)则表示完全使用Heu. 通过调整$\alpha$，可以在不同的应用场景下找到合适的配置.

3 ）负载. 如表3所列，本文使用3个负载（即S1，S2和S3）进行端到端实验，其中每个负载均由代表性的深度学习推荐模型和数据集组成. 为了排除初始阶段的影响，本文排除了最初的10次迭代作为预热，并报告随后迭代的性能表现. 本文没有展示模型准确率的结果，因为正如第1.1节分析的那样，ESD不会影响模型准确率. 表3所示的数据集均以用户行为日志（如广告点击、搜索转化）为核心，包含用户ID、设备信息、上下文属性等在内的匿名化的高维稀疏特征. 其中Criteo Kaggle数据集中每个样本有26个ID，总样本数为41256556；Avazu数据集中，每个样本有18个ID，总样本数为36386071；在Criteo Sponsored Search数据集中，每个样本有17个ID，总样本数为14 396 071.

表  3  实验所用负载

Table  3.  Workloads in Experiment

负载序号	所用模型	数据集
S1	WDL[26]	Criteo Kaggle[36]
S2	DFM[27]	Avazu[79]
S3	DCN[68]	Criteo Sponsored Search[80]

下载: 导出CSV 

| 显示表格

4）指标. 用于评估不同方法的性能指标是每秒训练迭代次数（Iterations per second, ItpS）和总嵌入传输代价（Cost）. 为了便于比较，使用LAIA的ItpS作为参考基准，其他机制的性能提升则以相对于这个参考值的比例来表示.

同样，LAIA也被用作减少嵌入传输代价的参考基准.

5.2   总体性能

本文首先评估了在默认设置下，ESD($\alpha =1$)、ESD($\alpha =0.5$) 和 ESD($\alpha =0$)的整体性能. 图5（a）展示了不同工作负载下，ESD($\alpha =1$)、ESD($\alpha =0.5$) 和 ESD($\alpha =0$)相对于基线方法的训练加速比.

图  5  总体性能

Figure  5.  Overall performance

下载: 全尺寸图片 幻灯片

观察发现，相比LAIA（用作参考且未在图5中显示），ESD可以实现1.03倍到1.74倍的加速. 具体来说，本文注意到随着$\alpha$值的减小，加速比也随之下降. 这是因为较大的$\alpha$值意味着更多的嵌入样本由Opt处理，从而降低了每次迭代的嵌入传输代价. 如图5（b）所示，与LAIA相比，ESD($\alpha =1$)可以减少至多36.76%的传输代价，而ESD($\alpha =0.5$) 和 ESD($\alpha =0$)分别将嵌入代价降低了10.81%和7.03%. 实验结果还表明，FAE和HET相比于LAIA表现较差. 因此，为了专注于ESD相对于LAIA的改进，本文在后续的实验分析中省略了FAE和HET的结果.

5.3   命中率和传输代价组成

为了探讨影响这些机制性能的原因，本文在图6中展示了命中率和嵌入传输操作的组成. 本文假设，若输入嵌入样本中存在${x}_{i}$且最新版本的 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$ 已经缓存于工作节点${w}_{j}$的嵌入缓存中，则视为一次命中. 命中率定义为相对于总查找次数的缓存命中的查找比例. 本文在图6（a）中展示了LAIA、ESD($\alpha =1$)、ESD($\alpha =0.5$) 和 ESD($\alpha =0$)的命中率. 与LAIA相比，ESD并没有实现更高的命中率. 然而，如图5所示，ESD相比LAIA降低了代价并加速了端到端训练. 这与引言部分讨论的内容一致，因为嵌入传输代价不仅来自于嵌入未命中，还来自于Update Push和Evict Push操作. 因此，更高的命中率并不一定能降低嵌入传输代价.

图  6  命中率和传输操作组成

Figure  6.  Hit ratio and ingredient of transmission operations

下载: 全尺寸图片 幻灯片

图 6（ b ）说明了不同机制的嵌入传输操作的组成，即未命中拉取（Miss Pull）、更新推送（Update Push）和逐出推送（Evict Push）操作在总传输操作中的比例. 在每个条形图中，底部三个部分代表5 Gbps工作节点的结果，而上部部分对应0.5 Gbps工作节点. 如图6（b）所示，与LAIA相比，ESD在所有三种工作负载下，5 Gbps工作节点的操作比例更大，而在LAIA中，5 Gbps工作节点的操作比例小于0.5 Gbps工作节点. 这表明ESD有效地考虑了异构网络的情况. 图6（b）还显示，未命中拉取和更新推送占嵌入传输操作的90%以上，而逐出推送的占比不到10%. 此外，实验表明，每节点批量大小的增加会使得未命中拉取的比例增加，缓存比例越大则逐出推送操作占比越少，嵌入大小的变化一般不影响各操作占比

5.4   代价降低和GPU资源消耗

由于边缘工作节点上的资源有限，本文提出了一种名为HybridDis的混合方法来决定输入嵌入样本的调度，其中$\alpha$表示使用Opt进行调度的比例.

图7展示了，当$\alpha$为1、0.5、0.25、0.125和0时，每个工作节点的批量大小分别为128和256时，代价降低和GPU 资源消耗（以GPU利用率表示，GPU利用越高表示该方法占用GPU资源越多）. 对于ESD($\alpha =0$)，GPU利用率为0. 当每个工作节点的批量大小为128时，如图7（a）所示，在不同工作负载下，较大的$\alpha$值会带来更大的代价降低和更高的GPU利用率. 在S1工作负载上，ESD($\alpha =1$) 带来的代价降低最多，GPU利用率为74.89%. 当每个工作节点的批量大小为256时，如图7（b）所示，ESD可以将嵌入传输代价减少多达40.84%. 对于负载S1，当每个工作节点的批量大小为256时，对于ESD($\alpha =0.5$)，代价降低为12.96%，GPU利用率为50%，对于ESD($\alpha =1$)，代价降低为29.51%，GPU利用率为75%. 总体而言，较大的$\alpha$值会带来更大的代价降低和更高的GPU利用率. $\alpha$的设置取决于边缘工作节点上GPU资源的多少以及多个任务之间的竞争情况. 可以看到，即使$\alpha$ = 0，ESD相对于LAIA仍然可以减少传输代价.

图  7  代价降低和GPU资源消耗

Figure  7.  Cost reduction and GPU resource consumption

下载: 全尺寸图片 幻灯片

需要注意的是，准确测量GPU的资源消耗是计算机系统中的一个极具挑战性的问题^[81-82]. 在图7中，本文使用执行命令nvtop得到的GPU利用率作为衡量GPU资源消耗的标准，显然，这是一个粗粒度的资源消耗测量标准. 需要说明的是，图7中ESD的GPU 利用率是在 GPU 上单独执行ESD的过程中而非在DLRM训练过程中测得的. 实际上，当节点批量大小为128，在负载S3上进行训练时，当在训练过程中同时执行ESD($\alpha =1$)时，通过nvtop观察到的GPU利用率约为55%，而图7（a）中展示的单独执行ESD($\alpha = 1$)时GPU利用率约为58%，因此，图7中显示的GPU利用率旨在说明随着$\alpha$值的减小，使用的GPU资源也随之减少，并没有反应真实的GPU资源消耗比例，也就是说，ESD($\alpha =1$)这一调度机制实际上并不会像图7所示那样消耗高达70%的GPU资源.

5.5   敏感性分析

接下来，本文将探讨当每个工作节点的批量大小、缓存比例和嵌入大小发生变化时ESD的性能. 此外，本文还评估了在四个工作节点以及工作节点与参数服务器之间具有相同带宽（同构网络）的情况下ESD的性能表现. 当某一设置发生变化时，其他设置保持默认值. 在这一部分中，本文主要关注工作负载S2.

5.5.1   每个工作节点的批量大小

如图8所示，为了研究每个工作节点批量大小的影响，本文将其从64变化到512，并展示了加速比和代价降低的情况. 当每个工作节点的批量大小从64增加到256时，ESD($\alpha =1$)、ESD($\alpha =0.5$) 和 ESD($\alpha = 0$)的加速比呈增长趋势，最高可达1.54倍. 然而，当批量大小从256增加到512时，ESD($\alpha =1$)、ESD($\alpha = 0.5$) 和 ESD($\alpha =0$) 的加速比并未超过256时的表现（尽管仍保持在1以上）. 这是因为增加每个工作节点的批量大小会增加决策时间，并且随着批量大小的增加，ESD($\alpha =0$)的解决方案质量下降，导致这三种机制的加速比均有所下降. 对于传输代价，随着每个工作节点批量大小的增加，代价降低的趋势与加速比的趋势相似. 当批量大小从256增加到512时，虽然ESD($\alpha =1$)实现了更大的代价降低，但增加的决策时间使得加速比从1.54降至1.23.

图  8  每工作节点批量大小对性能的影响

Figure  8.  Impact of batch size per worker on performance

下载: 全尺寸图片 幻灯片

5.5.2   缓存比例

如图9所示，本小节展示缓存比例的影响. 缓存比例，即缓存中嵌入数量与总嵌入数量的比例，范围4%~10%.

图  9  缓存比例对性能的影响

Figure  9.  Impact of cache ratio on performance

下载: 全尺寸图片 幻灯片

图9表明，ESD在不同大小的嵌入缓存下相对于LAIA保持了性能上的优越性，并且对于相同的$\alpha$值，加速比在不同缓存大小下并没有显著变化. 这个实验验证了ESD在不同缓存比例下的持续有效性.

5.5.3   嵌入大小

嵌入大小，即嵌入向量的维度，是影响DLRM模型性能的重要因素. 如图10所示，本文测试了嵌入大小为128、256、512和1024时，ESD($\alpha =1$)、ESD($\alpha = 0.5$) 和 ESD($\alpha =0$)的加速比和代价降低的变化情况. 当嵌入大小增加时，如图10（a）所示，三种机制相对于LAIA的加速比均有所增加，最高可达1.59倍. 原因是随着嵌入大小的增加，每次嵌入拉取和推送的数据量（即 ${D}_{tran}$）变大，从而增加了嵌入传输的代价. 当每次嵌入传输代价增加时，ESD的效果变得更加显著. 对于代价降低，嵌入大小的变化仅影响 ${D}_{tran}$，并不影响ESD($\alpha =1$)、ESD($\alpha =0.5$) 和 ESD($\alpha =0$)相对于LAIA的代价降低效果. 例如，当嵌入大小从256增加到512时，${D}_{tran}$翻倍，导致LAIA和ESD的嵌入传输代价也都翻倍. 然而，ESD相对于LAIA的代价降低比例保持不变.

图  10  嵌入大小对性能的影响

Figure  10.  Impact of embedding size on performance

下载: 全尺寸图片 幻灯片

5.5.4   工作节点数量和网络带宽

之前实验是在8个边缘工作节点上进行的，这些工作节点与参数服务器（PS）之间的网络带宽是异构的. 为了验证ESD在不同数量的工作节点以及工作节点与PS之间具有相同网络带宽的情况下的有效性，本文测试了以下设置下的ESD($\alpha =1$)、ESD($\alpha = 0.5$) 和 ESD($\alpha =0$)的性能. 一是使用4个边缘工作节点，其中2个带宽为5 Gbps，另外两个带宽为0.5 Gbps. 二是使用4个带宽均为5Gbps的工作节点. 实验结果如图11所示. 在这两种设置下，对于3种机制和3种工作负载，加速比分别在1.07~1.31倍和1.03~1.23倍之间. 对于代价降低，当使用两个5 Gbps工作节点和两个0.5 Gbps工作节点时，代价降低范围为6.06%到42.15%. 相比之下，当使用四个5 Gbps工作节点时，代价降低范围为0.33%到29.11%. 实验表明，ESD在具有四个工作节点的同构网络中是有效的，并且在异构网络中的表现更好，这与本文的动机一致.

图  11  当使用4个工作节点时的实验结果

Figure  11.  Experiment results when using four workers

下载: 全尺寸图片 幻灯片

6.   相关工作

6.1   为边缘智能计算系统设计的推荐模型训练方法

为边缘智能计算系统设计的推荐模型训练方法通常专注于隐私保护和效率. Yuan等人提出了无参数传输联邦推荐框架PTF-FedRec，通过在客户端与参数服务器之间传输预测来促进协作学习，同时通过本地模型预测的采样和交换机制确保隐私^[83]. HFSA 是一个半异步层次化的联邦推荐系统，通过边缘聚合减少通信开销，采用半同步机制提高性能，并允许慢速客户端异步贡献其参数以确保全局模型收敛，适用于动态移动和边缘环境^[24]. DualRec是一个结合联邦学习与高效模型聚合和降噪机制的协同训练框架，允许设备用本地数据训练轻量级模型，而较大的模型则在云端训练，通过生成伪用户交互和在设备与云端模型之间进行知识蒸馏来提升推荐系统性能^[84]. PREFER ^[23]是一个针对兴趣点推荐的边缘加速联邦学习框架，其中用户的独立参数在用户间共享并在边缘服务器上进行聚合. PEPPER^[59]是一个基于gossip learning的去中心化推荐系统，使用户能够异步训练个性化模型. 与已有工作类似，本文专注于在边缘智能计算系统中为物联网应用提供推荐服务，不同之处在于本文更关注于通过调度嵌入样本减少嵌入传输代价从而加速模型训练，而现有工作主要关注训练方法设计和联邦推荐系统设计.

6.2   深度学习推荐模型训练加速方法

先前的部分工作集中在最小化传输次数上^[49,50,85]. FAE ^[50]通过在GPU上存储热门嵌入来减少从CPU到GPU的嵌入传输. Persia ^[85]使用混合同步和异步机制分别更新MLP和嵌入表. HET ^[49]设计了一个缓存一致性模型，允许缓存读写操作中的陈旧性以最小化传输开销. LAIA ^[37]对嵌入进行调度以减少传输次数而不牺牲准确性. 其他工作则专注于减少每次传输的延迟. Ugache^[35]引入了一种分解提取机制以防止带宽拥塞，并利用NVLink和NVSwitch加速远程GPU内存访问. AdaEmbed ^[86]和CAFE ^[31]旨在通过压缩和剪枝减少嵌入的传输代价. ScaleFreeCTR^[29]采用混合缓存机制消除主机与GPU之间的传输代价，并利用虚拟稀疏ID减少传输量. 本文关注在边缘智能计算系统中训练DLRM，并提出了ESD来应对边缘侧的独特挑战，如资源受限和异构网络，以最小化总的嵌入传输代价，从而加速DLRM训练.

7.   讨论和未来工作

7.1   缓存替换策略

在DLRM的训练过程中，当嵌入缓存达到容量时，必须将一个或多个已缓存的嵌入替换出去以容纳新的嵌入. 在按需同步的情况下，如果被替换出去的嵌入的梯度尚未与参数服务器（PS）同步，则会触发Evict Push操作. 本文设计了Emark，一种基于标记的策略来管理每个工作节点中的缓存嵌入，以减少Evict Push操作的数量，该策略考虑了最近性、频率和嵌入版本. 当嵌入ID ${x}_{i}$被调度到${w}_{i}$时，Emark为 $\boldsymbol{E}\boldsymbol{m}\boldsymbol{b}\left({\boldsymbol{x}}_{\boldsymbol{i}}\right)$分配一个标记（target），target是一个从1开始的正整数. 当缓存满且所有嵌入的标记都是target时，target加1. 对于缓存替换，当缓存满时，Emark首先逐出过期的嵌入，然后按标记升序比较，最后比较访问频率. 本文在C++中重载了<运算符以实现这一点. 此外，通过调整target的递增方法和重载<运算符中的比较顺序，Emark可调整为优先考虑频率、最近性或嵌入版本. 由于图5（b）显示逐出推送对传输操作的贡献不到10%，本文在此讨论缓存替换策略而不是在第3节中讨论. 此外，将Evict Push和替换策略纳入预期传输代价的计算是减少Evict Push操作的有效方式，本文将此作为未来的工作方向.

7.2   非均一嵌入大小

本文假设所有嵌入向量维度（即嵌入大小）是均一的. 然而，最近的趋势表明，使用非均一嵌入大小可以减少DLRM的内存占用、训练时间和推理时间^[87-88]. 当嵌入大小不均一时，ESD可以通过以下调整有效处理这种情况：首先，对于计算预期传输代价，可以使用不同的数据大小（${D}_{tran}$）来考虑非均一的嵌入大小. 其次，关于缓存替换策略，非均一嵌入大小会导致嵌入缓存中不同嵌入占用的的内存大小不同. 这可以通过优先级指标进行管理，缓存中每个嵌入的优先级的计算方式如下，使用频率、最近性和版本（最新或过时）的相关数值作为分子，而每个嵌入的内存占用作为分母，当缓存达到容量时，优先级最低的嵌入将首先被逐出. 在未来的研究中，本文将进一步探索边缘智能计算系统中训练和部署 DLRM 时嵌入大小的选择问题.

7.3   与其他边缘计算优化方法的异同

在边缘智能计算系统中，资源分配、任务卸载和缓存策略是常见的优化方法. 然而，这些方法与本文提出的ESD机制在优化目标、技术路径和适用场景上存在差异. 边缘计算中的资源分配方法通常聚焦于存储、计算、网络资源的动态分配以提升系统吞吐率^[89]，其核心在于平衡多任务间的资源竞争. 与之相比，虽然ESD中HybridDis也考虑了资源受限场景中多任务争用资源的情况，但其并不直接干预资源分配，而是采用$\alpha$来平衡求解质量和资源消耗. 任务卸载方法通常将计算任务迁移至云端或其他边缘节点以降低延迟或能耗^[90]，其卸载决策基于任务计算量与节点处理能力的匹配. 与任务卸载相似，ESD基于预期传输代价将嵌入样本调度到不同的工作节点上，不同之处在于，任务卸载中多个任务间一般无关联，而对嵌入样本进行调度会影响更新推送操作的数量. 缓存策略主要基于数据的历史访问模式来提升缓存命中率^[91]，在ESD中，如引言部分和7.1节所述，与传统缓存问题不同，DLRM训练中的嵌入具有动态更新特性，ESD需要同时考虑未命中拉取、更新推送和逐出推送三类操作代价. 总的来说，本文主要考虑在边缘智能计算系统中加速DLRM训练，面临嵌入传输代价组成复杂、异构网络、资源受限等挑战，资源分配、任务卸载和缓存策略等边缘计算优化工作也会考虑网络异构、资源受限等问题，但尚无研究工作面向在边缘节点上训练DLRM这个场景进行深入研究.

8.   结　　论

在边缘智能计算系统中训练和部署DLRM是在确保隐私保护和提供低延迟服务的情况下，为物联网应用提供个性化推荐服务的有效方式. 本文专注于基于预期嵌入传输代价调度输入嵌入样本，以最小化总的嵌入传输代价，进而加速DLRM训练. 本文强调了在边缘智能系统中设计调度机制所面临的挑战，包括代价构成、异构网络和资源受限. 为应对这些挑战，本文提出了一种名为ESD的调度机制，其中包含作为关键组件的混合决策方法HybridDis. 本文使用C++（包括CUDA）和Python实现了ESD，并通过典型的负载在边缘工作节点上进行了实验，以验证其相较于最先进机制的改进. 构建一个高效的边缘智能计算系统用于服务物联网应用需要在数据收集、处理、模型训练、部署等方面进行优化. 本文希望这项工作能为构建高效的边缘智能计算系统贡献一份力量.

作者贡献声明：李国鹏明确研究挑战，提出解决思路，设计并完成实验和撰写论文；谈海生提出问题，参与解决方案设计，对论文撰写与实验方案设计进行指导；张弛参与方案设计和撰写论文；倪宏秋、王子龙、章馨月、徐洋调研文献以及参与算法设计，田晗提供问题背景、对实验、论文写作进行指导；陈国良对整体研究方向和思路进行指导.