INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

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

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF Ren_Huan.pdf (1MB) (no description provided) PDF
Title: Novel Discrete Optimization Techniques with Applications to Complex Physical Synthesis Problems in EDA
Author(s): Ren, Huan
Advisor(s): Dutt, Shantanu
Contributor(s): Rao, Wenjing; Wu, Kaijie; Lillis, John; Banerjee, Prashant
Department / Program: Electrical and Computer Engineering
Graduate Major: Electrical and Computer Engineering
Degree Granting Institution: University of Illinois at Chicago
Degree: PhD, Doctor of Philosophy
Genre: Doctoral
Subject(s): 0/1 integer programming buffer insertion cell replication cell sizing discretized network flow physical synthesis placement supply voltage and threshold voltage assignment area, timing and voltage-island constraints dynamic programming with weak domination power, timing and yield optimization
Abstract: 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.
Issue Date: 2012-12-11
Genre: thesis
Rights Information: Copyright 2012 Huan Ren
Date Available in INDIGO: 2012-12-12
Date Deposited: 2012-05

This item appears in the following Collection(s)

Show full item record


Country Code Views
United States of America 106
China 35
Netherlands 6
United Kingdom 3
India 2


My Account


Access Key