Semi-Online Multi-Machine with Restart Scheduling for Integrated Edge and Cloud Computing Systems
Authors: 
Liming Ge, Zizhao Wang, Wei Bao, Dong Yuan, Nguyen H. Tran, Bing B. Zhou, 
Albert Y. ZomayaAuthors Info & Claims
Article No.: 70, Pages 1 - 13
Abstract
We study the multi-machine task scheduling problem in an integrated serverless edge and cloud computing system, where tasks can be scheduled locally on edge processors or offloaded to cloud servers, with the objective of minimizing the makespan, i.e., the total time to finish all tasks. The system is semi-online, where the edge processing delays of the tasks are known as priori, but the cloud processing delays remain unknown due to the uncertainty introduced by uploading and loading delay (loading the software environment). The problem is NP-hard in nature, and therefore we resort to approximation schemes and propose a novel algorithm named multi-machine with restart scheduling (MRS). MRS utilizes task restart, where a task that is cancelled will be restarted later when its processing time exceeds the threshold, and the threshold can be adaptively adjusted. We derive an competitive ratio for MRS so that its worst-case gap from the optimal solution is bounded. We also implement the MRS scheduler in a real-world system, which schedules a diverse set of Deep Neural Network (DNN) inference tasks. It shows that MRS achieves significant reduction in makespan compared to existing benchmark schemes.
References
[1]
2022. Docker. https://docs.docker.com/
[2]
2022. Kubernetes. https://kubernetes.io/
[3]
2022. Oracle VM VirtualBox. https://www.virtualbox.org/manual/
[4]
Martín Abadi 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. https://www.tensorflow.org/ Software available from tensorflow.org.
[5]
Susanne Albers and Matthias Hellwig. 2012. Semi-online scheduling revisited. Theoretical Computer Science 443 (2012), 1–9.
[6]
Susanne Albers and Maximilian Janke. 2021. Online Makespan Minimization with Budgeted Uncertainty. In Workshop on Algorithms and Data Structures. Springer, 43–56.
[7]
Ammar Ahmad Awan, Arpan Jain, Ching-Hsiang Chu, Hari Subramoni, and Dhableswar K Panda. 2019. Communication profiling and characterization of deep-learning workloads on clusters with high-performance interconnects. IEEE Micro 40, 1 (2019), 35–43.
[8]
S. Barbarossa, S. Sardellitti, and P. Di Lorenzo. 2014. Communicating While Computing: Distributed mobile cloud computing over 5G heterogeneous networks. IEEE Signal Processing Magazine 31, 6 (Nov 2014), 45–55.
[9]
Marco V Barbera, Sokol Kosta, Alessandro Mei, and Julinda Stefa. 2013. To offload or not to offload? the bandwidth and energy costs of mobile cloud computing. In IEEE International Conference on Computer Communications. IEEE, Turin, Italy, 1285–1293.
[10]
Luciano Baresi and Danilo Filgueira Mendonça. 2019. Towards a serverless platform for edge computing. In IEEE International Conference on Fog Computing (ICFC). IEEE, Prague, Czech Republic, 1–10.
[11]
Jaya Prakash Champati and Ben Liang. 2017. Single restart with time stamps for computational offloading in a semi-online setting. In IEEE International Conference on Computer Communications. IEEE, Atlanta, GA, USA, 1–9.
[12]
Jaya Prakash Varma Champati and Ben Liang. 2019. Single Restart with Time Stamps for Parallel Task Processing with Known and Unknown Processors. IEEE Transactions on Parallel and Distributed Systems (2019).
[13]
Shichao Chen, Qijie Li, Mengchu Zhou, and Abdullah Abusorrah. 2021. Recent advances in collaborative scheduling of computing tasks in an edge computing paradigm. Sensors 21, 3 (2021), 779.
[14]
Xin Chen, Sergey Kovalev, Yuqing Liu, Małgorzata Sterna, Isabelle Chalamon, and Jacek Błażewicz. 2021. Semi-online scheduling on two identical machines with a common due date to maximize total early work. Discrete Applied Mathematics 290 (2021), 71–78.
[15]
TC Edwin Cheng, Hans Kellerer, and Vladimir Kotov. 2005. Semi-on-line multiprocessor scheduling with given total processing time. Theoretical computer science 337, 1-3 (2005), 134–146.
[16]
François Chollet. 2017. Xception: Deep learning with depthwise separable convolutions. In IEEE Conference on Computer Vision and Pattern Recognition. Honolulu, HI, USA, 1251–1258.
[17]
François Chollet 2015. Keras. https://keras.io.
[18]
N. Chopra and S. Singh. 2014. Survey on scheduling in hybrid clouds. In International Conference on Computing, Communications and Networking Technologies. Hefei, China, 1–6. https://doi.org/10.1109/ICCCNT.2014.6963050
[19]
Thinh Quang Dinh, Ben Liang, Tony QS Quek, and Hyundong Shin. 2020. Online resource procurement and allocation in a hybrid edge-cloud computing system. IEEE transactions on wireless communications 19, 3(2020), 2137–2149.
[20]
Gyorgy Dosa, Hans Kellerer, Tomas Olaj, and Zsolt Tuza. 2021. An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time. Theoretical Computer Science 880 (2021), 69–81.
[21]
Maciej Drozdowski. 2009. Scheduling for Parallel Processing. Springer.
[22]
Debasis Dwibedy and Rakesh Mohanty. 2022. Semi-online scheduling: A survey. Computers & Operations Research 139 (2022), 105646.
[23]
Leah Epstein. 2018. A survey on makespan minimization in semi-online environments. Journal of Scheduling 21, 3 (2018), 269–284.
[24]
Niroshinie Fernando, Seng W Loke, and Wenny Rahayu. 2013. Mobile cloud computing: A survey. Future generation computer systems 29, 1 (2013), 84–106.
[25]
Keke Gai, Meikang Qiu, and Hui Zhao. 2018. Energy-aware task assignment for mobile cyber-enabled applications in heterogeneous cloud computing. J. Parallel and Distrib. Comput. 111 (2018), 126–135.
[26]
Keke Gai, Meikang Qiu, Hui Zhao, Lixin Tao, and Ziliang Zong. 2016. Dynamic energy-aware cloudlet-based mobile cloud computing model for green computing. Journal of Network and Computer Applications 59 (2016), 46–54.
[27]
R. L. Graham. 1966. Bounds for certain Multiprocessing Anomalies. Bell System Technical Journal 45 (1966), 1563–1541.
[28]
Ronald L. Graham. 1969. Bounds on multiprocessing timing anomalies. SIAM journal on Applied Mathematics 17, 2 (1969), 416–429.
[29]
Ronald L Graham, Eugene L Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. 1979. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics. Vol. 5. Elsevier, 287–326.
[30]
Songtao Guo, Bin Xiao, Yuanyuan Yang, and Yang Yang. 2016. Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing. In IEEE International Conference on Computer Communications. IEEE, San Francisco, CA, USA, 1–9.
[31]
Yongsheng Hao, Jie Cao, Qi Wang, and Tinghuai Ma. 2021. Energy-aware offloading based on priority in mobile cloud computing. Sustainable Computing: Informatics and Systems 31 (2021), 100563.
[32]
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, NV, USA, 770–778.
[33]
Qiang He, Guangming Cui, Xuyun Zhang, Feifei Chen, Shuiguang Deng, Hai Jin, Yanhui Li, and Yun Yang. 2019. A game-theoretical approach for user allocation in edge computing environment. IEEE Transactions on Parallel and Distributed Systems 31, 3 (2019), 515–529.
[34]
Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. 2017. Mobilenets: Efficient convolutional neural networks for mobile vision applications. preprint arXiv:1704.04861(2017).
[35]
Hans Kellerer, Vladimir Kotov, Maria Grazia Speranza, and Zsolt Tuza. 1997. Semi on-line algorithms for the partition problem. Operations Research Letters 21, 5 (1997), 235–242.
[36]
Karthik Kumar, Jibang Liu, Yung-Hsiang Lu, and Bharat Bhargava. 2013. A survey of computation offloading for mobile systems. Mobile Networks and Applications 18, 1 (2013), 129–140.
[37]
Karthik Kumar and Yung-Hsiang Lu. 2010. Cloud computing for mobile users: Can offloading computation save energy?Computer4(2010), 51–56.
[38]
L. Lei, Z. Zhong, K. Zheng, J. Chen, and H. Meng. 2013. Challenges on wireless heterogeneous networks for mobile cloud computing. IEEE Wireless Communications 20, 3 (June 2013), 34–44.
[39]
Jan Karel Lenstra, David B Shmoys, and Eva Tardos. 1990. Approximation algorithms for scheduling unrelated parallel machines. Mathematical programming 46, 1-3 (1990), 259–271.
[40]
Li Lin, Xiaofei Liao, Hai Jin, and Peng Li. 2019. Computation offloading toward edge computing. Proc. IEEE 107, 8 (2019), 1584–1607.
[41]
Quyuan Luo, Shihong Hu, Changle Li, Guanghui Li, and Weisong Shi. 2021. Resource scheduling in edge computing: A survey. IEEE Communications Surveys & Tutorials 23, 4 (2021), 2131–2165.
[42]
Ran Ma, Sainan Guo, and Cuixia Miao. 2021. A semi-online algorithm and its competitive analysis for parallel-machine scheduling problem with rejection. Appl. Math. Comput. 392(2021), 125670.
[43]
CT Ng, Zhiyi Tan, Yong He, and TC Edwin Cheng. 2009. Two semi-online scheduling problems on two uniform machines. Theoretical Computer Science 410, 8-10 (2009), 776–792.
[44]
Michael L. Pinedo. 2015. Scheduling: Theory, Algorithms, and Systems (5th ed.). Springer.
[45]
Ci N Potts. 1985. Analysis of a linear programming heuristic for scheduling unrelated parallel machines. Discrete Applied Mathematics 10, 2 (1985), 155–164.
[46]
M. Shifrin, R. Atar, and I. Cidon. 2013. Optimal scheduling in the hybrid-cloud. In IFIP/IEEE International Symposium on Integrated Network Management. Ghent, Belgium, 51–59.
[47]
David B. Shmoys, Joel Wein, and David P. Williamson. 1995. Scheduling Parallel Machines On-Line. SIAM J. Comput. 24, 6 (1995), 1313–19.
[48]
Karen Simonyan and Andrew Zisserman. 2014. Very deep convolutional networks for large-scale image recognition. preprint arXiv:1409.1556(2014).
[49]
Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. 2012. UCF101: A dataset of 101 human actions classes from videos in the wild. preprint arXiv:1212.0402(2012).
[50]
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. 2016. Rethinking the inception architecture for computer vision. In IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, NV, USA, 2818–2826.
[51]
Blesson Varghese and Rajkumar Buyya. 2018. Next generation cloud computing: New trends and research directions. Future Generation Computer Systems 79 (2018), 849–861.
[52]
X. Wang, A. Shrivastava, and A. Gupta. 2017. A-Fast-RCNN: Hard Positive Generation via Adversary for Object Detection. In IEEE Conference on Computer Vision and Pattern Recognition. Honolulu, HI, USA, 3039–3048.
[53]
Zizhao Wang, Wei Bao, Dong Yuan, Liming Ge, Nguyen H Tran, and Albert Y Zomaya. 2019. SEE: Scheduling early exit for mobile DNN inference during service outage. In International ACM Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems. 279–288.
[54]
David P Williamson and David B Shmoys. 2011. The design of approximation algorithms. Cambridge university press.
[55]
Xiaoyu Xia, Feifei Chen, Qiang He, John Grundy, Mohamed Abdelrazek, and Hai Jin. 2020. Online collaborative data caching in edge computing. IEEE Transactions on Parallel and Distributed Systems 32, 2 (2020), 281–294.
[56]
Xiaoyu Xia, Feifei Chen, Qiang He, John C Grundy, Mohamed Abdelrazek, and Hai Jin. 2020. Cost-effective app data distribution in edge computing. IEEE Transactions on Parallel and Distributed Systems 32, 1 (2020), 31–44.
[57]
Xiaolong Xu, Hao Tian, Xuyun Zhang, Lianyong Qi, Qiang He, and Wanchun Dou. 2022. DisCOV: distributed COVID-19 detection on X-ray images with edge-cloud collaboration. IEEE Transactions on Services Computing(2022).
[58]
Weiwen Zhang, Yonggang Wen, and Dapeng Oliver Wu. 2013. Energy-efficient scheduling policy for collaborative execution in mobile cloud computing. In IEEE International Conference on Computer Communications. IEEE, Turin, Italy, 190–194.
[59]
Weiming Zhuang, Yonggang Wen, and Shuai Zhang. 2021. Joint Optimization in Edge-Cloud Continuum for Federated Unsupervised Person Re-identification. preprint arXiv:2108.06493(2021).
Recommendations
Semi-online scheduling on a single machine with unexpected breakdown
In this paper, we consider a single machine scheduling problem where a breakdown period occurs in an online way. Two main objective functions are studied: the makespan and the maximum lateness. We propose two approximation algorithms for the makespan ...
An efficient algorithm for semi-online multiprocessor scheduling with given total processing time
We consider a semi-online multiprocessor scheduling problem with a given a set of identical machines and a sequence of jobs, the sum of whose processing times is known in advance. The jobs are to be assigned online to one of the machines and the ...
Semi-online scheduling on two identical machines with rejection
In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2022
976 pages
ISBN:9781450397339
DOI:10.1145/3545008
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 January 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
ICPP '22
ICPP '22: 51st International Conference on Parallel Processing
August 29 - September 1, 2022
Bordeaux, France
Acceptance Rates
Overall Acceptance Rate 91 of 313 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 104Total Downloads
- Downloads (Last 12 months)44
- Downloads (Last 6 weeks)5
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format