边缘计算环境中基于复制的任务加速机制
2022-01-19彭丽丽蔡园园王兴阳
刘 敏 彭丽丽 蔡园园 王兴阳
江苏电力信息技术有限公司
0 引言
随着边缘计算的发展，网络边缘产生的数据呈指数级增长，据预测，在不久的将来，边缘集群数据的产生速度将超过当今互联网的容量。随着边缘集群数量的增加和机器学习的快速发展，机器学习作业成为边缘系统的主要工作负载。
每个边缘集群有限的资源使得机器学习作业的运行具有很大的挑战。一个作业的完成通常取决于最慢的任务，即慢任务。避免慢任务的传统方法是将任务卸载到远程云，然而这会导致较大的广域网络延迟和较大的资金成本。另一个有潜力的替代方案是将任务从过载的边缘复制到空闲的边缘。当任何一个副本完成时，该任务就完成了。也就是说，任务的完成取决于其最快的副本，这可能会减少任务排队和计算时延。但是在边缘集群中实现高效的任务复制有以下几个挑战。
首先，要选择最佳副本位置，需要提前知道在边缘集群中运行的任务的计算时延，在做出复制决策并完成副本之前，无法知道此类信息。其次，边缘集群之间的网络带宽通常是时变的，这也导致了不确定的传输时延。这两个相互交织的挑战进一步使任务的完成变得不可预测。因此，设计一种能够持续适应这种动态和不确定环境的高效复制算法并不容易。
现有的复制方法无法应对这些挑战。基于检测的算法需要花费大量时间和成本来监控和识别掉队者。通常，这样的开销是巨大的，因此基于检测的策略有其固有的缺陷。基于克隆的算法提前复制任务的一定数量的副本，并将其卸载到相应的边缘。但是，在执行算法之前，时延总是未知的，因此无法找到卸载这些副本的最佳边缘。
文中首先建立了基于多臂赌博机的边缘系统的任务复制问题的模型，并给出了相应的公式。其次，设计一种边缘环境中基于复制的高效任务加速机制，即TRAN，通过权衡探索和利用来最小化任务级regret。在TRAN中，将由多个边缘集群组成的系统视为一个多臂赌博机，并将每个边缘集群视为多臂赌博机中的一个手臂。对于过载边缘上的任务，作出在线决策，以决定为任务选择哪些手臂，即执行任务副本的目标边缘群集，证明了所提出的TRAN机制的regret是次线性的。
1 问题分析
一个机器学习作业通常包含多个任务，一个任务由一个三元组构成，分别是该任务的输入数据量、输出数据量以及任务的类型。由任务类型和输入数据量可以得出该任务的计算量。从而，任务复制时延模型可以定义为以下三部分：（1）副本从一个边缘到目标边缘的传输时延；（2）副本在目标边缘上的计算时延；（3）从目标边缘向原边缘传回结果的时延。时延模型的第一部分取决于其输入数据大小和带宽。第二部分取决于任务所需的计算量和边缘的计算能力。第三部分则取决于计算结果的大小和带宽。如图1是基于复制的任务加速机制的基本原理。其中绿色作业的任务3经过决策之后，选择了边缘4和边缘7作为目标边缘集群来执行副本。
图1 基于复制的任务加速机制基本工作原理
由于执行任务时网络带宽和边缘集群计算性能的不断波动，无法在复制决策之前预测复制到不同边缘的任务的完成延迟。而且，决策后的总延迟仍然是一个随机量。每个任务的实际完成延迟只有在任务实际完成后才能知道。因此，任务完成延迟是未知分布的样本。具体而言，在上述时延模型中，带宽和边缘计算能力满足未知分布，随时间波动，无法提前预测。因此，使用多臂赌博机模型来解决复制的随机性问题。
基于任务复制和多臂赌博机，设计了一种边缘环境中的高效任务加速机制，即TRAN，通过权衡探索和利用来最小化任务级regret。在TRAN中，将由多个边缘集群组成的系统视为一个多臂赌博机，并将每个边缘集群视为多臂赌博机中的一个手臂。对于过载边缘上的任务，会在线作出决策，以决定为任务选择哪些手臂，即执行任务副本的目标边缘群集。该算法的每次决策都为算法本身的学习提供了一次样本，通过学习不断完善的模型也就是每次在线决策的依据。随后，证明了所提出的TRAN机制的regret是次线性的。
2 基于复制的任务加速算法思想
解决上述任务复制问题的主要挑战来自两个方面。第一个方面是估计机器学习任务的计算量。第二个方面是基于在线多臂赌博机的任务复制算法的设计。在这两部分的算法设计中，基于复制的任务加速算法的体系结构如图2所示，描述了TRAN算法的体系结构。计算量估计模块根据任务数据量和任务类型估计任务的计算量。边缘系统管理器模块则根据历史的系统状况预估边缘集群的计算能力和网络带宽。TRAN代理和调度器模块根据边缘系统管理器模块的预判作出复制决策。
其中，任务计算量模块的设计思想如下。若任务为机器学习推断任务：直接根据模型结构，统计计算过程中的原子操作数量，估计任务的总体计算量。若任务为机器学习训练任务：若该训练过程能够直接通过闭式表达式获取最优模型参数向量，通过分析该等式可直接得到计算量与输入数据量的关系。对于大部分需要通过迭代更新的训练任务，一次迭代可表述为一个闭式表达式，因此根据输入向量维度N，一次迭代的计算量也是能准确估算的。
TRAN代理（基于多臂赌博机的在线决策模块）主要通过不断在线决策，逐步学习整个边缘系统的带宽和计算性能的分布。再利用学到的分布，为系统的下一次复制决策提供依据。在算法运行的过程中，也设置了padding项来平衡探索和利用，以使整个边缘系统所有作业的完成时延最小。
3 结束语
本文将多臂赌博机应用于任务复制问题，并对边缘计算性能和链路带宽的随机性进行了描述，提出了一种边缘计算环境中基于复制的任务加速机制。基于复制的任务加速机制的核心在于用多臂赌博机刻画计算时延和传输时延的波动性，设置padding项权衡探索和利用。
