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

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 1992-10, Vol.11 (10), p.1317-1322
• Main Authors: Hinsberger, U., Kolla, R.
• Format: Article
• Language: English
• Subjects: Applied sciences; Combinational circuits; Delay; Design. Technologies. Operation analysis. Testing; Dynamic programming; Electronics; Exact sciences and technology; Heuristic algorithms; Impedance; Integrated circuits; Libraries; Logic; Optimization; Semiconductor electronics. Microelectronics. Optoelectronics. Solid state devices; Timing; Variable structure systems
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/43.170993

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.< >