More Web Proxy on the site http://driver.im/

research-article

Semi-Online Algorithms for Computational Task Offloading with Communication Delay

Authors:

Jaya Prakash Champati,

Ben LiangAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 28, Issue 4

Pages 1189 - 1201

https://doi.org/10.1109/TPDS.2016.2605684

Published: 01 April 2017 Publication History

Abstract

We study the scheduling of computational tasks on one local processor and one remote processor with communication delay. This problem has important application in cloud computing. Although the communication time to transmit a task can be inferred from the known data size of the task and the transmission bandwidth, the processing time of the task is generally unknown until it is processed to completion. Given a set of independent tasks with unknown processing times, our objective is to minimize makespan. We study the problem under two scenarios: 1) the communication times of the tasks to the remote processor are smaller than their corresponding processing times on the remote processor, and 2) the communication times of the tasks to the remote processor are larger than their corresponding processing times on the remote processor. For the first scenario we propose the Semi-online Partitioning and Communication (SPaC) algorithm, and for the second scenario we propose the SPaC-Restart (SPaC-R) algorithm. Even though the offline version of this problem, with a priori known processing times, is NP-hard, we show that the proposed semi-online algorithms achieve $O(1)$ competitive ratios for their intended scenarios. We also provide competitive ratios for both algorithms for more general communication times. We use simulation to demonstrate that SPaC and SPaC-R outperform online list scheduling and performs comparably well with the best known offline heuristics.

References

[1]

M. Armbrust, et al., “A view of cloud computing,” Commun. ACM, vol. Volume 53, no. Issue 4, pp. 50–58, 2010.

Digital Library

[2]

R. L. Graham, “Bounds for certain multiprocessing anomalies,” Bell Syst. Tech. J., vol. Volume 45, pp. 1563–1541, 1966.

[3]

D. B. Shmoys, J. Wein, and D. P. Williamson, “Scheduling parallel machines on-line,” SIAM J. Comput., vol. Volume 24, no. Issue 6, pp. 1313–1331, 1995.

Digital Library

[4]

G. Fries, “Scheduling independent tasks on uniform processors,” SIAM J. Comput., vol. Volume 13, no. Issue 1, pp. 705–716, 1984.

Digital Library

[5]

A. Kovcs, “New approximation bounds for LPT scheduling,” Algorithmica, vol. Volume 57, no. Issue 2, pp. 413–433, 2010.

Digital Library

[6]

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey,” Ann. Discrete Math., vol. Volume 5, no. Issue 2, pp. 287–326, 1979.

[7]

D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, 1st ed. Cambridge, U.K.: Cambridge Univ. Press, 2011.

Digital Library

[8]

H. Casanova, A. Legrand, D. Zagorodnov, and F. Berman, “Heuristics for scheduling parameter sweep applications in grid environments,” in Proc. 9th Heterogeneous Comput. Workshop, 2000, pp. 349–363.

Digital Library

[9]

A. Giersch, Y. Robert, and F. Vivien, “Scheduling tasks sharing files on heterogeneous master-slave platforms,” J. Syst. Archit., vol. Volume 52, no. Issue 2, pp. 88–104, 2006.

Digital Library

[10]

K. Kaya and C. Aykanat, “Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master-slave environments,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 17, no. Issue 8, pp. 883–896, 2006.

Digital Library

[11]

O. Beaumont, A. Legrand, and Y. Robert, “The master-slave paradigm with heterogeneous processors,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 14, no. Issue 9, pp. 897–908, 2003.

Digital Library

[12]

M. Drozdowski, Scheduling for Parallel Processing, 1st ed. Berlin, Germany: Springer, 2009.

Digital Library

[13]

K. Kumar, J. Liu, Y.-H. Lu, and B. Bhargava, “A survey of computation offloading for mobile systems,” Mobile Netw. Appl., vol. Volume 18, no. Issue 1, pp. 129–140, 2013.

Digital Library

[14]

E. K. Tabak, B. B. Cambazoglu, and C. Aykanat, “Improving the performance of independent task assignment heuristics minmin, maxmin and sufferage,” IEEE Trans. Parallel Distrib. Syst., vol. Volume 25, no. Issue 5, pp. 1244–1256, 2014.

Digital Library

[15]

V. V. Vazirani, Approximation Algorithms . New York, NY, USA: Springer-Verlag, 2001.

Digital Library

[16]

H. Kellerer, V. Kotov, M. G. Speranza, and Z. Tuza, “Semi on-line algorithms for the partition problem,” Operations Res. Lett., vol. Volume 21, no. Issue 5, pp. 235–242, 1997.

Digital Library

[17]

T. E. Cheng, H. Kellerer, and V. Kotov, “Semi-on-line multiprocessor scheduling with given total processing time,” Theoretical Comput. Sci., vol. Volume 337, no. pp.1</fpage>––3</lpage>, pp. <fpage>134<lpage>146, 2005.

Digital Library

[18]

S. Albers and M. Hellwig, “Semi-online scheduling revisited,” Theoretical Comput. Sci., vol. Volume 443, pp. 1–9, 2012.

Digital Library

[19]

H. Kellerer, V. Kotov, and M. Gabay, “An efficient algorithm for semi-online multiprocessor scheduling with given total processing time,” J. Scheduling, vol. Volume 18, no. Issue 6, pp. 623–630, 2015.

Digital Library

[20]

C. Ng, Z. Tan, Y. He, and T. Cheng, “Two semi-online scheduling problems on two uniform machines,” Theoretical Comput. Sci., vol. Volume 410, no. pp.8</fpage>––10</lpage>, pp. <fpage>776<lpage>792, 2009.

Digital Library

[21]

R. K. Balan, M. Satyanarayanan, S. Y. Park, and T. Okoshi, “Tactics-based remote execution for mobile computing,” in Proc. Int. Conf. Mobile Syst. Appl. Services, 2003, pp. 273–286.

Digital Library

[22]

E. Cuervo, et al., “MAUI: Making smartphones last longer with code offload,” in Proc. 8th Int. Conf. Mobile Syst. Appl. Services, 2010, pp. 49–62.

Digital Library

[23]

S. Kosta, A. Aucinas, P. Hui, R. Mortier, and X. Zhang, “ThinkAir: Dynamic resource allocation and parallel execution in the cloud for mobile code offloading,” in Proc. IEEE INFOCOM, 2012, pp. 945–953.

[24]

N. Fernando, S. W. Loke, and W. Rahayu, “Mobile cloud computing: A survey,” Future Generation Comput. Syst., vol. Volume 29, no. Issue 1, pp. 84–106, 2013.

Digital Library

[25]

J. Champati and B. Liang, “Energy compensated cloud assistance in mobile cloud computing,” in Proc. IEEE INFOCOM Workshop Mobile Cloud Comput., Apr. 2014, pp. 392–397.

[26]

M. Rahman, X. Li, and H. N. Palit, “Hybrid heuristic for scheduling data analytics workflow applications in hybrid cloud environment,” in Proc. IEEE Int. Symp. Parallel Distrib. Process. Workshops, 2011, pp. 966–974.

Digital Library

[27]

X. Qiu, W. L. Yeow, C. Wu, and F. C. M. Lau, “Cost-minimizing preemptive scheduling of MapReduce workloads on hybrid clouds,” in Proc. IEEE Int. Symp. Quality Service, 2013, pp. 213–313.

[28]

M. Shifrin, R. Atar, and I. Cidon, “Optimal scheduling in the hybrid-cloud,” in Proc. IFIP/IEEE Int. Symp. Integr. Netw. Manage., 2013, pp. 51–59.

[29]

J. P. Champati and B. Liang, “One-restart algorithm for scheduling and offloading in a hybrid cloud,” in Proc. IEEE/ACM 23rd Int. Symp. Quality Service, Jun. 2015. pp. 31–40.

[30]

S. M. Johnson, “Optimal two-and three-stage production schedules with setup times included,” Naval Res. Logistics Quart., vol. Volume 1, no. Issue 1, pp. 61–68, 1954.

[31]

K. R. Baker and D. Trietsch, Principles of Sequencing and Scheduling . Hoboken, NJ, USA: Wiley, 2009.

Digital Library

Cited By

Fresa AChampati J(2023)Offloading Algorithms for Maximizing Inference Accuracy on Edge Device in an Edge Intelligence SystemIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.326745834:7(2025-2039)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3267458
Moothedath VChampati JGross J(2023)Energy Efficient Sampling Policies for Edge Computing Feedback SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2022.316585222:8(4634-4647)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3165852
Fresa AChampati JBoukerche AGiannelli CSun Z(2022)An Offloading Algorithm for Maximizing Inference Accuracy on Edge Device in an Edge Intelligence SystemProceedings of the 25th International ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems10.1145/3551659.3559044(15-23)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1145/3551659.3559044
Show More Cited By

Semi-Online Algorithms for Computational Task Offloading with Communication Delay
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
  2. Software organization and properties
    1. Software system structures
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Semi-online algorithms for scheduling with machine cost

In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and ...
Semi-online scheduling for jobs with release times

In this paper we consider three semi-online scheduling problems for jobs with release times on m identical parallel machines. The worst case performance ratios of the LS algorithm are analyzed. The objective function is to minimize the maximum ...
Optimal semi-online algorithms for machine covering

This paper investigates the semi-online machine covering problems on m>=3 parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed. We prove that if the total processing time of all jobs or the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 28, Issue 4

April 2017

310 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2017.

Publisher

IEEE Press

Publication History

Published: 01 April 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fresa AChampati J(2023)Offloading Algorithms for Maximizing Inference Accuracy on Edge Device in an Edge Intelligence SystemIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.326745834:7(2025-2039)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3267458
Moothedath VChampati JGross J(2023)Energy Efficient Sampling Policies for Edge Computing Feedback SystemsIEEE Transactions on Mobile Computing10.1109/TMC.2022.316585222:8(4634-4647)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3165852
Fresa AChampati JBoukerche AGiannelli CSun Z(2022)An Offloading Algorithm for Maximizing Inference Accuracy on Edge Device in an Edge Intelligence SystemProceedings of the 25th International ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems10.1145/3551659.3559044(15-23)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1145/3551659.3559044
Eshraghi NLiang B(2019)Joint Offloading Decision and Resource Allocation with Uncertain Task Computing RequirementIEEE INFOCOM 2019 - IEEE Conference on Computer Communications10.1109/INFOCOM.2019.8737559(1414-1422)Online publication date: 29-Apr-2019
https://dl.acm.org/doi/10.1109/INFOCOM.2019.8737559

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents