Static scheduling of conditional branches in parallel programs
George, Robert Tyler
MetadataShow full item record
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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Caudill, Michael R. (Monterey, California. Naval Postgraduate School, 1995-06);This thesis investigates methods for constructing fielded jet engine performance goals using Non-Parametric and Parametric analysis methods. The procedures developed can be applied with any fielded jet engine. Emphasis is ...
Lee, Seungchan (Monterey, CA; Naval Postgraduate School, 2018-06);We propose an algorithm modifying a popular exact conditional test involving the goodness-of-fit of contingency tables. This study focuses on improving the efficiency of Markov chain Monte Carlo (MCMC) when sampling ...
Liu, J.; Saletore, V.A.; Lewis, T.G. (1994-12-01);In this paper we present Safe Self-Scheduling (SSS), a new scheduling scheme that schedules parallel loops with variable length iteration execution times not known at compile time. The scheme assumes a shared memory space. ...