Logic decomposition during technology mapping

摘要

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.