中文摘要：

研究了一类多重循环算法的线性脉动阵列实现．为了提高线性脉动阵列变换中空时映射的搜索效率，在Moldovan空时映射的基础上，采用启发式搜索方法，并引入基削减与分支定界相结合的算法，大大降低了算法复杂度，提高了效率．通过合理安排验证顺序，结合实际硬件结构进行搜索，进一步降低了计算复杂性，并使得到的线性阵列更加易于实际实现，硬件功能及结构之间达到了最大程度的均衡性．

英文摘要：

The realization of mapping a class of nested loop algorithms to linear systolic array is studied. A heuristic algorithm that decreases the computation complexity for the searching of space transformation S is introduced. Moreover, the basis reduction and a branch-and-bound algorithm are adopted in order to reduce the time complexity from exponential to polynomial. Finally, by rearranging the verification order and combining the verification with the structure of an actual processing element, the time complexity is further reduced and a better PE structure has been achieved. The experiments show that this method can lead to better results in relatively shorter time compared to previous algorithms.