Optimal Accuracy-Time Trade-off for Deep Learning Services in Edge Computing Systems
Optimal Accuracy-Time Trade-off for Deep Learning Services in Edge Computing Systems
复制标题
DOI：
10.1109/icc42927.2021.9500744
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Minoo Hosseinzadeh;Andrew Wachal;Hana Khamfroush;D. Lucani
中科院分区：
文献类型：
--
作者：
Minoo Hosseinzadeh;Andrew Wachal;Hana Khamfroush;D. Lucani
随着对深度学习任务等计算密集型服务的需求不断增长，新兴的分布式计算平台（如边缘计算（EC）系统）变得越来越受欢迎。与传统云系统相比，边缘计算系统在延迟减少方面表现出了良好的效果。然而，它们有限的处理能力要求在潜在的延迟减少和计算密集型服务（如基于深度学习的服务）中实现的准确性之间进行权衡。在本文中，我们专注于寻找在三层EC平台中运行深度学习服务的最佳准确性-时间权衡，其中有几个具有不同准确度的深度学习模型。具体来说，我们投的问题作为一个线性规划，最佳的任务调度决策，以最大限度地提高整体用户满意度的准确性和时间的权衡。我们证明了我们的问题是NP-难的，然后提供了一个多项式常数时间贪婪算法，称为GUS，这是达到接近最优的结果。最后，在通过数值实验和与一组算法的比较来审查我们的算法解决方案后，我们将其部署在一个测试平台上，以测量真实世界的结果。数值分析和实际应用的结果都表明，GUS在满意用户的平均百分比方面至少可以超过50%。
With the increasing demand for computationally intensive services like deep learning tasks, emerging distributed computing platforms such as edge computing (EC) systems are becoming more popular. Edge computing systems have shown promising results in terms of latency reduction compared to the traditional cloud systems. However, their limited processing capacity imposes a trade-off between the potential latency reduction and the achieved accuracy in computationally-intensive services such as deep learning-based services. In this paper, we focus on finding the optimal accuracy-time trade-off for running deep learning services in a three-tier EC platform where several deep learning models with different accuracy levels are available. Specifically, we cast the problem as an Integer Linear Program, where optimal task scheduling decisions are made to maximize overall user satisfaction in terms of accuracy-time trade-off. We prove that our problem is NP-hard and then provide a polynomial constant-time greedy algorithm, called GUS, that is shown to attain near-optimal results. Finally, upon vetting our algorithmic solution through numerical experiments and comparison with a set of heuristics, we deploy it on a testbed implemented to measure for real-world results. The results of both numerical analysis and real-world implementation show that GUS can outperform the baseline heuristics in terms of the average percentage of satisfied users by a factor of at least 50%.