Schedule-driven loop unrolling for parallel processors

A discussion is given on the problem of scheduling parallel program tasks that are enclosed in a set of nested loops on parallel computers. The authors introduce a representation of the tasks and their relations in a loop. The representation allows them to express loop-carried data dependences among tasks as well as loop information that cannot be represented using ordinary task graphs. They also introduce a new technique for scheduling unrolled loops onto arbitrary target machines. The technique allows several iterations of a set of loops as well as tasks within the same iteration to overlap in execution in a way that minimizes the loop completion time. They use local neighborhood search and simulated annealing optimization methods to find the best way to unroll a set of nested loops. The goal is to find which loops to unroll and for how many times and the schedule of the tasks in the post-unrolling loop on the available processors.>