Scheduling of parallel programs including dynamic loops

The classical static scheduling strategies do not consider the dynamic behavior of parallel programs. These strategies provide near-optimal solutions for the scheduling problem when the programs are well-known beforehand. However, the schedulings provided can be quite inefficient when the conditions of a real execution are not those assumed to obtain the scheduling. On the other hand, some of the structures with a dynamic behavior included in parallel programs include an intrinsic parallelism (e.g., Do-All loops), that cannot be exploited by the classical scheduling policies. To avoid these situations, the authors developed a methodology based on Task Replication that keeps the processors as busy as possible and takes advantage of the intrinsic parallelism of parallel programs. This methodology provides static schedulings, with some replicated tasks, that take into account the dynamic behavior of parallel programs including loops with a variable number of iterations and conditional structures. © 1994.