| 摘 要： | 作者为电子计算机向量运算识别器研制了一种识别与构造算法,这种算法被命名为“下标追踪法”。跟目前通用的坐标方法相比较,下标追踪法取得下列进展: 1.除去线性下标表达式的系数编译时可计值的要求外,对于赋值语句循环几乎没有任何额外的限制; 2.在某种意义上,得到的是充分必要条件,从而最大限度地发掘出并行的潜力。特别是对于单层循环,或多重循环的内层循环,坐标方法能够识别的,下标追踪法都能够识别;大量坐标方法不能识别的,下标追踪法也能够识别; 3.识别与构造范围扩张到算术IF、逻辑IF和块IF语句,算法简便,从编译的角度观察,结果仍不失充分必要的性质。这样一来,结构程序设计语言的三种主要语句——赋值、循环和条件判别的向量化问题全部得到解决。而坐标方法、时性关系矩阵方法,以及CRAY-1向量FORTRAN编译系统迄今均把包含任何一种IF语句的循环排斥在外,认为这些循环“实际上大多难于向量化,即使有些可以向量化,算法上也特别复杂。”为了减少条件判别的出现,用户甚至在一定程度上不惜放弃“top-down”(自顶向下)的结构程序设计方法; 4.由于解决了赋值、循环和条件判别的向量化问题,其他能够经过程序变换(为了把纠集在一个双臂IF语句或多重嵌套IF语句里的语句分解开来交给多处理机并行操作,D.Kuck教授等人在文[8]中专门讨论过这种变换)用这三种基本成份表达的所有循环(例如由算术IF和无条件GOTO形成的三叉控制转移,以及由计算GOTO和无条件GOTO形成的多叉控制转移)的向量化问题也都迎刃而解; 5.考虑到机器实现中的工程问题,计算量与存储量不仅是可接受的,甚至是比较小的; 还有: 6.处理方法是新颖的; 7.通过一系列定义、公理和定理,建立起牢固的数学基础。下标追踪法正在诸如151—3/4大型序列机一类的系统上加以实施。在我从事串行运算向量化的研究过程中,得到慈云桂教授、陈火旺付教授的大力支持、鼓励与指导,吴健安、郭自华、丁亚希、娄彦军、李凌等同志仔细地阅读了全文,提出若干宝贵意见,并且在工程实现中给予诚挚的合作,作者谨向他们致以衷心的感谢。本文介绍下标追踪法的基本思想、基本理论和基本方法。主要提出构造时序层次的公理系统——繁衍规则,证明了年长顺序定理和判别准则。前者在串行的范畴内,把DO循环的语义顺序改造成为以数据依赖关系为主,以语义顺序为辅的年长顺序;后者在年长顺序的基础上,给出可并发执行的充要条件,对于赋值语句循环也就是可向量化的充要条件。
|
