Computer Science Seminar Series
Scheduling Jobs on Parallel Systems Using a Relaxed Backfill Strategy
April 11, 3:00pm
Weir Hall, Room 235
Presenter: William A. Ward
U.S. Army Engineer Research and Development Center Major Shared Resource Center, 3909 Halls Ferry Road Vicksburg, Mississippi 39180, USA
Abstract:
Backfill is a technique in which lower priority jobs requiring fewer resources are initiated before one or more currently waiting higher priority jobs requiring as yet unavailable resources. Processors are frequently the resource involved and the purpose of backfilling is to increase system utilization and reduce average wait time. Generally, a scheduler backfills when the user-specified run times indicate that executing the lower priority jobs will not delay the anticipated initiation of the higher priority jobs. This paper explores the possibility of using a relaxed backfill strategy in which the lower priority jobs are initiated as long as they do not delay the highest priority job too much. A simulator was developed to model this approach; it uses a parameter w to control the length of the acceptable delay as a factor times the wait time of the highest priority job. Experiments were performed for a range of w values with both user-estimated run times and actual run times using workload data from two parallel systems, a Cray T3E and an SGI Origin 3800. For these workloads, overall average job wait time typically decreases as w increases and use of user-estimated run times is superior to use of actual run times. More experiments must be performed to determine the generality of these results.
Biography of the Speaker:
William A. (Bill) Ward, Jr. was raised in Mobile, Alabama and graduated summa cum laude from the University of South Alabama (USA) in 1976 with a B.A. in mathematics. Purdue University awarded him an M.S. in computer sciences in 1978 and a Ph.D. in 1982. He worked for two years as a research mathematician at Exxon Production Research Company in Houston, Texas, as part of the development team for Exxon's multiple application reservoir simulator, and then served on the computer science faculty at USA for 15 years, teaching graduate courses on algorithms, computer architecture, programming languages, and theory of computing. For the past seven years he has been a member of the contractor staff at the U.S. Army Engineer Research and Development Center Major Shared Research Center with responsibility for leading a team of computational scientists in the yearly preparation of acquisition benchmarks for high-performance computers for the Department of Defense.