| 一种引入互斥关系的功能单元分配算法 |
| |
| 引用本文： | 程利新,石峰,Muhammad Kamran.一种引入互斥关系的功能单元分配算法[J].北京理工大学学报,2005,25(10):885-889. |
| |
| 作者姓名： | 程利新 石峰 Muhammad Kamran |
| |
| 作者单位： | 北京理工大学,信息科学技术学院计算机科学工程系,北京,100081;北京理工大学,信息科学技术学院计算机科学工程系,北京,100081;北京理工大学,信息科学技术学院计算机科学工程系,北京,100081 |
| |
| 摘 要： | 为使条件分支数据通道中功能单元的分配结果得到进一步优化,在数据流图操作相容性分析中引入操作间互斥关系,并构建基于图论的分配模型.使用团划分算法在该模型上进行功能单元分配,同时提出一种针对功能单元分配问题的团划分启发式方法.不仅提高了团划分算法求解功能单元分配问题的计算结果一致性,而且使算法的收敛速度得以提高.根据实验结果,该算法得到的数据通道中所需功能单元平均减少了41%,同时执行速度加快了50%.
|
| 关 键 词： | 互斥关系 功能单元分配 团划分 |
| 文章编号： | 1001-0645(2005)10-0885-05 |
| 收稿时间： | 11 5 2004 12:00AM |
| 修稿时间： | 2004年11月5日 |
A Functional Unit Allocation Algorithm by Importing Mutex Relationship |
| |
| CHENG Li-xin,SHI Feng and Muhammad Kamran.A Functional Unit Allocation Algorithm by Importing Mutex Relationship[J].Journal of Beijing Institute of Technology(Natural Science Edition),2005,25(10):885-889. |
| |
| Authors: | CHENG Li-xin SHI Feng and Muhammad Kamran |
| |
| Institution: | Department of Computer Science and Engineering, School of Information Science and Technology, Beijing Institute of Technology, Beijing 100081, China |
| |
| Abstract: | To make the result of functional unit allocation of data-path with conditional branch more optimized,the mutex relationship between operations is imported into the consistence analysis process of operations in DFG,and the allocation model based on graph theory is constructed.Clique partition algorithm is applied to perform the functional unit allocation based on the model.A heuristic method aimed at functional unit allocation is also presented to improve the clique partition algorithm.The consistency of the allocation result and the convergence speed of clique partition algorithm can be improved greatly by the heuristic method.Experimental results showed that the number of required functional unit in data-path obtained by this algorithm is decreased 41% in average and the running speed is improved 50% in average. |
| |
| Keywords: | mutex relationship functional unit allocation clique partition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《北京理工大学学报》浏览原始摘要信息 |
| 点击此处可从《北京理工大学学报》下载免费的PDF全文 |
|
