Grant: Discovery Grants Program - Individual

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 (i.e., minimum wirelength, minimum area, minimum power and congestion) demand near optimal designs subject to many millions to billions of variables and constraints. 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.There are two main objectives in developing this research program and direction. First, a major objective of the proposed research program is aimed at "integration" of large-scale interior point methodologies used in linear, quadratic, convex, second-order cone programming to form the basis of generating relative placements and routings with "little or no overlap" while reducing wirelength and area. A second major objective is to develop promising approaches to "allow optimizers to scale"; that is, predictable fast running times will be achieved as problem size increases beyond a million constraints and variables for these present day layout problems. To achieve these objectives during the next five years, two novel approaches to solve large optimization problems containing more than a million variables and constraints will be developed. First, recent advances in "matrix free" interior-point approaches will allow the scope and size of solved problems to be in the order of millions or billions of variables and constraints. Second, we plan to accelerate interior-point algorithms using new warmstarting techniques to speed up the running time of for these very large problems. Initial focus will be on the generation of Very Large Scale Integrated (VLSI) circuit layout for "standard cell" and "mixed cell" technologies that still form a major part of integrated circuit design. Second, the exploration of analytic-based models and large-scale nonlinear interior-point solvers will be developed to solve emerging large placement problems arising in Field Programmable Gate Array (FPGAs) layout. Another equally important "objective" of this research is to reduce the need for search techniques such as simulated annealing, genetic algorithms and Tabu search to further reduce wirelength and area as well as timing, delay, power and congestion problems. In this overall research program, we plan to minimally use search techniques to refine feasible starting solutions that are generated by the powerful interior point or semidefinite programming solvers. The aim is to use 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.