A Fast And High-quality Technology Mapping Algorithm For FPGAs

The task of technology mapping is to convert a gate-level circuit into a LUT-level circuit where the LUTs are consistent with the LUTs in the FPGA chip. It consists of two parts: the logic optimization and the structural optimization. The main goal of the logic optimization is to decompose the circuit to satisfy the k-LUT requirement that the number of input nodes of every unit of a circuit is less than or equal to k. The main goal of structural optimization is to convert the circuit into a LUT network. At present, the operation efficiency of the existing logic optimization algorithms is not satisfactory, while the existing structural optimization algorithms still have the space to improve the circuits' delay and area and the operation efficiency of the algorithms.In this paper, an improved algorithm for the two parts of the technology mapping is presented. In the logic optimization, different ROBDD representation methods are used for circuits with different scale. The Local ROBDD is used to represent the large-scale circuits to reduce the memory consumption, while the Global ROBDD is used for small-scale circuits to improve the efficiency of logic optimization. After the representation of circuits, the domain nodes and their operations are used to decompose the ROBDDs. In the structural optimization, a new heuristic optimization algorithm based on the iteration is proposed, which takes delay, area and efficiency as the optimization objective. The technology mapping process includes cuts generation, cuts selection and LUT covering. The cuts generation part generates all k-feasible cuts for all nodes in a circuit using the dynamic programming algorithm. The cuts selection is an iterative process, which includes forward and backward traversal. The forward traversal selects the optimal cut for each node, and the backward traversal selects appropriate nodes as the roots of LUTs. The optimal cut-set is selected by the iteration of forward and backward traversal. The LUT covering part uses the result of cuts selection to form the LUT network finally. The experimental results show that the technology mapping algorithm proposed in this paper has achieved obviously improvement in the delay and area of the circuits and the operation efficiency of the algorithm.