| 摘要: |
| 对于已知n维距离向量矩阵的多重串行循环,过去的并行化编译研究还缺乏寻找使循环外层并行化的幺模矩阵的可行算法.文章介绍了多重串行循环并行化的幺模变换方法,不仅从理论上证明满足外层并行化要求的合法幺模矩阵是存在的,而且通过构造性证明给出一个计算外层并行化幺模变换矩阵的可行算法,并探讨了扩大其适用范围于非完全嵌套和非常数相关距离循环的有效途径. |
| 关键词: 相关性分析,自动并行化变换,循环幺模变换. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金、国家863高科技项目基金、国家攀登计划基金和国家教委博士点基金资助. |
|
| Automatically Computing Unimodular Transforming Matrix to Parallelize Nested Sequential Loops |
|
YU Yi-jun,ZANG Bin-yu,SHI Wu,ZHU Chuan-qi
|
| Abstract: |
| 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 nested-loops as have n-dimension distance matrix. In this paper, the authors discuss a general outer-loop 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 outer-loops transformed. Thus, the application scope of the algorithms can be enlarged to non-perfect or non-constant dependence distance loops. |
| Key words: Dependence test, automatic parallelizing transformation, unimodular transformation. |
