计算机科学
调度(生产过程)
计算
并行计算
延迟(音频)
工作量
试验台
边缘计算
分布式计算
算法
GSM演进的增强数据速率
数学优化
计算机网络
数学
人工智能
电信
操作系统
作者
Quan Chen,Kaijia Wang,Song Guo,Tuo Shi,Jing Li,Zhipeng Cai,Albert Y. Zomaya
标识
DOI:10.1109/infocom53939.2023.10228964
摘要
By combing edge computing and parallel computing, distributed edge computing has emerged as a new paradigm to accelerate computation at the edge. Considering the parallelism of both computation and communication, the problem of Minimum Latency joint Communication and Computation Scheduling (MLCCS) is studied recently. However, existing works have rigid assumptions that the communication time of each device is fixed and the workload can be split arbitrarily small. Aiming at making the work more practical and general, the MLCCS problem without the above assumptions is studied in this paper. Firstly, the MLCCS problem under a general model is formulated and proved to be NP-hard. Secondly, a pyramid-based computing model is proposed to consider the parallelism of communication and computation jointly, which has an approximation ratio of 1 + δ, where δ is related to devices’ communication rates. An interesting property under such computing model is identified and proved, i.e., the optimal latency can be obtained under arbitrary scheduling order when all the devices share the same communication rate. When the devices own different communication rates, the optimal scheduling order is also obtained. Additionally, when the workload cannot be split arbitrarily, an approximation algorithm with ratio of at most 2 (1 + δ) is proposed. Finally, the theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency. Two testbed experiments are also conducted, which show that the proposed method outperforms the existing methods, reducing the latency by up to 29.2% in real-world applications.
科研通智能强力驱动
Strongly Powered by AbleSci AI