Optimization Of Array Data-Flow Analysis And Research And Implementation Of Array Privatization Technology

Program parallelism analysis and program optimization are two important contents for a parallelizing compiler. Program optimization techniques are various equivalent program transformations in order to take full advantage of the parallel hardware. The precondition of the equivalent program transformations is that the data dependence in the program keeps unchangeable. This thesis researches the optimization of the array data-flow analysis and the array privatization technique on program optimization.Data dependence analysis is the basic step in detecting loop level parallelism. It must include sufficient information to support the code optimizations and transformations. But most of the testing algorithms of traditional data dependence analysis are conservative and the results are not accurate. To determine if a loop can be parallelized by privatizing the work arrays and to maintain the exactness of data communications among the computing nodes for distributed memory machines, we need the more accurate dependence analysis. This thesis introduces the algorithm of the array data-flow analysis proposed by Stanford University. By analyzing the loop structure, the thesis points out the deficiencies of the original algorithm of the array data-flow analysis and gives corresponding solutions. Then, the thesis presents the designing and the implementation of the optimized array data-flow analysis. The optimized array data-flow analysis aims at a couple of read and write array references of the same array when they appear in a given model of the imperfect loop. Finally, the performance is detected by testing some instances. The experiment result indicates that the optimized techniques of the array data-flow analysis can ensure correctness and enhance the analysis capability and extend the range of the problem to be solved effectively.Array privatization is one of the most effective loop transformations for the exploitation of parallelism. This transformation technique privatizes arrays according to the information of the data dependence analysis, which eliminates the memory-related dependences, i.e. anti and output dependences, to make the loop execute parallel. By analyzing the basic rules of array privatization and the determinant conditions of the parallelizable loop, this thesis proposes an array privatization technique that is significant for the exploitation of loop parallelism. Then, the thesis presents the designing and the implementation of the effective array privatization technique based on the accurate array data-flow analysis. Finally, the performance is detected by testing some instances. The experiment result indicates that the array privatization method introduced in the thesis is effective for the exploitation of loop parallelism.