(A) study on performance enhancement of technology mapping algorithms

Abstract

The main object of this dissertation is to develop new technology mapping techniques to improve the performance. The methods are targeting the most favorated ASIC technology such as Field-Programmable Gate Arrays (FPGAs), standard cells and gate arrays. At first, this thesis proposes a simple model for estimating the delay of an FPGA-mapped circuits prior placement and routing, and presents a new technology mapping algorithm for minimizing the delays of lookup table-based field-programmable gate arrays using the proposed delay model as a cost function to be minimized. The model proposes that delay through a node varies as a function of both the number of logic blocks and the number of logic levels along the critical path of a mapped circuit. The model parameters are derived using the statistics on MCNC benchmark circuits and Xilinx automatic design tool, and show how the predicted delays compare with the actual delays. Results on the performance of this algorithm using a set of MCNC benchmark examples have shown a notable improvement compared to the earlier delay minimized FPGA technology mapping algorithm. Secondly, this thesis proposes a new technology mapping procedure for minimizing the area and/or delay of complex logic gates using the so-called Path-Sensitized Covering Graph (PSCG) constructed from the given Boolean network and library cells. In the earlier tree covering algorithms, the original DAG (Directed Acyclic Graph) covering problem is only approximately solved by reducing the problem size and the search space based on the partitioning of the whole circuit at the multiple fan-out node, which makes the resultant solution locally optimal. Compared to this, our algorithm is more general in that it does not arbitrarily partition the DAG into a set of trees. This is necessary not to exclude the possibility of mapping into some library cell a portion of a given circuit across branching points (fan-out nodes). Three different problems, i.e., area minimiz...