Asee peer logo

Comparison Of Backfilling Algorithms For Job Scheduling In Distributed Memory Parallel System

Download Paper |


2006 Annual Conference & Exposition


Chicago, Illinois

Publication Date

June 18, 2006

Start Date

June 18, 2006

End Date

June 21, 2006



Conference Session

Issues in Computer Education

Tagged Division

Computers in Education

Page Count


Page Numbers

11.339.1 - 11.339.12



Permanent URL

Download Count


Request a correction

Paper Authors


Hasasn Rajaei Bowling Green State University

visit author page

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.

visit author page

author page

Mohammad Dadfar Bowling Green State University

Download Paper |

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


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