Layout driven decomposition with congestion consideration

Abstract

We present a novel algorithm that applies physical layout information during common subexpression extraction to improve wiring congestion and delay, resulting in improved design closure. As feature sizes decrease and chip sizes increase, the traditional separation of physical design and logic synthesis proves to be increasingly detrimental. Interconnect delay and wiring congestion, among the most critical objective functions to meet design closure, are not considered during logic synthesis. On the other hand, physical design is too deep in the design process to be able to significantly restructure the already technology mapped netlist. While this problem has been addressed previously, the existing solutions only apply simple synthesis transforms during physical design. Hence they are generally unable to reverse decisions made during logic restructuring which have a major negative impact on the circuit structure. In our novel approach, we propose a layout driven algorithm for the concurrent extraction of common subexpressions, one of the most important steps that affect the overall circuit structure, and consequently congestion and wire length during logic synthesis. In addition, we consider dependency relations between cube divisors to improve the extraction process. As a result, our layout driven decomposition algorithm combines logic synthesis and physical layout information to effectively decrease wire length and improve congestion for improved design closure. © 2002 IEEE.