Research And Design On Reduction Recognition Methods Based On Array Privatization

The goal of serial program collateralization is to convert the serial program equivalently to program which can be executed in a parallel environment. The meaning of equivalence is that the results of the new program are exactly equivalent to the results of serial program. In the conversion process, the key to improve the efficiency when the new program is executed in parallel environment is to recognise more parts of original program which can be executed parallel,and it is particularly important to recognise the parallel loops. The way to convert non-parallel loops to parallel loops commonly known as loop parallelization techniques. Array privatization is one of the important loop parallelization techniques and it has been researched a lot. And another loop parallelization technique which called reduction recognition has not developed.Based on the research of array privatization and combining the characteristics of the process of the reduction operation, this thesis analyses the various elements of the reduction operation of the data processing and sum up the concept, nature of the operation that can be used in reduction and the parameter in reduction and proves criterion of them. Then, based on these findings, this thesis shows the design of the reduction recognition algorithms applied to different situations.The main work of this thesis is as follows:First, based on research and learning of array privatization and analysis of the amount of the process of reduction operations, this thesis describes the concept of the reduction operation and the reduction parameters and analyses their properties and proves the criterion determining the reduction operation and the reduction parameters.Secondly, based on the theory before and the immutable parameters and the related research of array privatization, this thesis designs a partial block reduction recognition algorithm. And based on the algorithm, this thesis designs cycle reduction recognition algorithm for the loops that every iteration of the loops has reduction parameter information. Next, based on the current reduction recognition strategy, this thesis designs static loop recognition algorithm. Next, based on the correlation-cover array privatization method, this thesis designs a unified reduction recognition algorithm.Finally, this thesis proves the correctness of the partial block reduction recognition algorithm, limited circulation reduction recognition algorithms, static recognition circulation algorithm and the unified reduction recognition algorithm and describes that these algorithms can identify more types of situation that reduction operation could be used in. And then this thesis proves that the algorithms are superior to existing algorithms.