CPA: Closing the Gap in VLSI Physical Design

University Of California-Los Angeles, Los Angeles CA

Investigators

Abstract

PROPOSAL NO: 0430077 INSTITUTION: University of California-Los Angeles PRINCIPAL INVESTIGATOR: Cong, Jason TITLE: CPA: Closing the Gap in VLSI Physical Design Abstract: Gordon Moore's famous observation that the number of transistors per integrated circuit doubles every two years has held true for the last four decades. The impact of this explosive increase has already transformed practically all areas of society, making possible all the recent revolutions in information technology: personal computing, telecommunications, bioinformatics, digital imaging, electronic commerce, etc. As the final economic and physical barriers to continued increases in silicon-based circuit densities begin to take shape, automated design tools play an ever more important role in determining system performance. Recent studies showed that existing circuit-placement tools are surprisingly far from optimal (70-150% excess wirelength) on simplified circuit benchmarks adapted from real industrial test cases. If this quality gap can be closed, the resulting benefit will be equivalent to advancing several generations in fabrication process technology, the cost of which, when feasible, is normally measured in billions of US dollars. The goal of this research is to develop new, scalable algorithms for VLSI physical design to enable multiple Moore's-Law generations of performance improvement through 3-D design optimization in the presence of complex timing and temperature constraints. The focus in this project will be primarily on circuit placement, as it is the step that most constrains the layout of the interconnect wiring which dominates system performance. The core placement problem is to arrange all circuit elements within a given rectangle such that no two of them overlap and such that a standard estimate of total wirelength is minimized. A broader and deeper analysis of existing algorithms' deviation from optimality and how that deviation changes as design sizes increase will be used to develop a highly efficient and optimized placement engine for the core placement model problem. Scalability of the engine will derive from a multiscale framework, in which objectives and constraints are simultaneously represented and manipulated across a hierarchy of resolution scales. This engine will then be and augmented to handle various complex constraints in both the 2-D and 3-D settings, e.g., signal propagation times, maximum wiring density, maximum temperature, and circuit elements of widely varying sizes. The broader impact of advancing the equivalent of an entire technology generation at almost negligible cost would be considerable. A large jump in raw computing power ultimately translates into new qualitative understanding, as previously intractable problems gradually become solvable. Of potentially even greater impact, moreover, are the possible advances in basic science to be obtained by incorporating detailed physical modeling into a scalable program for optimization over millions of interconnected elements. Ultimately, the vast size and complexity of nanoscale design problems can realistically be approached only by 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.