Limits of Static Dependence Analysis for Automatic Parallelization
Niall Murphy, Timothy Jones, Simone Campanoni, Robert Mullins
International Workshop on Compilers for Parallel Computing (CPC), January, 2015
Automatic parallelization is an increasingly important technique for accelerating sequential applications on multicore processors. This approach relies on having a very accurate static dependence analysis to identify independent sections of code. Previously it has been assumed that improving this analysis would also improve the performance of parallelized code. In this paper we use novel profiling techniques to see how much room there is for improvement of the static analysis. By feeding this knowledge back into the compiler we simulate a perfectly accurate dependence analysis. Although we find that the compiler does indeed overestimate the number of data dependences, this extra knowledge does not help the compiler to achieve better performance. We conclude that other avenues, such as speculation, must be explored to surpass current automatic parallelization efforts.