PATH-SENSITIZED COVERING GRAPH METHOD FOR TECHNOLOGY MAPPING OF COMPLEX GATES

Abstract

This paper 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 minimization. delay minimization considering the capacitive loading, and area minimization under timing constraint are formulated as a nonlinear 0-1 integer programming problem for which a recently developed MFA (Mean Field Annealing) algorithm was successfully applied. Results on the performance of this procedure using a set of MCNC Benchmark examples have shown a notable improvement compared to the earlier tree covering algorithm for the case of area minimization.