自动寻找使多重串行循环并行化的幺模变换

Automatically Computing Unimodular Transforming Matrix to\=Parallelize Nested Sequential Loops

对于已知ｎ维距离向量矩阵的多重串行循环，过去的并行化编译研究还缺乏寻找使循环外层并行化的幺模矩阵的可行算法．文章介绍了多重串行循环并行化的幺模变换方法，不仅从理论上证明满足外层并行化要求的合法幺模矩阵是存在的，而且通过构造性证明给出一个计算外层并行化幺模变换矩阵的可行算法，并探讨了扩大其适用范围于非完全嵌套和非常数相关距离循环的有效途径．

Lacking an effective and feasible algorithm to compute the valid unimodular matrix for parallelizing of the outer loops, previous parallelizing researches can not automatically reveal the parallelism in such sequential nestedloops as have ndimension distance matrix. In this paper, the authors discuss a general outerloop parallelizing method by valid unimodular transformations, prove the existence of such a valid unimodular transformation, and suggest several practical computing algorithms through the constructive proofs. This discovered unimodular transformation can have the maximal number of parallelizable outerloops transformed. Thus, the application scope of the algorithms can be enlarged to nonperfect or nonconstant dependence distance loops.