Research And Implementation Of Global Array Data-flow Analysis Technology

In distributed memory computer system, it must be taken into account that how to reduce communication overhead between processors to improve the performance of programs when parallelizing. The technologies of automatic parallelizing currently focus on the loop nest, and the array in the loop is the object when optimizing communication. Traditional dependence analysis can only determine the location of communication, but can not determine the array regions to be communicated, so the code generated contains a large amount of redundant communication. The information obtained from accurate array data-flow analysis can be used for backend to generate accurate communication code, but its scope is limited within a single loop and can not eliminate the redundant communication caused by data dependence across loop nests. Further data-flow information can be obtained based on the traditional data-flow analysis, but it can not give the access information of array by element.This thesis designs and implements the algorithm of global array data-flow analysis for communication optimization in automatic parallelizing for distributed memory system. Firstly, it compares two mainly methods of data-flow analysis:grammer-guided and iterative solution; it extends the concept of the basic block to construct an extended control flow graph based on the intermediate code of SW-KAP, and builds the framework for global data-flow analysis. Secondly, the thesis makes a thoroughly study on the linear inequality expression of array regions and last-write analysis for arrays in loop nest, and proposes an exposed-set calculating algorithm which eliminates redundant communication; the algorithm inserted into SW-KAP can precisely process the input and flow dependence of array references in loop nest, and automatically calculate the exposed-set. Thirdly, the thesis combines the global data-flow analysis and accurate array data-flow analysis within a loop, and designs and implements the algorithm of global array data-flow analysis to obtain accurate array data-flow information across loop nests within a procedure.The algorithm in this thesis has been implemented in SW-KAP, and provides the information for the backend of the compiler to generate accurate communication code. The results of the tests show that the algorithm proposed in this thesis is correct and can optimize array communication in parallelizing compilation by accurate array communication information.