| 线性脉动阵列变换的空时映射搜索算法 |
| |
| 引用本文： | 陈慕羿,李挥.线性脉动阵列变换的空时映射搜索算法[J].小型微型计算机系统,2007,28(2):297-301. |
| |
| 作者姓名： | 陈慕羿 李挥 |
| |
| 作者单位： | 1. 北京大学,信息科学与技术学院,北京,100871
2. 北京大学,深圳研究生院,信息学院,广东,深圳,518055 |
| |
| 摘 要： | 研究了一类多重循环算法的线性脉动阵列实现.为了提高线性脉动阵列变换中空时映射的搜索效率,在Moldovan空时映射的基础上,采用启发式搜索方法,并引入基削减与分支定界相结合的算法,大大降低了算法复杂度,提高了效率.通过合理安排验证顺序,结合实际硬件结构进行搜索,进一步降低了计算复杂性,并使得到的线性阵列更加易于实际实现,硬件功能及结构之间达到了最大程度的均衡性.
|
| 关 键 词： | 空时映射 线性脉动阵列 并行计算 算法变换 数据依赖 |
| 文章编号： | 1000-1220（2007）02-0297-05 |
| 修稿时间： | 2005-12-13 |
Searching Algorithm for Space and Time Mapping in Linear Systolic Array Transformation |
| |
| CHEN Mu-yi,LI Hui.Searching Algorithm for Space and Time Mapping in Linear Systolic Array Transformation[J].Mini-micro Systems,2007,28(2):297-301. |
| |
| Authors: | CHEN Mu-yi LI Hui |
| |
| Affiliation: | 1 Department of Information Science and Technology, Peking University, Beijing 100871, China; 2 School of Information and Computer Eng. Shenzhen Graduate Schoolt, Peking University, Shenzhen 518055, China |
| |
| Abstract: | 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. |
| |
| Keywords: | space and time mapping linear systolic array parallel computation algorithm transformation data dependence |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
