Hybrid loop interchange: optimization for parallel programs

Parallel loops account for the greatest amount of parallelism in numerical programs. Executing nested loops in parallel with low run-time overhead is thus very important for achieving high performance in parallel processing systems. However, in parallel processing systems with caches or local memories in memory hierarchies, `thrashing problem´ may arise whenever data moves back and forth between the caches or local memories in different processors. Previous techniques can only deal with the rather simple cases with one linear function in the perfectly nested loop. The authors present a parallel program optimizing technique called hybrid loop interchange (HLI) for the cases with multiple linear functions and loop-carried data dependences in the nested loop. With HLI they can easily avoid the `thrashing problem´ without reducing the program parallelism