Interconnect Analysis and Synthesis

by Cheng, Chung-Kuan; Lillis, John; Lin, Shen; Chang, Norman

• ISBN13: 9780471293668
• ISBN10: 0471293660
• Edition: 1st
• Format: Hardcover
• Copyright: 1999-11-03
• Publisher: Wiley-Interscience

Summary

* Emphasis on realistic problem formulations, addressing key design tradeoffs such as those between area and performance

Author Biography

Chung-Kuan Cheng is the author of Interconnect Analysis and Synthesis, published by Wiley.

John Lillis is the author of Interconnect Analysis and Synthesis, published by Wiley.

Shen Lin is the author of Interconnect Analysis and Synthesis, published by Wiley.

Norman Chang is the author of Interconnect Analysis and Synthesis, published by Wiley.

Table of Contents

Preface	xi
Acknowledgments	xiii
Introduction	1	(4)
Overview	1	(1)
Book Organization	2	(3)
Models and Analysis	3	(1)
Synthesis	3	(2)
Interconnect Models	5	(34)
Technology Trends	5	(1)
Device and Interconnect Scaling	6	(4)
Timing	8	(1)
Noise	8	(1)
Power	9	(1)
Reliability	9	(1)
Interconnect Models	10	(12)
Resistors	10	(1)
Capacitors	11	(1)
Inductors	12	(1)
RC Model	13	(3)
RLC Model	16	(6)
The Effect of Capacitive Coupling	22	(8)
Output Response of Step Input	23	(6)
Output Response of Ramp Input	29	(1)
The Effect of Inductive Coupling	30	(3)
Transmission Line Model	33	(1)
Power Dissipation	34	(1)
Interconnect Reliability	34	(5)
Device Models	39	(12)
Introduction	39	(1)
Device I-V Characteristics	39	(2)
General Format of Device Models	41	(1)
Device Models in Explicit Expression	42	(1)
Device Model Using a Table-Lookup Model	43	(2)
Effective Capacitance Model	45	(6)
Interconnect Analysis	51	(48)
Introduction	51	(1)
Time Domain Analysis	52	(4)
RLC Network Analysis	52	(2)
RC Network Analysis	54	(1)
Properties of the Matrices	55	(1)
Responses in Time Domain	56	(1)
S Domain Analysis	56	(3)
Circuit Reduction via Matrix Approximation	59	(9)
Stability and Passivity	65	(3)
Analysis Using Moment Matching	68	(17)
Concept of Moments	69	(1)
Delay Estimation Using Central Moments	70	(2)
Pade Approximation	72	(4)
Moment Derivation Using Interconnect Tree	76	(2)
Connection between Pade Approximation and PVL Matrix Approximation	78	(1)
Voltage-Time Area of RLC and RC Network	79	(1)
Capacitive Coupling Output with Respect to Ramp Input	80	(1)
Elmore Model (First-Order Moment) Analysis for Single Tree	81	(2)
Layout-Driven Analysis Procedure	83	(1)
Output π Model for RC Tree Reduction	84	(1)
Transmission Lines	85	(14)
Step Input Response	87	(4)
Attenuation, Phase Shift, and Characteristic Impedance	91	(3)
Reflected and Transmitted Waves	94	(5)
Inductance and Inductive Coupling for On-Chip Interconnect	99	(62)
Introduction	99	(26)
Differences in On-Chip Inductance Consideration	101	(4)
Spectrum and Significant Frequency of High-Speed Pulse	105	(3)
Inductance Calculation	108	(8)
Skin-Effect and Proximity-Effect Resistance Calculation	116	(9)
On-Chip Inductance Consideration	125	(20)
Handling Frequency-Dependent Resistance and Inductance	125	(4)
Worst Case and Inductance Impact on Delay and Crosstalk	129	(10)
When Do We Need to Consider On-Chip Inductance?	139	(6)
On-Chip Design Solutions to Cope with Inductance Effects	145	(12)
Dedicated Ground Wires	145	(1)
Differential Signals	146	(1)
Buffer Insertion	147	(2)
Splitting Wires	149	(4)
Terminations	153	(3)
Continuous Power/Ground Planes	156	(1)
Summary	157	(4)
Synthesis: Overview and Static Topology Optimization	161	(32)
Introduction	161	(1)
Overview of Interconnect Synthesis	162	(8)
Delay Estimators	162	(2)
Design Space	164	(2)
Problem Formulations	166	(2)
Scaling Coefficients	168	(1)
Error in Delay Estimators	169	(1)
Optimization of Static Routing Topologies	170	(19)
Notational Conventions	170	(1)
Formulations	171	(1)
Algorithmic Framework	172	(1)
Maximizing Required Arrival Time	173	(5)
Minimizing Total Capacitance Subject to Timing Constraints	178	(5)
Accounting for Signal Slew	183	(6)
Summary, Discussion, and Further Reading	189	(1)
Exercises	190	(3)
Global Routing Topology Synthesis	193	(30)
Introduction	193	(1)
Background and Overview	193	(3)
Algorithm Overview	193	(3)
Preliminaries	196	(3)
Delay Models	196	(1)
Graphs, Trees, and Permutations	197	(2)
Finding High-Quality Sink Permutations	199	(3)
Hierarchy Construction and Reorientation	199	(1)
Tour Length Minimization	200	(2)
Tree Construction for a Given Permutation	202	(9)
Overview	202	(2)
Routing for Min-Area: The P-Tree+A Algorithm	204	(2)
Routing for Performance: The P-Tree+AT Algorithm	206	(3)
Complexity	209	(2)
Heuristic Limitation of cq-Set Size	211	(1)
Experiments	211	(5)
Summary and Comments	216	(3)
Speedup Techniques and P-Tree-like Algorithms	217	(2)
Delay Model Generalizations	219	(1)
Further Reading	219	(1)
Exercises	220	(3)
Optimization of Multisource Nets	223	(18)
Introduction	223	(2)
Preliminaries and Formulations	225	(2)
Linear Time Computation of ARD(T) Under Elmore	227	(2)
The Repeater Insertion Algorithm	229	(9)
A Motivational Example	230	(2)
Solution Characterization	232	(1)
PWL Primitives	232	(1)
Solution Dominance	233	(2)
The Overall Algorithm	235	(3)
Discussion	238	(1)
Summary, Discussion, and Further Reading	238	(1)
Exercises	239	(2)
Timing-Driven Maze Routing	241	(18)
Introduction	241	(1)
Assumptions	242	(1)
Formulations	243	(2)
Algorithms	245	(2)
Dominance	245	(1)
A Sink-to-source Algorithm for Bufferless Constrained Maze Routing	245	(2)
A Label-Setting Refinement	247	(1)
Example	248	(4)
An Algorithm for Formulation 9.2	252	(1)
Incorporating Buffer Insertion	253	(1)
Complexity	254	(1)
Summary and Comments	255	(2)
Exercises	257	(2)
Index	259