Grant: Discovery Grants Program - Individual
University of Guelph
$27,000.00
Advanced interior point techniques for placement, routing and floorplanning problems arising in integrated circuit design
FY 2014-15
Summary
The design of many fundamental manufacturing and circuit layout problems can be modeled as linear or nonlinear combinatorial optimization problems. All of these problems are NP hard. Very tight performance specifications for these problems (minimum area, minimum power and congestion) demand near optimal designs subject to many millions to billions of constraints and variables. Over the last six years, we have developed efficient optimization techniques that can be used to solve these problems using interior point and semidefinite programming approaches that can be solved in polynomial time. We have also developed efficient interior point solvers including warmstarting that accelerate solution times for combinatorial problems. A primary ""objective'' of the proposed research is aimed at ""integration"" of large-scale interior pointmethodology used in linear, quadratic, convex, second-order cone programming and semidefinite programming to form the basis of generating relative placements and routings with ""little or no overlap"" while reducing wirelength and area. Recent advances in a ""matrix free"" interior point methods will allow the scope and size of solved problems to be in the order of millions or billions of constraints and variables. Initial focus will be on the generation of VLSI circuit layout for ""standard cell'' and ""mixed-size cell'' technologies that still form a major part of integrated circuit design. Floorplanning and facility layout problems will also be tackled. Another equally important ""objective'' is to reduce the need for search techniques (i.e., Tabu Search) to further reduce wirelength and area as well as timing, delay, power and congestion problems. In this work, we plan to minimally use search techniques to refine feasible starting solutions that are generated by the proposed powerful interior point or semidefinite programming solvers. The aim is to use the mathematical programming models of placement, floorplanning and global routing and to solve them as efficiently as possible to reduce or ideally eliminate the need for search techniques.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
44456-2011
Name nom
Vannelli, Anthony
Department département
Physical and Engineering Science, College of
Organization id
24
Institution établissement
University of Guelph
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2011
Award amount
27000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Partie
4
Nb partie
5
Application title
Advanced interior point techniques for placement, routing and floorplanning problems arising in integrated circuit design
Keyword
NSERC
Application summary
The design of many fundamental manufacturing and circuit layout problems can be modeled as linear or nonlinear combinatorial optimization problems. All of these problems are NP hard. Very tight performance specifications for these problems (minimum area, minimum power and congestion) demand near optimal designs subject to many millions to billions of constraints and variables. Over the last six years, we have developed efficient optimization techniques that can be used to solve these problems using interior point and semidefinite programming approaches that can be solved in polynomial time. We have also developed efficient interior point solvers including warmstarting that accelerate solution times for combinatorial problems. A primary ""objective'' of the proposed research is aimed at ""integration"" of large-scale interior pointmethodology used in linear, quadratic, convex, second-order cone programming and semidefinite programming to form the basis of generating relative placements and routings with ""little or no overlap"" while reducing wirelength and area. Recent advances in a ""matrix free"" interior point methods will allow the scope and size of solved problems to be in the order of millions or billions of constraints and variables. Initial focus will be on the generation of VLSI circuit layout for ""standard cell'' and ""mixed-size cell'' technologies that still form a major part of integrated circuit design. Floorplanning and facility layout problems will also be tackled. Another equally important ""objective'' is to reduce the need for search techniques (i.e., Tabu Search) to further reduce wirelength and area as well as timing, delay, power and congestion problems. In this work, we plan to minimally use search techniques to refine feasible starting solutions that are generated by the proposed powerful interior point or semidefinite programming solvers. The aim is to use the mathematical programming models of placement, floorplanning and global routing and to solve them as efficiently as possible to reduce or ideally eliminate the need for search techniques.