A Functional Unit Allocation Algorithm by Importing Mutex Relationship

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.