Comparison Of Backfilling Algorithms For Job Scheduling In Distributed Memory Parallel System
- Conference
- Location
-
Chicago, Illinois
- Publication Date
-
June 18, 2006
- Start Date
-
June 18, 2006
- End Date
-
June 21, 2006
- ISSN
-
2153-5965
- Conference Session
- Tagged Division
-
Computers in Education
- Page Count
-
12
- Page Numbers
-
11.339.1 - 11.339.12
- DOI
-
10.18260/1-2--1000
- Permanent URL
-
https://strategy.asee.org/1000
- Download Count
-
1947
Paper Authors
Hasasn Rajaei Bowling Green State University
Hassan Rajaei is an Associate Professor in the Computer Science Department at Bowling Green State University.
His research interests include computer simulation, distributed and parallel simulation, performance evaluation of communication networks, wireless communications, distributed and parallel processing. Dr. Rajaei received his Ph.D. from Royal Institute of Technologies, KTH, Stockholm, Sweden and he holds an MSE from U. of Utah.
Mohammad Dadfar Bowling Green State University
Abstract
NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract
Session xxxx
Comparison Of Backfilling Algorithms For Job Scheduling In Distributed-Memory Parallel System
Hassan Rajaei And Mohammad B. Dadfar
Department Of Computer Science Bowling Green State University Bowling Green, Ohio 43403 {Rajaei, Dadfar}@Cs.Bgsu.Edu
Abstract
In this paper, we compare the performance of backfilling scheduling algorithms using multiple- queue and look-ahead with the basic aggressive strategy on a multiprocessor system. Schedulers employing backfilling algorithms in distributed-memory parallel system have been found to improve system utilization and job response time by allowing smaller jobs from back of the waiting queue to execute before the larger jobs which have arrived earlier. Backfilling algorithms also overcome the problem of starvation and waste of processing resources exhibited by algorithms like shortest job first and longest job first. We have implemented the backfilling scheduling algorithms with basic aggressive, multiple-queue, and with look-ahead strategy. We compare their performances and investigate the conditions for increasing the utilization and decreasing the fragmentation of the system resources.
The look-ahead backfilling scheduling algorithm attempts to find the best packing possible given the current composition of the queue, thus maximizing the utilization at every scheduling step. It reduces the mean response time of all jobs. We use simulation to evaluate the performance of the scheduling disciplines.
1. Introduction
We have installed a Beowulf cluster1, 2 with 16 computing nodes in one of our instructional labs. It provides a high performance computing environment for our courses. In our previous paper3, we focused on a single queue of jobs and discussed three scheduling algorithms in the framework of variable partitioning: Non-FCFS, Aggressive Backfilling4, 5, and Conservative Backfilling5, 6, 7.
In this paper we focus on the comparison of backfilling scheduling algorithms using multiple- queue4, look-ahead8, 9, and basic aggressive strategy. Our cluster computing lab provides an excellent environment for student projects in several of our courses including Operating
Proceedings of the 2006 American Society for Engineering Education Annual Conference & Exposition Copyright 2006, American Society for Engineering Education
Rajaei, H., & Dadfar, M. (2006, June), Comparison Of Backfilling Algorithms For Job Scheduling In Distributed Memory Parallel System Paper presented at 2006 Annual Conference & Exposition, Chicago, Illinois. 10.18260/1-2--1000
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2006 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015