Run-Time Parallelization and Scheduling of Loops

In this paper, we study run-time methods to automatically parallelize and schedule iterations of a do loop in certain cases, where compile-time information is inadequate. The methods we present in this paper involve execution time preprocessing of the loop. At compile-time, these methods set up the framework for performing a loop dependency analysis. At run-time, wavefronts of concurrently executable loop iterations are identified. Using this wavefront information, loop iterations are reordered for increased parallelism. We utilize symbolic transformation rules to produce: 1) inspector procedures that perform execution time preprocessing and 2) executors or transformed versions of source code loop structures. These transformed loop structures carry out the calculations planned in the inspector procedures. We present performance results from experiments conducted on the Encore Multimax. These results illustrate that run-time reordering of loop indexes can have a significant impact on performance. Furthermore, the overheads associated with this type of reordering are amortized when the loop is executed several times with the same dependency structure.