一种引入互斥关系的功能单元分配算法  

A Functional Unit Allocation Algorithm by Importing Mutex Relationship

作　　者：程利新[1] 石峰[1] Muhammad Kamran 

机构地区：[1]北京理工大学信息科学技术学院计算机科学工程系,北京100081

出　　处：《北京理工大学学报》2005年第10期885-889,共5页Transactions of Beijing Institute of Technology

基　　金：国家自然科学基金资助项目(69973007)

摘　　要：为使条件分支数据通道中功能单元的分配结果得到进一步优化,在数据流图操作相容性分析中引入操作间互斥关系,并构建基于图论的分配模型.使用团划分算法在该模型上进行功能单元分配,同时提出一种针对功能单元分配问题的团划分启发式方法.不仅提高了团划分算法求解功能单元分配问题的计算结果一致性,而且使算法的收敛速度得以提高.根据实验结果,该算法得到的数据通道中所需功能单元平均减少了41%,同时执行速度加快了50%.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.

关 键 词：互斥关系 功能单元分配 团划分 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]