A Priori Wire Length Estimates for Digital Design, 2001

The roots of this book, and of the new research field that it defines, lie in the scaling of VLSI technology. With gigahertz system clocks and ever­ accelerating design and process innovations, interconnects have become the limiting factor for both performance and density. This increasing impact of interconnects on the system implementation space necessitates new tools and analytic techniques to support the system designer. With respect to modeling and analysis, the response to interconnect dom­ inance is evolutionary. Atomistic- and grain-level models of interconnect structure, and performance models at multi-gigahertz operating frequencies, together guide the selection of improved materials and process technologies (e. g. , damascene copper wires, low-permittivity dielectrics). Previously in­ significant effects (e. g. , mutual inductance) are added into performance mod­ els, as older approximations (e. g. , lumped-capacitance gate load models) are discarded. However, at the system-level and chip planning level, the necessary response to interconnect dominance is revolutionary. Convergent design flows do not require only distributed RLC line models, repeater awareness, unifi­ cations with extraction and analysis, etc. Rather, issues such as wiring layer assignment, and early prediction of the resource and performance envelope for the system interconnect (in particular, based on statistical models of the system interconnect structure), also become critical. Indeed, system-level interconnect prediction has emerged as the enabler of improved interconnect modeling, more cost-effective system architectures, and more productive design technology.

1. Overview.- 1.1 Prologue.- 1.2 Setting of the research domain.- 1.3 Purpose of this research work.- 1.4 Three ways to follow.- 1.5 Overview of published work.- 1.6 Overview of this research work.- 2. Definitions and Basic Models.- 2.1 Model for the circuit.- 2.2 Model for the architecture.- 2.3 Model for the layout.- 2.4 Rent’s rule.- 3. Multi-Terminal Nets.- 3.1 Model for multi-terminal nets.- 3.2 Synthetic benchmark circuits.- 4. A priori Wire Length Estimation.- 4.1 Overview of wire length estimation principles.- 4.2 Donath’s hierarchical wire length estimation method.- 4.3 Global wire length distribution.- 4.4 Extending Donath’s placement model.- 4.5 Discussion and results.- 4.6 External nets.- 5. Three-Dimensional Architectures.- 5.1 Conquest of the third dimension.- 5.2 Three-dimensional architectures.- 5.3 Wire length in three-dimensional architectures.- 5.4 Anisotropic architectures.- 6. Applications of a priori Wire Length Estimation.- 6.1 Applications in computer-aided design.- 6.2 Evaluation of new architectures.- 6.3 Theoretical characterization of circuits.- 7. Conclusion.- 7.1 Overview of research results presented in this book.- 7.2 Possibilities for further research.- Appendices.- Generating polynomials as efficient representation of distributions.- A.1 Enumeration of site density functions.- A.1.1 Problem formulation.- A.1.2 Generating polynomials.- A.2 Construction of polynomials.- A.2.1 Composition.- A.2.2 Convolution.- A.3 Extraction of distributions.- A.4 Examples.- A.4.1 Two-dimensional isotropic grid.- A.4.2 More complicated architectures.- Symbols.- References.