Mapping algorithms onto parallel architectures: time schedules

Time scheduling is one of the important problems faced in mapping algorithms onto parallel architectures, particularly in real-time fault-tolerant computing. The paper shows how linear schedules can be used to exploit parallelism available in nested-loop programs. It relates linear schedules to known loop transformation techniques for modeling the parallel execution and extracting parallelism of nested loop structures. These techniques are the Doaccross technique used to model the simultaneous execution of loop computations that belong to different iterations and a technique for parallelism exploitation called selective cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how to find the selective shrinking with minimum total execution time by applying techniques of finding optimal linear schedules. The execution of these schedules can be modeled using the Doaccross technique