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

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

作　　者：俞一峻[1] 臧斌宇[1] 施武[1] 朱传琪[1] 

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

出　　处：《软件学报》1999年第4期366-371,共6页Journal of Software

基　　金：国家自然科学基金;国家863高科技项目基金;国家攀登计划基金;国家教委博士点基金

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

关 键 词：自动并行化变换 幺模变换 并行化编译 

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