A COMPILER OPTIMIZATION ALGORITHM FOR SHARED-MEMORY MULTIPROCESSORS

This paper presents a new compiler optimization algorithm that paralle lizes applications for symmetric, shared-memory multiprocessors. The a lgorithm considers data locality, parallelism, and the granularity of parallelism. It uses dependence analysis and a simple cache model to d rive its optimizations. It also optimizes across procedures by using i nterprocedural analysis and transformations. We validate the algorithm by hand-applying it to sequential versions of parallel, Fortran progr ams operating over dense matrices. The programs initially were hand-co ded to target a variety of parallel machines using loop parallelism. W e ignore the user's parallel loop directives, and use known and implem ented dependence and interprocedural analysis to find parallelism. We then apply our new optimization algorithm to the resulting program. We compare the original parallel program to the hand-optimized program, and show that our algorithm improves three programs, matches four prog rams, and degrades one program in our test suite on a shared-memory, b us-based parallel machine with local caches. This experiment suggests existing dependence and interprocedural array analysis can automatical ly detect user parallelism, and demonstrates that user parallelized co des often benefit from our compiler optimizations, providing evidence that we need both parallel algorithms and compiler optimizations to ef fectively utilize parallel machines.