\documentclass[psfig,11pt]{article} %\usepackage{epsfig} %\usepackage{mathcharter,latexsym} \setlength{\oddsidemargin}{-0.275in} \setlength{\evensidemargin}{-0.275in} \setlength{\topmargin}{-0.25in} \setlength{\textwidth}{7.0in} \textheight9.25in \begin{document} \bibliographystyle{plain} \part{Specific Questions} \section{Type of grant: \large{\bf Information Technologies.}} \section{title} \begin{center} title: \large{\bf Semidefinite Programming and other Large Scale Quadratic Techniques \\ to Solve VLSI Circuit Layout Problems} \end{center} \section{Codes} \begin{itemize} \item 1601 Operations research and management science \item 2503 circuit theory \item 2507 communications systems \item 2523 semiconductor fabrication and packaging \item 2712 Theory of computation \item 2715 Optimization \item 2718 Comminication and information theory \item 2722 VLSI systems \end{itemize} \begin{itemize} \item Henry's codes and keywords: \begin{itemize} \item optimization 2715 Key Words: ????? \end{itemize} \begin{itemize} \item Tamas's codes and keywords: \end{itemize} \begin{itemize} \item Tony's codes and keywords: \end{itemize} \end{itemize} \newpage \section{Co-applicants} \begin{verbatim} Prof. Tamas Terlaky Office: JHE/214 Department of Computing and Software McMaster University Hamilton, Ontario, Canada, L8S 4L7 Phone: (905) 525-9140 ext. 27780 Fax: (905) 524-0340 Email: terlaky@cas.mcmaster.ca www: http://www.cas.mcmaster.ca/~terlaky NSERC PIN: 9319 Hours per month to spend on this project: 32 hours Prof: Vannelli, Anthony department: Electrical & Computer Engineer University of Waterloo Waterloo, Ontario N2L 3G1 phone: +1 519-888-4567 X2241 : +1 519-888-4016 or X4016 office: DC 3617 : DC 2597F uwuserid: vannelli email: vannelli@cheetah.vlsi.uwaterloo.ca NSERC PIN: Hours per month to spend on this project: 32 hours Prof: Wolkowicz, Henry department: Combinatorics & Optimization University of Waterloo Waterloo, Ontario N2L 3G1 phone: +1 519-888-4567 X5589 office: MC 6065 uwuserid: hwolkowicz email: hwolkowicz@orion.math.uwaterloo.ca NSERC PIN: 11131 Hours per month to spend on this project: 32 hours \end{verbatim} \newpage \section{Summary of Proposal for Public Release} \subsection{Nature of the work;\\ why and to whom the research is important;\\ anticipated outcomes;\\ how our field and Canada will benefit} Information technology has become one of the most important initiatives in the twenty-first century. One of the major tasks is to increase computational speed. This includes combinatorial problems in manufacturing of chip design and VLSI circuit layout problems. Such problems are far too complex for any single optimization technique to entirely solve the problem on its own. A major direction of our research over the next five years is aimed at the integration of algorithms based on interior-point methods from convex analysis applied to semidefinite and other relaxations along with heuristics, in order to find relative placements (possibly overlapping) and global routings. Then, advanced search techniques are used to find non overlapping placements and final detailed routings. The need to look at newer optimal design techniques is becoming more important because of the increasing pressures to bring chips onto the market place in a short time. Present industrial CAD tools running on gate-array (simple uniform squares on a chip) design contain ???500,000 gates and require {\bf ???weeks to run} tasks such as placement, routing and layout verification. The entire design cycle may be viewed as transformations of representation in various steps. The layout is iteratively improved to meet timing specifications of the system. Another example is to detect design rule violations during design verification. If such violations are detected, the physical design step needs to be repeated to {\it correct} the error. Thus one of the objectives of VLSI CAD tools is to minimize the number of iterations and thus reduce the time-to-market. This is usually accomplished by having efficient heuristics, that can produce near optimal solutions in reasonable amounts of time. With the advent of more powerful parallel machines we plan to exploit special structure (sparsity) and use more mathematical tools based on the above mentioned interior-point methods and semidefinite relaxations. The development of efficient heuristics will focus on the advanced search techniques that we plan to follow in this work possess all the desirable features of a good search technique. ????They use GRASP and Genetic Algorithms to find good initial solutions. It adjusts short and long term memory and aspiration levels in Tabu Search to perform a fast local neighbourhood search that does not explore previous fruitless paths over and over like simulated annealing. ???? During the next five years, we plan to continue our research on the fundamental placement and routing problems that we analyzed with interior point methods. We plan to conduct this research on two interrelated fronts. First, we will investigate and compare several linear programming (LP) and semidefinite programming (QP) models for both the placement and routing problems. Second, we will continue to develop and refine iterative solvers for solving the expected huge systems of equations (i.e., greater than 100,000 constraints and variables) that evolve from a numerically stable primal-dual interior point methods. The final aim of this research is to complete a CAD tool that can generate near-optimal layouts. Thus, there is a major technology-transfer component that is ``built-in'' with this research. Microelectronics firms that design their own chips use one of these two packages. The potential market would be very large for using this research given that chip layout must be ``near optimal'' to compensate for the large number of components being packed into smaller sub-micron areas. ?????just rough outline for now - till we discuss more details????? \subsection{(also French summary ???Tony???)} \newpage \subsection{Research Activity Schedule\\ {\small Tasks required to achieve objectives for each year\\ start and end dates of activities leading to (clear) milestones\\ major results expected} (3 last lines to be removed) } \begin{enumerate} \item[{\bf year 1:}] Formulating the Model:\\ We will start by performing a literature overview, in conjunction with the industrial contacts, of the various models being used and available for formulating the different VLSI related problems, e.g. problems dealing with: routing; partitioning; Elmore delay; semidefinite programming; etc... Using our expertise we will decide which models need more development, which ones will be pursued , and which will be discarded. By the end of the first year we expect to have the overview completed as well as identified the tractable models that will be further explored. \item[{\bf year 2:}] Gathering Data and Building a Test Set Library:\\ VlSI problems arise in ???? We plan to contact several industries ??? visit IBM ??? phone??? Canadian IBM - MOntreal??? phone??? Ottawa??? get faxes? By the end of the year we plan to have a test set library set up with a proper interface for testing purposes. This will include small academic problems as well as large real life problems. This will be an ongoing database for researchers in this area, i.e. we will keep the database up to date. e.g. other databases netlib, minlp (Borchers sdplib) Bixby's miplib??? - one of pluses for Canada.??? cute and ??? (see Mittlemans home page) \item[{\bf year 3:}] Algorithmic and Software Development:\\ There are several different techniques that can be used to find approximate solutions for the hard combinatorial problems that we are dealing with. The techniques we plan to use are based on using convex programming relaxations and applying interior-point methods. We will use combinations of current techniques that have been used by the three applicants. Although we cannot promise to solve all the large scale problems in a reasonable amount of time, we do forsee a significant improvement in the perfomance of our algorithms adapted to the specific models, by the end of this third year. \item[{\bf year 4:}] Sensitivity Analysis and Robust Solutions:\\ We will study how small changes in the data influence the solutions. Knowing the end results of these changes is usually more important than knowing the exact soluitons, since data is constantly in flux. In addition, this knowledge will provide improvements in warm starts for the algorithms, i.e. restarting the algorithm from a known feasible solution or from an optimal solution before a data change. Moreover, there is a novel semidefinite model that is able to produce robust solutions, i.e. solutions that are not overly affected by small data perturbations. This theory will be used in conjunction with the models and algorithms developed above. \item[{\bf year 5:}] Testing and Validation:\\ The final year will be devoted to testing, benchmarking, and fine tuning our new algorithms and models in conjunction with several industrial partners. We will explore the special structure of the models to see if they are amenable to parallelization. Parallelization will be implemented only if time permits. Otherwise, this will be done in a further project. \end{enumerate} \newpage \section{Proposed expenditures for the direct costs of research} \subsection{Table:} \small Five year budget:\\ \normalsize \begin{tabular}{|c|c|c|c|c|c|c|} \hline & Year 1 & Year 2 & Year 3 & Year 4 & Year 5 \\ \hline \hline Salaries (including benefits):& &&&&\\ ~~~~ Definite Term Appointments&***&***&***&***&*** \\ ~~~~ Research Staff&*** &***&***&***&*** \\ ~~~~ Postdocs& 90,000&90,000&90,000&90,000&90,000 \\ ~~~~ Visitors& 15,000&15,000&15,000&15,000&15,000 \\ ~~~~ ???Graduate Students& 40,000 & 40,000 & 40,000 &40,000&40,000\\ \hline ???Overhead (50 percent) & 5,000 & 15,000 & 10,000 &10,000&10,000\\ Materials, Supplies, &&&&&\\ \ \ Computing, etc. & 120,000 & 4,000 & 4,000 & 4,000 & 4,000 \\ Travel & 15,000 & 15,000 & 15,000 & 15,000 & 15,000 \\ \hline OPERATING BUDGET TOTAL& 135,000 & 130,000 & 130,000 &120,000&120,000\\ \hline \end{tabular} \subsection{Salaries and benefits:} We plan to have two postdocs, one situated at Waterloo and one at McMaster. In addition, we plan on having 1 graduate student at each University involved in this project. These personnel will be involved in the research and development of the project. Responsibilities of ???postdocs??? grad students??? need details on visitors, overhead, grad student costs, foreign students??? \$7500 per year for landed immigrant but with TA and \$15000 without TA not landed immigrant then it is an additional \$7500 for each case. 2 grad students at each university. \subsection{Equipment or facility:} ?????I assume we only need one machine at Waterloo ??Tony??? SUN Ultra at Waterloo and SGI Octane at McMaster \begin{enumerate} \item {\bf Ultra 60 Model 2450 Workstation} with 2 CPU slots, 16 memory slots, 4 PCI I/O slots, and 2 UltraSCSI disk bays, includes: (2) 450MHz UltraSPARC-II CPUs, 4MB L2 cache 512MB memory (4 x 128MB DIMMS) (1) 18.2GB 10000RPM UltraSCSI disk 1 Creator3D graphics card Solaris Desktop Right-To-Use (RTU), and a 24in monitor. Price: \$29,970.00 in US dollars \item {\bf SGI Octaine} R12000. 300 MHz (1-2) Octane/SE, Graphics:Two Geometry, two raster engines, Memory: up to 4GB. Price: \$52,000. \end{enumerate} File backups, maintenance costs ???? phone??? Improvement of the communication link room between McMaster and Waterloo (and Guelph).???? phone??? check on status??? need upgrade??? for meetings between the three applicants. cameras on computers?? cost??? \subsection{Materials and supplies:} details? items? Miscellaneous costs: zeroxing, printing, printing cartridges, supplies, page costs for publications, software for new machines (e.g. NAG, MATLAB, CPLEX, GAMS, costs???), etc... \subsection{Travel:} conference details??? We will have 6 people per year travelling to conferences. These conferences are typically \$2,000 per person per conference. Data collection with industrial partners in Montreal and Ottawa. We will also visit other experts in this area, e.g. Boyd (at Stanford University) and Vandenberghe (at UCLA) in California who have started company ??? Costs for travel to conferences for three main researchers as well as the graduate students and postdocs. In addition, travel costs for visitors and local travel costs for frequent visits between Waterloo and McMaster. \subsection{Dissemination costs:} workshops? industry participation? Coordination with the Fields special year: Numerical and Computational Challenges, in Science and Engineering, August 2001 to June 2002, i.e. have a workshop since there will be so many visitors in the neighbourhood. \subsection{Other expenses:} ???? \subsection{Other Research Support:} NSERC operating grants ???? look at web page??? \section{Contributions from supporting organizations} ???? ???? \newpage \part{Free Form Proposal Description} \section{Synopsis} The last 10 years have seen tremendous improvement in computer power. This has coincided with a revolution in the theory behind optimization and our ability to solve large scale optimization problems. The three applicants have been intricately involved in these areas of research and are perfectly suited to apply these new techniques to further improve on the solution of the combinatorial aspects of manufacturing and VLSI circuit layout problems. Interior-point methods have \section{Background} One of the most important problems in information technology is that of increasing computer speed. This involves obtaining better, more efficient, chips and doing this quickly. The techniques for this are ???? \section{Proposed Research} \subsection{Introduction and Overview} The aim of this proposal is the development and implementation of software for solving problems related to VLSI design. The solution techniques we use come from convex programming relaxations of hard combinatorial prolbems in combination with heuristics for final placements. \subsection{Related Research} The three applicants have worked in areas directly and indirectly related to VLSI and other large scale optimization problems. \section{Benefits to Canada} The designers in the Microelectronics Industry are always looking for faster and more efficient CAD layout packages to deal with the denser, smaller and faster chips htat are required to meet customer needs. Our proposed advanced large-scale optimization approaches will allow for ``near optimal'' placements to aid in the development of CAD packages that designers can totally rely on in making circuit or systems related decisions. In addition, this project will open up direct communication between the Universities of Waterloo and McMaster. We hope that this will result in a long term interaction between the two universities and, thus, benefit both. \section{Team Expertise} The three applicants have expertise in optimization with applications to VLSI problems. References can be found in Section A of form 100 and/or by using the URLS of the respective co-investigators. In the last 3 years:\\ Tamas Terlaky has ???\\ Tony Vannelli has ???\\ Henry Wolkowicz has been involved in several projects dealing with SDP relaxations of hard combinatorial problems; a few are \cite{PardWolk:96,PardWolk:97,OvWo:96,SaVaWo:97,AnWo:00,Wolknonlinassign:99} and the references therein. In particular, this includes numerical tests with SDP relaxations for the quadratic assignment problem, graph partitioning problem, and max-cut problem. \section{Training} We expect to have two postdocs and two PhD graduate students directly involved in this project. They will learn both the optimization techniques as well as the VLSI background for this project. \section{Intellectual Property} \section{Synopsis} \appendix \section{Referee Suggestions} Lieven Vandenberghe\\ UCLA Electrical Engineering Department\\ 68-119 Engineering IV\\ Los Angeles, CA 90095-1594\\ ~~\\ Robert J. Vanderbei\\ Program in Statistics \& Operations Research\\ Princeton University\\ Princeton, NJ 08544 \\ ~~\\ W.R. Pulleyblank Thomas J. Watson Research Center\\ P.O.Box 218\\ Yorktown Heights,\\ NY 10598\\ USA \\ ~~\\ Prof. Dr. R.E. Burkard\\ Technische Universitaet Graz\\ Institut fuer Mathematik\\ Kopernikusgasse 24\\ A-8010 Graz\\ Austria \\ ~~\\ Tom Coleman\\ Computer Science Dept.\\ Advanced Computing Research Institute\\ 727 Theory Center\\ Cornell Univiversity\\ Ithaca, NY 14853-3801 \\ ~~\\ Jean Louis Goffin\\ McGill University\\ Faculty Management\\ 1001 Sherbrooke St West\\ Montreal, H3A 1G5 \\ ~~\\ Monique Laurent\\ Liens\\ Ecole Normale Superieure\\ 45 ru d'Ulm\\ 75230 Paris Cedex 05, France \\ ~~\\ Mike Todd\\ School of Operations Research\\ Cornell Univiversity\\ Ithaca, NY 14853\\ ~~\\ P.M. Pardalos\\ Department of Industrial and Systems Engineering\\ University of Florida\\ Gainesville, FL 32611 \\ ~~\\ Florian A. Potra\\ Department of Mathematics and Statistics\\ University of Maryland, Baltimore County\\ 1000 Hilltop Circle\\ Baltimore, MD 21250, USA\\ ~~\\ Mauricio G. C. Resende \\ office: Rm. 2D-152\\ AT\&T Bell Laboratories\\ 600 Mountain Avenue\\ Murray Hill, NJ 07974-0636 \\ USA\\ ~~\\ David Shanno\\ RUTCOR\\ Rutgers University\\ P.O. Box 5062\\ New Brunswick, NJ 08903-5062 \\ ~~\\ Yinyu Ye\\ Department of Management Sciences\\ The University of Iowa\\ Iowa City, Iowa 52242\\ ~~\\ ~~\\ OLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD\\ \noindent {\bf NOTE:} {\it Papers that are alpha-numeric are found in Section A of Form 100. Explanations of Research Contributions and Contributions to the Training of Highly Qualified Personnel are described in Sections B and C of the Form 100 also. Other references are cited in text because of limited space problems. Preprints of papers~[B1,S1-S4] can be obtained by {\bf anonymous} ftp at {\bf cheetah.vlsi.uwaterloo.ca}. Go to directory {\bf pub/nserc}}. In the last six years, I (along with my students and colleagues) have looked at three overlapping research areas: \begin{itemize} \item Advanced Techniques in Graph (Hypergraph) Partitioning and Applications \item Interior Point Methods for Solving Large-Scale Networks and Systems \item Optimization Techniques in VLSI and Manufacturing Layout \end{itemize} During this period, we have been able to formulate, develop and integrate the underlying mathematical models and optimization techniques that represent the design problems in several engineering research areas. A large part of the investigation into the {\it related areas} of VLSI and manufacturing layout has allowed us to develop the underlying heuristics to solve the resulting NP-hard problems. Moreover, we can assess the quality of the solutions generated by these heuristic techniques; that is, {\it bounds} on the global optimal solutions have been developed~[J2,J7,J6,J14,S3,S4] and \cite{PardWolk:94,PoReWo:94,HePoReWo:95,ReWo:90,HeReVaWo:93,ReVaWo:93b,KaReWoZh:94,prw:93}. This proposal will review the research areas, modeling and solution techniques that have been developed to solve the outlined problems. We outline new directions that we plan to pursue in the next four years in the areas of interior point research and applications, advanced search techniques and their {\it joint application} to VLSI circuit layout. \begin{center} {\bf RESEARCH PROBLEM AREAS, MODELS AND \\ REVIEW OF RESEARCH PROGRESS (October 1989-September 1995)} \end{center} \noindent {\bf A. Advanced Techniques in Graph (Hypergraph) Partitioning and Applications} The decomposition of large-scale systems into several subsystems is increasingly becoming an important engineering design tool. One uses decomposition to find strongly connected subsystems that have the {\it weakest} interaction between them. Such decompositions are useful because large-scale system analysis can then be performed at the subsystem level. The partitioning of a graph or hypergraph into $k$ blocks ($k \geq 2$) containing no more than $u$ nodes is known to be NP-complete [Preas, {\it Physical Design Automation of VLSI Systems}, Benjamin Publishing Co., 1988]. The work in this area has led to the development of three major approaches. First, an {\it eigenvector} approach is used to develop fast techniques {\it O(k n (log n))} (where $k<10^5$ constraints and variables) that evolve from a numerically stable primal-dual interior point methods such as the one due to Vanderbei and Carpenter, ~[Math. Prog., Vol. 58, pp. 1-32, 1993]. We feel that this work will be productive by focusing on {\it ordering} issues that arise from the factorization of the first-order conditions for optimality. Initial testing on several partitioning and placement problems reported in [S1] show the promise on these iterative approaches on large indefinite systems versus solving normal equations (CPLEX Barrier) or indefinite systems solved by {\it direct} solvers (LOQO)~[{\it LOQO User's Manual}, Tech. Report SOR-92-5, Dept. of Civil Eng. and OR, Princeton, 1992]. On a typical large-scale partitioning problem of 3000 nodes, our iterative approach using a second order level of fill [S1, p.22] was 30 times faster than LOQO; 150 times faster than CPLEX (Simplex) and CPLEX (Barrier) did not converge. \noindent {\bf D. Towards Integration} A major direction of our research over the next four years is aimed at the integration of interior point methods which are used to find relative placements (possibly overlapping) and global routings with the advanced search techniques which are used to find non overlapping placements and final detailed routings. An initial focus will be on the generation of a VLSI circuit layout for {\it standard cell} technologies. In a standard cell technology, one lays out the modules that are of a fixed height but varying length on a fixed number of rows. The layout is considered to good if a number of practical factors are optimized such as chip area, wirelength and timing/delay problems. The following ``real'' 800 node example (from [J10]) shows the effect of using (i) iterative IP methods to find initial overlapping placement~[B1,C2] ({\it left-most figure}) (ii) a sequence of advanced search techniques to partition the chip and reduce overlap~[J7,J15] ({\it two middle figures}) and (iii) a final mapping to the rows to obtain a legal VLSI circuit layout~[J10] ({\it right-most figure}). %\newline %\centerline{\hbox{ %\psfig{figure=pic1.ps,height=1.2in} %\psfig{figure=pic2.ps,height=1.2in} %\psfig{figure=pic3.ps,height=1.2in} %\psfig{figure=pic4.ps,height=1.2in} %}} You can see the effect that the optimizers have in driving the modules from the obvious useless solution of ``being on top of each other'' in the center of the chip (no wirelength) to a complete ``non-overlapping'' and legal placement at the far right. The resulting layout for this example has wirelength 5\% shorter and area 10\% smaller than a similar result generated by {\it TimberWolf} (a competitive academic CAD package). However, it has larger circuit timing and delay problems. Along with the pursuit of the individual optimization problems described in parts A and B of this section, we wish to explore adding the ``important feedback'' link to reduce these other objectives. We then plan to integrate our optimization-based routines into packages such such as {\it TimberWolf} or {\it Cadence} to compare (i.e. benchmark on large circuits containing $>10^5$ modules and wires) the generated chips performance with those that are {\bf not} generated by this approach. My proposal simply asks for funding for two of my three Ph.D. students (Andrew Kennings and Hussein Etawil) which will require full funding next Spring 1996. Both students are focused on all related research topics to this proposal. I believe that my track record of completely training 5 Ph.D.'s (2 of them solely supervised), 6 Master's and an equal number of promising undergraduate students in the last six years is strong. One of my recent Ph.D's, Paulina Chin received an {\it NSERC Postdoctoral Fellowship} in February 1995 and will continue in related research areas of this proposal. \bibliography{.master,.psd,.publs} \end{document}