skip to main content
10.1145/1362622.1362695acmconferencesArticle/Chapter ViewAbstractPublication PagesscConference Proceedingsconference-collections
research-article

A job scheduling framework for large computing farms

Published: 10 November 2007 Publication History

Abstract

In this paper, we propose a new method, called Convergent Scheduling, for scheduling a continuous stream of batch jobs on the machines of large-scale computing farms. This method exploits a set of heuristics that guide the scheduler in making decisions. Each heuristics manages a specific problem constraint, and contributes to carry out a value that measures the degree of matching between a job and a machine. Scheduling choices are taken to meet the QoS requested by the submitted jobs, and optimizing the usage of hardware and software resources. We compared it with some of the most common job scheduling algorithms, i.e. Backfilling, and Earliest Deadline First. Convergent Scheduling is able to compute good assignments, while being a simple and modular algorithm.

References

[1]
S. Baruah, S. Funk, and J. Goossens. Robustness results concerning edf scheduling upon uniform multiprocessors. IEEE Transactions on Computers, 52(9):1185--1195, September 2003.
[2]
A. Bayucan, R. L. Henderson, L. T. Jasinskyj, C. Lesiak, B. Mann, T. Proett, and D. Tweten. Portable batch system, administrator guide. Technical Report Release: 2.2, MRJ Technology Solutions, Mountain View, CA, USA, November 1999.
[3]
S.-H. Chiang, A. C. Arpaci-Dusseau, and M. K. Vernon. The impact of more accurate requested runtimes on production job scheduling performance. In JSSPP '02: Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, pages 103--127, London, UK, Lect. Notes Comput. Sci. vol. 2537, 2002. Springer-Verlag.
[4]
A. D. Techiouba, G. Capannini, R. Baraglia, D. Puppin, M. Pasquali, and L. Ricci. Backfilling strategies for scheduling streams of jobs on computational farms. In CoreGRID Workshop on Grid Programming Model, Grid and P2P Systems Architecture, Grid Systems, Tools and Environments, Heraklion-Crete, Greece, June 2007.
[5]
H. El-Rewini, T. G. Lewis, and H. H. ALI. Task Scheduling in Parallel and Distributed Systems. PTR Prentice Hall, Englewood Cliffs, New Jersey, 1994.
[6]
Y. Etsion and D. Tsafrir. A short survey of commercial cluster batch schedulers. Technical Report 2005--13, School of Computer Science and Engineering, The Hebrew University of Jerusalem, May 2005.
[7]
D. D. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel job scheduling, a status report. In Job Scheduling Strategies for Parallel Processing 10th International Workshop, pages 1--16, London, UK, Lect. Notes Comput. Sci. vol. 3277, 2004. Springer-Verlag.
[8]
A. Feldmann, J. Sgall, and S.-H. Teng. Dynamic scheduling on parallel machines. Theor. Comput. Sci., 130(1):49--72, 1994.
[9]
A. Fiat and G. J. Woeginger. Online algorithms, the state of the art. In Developments from a June 1996 seminar on Online algorithms, London, UK, Lect. Notes Comput. Sci. vol. 1442, 1998. Springer-Verlag.
[10]
V. Hamscher, U. Schwiegelshohn, A. Streit, and R. Yahyapour. Evaluation of job-scheduling strategies for grid computing. In GRID '00: Proceedings of the First IEEE/ACM International Workshop on Grid Computing, pages 191--202, London, UK, Lect. Notes Comput. Sci. vol. 1971, 2000. Springer-Verlag.
[11]
D. B. Jackson, Q. Snell, and M. J. Clement. Core algorithms of the maui scheduler. In JSSPP '01: Revised Papers from the 7th International Workshop on Job Scheduling Strategies for Parallel Processing, pages 87--102, London, UK, Lect. Notes Comput. Sci. vol. 2221, 2001. Springer-Verlag.
[12]
T. Kawaguchi and S. Kyan. Worst case bound of an lrf schedule for the mean weighted flow-time problem. SIAM J. Comput., 15(4):1119--1129, 1986.
[13]
D. A. Lifka. The anl/ibm sp scheduling system. In IPPS '95: Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, pages 295--303, London, UK, Lect. Notes Comput. Sci. vol. 949, 1995. Springer-Verlag.
[14]
S. Martello and P. Toth. Knapsack Problems, Algorithms and Computer Implementations. John Wiley and Sons, New York, 1990.
[15]
S. Microsystems. Sun one grid engine administration and user guide. Technical Report Part No. 816-2077-12, Sun Microsystems, Inc., Santa Clara, CA, USA, October 2002.
[16]
A. W. Muálem and D. G. Feitelson. Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling. IEEE Trans. Parallel and Distributed Syst., 12(6):529--543, June 2001.
[17]
D. Puppin, M. Stephenson, W. Lee, and S. Amarasinghe. Convergent scheduling. The Journal of Instruction Level Parallelism, 6(1):1--23, September 2004.
[18]
A. Radulescu and A. J. C. van Gemund. Low-cost task scheduling for distributed-memory machines. IEEE Trans. Parallel Distrib. Syst., 13(6):648--658, 2002.
[19]
U. Schwiegelshohn. Preemptive weighted completion time scheduling of parallel jobs. SIAM Journal on Computing, 33(6):1280--1308, 2004.
[20]
U. Schwiegelshohn, W. Ludwig, J. L. Wolf, J. Turek, and P. S. Yu. Smart smart bounds for weighted response time scheduling. SIAM J. Comput., 28(1):237--253, 1999.
[21]
U. Schwiegelshohn and R. Yahyapour. Analysis of first-come-first-serve parallel job scheduling. In SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pages 629--638, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics.
[22]
E. Shmueli and D. G. Feitelson. Backfilling with lookahead to optimize the packing of parallel jobs. J. Parallel Distrib. Comput., 65(9):1090--1107, 2005.
[23]
S. Srinivasan, R. Kettimuthu, V. Subramani, and P. Sadayappan. Selective reservation strategies for backfill job scheduling. In JSSPP '02: Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, pages 55--71, London, UK, Lect. Notes Comput. Sci. vol. 2537, 2002. Springer-Verlag.

Cited By

View all
  • (2022)Task Scheduling Algorithms in Fog Computing: A Comparison and Analysis2022 International Conference on Automation, Computing and Renewable Systems (ICACRS)10.1109/ICACRS55517.2022.10029029(483-488)Online publication date: 13-Dec-2022
  • (2019)Asymptotic scheduling for many task computing in Big Data platformsInformation Sciences: an International Journal10.5555/2794084.2794143319:C(71-91)Online publication date: 6-Jan-2019
  • (2019)A multi-criteria job scheduling framework for large computing farmsJournal of Computer and System Sciences10.1016/j.jcss.2012.05.00579:2(230-244)Online publication date: 1-Jan-2019
  • Show More Cited By

Index Terms

  1. A job scheduling framework for large computing farms

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    SC '07: Proceedings of the 2007 ACM/IEEE conference on Supercomputing
    November 2007
    723 pages
    ISBN:9781595937643
    DOI:10.1145/1362622
    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: 10 November 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. computing farm
    2. deadline scheduling
    3. job scheduling
    4. software license scheduling

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    SC '07
    Sponsor:

    Acceptance Rates

    SC '07 Paper Acceptance Rate 54 of 268 submissions, 20%;
    Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

    Upcoming Conference

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Task Scheduling Algorithms in Fog Computing: A Comparison and Analysis2022 International Conference on Automation, Computing and Renewable Systems (ICACRS)10.1109/ICACRS55517.2022.10029029(483-488)Online publication date: 13-Dec-2022
    • (2019)Asymptotic scheduling for many task computing in Big Data platformsInformation Sciences: an International Journal10.5555/2794084.2794143319:C(71-91)Online publication date: 6-Jan-2019
    • (2019)A multi-criteria job scheduling framework for large computing farmsJournal of Computer and System Sciences10.1016/j.jcss.2012.05.00579:2(230-244)Online publication date: 1-Jan-2019
    • (2011)EFFICIENT GRID SCHEDULING THROUGH THE INCREMENTAL SCHEDULE‐BASED APPROACHComputational Intelligence10.1111/j.1467-8640.2010.00369.x27:1(4-22)Online publication date: 16-Feb-2011
    • (2010)A Multi-criteria Job Scheduling Framework for Large Computing FarmsProceedings of the 2010 10th IEEE International Conference on Computer and Information Technology10.1109/CIT.2010.69(187-194)Online publication date: 29-Jun-2010
    • (2009)A new grid resource management mechanism with resource-aware policy administrator for SLA-constrained applicationsFuture Generation Computer Systems10.1016/j.future.2008.11.00525:7(768-778)Online publication date: 1-Jul-2009
    • (2008)A two-level scheduler to dynamically schedule a stream of batch jobs in large-scale gridsProceedings of the 17th international symposium on High performance distributed computing10.1145/1383422.1383460(231-232)Online publication date: 23-Jun-2008
    • (2008)Alea – Grid Scheduling Simulation EnvironmentParallel Processing and Applied Mathematics10.1007/978-3-540-68111-3_109(1029-1038)Online publication date: 2008
    • (2008)Comparison Of Multi-Criteria Scheduling TechniquesGrid Computing10.1007/978-0-387-09457-1_15(173-184)Online publication date: 2008
    • (2007)AleaProceedings of the 7th international conference on Parallel processing and applied mathematics10.5555/1786194.1786315(1029-1038)Online publication date: 9-Sep-2007

    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