A cell-based approach to performance optimization of fanout-free circuits

The following optimization problem is considered. Assume that each gate of a given circuit can be realized by one of several implementations which have different physical properties. Given this assumption, realizations of the circuit with optimal area delay tradeoff are sought. The formal model used is a discrete version of the transistor sizing problem on one hand and a special case of the library mapping problem on the other hand. It is independent of technology and applicable to even very restrictive design styles, as, for example, gate arrays or sea of gates. Since sizing of general combinational circuits is NP-complete, it is proposed to use heuristics on the base of optimal solutions for subcircuits. With this in mind, an efficient dynamic programming algorithm for minimizing the delay of a fanout-free circuit (tree) under an area constraint is presented