Multilevel Optimization in VLSICAD

December 3 - 5, 2001

Schedule and Presentations

Program Poster PDF

Organizing Committee:

Achi Brandt (Weizmann Institute of Science)
Jason Cong (UCLA)
Joseph Shinnerl (UCLA)

Introduction

In the past thirty years, VLSICAD (Computer-Aided Design of Very Large-Scale Integrated circuits) has been an enabling force behind the exponential growth of the performance and capacity of integrated circuits according to Moore’s Law. The challenges in continuing this growth in computing power to gigascale integration have to a great degree shifted from process and manufacturing technology to design automation. In the last ten years, hierarchical algorithms have been applied with dramatic results to several important areas in VLSICAD, but with relatively little direct transfer of known results in applied math. Moreover, top-down hierarchical methods are facing serious limitations as interconnects and other factors associated with the deep submicron process technologies make high-level design abstraction more and more difficult. Increasingly, multilevel methods are seen as indispensable to scalable solutions, but the associated knowledge seems insufficient to meet the immediate demands of VLSICAD. As engineers and computer scientists continue to devise new strains of multilevel algorithms, opportunities abound for more direct participation by mathematicians.

Concurrently with the steady advances in VLSI design, hierarchical methods for scientific computation have emerged as the only viable class of scalable solutions for mathematical problems in the gigascale range. These so-called multilevel methods model problems across many scales of resolution and efficiently manage local and global communication within and between scales. Typically, they converge in the optimal time order to solutions equal or superior to those obtained by non-hierarchical means. They have had enormous impact in many fields. General examples include wavelets in signal and image processing, domain decomposition methods in computational fluid dynamics, multigrid in numerical PDE simulation, and fast multipole methods in large-scale particle simulations.  The multilevel approach has been successfully applied to several areas of VLSICAD, including circuit partitioning (e.g., the hMETIS package from University of Minnesota), circuit placement (e.g., the mPL algorithm from UCLA), and parasitic extraction (e.g., the FASTCAP package from MIT).

Increasingly, multiscale methods are viewed as a generic framework for solving difficult large-scale constrained global optimization problems. To design a multiscale algorithm for a particular class of problems, one must decide (i) how to improve an existing solution at a given level by relaxation, (ii) how to aggregate information at finer scales into information at coarser scales, (iii) how to interpolate information at coarser levels into information at finer levels, and (iv) how to solve the problem at the coarsest level of representation as accurately as possible. Relaxation may use problem-specific heuristics to iteratively reduce some residual or objective function. The process may be deterministic or stochastic, discrete or continuous. It must be efficient and scalable. Example formulations include iterative methods for linear systems of equations, Monte Carlo methods, sweeps of local exchanges, and repeated solutions of mathematical programming subproblems on specially selected subsets. Different levels in the VLSI design hierarchy may represent the circuit in different ways to capture only the information most important for the given level. Notions of relaxation, aggregation, and interpolation may vary from level to level.

The goal of this workshop is to provide much needed innovation to the VLSICAD field. The prevailing VLSICAD methodology is facing serious challenges due to the rapid increase of design complexity and interconnect bottleneck in deep submicron technologies. On-chip integration, as expressed in transistors per chip, increases at approximately 58% per year compounded, while design productivity, as expressed in transistors per person-month, grows only at 21% per year compounded. Total wirelength is increasing in a similar fashion, from around 2 km today to around 10 km projected by 2009, with 8—9 routing layers and around 800,000 buffers inserted for performance optimization. Accompanying this growth are qualitative transitions in the structure and design of the interconnect. In deep submicron designs the interconnect delay far exceeds the device delay and is the dominant factor determining system performance. Typically, more time is now required to transmit data between chip locations than is required to generate it by computation. Ultimately, these changes are leading to a breakdown in the abstraction hierarchy traditionally used to divide VLSI design into separate tasks suitable for execution by separate teams of workers. The current VLSI design flow typically proceeds in the following sequence: behavioral level design, RTL design, logic design, physical design. The success of this approach depends heavily on a tight correlation between the abstract model at the higher level and the implementation at the lower level. Such a correlation, however, is difficult to maintain, as the existing abstractions are largely incapable of modeling the performance, reliability, and complexity of the interconnect. Consequently, many iterations over the flow sequence are typically required to meet timing requirements. The lack of adequate physical models in the behavioral and logical design stages leads ultimately to instability in the design process which grows increasingly problematic as design sizes increase. The continuing exponential scaling of on-chip integration poses organizational challenges that can be met only by fundamental advances in the scalability, scope, and sophistication of VLSI design algorithms. 

We announce a 3-day IPAM workshop beginning December 3, 2001, for mathematicians, computer scientists, and electrical engineers interested in this area. The program includes tutorials in general VLSICAD and combinatorial multilevel algorithms, as well as talks by specialists on state-of-the art solutions to some of the most difficult problems in the field.

Publications

Speakers

Contact Us:

Institute for Pure and Applied Mathematics (IPAM)
Attn: MOV2001
460 Portola Plaza
Los Angeles CA 90095-7121
Phone: 310 825-4755
Fax: 310 825-4756
Email: ipam@ucla.edu
Website: http://www.ipam.ucla.edu/programs/mov2001/