Novel Discrete Optimization Techniques with Applications to Complex Physical Synthesis Problems in EDA

VLSI circuit designs are very challenging optimization problems in the electronic design automation (EDA) domain. There are usually 100K's to tens of millions of components in such circuits, and a wide range of metrics that need to be considered. A post place-and-route (P&R) phase called "physical synthesis" (PS) is a crucial stage where effective optimization of VLSI circuits can be performed using accurate interconnect metrics. Many design transforms have been developed to perform different types of optimizations in PS. These include cell re-placement, cell sizing, cell replication, buffer insertion, supply voltage assignment and threshold voltage assignment. We have developed a novel and efficient method called "discretized network flow (DNF)" for the simultaneous application of multiple transforms on the entire circuit with tractable runtimes. This enables us to achieve an average of 10% and 16% improvement for delay and power, respectively, compared to the state-of-the-art academic or industry tools that apply the transforms sequentially. Application of DNF to the timing yield PS problem resulted in a relative yield improvement of about 16% over a state-of-the-art academic method. DNF was also applied successfully to solve 0/1 integer linear programming problems, achieving an average speedup of 19X over the state-of-the-art academic tool SCIP with a similar optimality gap. Besides DNF, we also developed a dynamic programming method using the novel concept of weak domination for solving 0/1 integer non-linear programming problems with a guaranteed optimality gap. Compared to a state-of-the-art academic tool Bonmin with the same optimality gap, our method achieves a speedup of about 2X.