Publication:
Static scheduling of conditional branches in parallel programs

Loading...
Thumbnail Image
Authors
George, Robert Tyler
Subjects
Parallel processing
Scheduling
Advisors
Lewis, Theodore
Date of Issue
1996-12
Date
December 1996
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
The problem of scheduling parallel program tasks on multiprocessor systems is known to be NP-complete in its general form. When non-determinism is added to the scheduling problem through loops and conditional branching, an optimal solution is even harder to obtain. The intractability of obtaining an optimal solution for the general scheduling problem has led to the introduction of a large number of scheduling heuristics, These heuristics consider many real world factors, such as communication overhead, target machine topology, and the tradeoff between exploiting the parallelism in a parallel program and the resulting scheduling overhead. We present the probabilistic merge heuristic--in which a unified schedule of all possible execution instances is generated by successively scheduling tasks in order of their execution probabilities. When a conditional task is scheduled, we first attempt to merge the task with the time slot of a previously scheduled task which is a member of a different execution instance. We have found that the merge scheduler produces schedules which are 10% faster than previous techniques. More importantly, however, we show that the probabilistic merge heuristic is significantly more scalable -- being able to schedule branch and precedence graphs which exceed 50 modes.
Type
Thesis
Description
Series/Report No
Department
Department of Computer Science
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
viii, 55 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections