Tony Chan University of California-Los Angeles
Scalable Optimization Algorithms for VLSI Circuit Physical Design (NSF Proposal 0528583)
Physical design is one of the most important and challenging steps in the synthesis of very-large scale integrated circuits (VLSI), as it directly determines the distribution and layout of the interconnects, i.e. the wires connecting millions or billions of transistors. These wires are the bottleneck of circuit and system performance, as transistors are now so fast that it takes more time to transmit signals than to compute them. Core problems in physical design include the shaping and placement of both circuit components ("modules") and the wires connecting them. As the size and complexity of integrated circuits continue to grow exponentially with Moore's Law to 10 to 100 million modules, so does the difficulty in achieving designs that meet required performance targets under various constraints, such as constraints on the maximum power or temperature. Sophisticated computer-aided design (CAD) software plays a vital role in VLSI design. The systematic procedures or "algorithms" from which this software is derived are at the center of efforts to improve the quality and efficiency of circuit designs. To be useful in practice, these algorithms must be scalable; i.e., their runtime increases at a modest rate, e.g., linearly, as the design size increases. Mathematical formulations have been used extensively for physical design problems, but most of them assume either that the modules are evenly distributed over the circuit or that they follow a pre-specified density profile. The focus of this research is on the development of mathematical models and techniques to support the development of practical algorithms for the more general physical-design setting in which no pre-specified density profile is available. Such a formulation is a much better reflection of the underlying physical design problem, as, for example, the temperature distribution will not be known a priori.
The broader impact of a high-quality scalable algorithm for placement optimization under generalized density inequalities would be considerable. Improved design algorithms produce more powerful circuitry. A scalable high-quality solver with physically accurate constraint modeling allows designers to integrate diverse circuit elements in complex ways. The resulting increase in computing power ultimately translates into new products, new markets, and new science. Ultimately, the vast size and complexity of nano-scale design problems can realistically be approached only by generic, scalable algorithms yet to be developed. The successful formulation of a truly scalable methodology for physically realistic VLSI designs can be expected to have lasting and far-reaching impact on future design paradigms.
