同归约变换结合的自动单模变换技术

ENHANCED AUTOMATIC MULTINESTED LOOP UNIMODULAR PARALLELIZATION WITH ARRAY REDUCTION TECHNIQUE

针对应用自动单模变换的两大困难：如何自动找出使多重循环并行化的恰当的单模变换矩阵以及如何解决妨碍单模矩阵计算的非常数归约相关距离，提出了如何对给定常数距离矩阵，自动找出使循环并行化的恰当的单模变换矩阵的技术；然后提出将数组归约相关表示为最小常数距离向量，从而使存在归约相关的多重循环也能够应用自动单模变换技术，为自动单模变换技术走向实用化提供了理论依据．

Unimodular transformation is a kind of loop parallelizing transformations that keeps the normality of the transformed loop nest. However, there are two drawbacks that makes the UT method not practical. First, the dependence distance must be kept lexicographically positive after transformation, which makes the computation of unimodular matrix for multi fold loops difficult. Secondly, the array reduction dependence is not constant distance in its nature while most UT method deal with constant distance matrix. The paper aims at finding approaches to overcome these drawbacks. First, an automatic UT approach to multi fold loops with constant distance matrix is introduced to parallelize outer and inner multi nested loops, which reaches the first aim. Then, the paper defines a way to express array reduction dependence as mimimal constant distance vector such that the previous UT method can apply to the loops with array redution dependence, which fulfils the second aim. To illustrate the theory of enhancing UT method with array reduction technique, a complete example is given.