Static scheduling of conditional branches in parallel programs
By:  Robert Tyler George
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1996
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 55
Subjects: SCHEDULING; PARALLEL PROCESSING
Description: 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.
Notes: Thesis advisor(s): Ted Lewis.

"December 1996."

Thesis (M.S. in Computer Science) Naval Postgraduate School, December 1996.

Includes bibliographical references (p. 53).

Approved for public release; distribution unlimited.

Also available online.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.



dk/dk cc:9116 5/15/97