Performance-oriented technology mapping
H.J. Touati, Cho W. Moon, Robert K. Brayton et al. · Conference on Advanced Research in VLSI · 1990
This thesis presents a variety of techniques to minimize circuit delay during the translation of a set of Boolean equations into a list of connected logic gates that can be used for the manufacturing of combinational digital circuits. This translation process is called technology mapping. The first contribution of this work is to present an optimal algorithm to implement a Boolean circuits that can be represented as trees using an extension of known tree covering algorithms. The second and more important contribution of this work is an in-depth analysis of fanout optimization. The fanout problem is the problem of distributing a signal to several destinations, where the signal may be required at different times, in order to minimize the overall delay. This work presents the most detailed theoretical study of the complexity of fanout optimization published so far, and a spectrum of heuristics to solve the fanout problem under realistic delay models. This thesis also introduces a simple algorithm that can be used to apply fanout optimization to an entire network. This algorithm yields an optimal application of fanout optimization in terms of delay, while keeping area increase of the circuit to a low value. To study the integration of tree covering and fanout optimization, this work introduces a technology independent delay model that characterizes precisely suboptimalities due to inbalances in a network. This is the first technology independent delay model that models the delay through a node as a function of the arrival time distribution at a node. This delay model can be used to derive analytically optimal solutions in simple cases, which can be used to measure the suboptimality of heuristics. An extension to tree covering is then suggested, and shown to provide significant delay reductions for a relatively heavy cost in area. Finally this work investigates technology independent delay optimization techniques based on partial or total collapsing of logic, and shows that further delay reductions can be achieved with these techniques possibly at a higher cost in area.
Cited by 172 works.