Files in this item



application/pdf8721715.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Nonpreemptive Run-Time Scheduling Issues on a Multitasked, Multiprogrammed Multiprocessor With Dependencies, Bidimensional Tasks, Folding, and Dynamic Graphs
Author(s):Miller, Allan Ray
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:Increases in high speed hardware have mandated studies in software techniques to exploit the parallel capabilities. This thesis examines the effects a run-time scheduler has on a multiprocessor. The model consists of directed, acyclic graphs, generated from serial FORTRAN benchmark programs by the parallel compiler Parafrase. A multitasked, multiprogrammed environment is created. Dependencies are generated by the compiler. Tasks are bidimensional, i.e., they may specify both time and processor requests. Processor requests may be folded into execution time by the scheduler. The graphs may arrive at arbitrary time intervals. The general case is NP-hard, thus, a variety of heuristics are examined by a simulator. Multiprogramming demonstrates a greater need for a run-time scheduler than does monoprogramming for a variety of reasons, e.g., greater stress on the processors, a larger number of independent control paths, more variety in the task parameters, etc. The dynamic critical path series of algorithms perform well. Dynamic critical volume did not add much. Unfortunately, dynamic critical path maximizes turnaround time as well as throughput. Two schedulers are presented which balance throughput and turnaround time. The first requires classification of jobs by type; the second requires selection of a ratio value which is dependent upon system parameters.
Issue Date:1987
Description:114 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987.
Other Identifier(s):(UMI)AAI8721715
Date Available in IDEALS:2014-12-15
Date Deposited:1987

This item appears in the following Collection(s)

Item Statistics