Technology mapping using logical effort for solving the load-distribution problem

Technology mapping is a crucial step in the synthesis of digital designs and can be used to obtain mapped circuits that are optimized for delay or area. Current tree-based mapping algorithms break the circuit into individual trees and map these optimally. However, these solutions are not globally optimal. This paper presents a new approach to delay-optimal mapping based on the principle of logical effort. This algorithm maps individual trees such that the solution of the entire circuit is optimal. In traditional technology mapping, the best match for a gate depends on the load being driven, which is not known at the matching stage. Current algorithms handle this situation by generating matches for all loads and selecting the best match at a later stage. This strategy works for fan-out-free circuits but breaks down at multiple fan-out points where each fan-out has to be sized correctly, depending on its criticality. This can have a significant impact on the selection of matches as well but has not been adequately addressed in the published literature. We refer to the correct sizing of branches of multiple fan-out points as the load-distribution problem, which is formally defined and solved in the context of technology mapping in this paper. The effect of the new logical effort-based mapping algorithm, combined with correct sizing of individual branches of a multiple fan-out point, leads to implementations that are closer to the global optimum. On the average, benchmark circuits mapped using our approach are 39.45 % faster and 32.77 % smaller than those obtained using SIS.