A problem in technology mapping is that the quality of the final implementation depends significantly on the initially provided circuit structure. This problem is critical, especially for mapping with tight and complicated constraints. In this paper, we propose a procedure which takes into account a large number of circuit structures during technology mapping. A set of circuit structures is compactly encoded in a single graph, and the procedure dynamically modifies the set during technology mapping by applying simple local transformations to the graph. State-of-the-art technology mapping algorithms are naturally extended, so that the procedure finds an optimal tree implementation over all of the circuit structures examined. We show that the procedure effectively explores the entire solution space obtained by applying algebraic decomposition exhaustively. However, the run time is proportional to the size of the graph, which is typically logarithmic in the number of circuit structures encoded. The procedure has been implemented and used for commercial design projects, We present experimental results on benchmark examples to demonstrate its effectiveness.

We present a new delay model for use in logic synthesis. A traditional model treats the area of a library cell as constant and makes the cell's delay a linear function of load. Out model is based on a different, but equally fundamental linearity in the equation relating area, delay, and load: namely, we may keep a cell's delay constantly making its area a linear function of load. This allows us to technology map using a library with continuous device sizing, satisfies certain electrical noise and power constraints, and in certain cases is computationally simpler than a traditional model. We give results to support these claims. A companion paper uses the computational simplicity to explore a wide search space of algebraic factorings in a mapped network.

A problem in technology mapping is that quality of the final implementation depends significantly on the initially provided circuit structure. To resolve this problem, conventional techniques iteratively but separately apply technology independent transformations and technology mapping. In this paper, we propose a procedure which performs logic decomposition and technology mapping simultaneously. We show that the procedure effectively explores all possible algebraic decompositions. It finds an optimal tree implementation over all the circuit structures examined, while the run time is typically logarithmic in the number of decompositions.