Boolean matching tackles the problem whether a subcircuit of a boolean network can be substituted by a cell from a cell library. In previous approaches [7, 10, 8] each pair of a subcircuit and a cell is tested for NPN equivalence. This becomes very expensive if the cell library is large. In our approach the time complexity for matching a subcircuit against a library L is almost independent of the size of L. CPU time also remains small for matching a subcircuit against the huge set of functions obtained by bridging and fixing cell inputs; but the use of these functions in technology mapping is very profitable. Our method is based on a canonical representative for each NPN equivalence class. We show how this representative can be computed efficiently and how it can be used for matching a boolcan function against a set of library functions.

In this paper we present a new approach to the synthesis of combinational circuits and the mapping of standard gates like NAND, NOR, AOI and OAI with arbitrary number of inputs. Our method is based on the provable optimal synthesis of the fan-out-free regions of a circuit, represented as normal AND-OR-trees. Normal AND-OR-trees enable TROY to rebalance the regions with respect to delay without loosing area and lead to a much larger search space than that used by tree matching. Fast heuristics derived from the optimal approach yield significantly faster results than SIS on many standard benchmark circuits.

This paper presents a new approach to technology mapping for arbitrary technologies with single output cells. It overcomes the restrictions of tree-mapping based methods. Optimal algorithms for special cases of DAG-mapping are presented: for minimum delay mapping and for duplication-free mapping under a class of simple cost functions (including area and delay). Heuristics for duplication of logic and for AT-tradeoffs are developed and applied to LUT-FPGAs.

The following optimization problem is considered. Assume that each gate of a given circuit can be realized by one of several implementations which have different physical properties. Given this assumption, realizations of the circuit with optimal area delay tradeoff are sought. The formal model used is a discrete version of the transistor sizing problem on one hand and a special case of the library mapping problem on the other hand. It is independent of technology and applicable to even very restrictive design styles, as, for example, gate arrays or sea of gates. Since sizing of general combinational circuits is NP-complete, it is proposed to use heuristics on the base of optimal solutions for subcircuits. With this in mind, an efficient dynamic programming algorithm for minimizing the delay of a fanout-free circuit (tree) under an area constraint is presented.>