Asteroid_Resource_Efficient_Hybrid_Pipeline_Parallelism_for_Collaborative DNN_Training_on_Heterogeneous_Edge_Devices

题目：小行星：异构边缘设备上协同DNN训练的资源高效混合管道并行

出处：ACM MobiCom

时间：2024.11

作者：Shengyuan Ye等

代码：Asteroid: Resource-Efficient Hybrid Pipeline Parallelism for Collaborative DNN Training on Heterogeneous Edge Devices | Papers With Code

摘要

设备上深度神经网络（DNN）训练已被认为是边缘保护隐私的机器学习的关键。然而，密集的训练工作量和有限的机载计算资源对模型训练的可用性和效率提出了重大挑战。虽然现有的工作通过本地资源管理优化来解决这些挑战，但我们利用我们的观察，即边缘环境通常包含一组丰富的随附可信边缘设备，这些设备具有超出单个终端的空闲资源。我们提出了一个分布式边缘训练系统Asteroid，它打破了异构边缘设备之间的资源墙，从而实现了高效的模型训练加速。Asteroid采用混合管道并行来编排分布式训练，并在一定资源约束下进行明智的并行规划以最大化吞吐量。此外，开发了一种容错且轻量级的管道重放机制来驯服设备级动态，以训练鲁棒性和性能稳定性。我们使用视觉和语言模型在异构边缘设备上实现了Asteroid，通过评估表明，其训练速度比传统并行方法快12.2倍，比最先进的混合并行方法快2.1倍。此外，小行星可以恢复训练管道比基线方法快14倍，同时保持相当的吞吐量，尽管意外的设备退出和故障。

结论

本文提出小行星用于跨异构和资源受限边缘设备的协同DNN训练。

小行星解决了边缘环境中面临的多种挑战，比传统方法的训练速度快12.2倍，比最先进的HPP方法快2.1倍。

研究背景

DNN训练有什么问题？

对于DNN训练，有效的原位学习仍然存在训练时间过长、收敛稳定性差的问题。为了缓解这些（训练时间长、内存不足）问题，现有许多研究采用模型压缩技术（如剪枝、稀疏化和量化）或手工设计轻量级模型架构来降低DNN训练的计算复杂度，虽然减少了计算，但它们损害了模型的准确性。其他领先的研究工作已经探索了在本地资源上设计复杂的管理机制（例如，张量再物化，内存预算适应），但仍然受到物理资源短缺的内在缺陷的瓶颈。

为什么研究分布式边缘环境？

1、可以利用边缘环境分布式训练。智能家居等流行的边缘场景通常包括一组可信任的闲置设备，而不是单个终端。这些辅助设备通常在物理上接近运行设备上学习任务的主要设备，并且可以作为原位DNN训练加速的资源增强。可用设备视为一个资源池，并以分布式的方式与它们协作，以在边缘呈现加速的模型训练。

2、与云环境相比，直接利用边缘环境存在问题：(1)在计算能力、内存容量和通信带宽方面非常有限。(2)异构性要高得多，这就需要一种异构感知策略来最大限度地利用计算潜力。(3)由于设备的移动性和可访问性，表现出更多的潜在动态属性。。。不幸的是，没有现有的工作可以解决上述所有的挑战。

可以利用的DNN分布式训练方法有哪些？

数据并行。最常用的并行训练方法是数据并行（data parallelism， DP），输入在各个worker之间进行分区，每个worker维护整个模型的副本，并在与其他worker（即AllReduce）周期性同步梯度的同时对其本地数据执行训练。其工作负载的简单性为多个设备提供了更好的可伸缩性。然而，由于边缘连接松散且多变，同步带来的通信开销通常会占据训练时间。

管道并行。另一个广泛使用的并行是管道并行（pipeline parallelism， PP）。在PP中，DNN模型被划分为多个阶段，每个阶段被映射到一个单独的处理器上，以便逐级向前/向后传递执行，从而优化并行效率。然而，流水线并行也有缺点：(1)可扩展性弱。边缘集群的直接实现PP可能会创建太多的阶段，这会放大阶段间通信延迟的影响。(2)不可重叠的阶段间通信。当通信发生在具有大量中间激活的层之间时，PP无法有效地重叠前向和后向执行的层间通信。

分布式架构HPP。核心：组间PP和组内DP。融合DP和PP优点的混合并行架构，采用HPP来促进与边缘设备的协作。除了打破单个设备的资源墙之外，采用HPP还提供以下好处：(1)每个设备仅存储整个模型的一个子集，从而导致更小的内存占用，这对于具有巨大参数的模型尤其有利。(2) HPP提供了高度灵活的并行架构，通过防止参数密集层中的AllReduce，可以有效地减少通信量。(3)通过分层规划，HPP可以避免中间张量较大的层间通信。通过计算和通信的完全重叠，HPP掩盖了边缘环境下网络容量的限制。(4)在考虑复杂异构边缘环境时，HPP提供了更高的调度灵活性，扩展了更大的并行规划优化空间。

研究挑战

稀缺的内存和网络容量；计算资源异构；资源动态问题。

研究目的

针对DNN的分布式训练过程，打破异构边缘设备的资源墙，实现高效的模型训练加速。

论文贡献

提出了Asteroid，这是一个通用的分布式训练系统，能够协调多个异构边缘设备，以实现快速，资源高效和容错的模型训练。小行星的贡献不仅仅是利用分布式边缘设备进行训练加速，而是在三个层面上解决上述挑战。

首先，从并行性的角度，采用混合管道并行性（HPP）作为一种原理来管理分布式训练工作流，结合数据并行和管道并行的优点，为异构边缘环境下的并行规划提供更大的优化空间。

其次，为了最大限度地提高异构边缘设备间HPP的资源利用率，设计了一种基于动态规划的并行规划算法，并针对内存预算、有限通信容量和资源异构性等多维资源优化问题，设计了一种内存高效的批量摄取策略。

最后，为了在运行时适应动态参与者，通过轻量级粗粒度工作负载迁移和拓扑驱动的模型复制应用了容错机制。

论文方法

小行星的概述，其中包括三个主要阶段：预处理阶段，规划阶段和执行阶段。预处理阶段是在部署前运行一次的脱机过程。小行星分析器使用校准数据作为物理边缘设备的输入来执行训练过程，以记录并行规划（步骤1）所需的运行时配置文件。在规划阶段，Asteroid Planner将分析结果作为输入来生成规划配置，包括DNN模型分区点、设备分组策略和组内微批分配（步骤2）。这些配置全面解决了包括内存预算、有限的通信容量和资源异质性在内的挑战，并随后应用于目标DNN模型和训练参与者。在执行阶段，部署在每个参与者上的小行星工作者将负责模型执行，中间输出交换和梯度同步（步骤3）。为了应对运行时动态的挑战，需要容错管道重播机制将被应用（步骤4）。需要一个中央协调器（用户指定的设备）来应用规划配置和检测设备故障。

混合管道并行

首先将DNN模型划分为多个阶段，每个阶段包含一个由一组连续网络层组成的阶段模型。资源池中的边缘设备将被划分为相应数量的设备组，每个设备组包含一个或多个设备。HPP将这些组之间的管道并行性与组内的数据并行性结合起来。

在训练过程中，一个小批将被分割成𝑀更小的微批，并同时注入管道中以增加并行性。如果设备组包含多个设备，则微批将进一步分解。每个设备对它负责的阶段模型执行前向传递（FP）和后向传递（BP），并为每个小批中的所有微批累积梯度。在minibatch结束时，使用AllReduce同步每个设备组中的梯度，然后应用于阶段模型参数。整个小批量训练过程被称为HPP-Round。

对于DNN的训练内存，可以分为三类：(1)模型权重记忆（包括模型参数和累积梯度），(2)优化器记忆和(3)激活记忆（FP的中间输出）。HPP架构使每个设备只在内存中存储相应的阶段模型。实验表明，中间激活是内存占用的主要贡献者。受梯度积累思想的启发，我们采用了一种细粒度的微批调度，它以一前一后（1F1B）的方式工作，尽早调度BP以释放由FP产生的激活内存以供重用。设置较小的𝐾𝑝可以减少内存占用，但会损害阶段级管道并发性。

所需要的内存峰值为：

$\operatorname{Mem}_{p}(\beta)=\operatorname{Mem}_{p}^{(\mathrm{MOD})}+\operatorname{Mem}_{p}^{(\mathrm{OPT})}+K_{p} \times \operatorname{Mem}_{p}^{(\mathrm{ACT})}(\beta)$

并行计划

将模型划分为多个连续阶段，对图节点进行拓扑排序，将DNN模型转换为层序列。实验表明，较小的批处理规模并不能充分利用gpu的并行能力，导致它们之间的非线性相关。因此，Asteroid profiler测量各种批量大小的实际边缘硬件上每层的执行时间。考虑时延tf与tb与设备带宽b。

HPP-Round中每个步骤的训练过程分为三个阶段：等待阶段、执行阶段和AllReduce阶段，对应的时间分别表示为𝑇𝑠𝑤、𝑇𝑠𝑒和𝑇𝑠𝑎。核心的优化目标是最小化HPP-Round延迟，这是由三个阶段中总延迟最大的步骤决定的：

$\text{HPP-Round Latency}=\max_{s\in\{0,1,...,S-1\}}\left(T_w^s+T_e^s+T_a^s\right)$

s阶段的等待时间为前s-1个通信时间之和，AllReduce过程时间为s阶段的设备组中的通信容量除以通信带宽。对于执行时间，寻找一个步骤使得FP和BP在其执行阶段紧密注入的优势步骤（气泡数量最少），可以很好地近似为𝑀微批FP和BP的累积时间。根据梯形的形状，计算不同步骤s中的时间（优势步骤dm的FP / BP所花费的时间，加减其步骤s中FP / BP所花费的时间E）。

而对于FP / BP所花费的时间E，论文设计一种创新的动态规划算法，从所有可能的配置中识别最佳的HPP架构，有效地减少HPP轮延迟。关键目标是在资源不同的设备之间对微批样品进行最佳分配。这种分配力求在每个设备的内存预算内最小化数据并行执行时间。（FP / BP所花费的时间E即为时延tf与tb各自的和。）

$\begin{aligned} T(i\to j,\mathcal{G}_{s}) & =\min_{y_{d}\in\mathcal{Y}_{s}}\max_{d\in\mathcal{G}_{s}}\sum_{l=i}^{j}[t_{f}^{d,l}(y_{d})+t_{b}^{d,l}(y_{d})], \\ & s.t.\sum_{d\in\mathcal{G}_{s}}y_{d}=\mathrm{B},\quad\mathrm{Mem}_{s}(y_{d})\leq u_{d}, \end{aligned}$

论文通过算法1（微批样品的分配）解决上述约束优化问题。算法可分为两个不同的阶段：内存感知的工作负载均衡阶段和工作负载卸载阶段。在第一阶段，在设备之间递归地分配工作负载，以一种基于其计算能力平衡工作负载的方式，同时严格遵守内存预算。在第二阶段，迭代地将示例工作负载从掉队设备（最慢的设备）转移到具有足够内存的最快设备。当工作负载卸载导致较慢的散列器时，迭代终止。我们可以根据微批大小调整块大小，在规划开销和平衡之间进行权衡。

论文通过算法2（动态规划HPP规划）搜索最优HPP配置以最小化HPP轮延迟。为了降低跨异构设备编排的搜索复杂性，我们按内存容量降序对设备进行排序，并相应地映射阶段。在算法2中，并发记录了𝑄（𝑙，𝑛，𝑝）的并行配置，包括模型分区点、设备分组策略和组内微批分配。该过程在完成后确定HPP的最佳并行配置。

容错管道重放

由于边缘设备表现出强烈的动态性（可能随时离开训练、网络异常等等），重调度可能会在重新规划和模型传输中引起相当大的延迟。为了解决这些问题，Asteroid集成了一个动态容错管道重播轻量级重调度，具有三个有效响应资源波动的模块：

1、心跳引导的故障检测。每个设备定期向中央协调器发出心跳信号，作为其活动的证明，确认其运行状态。

2、拓扑驱动的模型复制。Asteroid采用拓扑驱动的模型复制，当设备发生故障时，可以从备份节点恢复模型权重。

3、分层轻量级管道重新规划。为了加快管道的重新规划，我们采用分层轻量级方法代替重新运行整个规划算法。在设备发生故障的情况下，相关的工作负载将根据其计算能力在其余阶段之间重新分配，通过对当前规划配置的层分区点进行微小调整来实现。

实验与结果

作者在pytorch上进行实验，与DP、PP、EDDL、PipeDream、Dapple、HetPipe对比，证明了论文方法的有效性。并通过消融实验证明了HPP中优化的性能提升。在容错机制的实验验证中，作者的方法与繁重的重新调度方法进行了对比，比重调度恢复得快得多，并且可以在不同的场景中实现相当的系统吞吐量。除此之外，还具有一定的扩展性。

引用内容（自用）：

@article{Ye2024AsteroidRH, title={Asteroid: Resource-Efficient Hybrid Pipeline Parallelism for Collaborative DNN Training on Heterogeneous Edge Devices}, author={Shengyuan Ye and Liekang Zeng and Xiaowen Chu and Guoliang Xing and Xu Chen}, journal={Proceedings of the 30th Annual International Conference on Mobile Computing and Networking}, year={2024}, url={https://api.semanticscholar.org/CorpusID:270125485} }