article

Scheduling of a meta-task with QoS requirements in heterogeneous computing systems

Authors:

Füsun ÖzgünerAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 66, Issue 2

Pages 181 - 196

https://doi.org/10.1016/j.jpdc.2005.07.004

Published: 01 February 2006 Publication History

Abstract

Due to the development of new applications and the increasing number of users with diverse needs who are exposed to heterogeneous computing (HC), providing users with quality of service (QoS) guarantees while executing applications has become a crucial problem that needs to be addressed. Motivated by this fact, this paper investigates the problem of scheduling a set of independent tasks with multiple QoS needs, which may include timeliness, reliability, security, data accuracy, and priority, in a HC system. This problem is referred to as the QoS-based scheduling problem and proved to be NP-hard. In the first part of this study, we formulate the QoS-based scheduling problem by using utility and penalty functions, where a utility function associated with a task is used to measure how much the owner of this task will benefit from a given scheduling decision, while penalty functions associated with resources are used to provide incentives to users to set their QoS requirements in accordance with their needs. In order to solve the QoS-based scheduling problem, a computationally efficient static scheduling algorithm (QSMTS_IP) which assumes time-invariant penalty functions is developed. We later extend the QSMTS_IP to the case where penalty functions are time varying. Furthermore, it is shown that the QSMTS_IP can be modified to run as a dynamic scheduling algorithm. The simulation studies carried out show that the QSMTS_IP is capable of meeting diverse QoS requirements of many users simultaneously, while minimizing the number of users whose tasks cannot be scheduled due to the scarcity of machines.

References

[1]

{1} R.J.A. Ali, et al., Analysis and provision of QoS for distributed grid applications, J. Grid Comput. 2 (2) (2004) 163-182.]]

[2]

{2} S. Ali, H.J. Siegel, M. Maheswaran, D. Hensgen, S. Ali, Task execution time modeling for heterogeneous computing systems, in: Heterogeneous Computing Workshop, Cancún, Mexico, May 2000, pp. 185-199.]]

Digital Library

[3]

{3} Y. Amir, B. Awerbuch, R.S. Borgstrom, A cost-benefit framework for online management of a metacomputing system, in: International Conference on Information and Computational Economies, October 1998, pp. 140-147.]]

Digital Library

[4]

{4} M. Baker, R. Buyya, D. Laforenza, Grids and grid technologies for wide-area distributed computing, Internat. J. Software: Practice Exp. 32 (December 2002) 1437-1466.]]

Digital Library

[5]

{5} T.D. Braun, et al., A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems, in: Heterogeneous Computing Workshop, San Juan, Puerto Rico, April 1999, pp. 15-29.]]

Digital Library

[6]

{6} T.D. Braun, H.J. Siegel, A. Maciejewski, Static mapping heuristics for tasks with dependencies, priorities, deadlines, and multiple versions in heterogeneous environments, in: International Parallel and Distributed Processing Symposium, Fort Lauderdale, FL, April 2002.]]

Digital Library

[7]

{7} R. Buyya, D. Abramson, J. Giddy, A case for economy grid architecture for service-oriented grid computing, in: Heterogeneous Computing Workshop, San Francisco, CA, April 2001.]]

Digital Library

[8]

{8} R. Buyya, D. Abramson, J. Giddy, H. Stockinger, Economic models for resource management and scheduling in grid computing, Concurrency Comput.: Practice Exp. 14 (13-15) (2002) 1507-1542.]]

[9]

{9} A. Caprara, H. Kellerer, U. Pferschy, D. Pisinger, Approximation algorithms for knapsack problems with cardinality constraints, Europ. J. Oper. Res. 123 (2000) 333-345.]]

[10]

{10} S. Chatterjee, A quality of service based allocation and routing algorithm for distributed, heterogeneous real time systems, in: International Conference on Distributed Computing Systems, Baltimore, MD, May 1997, pp. 235-243.]]

Digital Library

[11]

{11} S. Chatterjee, J. Sydir, B. Sabata, T. Lawrence, Modeling applications for adaptive QoS-based resource management, in: Proceedings of the Second IEEE High Assurance Systems Engineering Workshop, August 1997.]]

Digital Library

[12]

{12} R. Cocchi, S. Shenker, D. Estrin, L. Zhang, Pricing in computer networks: motivation, formulation, and example, IEEE/ACM Trans. Networking 6 (December 1993) 614-627.]]

Digital Library

[13]

{13} A. Doǧan, F. Özgüner, Scheduling independent tasks with QoS requirements in grid computing with time-varying resource pricing, Lecture Notes in Computer Science, vol. 2536, Springer, Berlin, 2002, pp. 58-69.]]

Digital Library

[14]

{14} M.M. Eshagian, Heterogeneous Computing, Artech House, Norwood, MA, 1996.]]

[15]

{15} I. Foster, C. Kesselman, Globus: a metacomputing infrastructure toolkit, Internat. J. Supercomput. Appl. 11 (2) (1997) 115-128.]]

Digital Library

[16]

{16} I. Foster, C. Kesselman, S. Tuecke, The anatomy of the grid: enabling scalable virtual organizations, Internat. J. Supercomput. Appl. 15 (3) (2001) 3-23.]]

Digital Library

[17]

{17} J. Frey, T. Tannenbaum, I. Foster, M. Livny, S. Tuecke, Condor-G: a computation management agent for multi-institutional grids, Cluster Comput. 5 (3) (2002) 237-246.]]

Digital Library

[18]

{18} K.S. Golconda, F. Özgüner, A. Doǧan, A comparison of static QoS-based scheduling heuristics for a meta-task with multiple QoS dimensions in heterogeneous computing, in: Heterogeneous Computing Workshop, Santa Fe, NM, April 2004.]]

[19]

{19} B. Hamidzadeh, Y. Atif, Dynamic scheduling of real-time tasks, by assignment, IEEE Concurrency: Parallel Distrib. Mobile Comput. 6 (1998) 14-25.]]

Digital Library

[20]

{20} D.A. Hensgen, et al., An overview of MSHN: the management system for heterogeneous networks, in: Heterogeneous Computing Workshop, San Juan, Puerto Rico, 1999, pp. 184-198.]]

Digital Library

[21]

{21} C. Irvine, T. Levin, Toward a taxonomy and costing method for security services, in: 15th Annual Computer Security Applications Conference, December 1999.]]

Digital Library

[22]

{22} M.A. Iverson, Dynamic mapping and scheduling algorithms for a multi-user heterogeneous computing environment, Ph.D. Thesis, The Ohio State University, Columbus, Ohio, 1999.]]

Digital Library

[23]

{23} M.A. Iverson, F. Özgüner, L. Potter, Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment, IEEE Trans. Comput. 48 (December 1999) 1374-1379.]]

Digital Library

[24]

{24} K. Keahey, et al., Grids for experimental science: the virtual control room, in: International Workshop on Challenges of Large Applications in Distributed Environments, Honolulu, HI, June 2004.]]

Digital Library

[25]

{25} J.-K. Kim, et al., A QoS performance measure framework for distributed heterogeneous networks, in: Proceedings of the Eighth Euromicro Workshop on Parallel and Distributed Processing, Rhodos, Greece, January 2000, pp. 18-27.]]

[26]

{26} J.-K. Kim, et al., Dynamic mapping in heterogeneous environment with task having priorities and multiple deadlines, in: Heterogeneous Computing Workshop, Nice, France, April 2003.]]

[27]

{27} Y.A. Korilis, A. Orda, Incentive compatible pricing strategies for QoS routing, in: IEEE INFOCOM, New York, NY, March 1999, pp. 891-899.]]

[28]

{28} K. Krauter, R. Buyya, M. Maheswaran, A taxonomy and survey of grid resource management systems for distributed computing, Internat. J. Software: Practice Exp. 32 (February 2002) 135-164.]]

Digital Library

[29]

{29} Y.-K. Kwok, I. Ahmad, Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors, IEEE Trans. Parallel Distrib. Systems 7 (May 1996) 506-521.]]

Digital Library

[30]

{30} Y.-K. Kwok, I. Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Comput. Surveys 31 (December 1999) 406-471.]]

Digital Library

[31]

{31} C. Lee, J. Lehoczky, D. Siewiorek, R. Rajkumar, J. Hansen, A scalable solution to the multi-resource QoS-problem, in: IEEE Real-Time Systems Symposium, Phoenix, AZ, December 1999, pp. 315-326.]]

Digital Library

[32]

{32} M. Maheswaran, Quality of service driven resource management algorithms for network computing, in: International Conference on Parallel and Distributed Processing Techniques and Applications, June 1999, pp. 1090-1096.]]

[33]

{33} M. Maheswaran, S. Ali, H.J. Seigel, D. Hensgen, R.F. Freund, Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems, in: Heterogeneous Computing Workshop, San Juan, Puerto Rico, April 1999, pp. 30-44.]]

Digital Library

[34]

{34} B. Sabata, S. Chatterjee, M. Davis, J. Sydir, T. Lawrence, Taxonomy for QoS specifications, in: Proceedings of WORDS, Newport Beach, CA, February 1997, pp. 100-107.]]

Digital Library

[35]

{35} J. Sairamesh, J.O. Kephart, Price dynamics of vertically differentiated information markets, in: International Conference on Information and Computational Economy, October 1998.]]

Digital Library

[36]

{36} N. Semret, R.R.-F. Liao, A.T. Campbell, A.A. Lazar, Market pricing of differentiated internet services, Technical Report CU/CTR/TR 503-98-37, Columbia University, December 1998.]]

[37]

{37} H.J. Siegel, S. Ali, Techniques for mapping tasks to machines in heterogeneous computing systems, EUROMICRO J. System Archit. Special Issue on Heterogeneous Distrib. Parallel Archit. Software Design Tools 46 (8) (2000) 627-639.]]

Digital Library

[38]

{38} W.E. Walsh, M.P. Wellman, P.R. Wurman, J.K. MacKie-Mason, Some economics of market-based distributed scheduling, in: International Conference on Distributed Computing Systems, Amsterdam, Netherlands, May 1998, pp. 612-621.]]

Digital Library

[39]

{39} R. Wolski, J.S. Plank, T. Bryan, J. Brevik, G-commerce: market formulations controlling resource allocation on the computational grid, in: International Parallel and Distributed Processing Symposium, San Francisco, CA, April 2001.]]

Digital Library

[40]

{40} M.-Y. Wu, W. Shu, H. Zhang, Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems, in: Heterogeneous Computing Workshop, Cancún, Mexico, May 2000, pp. 375-385.]]

Digital Library

[41]

{41} J. Yang, A. Khokhar, S. Sheikh, A. Ghafoor, Estimating execution time for parallel tasks in heterogeneous processing (HP) environment, in: Heterogeneous Computing Workshop, Cancú;n, Mexico, April 1994, pp. 23-28.]]

Cited By

De Falco IScafuri UTarantino E(2018)Mapping of time-consuming multitask applications on a cloud system by multiobjective Differential EvolutionParallel Computing10.1016/j.parco.2015.04.00148:C(40-58)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/j.parco.2015.04.001
Zhu XGe RSun JHe C(2013)3EJournal of Systems and Software10.1016/j.jss.2012.08.01786:2(302-314)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.jss.2012.08.017
Fard HProdan RBarrionuevo JFahringer T(2012)A Multi-objective Approach for Workflow Scheduling in Heterogeneous EnvironmentsProceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)10.1109/CCGrid.2012.114(300-309)Online publication date: 13-May-2012
https://dl.acm.org/doi/10.1109/CCGrid.2012.114
Show More Cited By

Index Terms

Scheduling of a meta-task with QoS requirements in heterogeneous computing systems

Recommendations

On QoS-Based Scheduling of a Meta-Task with Multiple QoS Demands in Heterogeneous Computing
IPDPS '02: Proceedings of the 16th International Symposium on Parallel and Distributed Processing

This paper investigates the problem of scheduling a set of independent tasks with multiple QoS needs, which may include timeliness, reliability, security, data accuracy, and priority, in a heterogeneous computing system. This problem is referred to as ...
A Novel Heterogeneous Scheduling Algorithm with Improved Task Priority
HPCC-CSS-ICESS '15: Proceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems

Efficient application scheduling algorithms are important to obtain high performance in heterogeneous computing systems. However, most of current algorithms are of low efficiency in scheduling. Aiming at this problem, we propose a heterogeneous ...
Algorithms for task scheduling in heterogeneous computing environments

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 66, Issue 2

February 2006

160 pages

ISSN:0743-7315

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2005.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 February 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

De Falco IScafuri UTarantino E(2018)Mapping of time-consuming multitask applications on a cloud system by multiobjective Differential EvolutionParallel Computing10.1016/j.parco.2015.04.00148:C(40-58)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.1016/j.parco.2015.04.001
Zhu XGe RSun JHe C(2013)3EJournal of Systems and Software10.1016/j.jss.2012.08.01786:2(302-314)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.jss.2012.08.017
Fard HProdan RBarrionuevo JFahringer T(2012)A Multi-objective Approach for Workflow Scheduling in Heterogeneous EnvironmentsProceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)10.1109/CCGrid.2012.114(300-309)Online publication date: 13-May-2012
https://dl.acm.org/doi/10.1109/CCGrid.2012.114
Zhu JZhu XJiang J(2011)Improving adaptivity and fairness of processing real-time tasks with QoS requirements on clusters through dynamic schedulingInformation Processing Letters10.1016/j.ipl.2011.03.020111:12(609-613)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.1016/j.ipl.2011.03.020
De Falco IScafuri UTarantino E(2010)An adaptive multisite mapping for computationally intensive grid applicationsFuture Generation Computer Systems10.1016/j.future.2010.02.00926:6(857-867)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1016/j.future.2010.02.009
Ding DLuo SGao Z(2010)A matrix scheduling strategy with multi-qos constraints in computational gridProceedings of the 5th international conference on Advances in Grid and Pervasive Computing10.1007/978-3-642-13067-0_10(59-68)Online publication date: 10-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13067-0_10
De Falco IMaisto DScafuri UTarantino EDella Cioppa AFolino GKrasnogor NMastroianni CZambonelli F(2009)An innovative perspective on mapping in gridsProceedings of the 2009 workshop on Bio-inspired algorithms for distributed systems10.1145/1555284.1555289(27-36)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1145/1555284.1555289
Jiang CWang CLiu XZhao Y(2007)A fuzzy logic approach for secure and fault tolerant grid job schedulingProceedings of the 4th international conference on Autonomic and Trusted Computing10.5555/2394798.2394867(549-558)Online publication date: 11-Jul-2007
https://dl.acm.org/doi/10.5555/2394798.2394867
Jiang CWang CLiu XZhao Y(2007)A survey of job scheduling in gridsProceedings of the joint 9th Asia-Pacific web and 8th international conference on web-age information management conference on Advances in data and web management10.5555/1769708.1769763(419-427)Online publication date: 16-Jun-2007
https://dl.acm.org/doi/10.5555/1769708.1769763

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents