|
Abstract : |
This paper presents a procedure which performs logic decomposition during technology mapping. A problem in technology mapping is that 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. Conventional techniques iteratively apply technology independent transformations and technology mapping, so that the implementation obtained by technology mapping is restructured and remapped. Although some progress can be made, the effectiveness of these techniques is limited, since when a circuit is restructured, it is not clear how it is implemented eventually. The central problem is that technology independent transformations and technology mapping are applied separately. In this paper, we propose a procedure which simultaneously applies technology mapping and algebraic logic decomposition, a key technology independent operation for changing circuit structures. A set of circuit structures is compactly encoded in a single graph, and the procedure dynamically modifies the set during technology mapping by introducing new structures while deleting others based on the actual cost function used in the mapping. State-of-the-art technology mapping algorithms are naturally extended, so that the procedure finds an optimal tree implementation over all the circuit structures examined. We show that the procedure effectively explores the same 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 decompositions. The procedure has been implemented and used for commercial design projects. We present experimental results on benchmark examples to demonstrate its effectiveness., |
