Program analysis techniques for transforming programs for parallel execution

In a multiple processor system, computer programs have to be redesigned to efficiently use the parallel processors and deliver higher performance. One major approach is automatic detection of parallelism, in which existing conventional sequential programs are translated into parallel programs, in order to benefit from the presence of multiple processors. Optimizing compilers rely upon pro-ram analysis techniques to detect data dependences between program statements, The results of the analysis enable the compiler to identify code fragments that can be executed in parallel. The proposed dependence analysis techniques fall into two different categories: either efficient and approximate tests or exact but exponential. In this paper, we show that exact data dependence information can be computed efficiently in practice. The Banerjee inequality and the GCD test are the two tests traditionally used to determine statement data dependence in automatic parallelization of loops, These tests are approximate in the sense that they are necessary but not sufficient conditions for data dependence. In an earlier work we formally studied the accuracy of the Banerjee and GCD tests and derived a set of conditions that can be tested along with the Banerjee inequality and the GCD test to obtain exact data dependence information. In this work, we perform an empirical study to explain and demonstrate the accuracy of the Banerjee and GCD tests in actual practice. Our experiments indicate that exact data dependence information can be computed in linear time in practice. (C) 2002 Elsevier Science B.V. All rights reserved.