用动态规划法求解延时/面积最小化工艺映射

本文提出了一个求解延时／面积最小化工艺映射动态规划法．它首先基干线性延时模型，给出了用动态规划法求解延时最小化工艺映射的步骤；然后从树型网络的面积计算公式入手，用动态规划法近似计算面积最小化工艺映射；最后用“线性加权和法”把延时／面积最小化工艺映射转变为单目标最优化问题求解．

THE TECHNOLOGY MAPPING DYNAMIC PROGRAMMING ALGORITHM FOR TIMING/AREA OPTIMIZATION

Minimizing delay and area of the designed FPGA circuit is the main tar-get of the technology mapping. Minimizing delay can be soled theoretically by thedynamic programming algorithm. Minimizing area can be solved theoretically bythe covering algorithm, but this is a NP-complete problem. This paper presents aperformance-driven technology mapping algorithm to reduce delay/area. Firstly, itgives a linear delay model of the LUT based FPGA and shows that the FPGA tech-nology mapping for delay optimization under the delay model can be solved in thedynamic programming algorithm. and then, it also shows that the FPGA technolo-gy mapping for area optimization for tree can be solved in the dynamic programmingalgorithm. Based on the tree calculating formula, it gives a near area optimizationtechnology mapping algorithm, which is a dynamic programming algorithm. Com-bining the two dynamic programming algorithms, it gives the technology mappingdynamic programming algorithm for timing/area optimization. The algorithm cannot only reduce the designed circuit delay, but also run fast.