软件流水领域二维数组的体差不等式测试算法  

Dependence Difference Inequality Test Algorithm for Two-dimensional Arrays in Software Pipelining Field

作　　者：乔林[1] 黄维通[1] 孟威[1] 汤志忠[2] 

机构地区：[1]清华大学计算中心,北京100084 [2]清华大学计算机科学与技术系高性能计算所,北京100084

出　　处：《计算机工程》2005年第21期1-3,24,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(69773028;60173010)

摘　　要：给出了二维数组的体差不等式测试算法,并证明二维数组的体差不等式测试算法具有多项式时间复杂度。相对于直接求解,体差不等式测试算法的时间复杂度要小得多。实验表明,对于科学计算循环中出现的大多数数据相关性判定问题,使用体差不等式测试算法可以获得很好的效果。This paper presents a new dependence difference inequality test algorithm for two-dimensional arrays, and proves that the time complexity of the algorithm is polynomial. Compared with directly solving algorithms, the time complexity of the dependence difference inequality test algorithm is much better than those of other algorithms. Experimental results also show that the dependence difference inequality test algorithm works well for most of data dependencies appeared in scientific computation programs.

关 键 词：数据相关性 二维数组 迭代向量 体差不等式测试 可行解域 

分 类 号：TP33[自动化与计算机技术—计算机系统结构]