Accession Number : ADA325621

Title :   Static Scheduling of Conditional Branches in Parallel Programs.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : George, Robert T.

PDF Url : ADA325621

Report Date : DEC 1996

Pagination or Media Count : 64

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.

Descriptors :   *PARALLEL PROCESSING, *SCHEDULING, TIME INTERVALS, OPTIMIZATION, GRAPHS, PROBABILITY, COMPUTER ARCHITECTURE, PARALLEL PROCESSORS, SOLUTIONS(GENERAL), HEURISTIC METHODS, MULTIPROCESSORS, TRADE OFF ANALYSIS, STATICS.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE