Load scheduling for distributed edge computing: A communication-computation tradeoff
Load scheduling for distributed edge computing: A communication-computation tradeoff
复制标题
DOI：
10.1007/s12083-018-0695-4
复制
发表时间：
2018-10
影响因子：
4.2
通讯作者：
Minghui Zhao;Wei Wang;Yitu Wang;Zhaoyang Zhang
中科院分区：
文献类型：
--
作者：
Minghui Zhao;Wei Wang;Yitu Wang;Zhaoyang Zhang
由于新兴应用的密集计算需求和边缘计算服务器的有限计算能力，计算任务必须以分布式和协作的方式在多个边缘服务器上执行。然而，在边缘服务器之间交换的大量信息是提高计算性能的主要障碍。通过利用多余的计算资源，编码MapReduce提供了一种有效的方法来减少通信负载。在本文中，我们开发了一个随机负载调度框架来完成编码MapReduce的计算任务，考虑了通信和计算负载之间的内在权衡。我们的目标是在时变的计算资源过剩情况下最小化通信负荷。我们首先利用编码MapReduce框架中计算重复的特性，将这个问题简化为任务调度问题。由于任务调度问题仍然是一个随机优化问题，所以通常很难求解。在离线环境下，采用增广拉格朗日方法得到了最优的计算负荷调度算法。在在线环境下，利用竞争分析方法导出了在线等任务调度算法的最坏情况性能界。此外，我们充分利用计算资源过去的状态信息进行预规划，并以学习的方式提出了一种基于ETS算法的改进算法。最后，通过仿真对我们提出的算法进行了评估，证明了我们提出的算法优于传统算法，并且在线和离线算法之间的性能差距相当小。
Due to the intensive computation requirements of emerging applications and the limited computational capability of edge computing servers, the computation task must be executed on multiple edge servers in a distributive and cooperative manner. However, the large amount of information exchanged among the edge servers is a major obstacle for improving the computing performance. By utilizing the excess computational resource, coded MapReduce provides an effective approach to reduce the communication load. In this paper, we develop a stochastic load scheduling framework to complete the computation tasks with coded MapReduce considering the intrinsic tradeoff between the communication and computation loads. Our goal is to minimize the communication load under time-varying excess computational resources. We first reduce this problem to a task scheduling problem by exploiting the property of the computing repetition in the coded MapReduce framework. Since the task scheduling problem is still a stochastic optimization problem, it is generally difficult to solve. In the offline setting, we obtain the optimal computation load scheduling algorithm by adopting the augmented Lagrangian method. In the online setting, we derive a worst-case performance bound of the online equal task scheduling (ETS) algorithm by using competitive analysis. Furthermore, we make full use of past state information of computing resources for pre-planing and propose an improved algorithm based on the ETS algorithm in a learning manner. Finally, our proposed algorithm is evaluated by simulation to demonstrate that the proposed algorithms are superior over the conventional algorithms, and the performance gap between the online and offline algorithms is fairly small.