A linear time algorithm for timing directed circuit optimizations

This paper describes an algorithm for doing timing directed circuit optimizations in linear time. An optimal gate input reordering scheme for performance improvement, and a gate sizing scheme for both performance improvement and area reduction is presented. The algorithm uses a combination and extent of partial validity of timing delays in obtaining linear runtime performance. The algorithm has been applied for gate input reordering and BiCMOS deselection in designs targeted for a BiCMOS gate array. At an average in linear time, a 50% reduction in BiCMOS site utilization, and a 5% gain in design performance through reordering has been achieved