论文部分内容阅读
科学计算中的许多算法包含大量的重复计算，它们可以用n重循环算法表示，空时映射技术是指循环中迭代的调度和它们到脉动处理器阵列(其维数为p≤(n-1))的映射。其目标是在一定的约束条件下，针对某个优化目标，将某嵌套循环的每个迭代指定到VLSI阵列中的一个处理器和一个时间步上。
本文首先针对线性阵列和二维阵列的情况，对空时映射搜索算法进行了研究。对于线性阵列，得到的结果如下：(1)采用启发式搜索方法，降低了搜索空间映射S过程的计算复杂度。(2)结合实际硬件结构进行搜索，进一步降低了计算复杂性。不但提高了空时映射的搜索效率，也使得单个处理器中寄存器数目得到了优化。(3)通过合理安排空时映射的合法性验证顺序，并将基削减技术与分支定界相结合的方法[1][2]用于检验空时映射矩阵的合法性，与已有的线性阵列算法[3][4]相比，较大程度降低了整个算法的时间复杂度。
对于二维阵列，本文针对当内层迭代的上下界为外层迭代的仿射函数时的情况，给出了一种脉动变换搜索的优化策略和相应的自动化算法。
然后本文进一步将研究范围从线性和二维阵列推广到一般的给定规模p维阵列，并在已给定空间映射的情况下，对搜索时间调度的方法进行了研究。
基于(n-1)维紧调度公式[5][6]，本文提出了针对目标阵列为任意p≤(n-1)维的两步构造算法。该算法构造出的调度集合Ω是紧调度集合ψ[5]的一个子集。本研究证明了该子集Ω中的调度在循环执行时间上的最优性，同时由于Ω中元素个数为ψ的1/Cpn-1，因此减小了调度搜索时的枚举范围，从而使搜索算法本身的时间复杂度下降到原来的1/Cpn-1。进一步，由于该子集中的调度所对应的循环执行时间均具有最优的主项，寻找最优调度时无须枚举整个子集Ω，从而进一步降低了调度搜索算法的时间复杂度。最后，由于Ω中调度具有的规则性，使得生成处理器硬件描述代码和硬件接口时更简单高效。