STATIC SCHEDULING OF CONDITIONAL BRANCHES IN PARALLEL PROGRAMS

The problem of scheduling non-deterministic graphs arises in several s ituations in scheduling parallel programs, particularly in the cases o f loops and conditional branching. When scheduling loops in a parallel program, non-determinism arises because the number of loop iterations may not be known before the execution of the program. However, since loops from a restricted class of conditional branching, there is a hig her degree of non-determinism associated with scheduling conditional b ranching. In this case, the direction of every branch remains unknown before run time. It follows that entire subprograms of the parallel pr ogram may or may not get executed, which in turn increases the amount of non-determinism and complicates the scheduling process. Thus, the t erm non-determinism is frequently associated with conditional branchin g in the literature. In this paper, we study the problem of constructi ng a static schedule for task graphs that contain conditional branchin g on parallel computers. Generally, it is difficult to obtain optimal solutions for solving various scheduling problems, even in the determi nistic case. When non-determinism is added to the scheduling problem t hrough conditional branching, an optimal solution will be even harder to obtain. We start the paper with a brief discussion of the schedulin g problem, then we introduce a model for representing parallel program s that contain branches. We present a two-step scheduling technique wh ich employs two different approaches: a graph theoretic appraoch and a multi-phase approach. The first approach is based on exploring severa l graph theoretic properties of the model. This approach is used as a preprocessing step to decrease the amount of non-determinism before ap plying the multi-phase approach. In the second step, several execution instances of the program are generated, a schedule for every instance is obtained, and a unified schedule is constructed by merging the obt ained schedules. Finally, we report the results of the experiments tha t we conducted to measure the performance of the techniques introduced in this paper. (C) 1995 Academic Press, Inc.