skip to main content
10.1145/1167350.1167380acmconferencesArticle/Chapter ViewAbstractPublication Pagesacm-seConference Proceedingsconference-collections
Article

A low complexity algorithm for dynamic scheduling of independent tasks onto heterogeneous computing systems

Published: 18 March 2005 Publication History

Abstract

Scheduling a set of independent tasks onto a network of heterogeneous computing systems to minimize the overall execution time is NP-hard. Among the algorithms that have been proposed in the past, the Sufferage algorithm [5] has the best performance in minimizing the makespan of a set of independent tasks. We propose a new low complexity scheduling algorithm, Heterogeneous Largest Task First (HLTF). Its complexity is O(s(Log s + m)) vs. O(s2*m) of Sufferage, where s is the number of tasks and m is the number of available machines. Simulation results reveal that in terms of minimizing the makespan, the performance of HLTF is slightly better than that of the Sufferage algorithm. In terms of running cost, HLTF significantly outperforms the Sufferage algorithm.

References

[1]
A. Abraham, R. Buyya and B. Nath, "Nature's Heuristics for Scheduling Jobs on Computational Grids," ADCOM 2000, pp. 45--52, Cochin India.
[2]
C. Junwei, D. P Spooner, S. A Jarvis, S. Saini and G. R Nudd, "Agent-based Grid Load Balancing using Performance driven Task Scheduling," Proceedings of the International Parallel and Distributed Processing Symposium, April 2003, pp. 22--26.
[3]
M. Arora, S. K. Das and R. Biswas, "A De-Centralized Scheduling and Load Balancing Algorithm for Heterogeneous Grid Environments," ICPP Workshops 2002, pp. 499--505.
[4]
M. Maheswaran, S. Ali and H. Siegel, "Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems," Eighth Heterogeneous Computing Workshop, April 1999, San Juan, Puerto Rico.
[5]
M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen and R. F. Freund, "Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems," Journal of Parallel and Distributed Computing, vol. 59, no. 2, Nov 1999, pp. 107--131.
[6]
M. Wu and X. H. Sun, "A General Self-adaptive Task Scheduling System for Non-dedicated Heterogeneous Computing," IEEE International Conference on Cluster Computing, 2003, Hong Kong, December 2003.
[7]
N. Fujimoto and K. Hagihara, "Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid," ICPP 2003.
[8]
R. F. Freund, M. Gherrity, S. Ambrosius, M. Campbell, M. Halderman, D. Hensgen, E. Keith, T. Kidd, M. Kussow, J. D. Lima, F. Mirabile, L. Moore, B. Rust, and H. J. Siegel, "Scheduling Resources in Multi-User, Heterogeneous, Computing Environments with SmartNet," 7th IEEE Heterogeneous Computing Workshop (HCW '98), Mar.1998, pp. 184--199.
[9]
T. H Cormen, C. E. Leiserson and R. L. Rivest, "Introduction to Algorithms," The MIT Press, 2001, pp. 13
[10]
X. He, X-H. Sun and G. Laszewski, "A QoS Guided Scheduling Algorithm for the Computational Grid," Proc. of the International Workshop on Grid and Cooperative Computing (GCC02), Hainan, China, Dec. 2002.
[11]
X-H Sun and M. Wu, "Grid Harvest Service: a System for Long-Term, Application-Level Task Scheduling," Proceedings of the International Parallel and Distributed Processing Symposium, 2003, April 22--26, 2003 pp. 25--32.
[12]
X. He, X-H Sun and G. V Laszewski, "QoS Guided Min-Min Heuristic for Grid Task Scheduling," Journal of Computer Science and Technology, Special Issue on Grid Computing, vol 18, no 4, 2003.
[13]
Z. Xu, X. Hou and J. Sun "Ant Algorithm-based Task Scheduling in Grid Computing," IEEE CCECE 2003 Canadian Conference on Electrical and Computer Engineering, vol 2, May 4--7 2003.

Cited By

View all
  • (2014)Improving the Performance of IndependentTask Assignment Heuristics MinMin,MaxMin and SufferageIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.10725:5(1244-1256)Online publication date: 1-May-2014
  • (2012)Characterization of the iterative application of makespan heuristics on non-makespan machines in a heterogeneous parallel and distributed environmentThe Journal of Supercomputing10.1007/s11227-011-0729-762:1(461-485)Online publication date: 1-Oct-2012
  • (2011)Efficient Algorithm on heterogeneous computing system2011 International Conference on Recent Trends in Information Systems10.1109/ReTIS.2011.6146840(57-61)Online publication date: Dec-2011
  • Show More Cited By

Index Terms

  1. A low complexity algorithm for dynamic scheduling of independent tasks onto heterogeneous computing systems

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ACMSE '05 vol 1: Proceedings of the 43rd annual ACM Southeast Conference - Volume 1
      March 2005
      408 pages
      ISBN:1595930590
      DOI:10.1145/1167350
      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 ACM 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]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 18 March 2005

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. heterogeneous computing
      2. independent tasks
      3. makespan
      4. scheduling

      Qualifiers

      • Article

      Conference

      ACM SE05
      Sponsor:
      ACM SE05: ACM Southeast Regional Conference 2005
      March 18 - 20, 2005
      Georgia, Kennesaw

      Acceptance Rates

      Overall Acceptance Rate 502 of 1,023 submissions, 49%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)2
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2014)Improving the Performance of IndependentTask Assignment Heuristics MinMin,MaxMin and SufferageIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.10725:5(1244-1256)Online publication date: 1-May-2014
      • (2012)Characterization of the iterative application of makespan heuristics on non-makespan machines in a heterogeneous parallel and distributed environmentThe Journal of Supercomputing10.1007/s11227-011-0729-762:1(461-485)Online publication date: 1-Oct-2012
      • (2011)Efficient Algorithm on heterogeneous computing system2011 International Conference on Recent Trends in Information Systems10.1109/ReTIS.2011.6146840(57-61)Online publication date: Dec-2011
      • (2011)Time Utility Functions for Modeling and Evaluating Resource Allocations in a Heterogeneous Computing SystemProceedings of the 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and PhD Forum10.1109/IPDPS.2011.123(7-19)Online publication date: 16-May-2011
      • (2010)A heuristic for task scheduling based on hasse diagram2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA)10.1109/BICTA.2010.5645109(1085-1092)Online publication date: Sep-2010
      • (2009)A Controlled Scheduling Algorithm Decreasing the Incidence of Starvation in Grid EnvironmentsProceedings of the International Conference on Artificial Intelligence and Computational Intelligence10.1007/978-3-642-05253-8_57(517-525)Online publication date: 21-Nov-2009
      • (2008)Dynamic On-Line Allocation of Independent Task onto Heterogeneous Computing Systems to Maximize Load Balancing2008 IEEE International Symposium on Signal Processing and Information Technology10.1109/ISSPIT.2008.4775659(418-425)Online publication date: Dec-2008

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media