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

ENHANCED AUTOMATIC MULTINESTED LOOP UNIMODULAR PARALLELIZATION WITH ARRAY REDUCTION TECHNIQUE

作　　者：俞一峻[1] 李剑慧[1] 黄波[1] 朱传琪[1] 

机构地区：[1]复旦大学并行处理研究所,上海200433

出　　处：《计算机学报》1999年第6期561-566,共6页Chinese Journal of Computers

基　　金：国家自然科学基金;国家八六三高技术研究发展计划;教育部科学技术项目基金;国防科技重点实验室基金

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

关 键 词：相关性分析 循环并行化 单模变换 并行化编译 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP314[自动化与计算机技术—计算机科学与技术]