Loop-synthesizing transformation for maintaining parallelism and enhancing locality

On parallel computers, parallelism and locality are critical points for the performance of programs. It is known that locality and parallelism of loop nests can be improved by loop transformations. However, many useful loop transformations are restricted to perfectly nested loop nests. We present a loop-synthesizing transformation for maintaining parallelism and improving locality, with respect to a sequence of parallel loop nests. Since the result of our synthesizing transformation is a perfectly nested loop nest, we can directly perform the loop transformations which are restricted to perfectly nested loop nests, to further parallelize and to further enhance locality after the transformation.