摘要
对程序进行并行变换是提高程序并行性的有效手段。许多并行变换都要寻找一种最优的循环置换。在寻找过程中,如果对每一个被考察的置换都重新进行相关性测试,那么整个寻找过程将极费时间。本文给出了一个测试嵌套循环任一置换的阻碍矩阵测试算法。它将测试任一循环置换的合法性转化为测试一组向前置换的合法性,并且仅需对嵌套循环做一遍相关性测试。利用该算法可以简便迅速地检查任一循环置换的合法性。从而使许多并行变换变得实际可行。
To perform parallel transformation for programs is an effective means to increase program parallelism.Many transformations need to find an optimal loop per- mutation.During the process,if every permutation is tested for dependency,it will be a waste of time.In the paper we present an impedimental matrix algorithm for testing any nested DO-LOOP permutation.The algorithm tests the legitimacy of a group of backward interchanges instead of testing that of any loop permutation,and needs only one dependency test for nested loops.With the algorithm we can quickly and easily check the legitimacy of any loop permutation.Therefore,it allows many parallel transforma- tions to be realistic and feasible.
出处
《计算机工程与科学》
CSCD
1996年第4期1-6,共6页
Computer Engineering & Science
基金
国家自然科学基金
关键词
程序并行性
循环置换
阻碍矩阵算法
parallel transformation
loop permutation
loop interchange
backward interchange
direction vector
