Scheduling Conditional Branching using Representative Task Graphs

We study the problem of scheduling parallel programs with conditional branching on parallel processors. The major problem in having conditional branching is the non-determinism since the direction of a branch may be unknown until the program is midway in execution. In this paper, we overcome the problem of non-determinism by proposing a probabilistic model that distinguishes between branch and precedence relations in parallel programs. We approach the problem of scheduling task graphs that contain branches by representing all possible execution instances of the program by a single deterministic task graph, called the representative task graph. The representative task graph can be scheduled using one of the scheduling techniques used for deterministic cases. We also show that a schedule for the representative task graph can be used to obtain schedules for all execution instances of the program.