部分三维算法的最优线性阵列设计

SYNTHESIZING COMPUTATION TIME OPTIMAL LINEAR PROCESSOR ARRAYS FOR SOME THREE DIMENSIONAL ALGORITHMS

自８０年代末，处理器阵列研究的一个新方向是设计线性阵列．在这方面，Ｌｅｅ和Ｋｅｄｅｍ作出了开创性的工作，他们提出了一个线性阵列设计框架．但是，目前还没有一个有效的设计方法．在文中，提出了一个线性阵列的设计方法，基于它，线性阵列的设计者通过分析算法对应的数据依赖图（ＤＧ）的最长路径，就可以获得可行的设计．该法适用于所有三维算法，对于满足特定条件的算法，能设计出运算时间最优的阵列．最后，以矩阵乘和传递闭包为例，文中演示了该法的应用．

Since the late 1980s, one trend of research on processor arrays is to design linear processor arrays. Lee and Kedem did the pioneer's work in this field as they proposed a framework for designing linear arrays. Their framework consists of three parts: the first part is a linear array model; the second part uses pairs ( H, S ), where H and S are vectors, to denote designs; and the third part is a group of necessary and sufficient conditions for pairs ( H, S ). Thus far, there are no practical design methodologies proposed in the literature. In the paper here, a design methodology is presented for three dimensional algorithms. This methodology is based on two observations: first, given a three dimensional algorithm, designers can directly determine several feasible pairs ( H, S ) by analyzing the longest path of the dependence graph (DG) of the algorithms; second, if the longest path satisfies a certain condition, one of these pairs ( H, S ) is computation time optimal. In summary, this methodology can produce computation time optimal design for some three dimensional algorithms. Finally, the matrix multiplication and the transitive closure problem are taken as examples to illustrate the application of the methodology.