9512.net
甜梦文库
当前位置:首页 >> >>

Modeling and Simulation of VLSI Interconnections with Moments



Modeling and Simulation of VLSI Interconnections with Moments
RLE Technical Report No. 543

May 1989

Steven Paul McCormick

Research Laboratory of Electronics Massachusetts Institute of Technology Cambridge, MA 02139 USA

a

a

a

1-

Y

Modeling and Simulation of VLSI Interconnections with Moments
by Steven Paul McCormick Submitted to the Department of Electrical Engineering and Computer Science on March 17, 1989, in partial fulfillment of the requirements for the degree of Doctor of Philosophy Abstract This thesis presents a new CAD simulation method for determining waveform estimates of
MOS circuits. The methods are particularly useful in determining the delay times and coupling

noise voltages of interconnection networks. Additionally, switching devices are also accurately emulated with a macromodeled equivalent circuit. The moment representation, based on the Laplace Transform, is used as the model for both signals and transfer functions of interconnection networks. A large interconnection network can be modeled by a small number of polynomial terms, making network analysis much simpler, computationally. A new matrix algorithm is developed for solving for the moment representation of almost any linear network. Transistor switching circuits are modeled by macromodeled linear network equivalents. On CMOS test circuits, after several logic stages the moment representation waveforms deviated no more than 10% from SPICE's waveforms, but were computed substantially faster than SPICE. The simulation speed is further improved by "compiling" results, in which an entire switching and interconnection circuit is represented by a macromodeled moment representation approximation. Thesis Supervisor: Jonathan Allen Professor

3

4

dir

0

IF

__

_

__

Acknowledgments
First, I would like to thank Jonathan Allen, my advisor, for his inspiration and encouragement, and for providing the flexibility to define my own work as it progressed. Thanks also to my thesis readers, John Wyatt and Jacob White, for actually reading all 182 pages and for providing good feedback. I thank my friends-particularly Keith Nabors, Andy Ayers and Don Baltus, who expressed occasional interest in this work, and Bob Armstrong, Cyrus Bamji, Barry Thompson and Mark Reichelt, who have been around on the eighth floor through the whole thing. I also thank Dorothy Fleischer. Mostly, I thank my wife, Lynne, for three things: her technical assistance in the form of the work frequently cited in Chapter 6, her emotional support, and her patience as I strived to make this thesis as good as possible. Lastly, I gratefully acknowledge my sponsor, the Joint Services Electronics Program, for supporting this research.

This research was supported in part by the Joint Services Electronics Program under contract number DAAL03-86-K-0002. 5

-------

111I

6

ff
.

a

_11

Contents
1 Introduction 1.1 Existing Performance Extraction Techniques. 1.1.1 Direct Method Simulation . . . . 1.1.2 Specialized Simulators .............. 1.1.3 Waveform Bounding of RC Trees ........ 1.1.4 Second Order RC Tree Model . . . . . . . . 1.1.5 Transmission Line Modal Analysis ....... 1.2 Simulation with the Moment Representation...... 1.3 Overview of Remaining Chapters. 2 VLSI Interconnection Properties 2.1 Propagation Characteristics of VLSI Interconnections 2.2 Coupling Characteristics of VLSI Interconnections . 2.3 Interconnection Propagation on Sample Technologies 2.4 Analysis of Silicon MOS Interconnections. 2.4.1 Effects of Classical Scaling on Interconnections 2.4.2 MOS Scaling in Practice . 2.5 Analysis of VLSI Transmission-Line Interconnections 2.5.1 Transmission Line Propagation ......... 2.5.2 Transmission Line Coupling ........... 2.6 Discussion......................... . . . . . . ....... . . . . . . . . .. . . .. . . . ... .. . .. .. . . .... .. . .. . . . . . . .. . . . .. . . . . . . . . . . 15 . . . 16 . . . 16 . . . 17 17 . . . 18 . . . 18 . . . 19 . . . 22 . . . . . . . . . 25 25 27 28 32 34 38 39 39 41 43 45 45 48 49 50 51 52 52 53 53 53 53 55 55

. . .. . . . . . . . . . . . . . .. . . . . . . . . .

. . . . . . . ............... . .. . .. . . . .. .. . . . . . . . . . . . . . . . . . . . .. . . . . .. . . . . . . . . . . . . .. . . . . . . . . . .

3 The Moment Representation 3.1 Node Voltage Transitions and Waveforms ...................... 3.2 Representation Definition. 3.2.1 Expressed in terms of (t) ........................... 3.2.2 Expressed in terms of the V(s) rational function .............. 3.3 Properties of the Moment Representation ...................... 3.3.1 Shifting in Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . ........................... 3.3.2 The Linearity Property . 3.3.3 Derivatives of Waveforms. 3.3.4 Linear Network Properties . . . . . . 3.3.5 Non-Linear Network Properties . . . . . . . . . . . . 3.4 Representations of Simple Waveform Functions ................... 3.5 Time Domain to Moment Representation Conversion ................ 3.6 Moment Representation to Time Domain Conversion ................ 7
_

I__ I_

8

CONTENTS 3.6.1 Basic principles . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Polynomial Exponential ............... . . . . ? . . 3.6.3 Double Exponential . . . . . . . . . . .. . . . . . 3.6.4 Choice of g(t)..................... 3.7 Discussion........................... . . . . 55 56 60 64 66 69 71 74 74 76 76 78 79 82 83 84 84 85 . . 92 95 96 101

4 General Linear Network Solutions 4.1 Formulating the Moment Polynomial Matrix Equations . . . . . . . . . 4.1.1 Distributed Circuit Elements ............ . . . . . . . . . 4.1.2 Moment Polynomial Matrix Properties ....... . . . . . . . . . 4.2 Solution of the Moment Polynomial Matrix Equation . . . . . . . . . . . . 4.2.1 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . * . . 4.2.2 LU Decomposition .................. . . . . . . . . . 4.2.3 Finite Truncation in Moment Polynomial Gaussian Elimination . 4.2.4 Computing Node Orders ............... 4.2.5 Pivoting for Accuracy ................ *. . . 4.2.6 Pivoting for Sparsity ................. . . . ...* . . 4.3 Examples . .................. 4.4 Computational Requirements . . . . . . . . . . . . . . . . 4.5 Discussion. ..........................
e,........ .e.eee.eeee
.

. . . . . .

e....eee...
. .

*

*

.

.eeeeeeeee.

5 Transmission Line Solutions 5.1 Modal Analysis of Coupled Lossless Transmission Lines 5.2 Modal Analysis with the Moment Representation ..... 5.3 Discussion. ..........................

. . . . .. .............
. . . . ..

. . ..
..

.

. . 105

.

6 Macromodels for Non-Linear Networks 105 . . . . . . . . . . . . . . . . . . . .106 6.1 MOS Network Decoupling ........... 6.1.1 Cells . .................. . . . . . . . . . . . . . . . . . . . .106 6.1.2 Sub-networks .............. . . . . . . . . . . . . . . . . . . . .106 6.1.3 Macromodel Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107 6.2 Fundamentals of Macromodeling. . . . . . . . . . . . . . . . . . . . .108 6.3 Transistor Driver Cell Model ......... . . . . . . . . . . . . . . . . . . . .109 6.3.1 Input Capacitance. ..... . 109 .................... 110 .................... 6.4 Macromodel Input Parameters ........ ..... 6.4.1 Input Waveform Parameter ...... . 110 .................... . . . . . . . . . . . . . . . . . . . .113 6.4.2 Output Load Parameter ........ . . . . . . . . . . . . . . . . . . . .117 6.5 Macromodel Output Functions ........ 6.6 Extracting Macromodel Function Values . . . . . .. . . . . . . . . . . . .. . . .120 6.6.1 Macromodel Extraction CPU Time . . . . . . . . . . . . . . . . . . . . .128 . . . . . . . . . . . . . . . . . . . .128 6.6.2 Macromodel Memory Requirements 6.7 Transistor Transmission Cells. . . . . . . . . . . . . . . . . . . . .129 . . . . . . . . . . . . . . . . . . . .131 6.7-1 Conducting Transmission Cell . . . . . . . . . . . . . . . . . . . . .133 6.7.2 Switching Transmission Cell . . . . . . . . . . . . . . . . . . . . . . .139 6.8 Examples .................... . . . . . . . . . . . . . . . . . . . .144 6.9 Computational Requirements . . . . . ............................... s · 1 6.10 Discussion ...... 144

CONTENTS
7 Circuit Model Compilation 7.1 Circuit Model Levels ................ 7.1.1 Compiled Circuit Model. 7.1.2 Multi-Stage Compiled Circuit Model . . . 7.2 Computation Requirements ............

9 147 .. 147 .. 149 . . 152 .. 152 155 156

. . . .

. . . .

. . . . .. . . . . . . .. . .. . . . . .. . . . ..

.. . . . . . . . . . . . .. .

... ... ... ...

8 Conclusions and Future Work 8.1 Future Work. A Moment Polynomial Operations A.1 Definitions . .......... ......... A.2 Minimum Polynomial Orders. A.3 Truncation Order Rules ............ A.4 Floating Point Operation Counts .......

. . . . . . . . . . .. . . . . . . . .. . . . .

. ..

...

159 . . . . . . . . . . 159 . . . . .. . . . . . . . 160 ... . . .. . ... . . . . . 161 .... . . . . . .. . . . . . . 161 ... 163 . . 163 164 165 168 168 169

B Truncation Orders During Gaussian Elimination B.1 Moment Representation Admittance Properties ................. B.2 MPNA matrix properties ............... ............... B.2.1 Gaussian Elimination of Nodal Analysis Matrices .............. B.3 Truncation Orders for Gaussian Elimination ..................... B.3.1 Backward elimination ............................ B.3.2 Forward Elimination .. ............ ................ C Using Moments as Macromodel Parameters

173

_I_

_·_

__ I

_

10

CONTENTS

Ie

a

I

_

_

_

List of Figures
1-1 Elmore delay of a waveform . ..... . 1-2 Transitions of node voltage, v(t) . ............. 1-3 Waveform modeling in the simulator. ................ 2-1 2-2 2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10 2-11 2-12 2-13 2-14 3-1 3-2 3-3 3-4 3-5 3-6 3-7 Lumped element circuit approximations for propagation classes.. Lumped element circuit approximation for coupled lines. .... Two-port circuit symbols for coupled RC and LC lines....... Eight layer Wafer Scale Integration interconnections. ....... Multi-layer ceramic substrate technology . . . . . . . Integrated circuit groundplanes.................... Scaling of Ic interconnections. Sample circuit and model for studying delay. ........ . . . Interconnection dimensions of 1.5 am process ............ Delay vs. line length for 1.5 pm process. .............. Delay vs. line length for 0.5 m process. .............. Ground and coupling capacitance vs. conductor spacing...... GaAs dimensions contrasted with silicon's . . . . . . . Transmission line coupling waveforms ............... ......... ......... .......... ......... ......... ......... ......... ......... 17 20 .. 21 .. .26 29 .. 30 .. 31 .. 31 ... .32

.........
......... ......... ......... ......... ........
. . . . .....

35
36 37 ... .37 38 40 ... 41 42 .. 46 .. 47 51 59 61 62 65 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ........ 71 . 72 . 75 . 84 . 86 . 87 . 88 . 89 . 90 . 91

.........

Interfaces between representation domains ......... ......... Individual transitions of node voltage, (t))........ ........ Graphical meaning of some moment representation terms.. ......... Basis functions for the polynomial exponential waveform approximation.. Polynomial exponential waveform approximations ............. Effects of iterating to find double exponential poles ............ Procedure for selecting assumed waveform shape. ..............

4-1 4-2 4-3 4-4 4-5 4-6 4-7 4-8 4-9 4-10

Thevenin and Norton equivalent circuits.. Circuit Element template patterns. .......... Distributed RC element template ........... Circuit requiring node pivoting ............. Two connecting RC trees ............... Charge sharing. 10-stage RC line ................... Distributed RC tree .................. 10-stage coupled RC lines ............... Two-stage coupled RLC lines .............
11

. . . . . . . . . . . .

. ..... . . . . . . . . . . . . . . .. . .. . . . . . . . . . .. . . . . . .

. . . . . . . . . . . . .. . . . .

. . . . . . .. .. . . . . . . . . . .

... ... ... ... .... ... ... ... ...

___1_11·__ 1 · -·-11.1

·---- 1



12 4-11 Computations vs. node count .............................. 5-1 5-2 5-3 5-4 5-5 5-6 6-1 6-2 6-3 6-4 6-5 6-6 6-7 6-8 6-9 6-10 6-11 6-12 6-13 6-14 6-15 6-16 6-17 6-18 6-19

LIST OF FIGURES 93 96 97 97 99 . 99 100

Response of single transmission line .......................... Waveforms from MPNA and modal analysis of transmission lines ........ Coupled transmission line geometries .................... Modal analysis equivalent representation ............... Method of characteristics equivalent circuit ................. Modal analysis circuit .. ...............

... ...

Sub-network boundaries .......... . ... 108 Legal and illegal macromodel cells for a cross-coupled inverter circuit . .... 109 Linear network equivalents for macromodel driver cell ............... 111 MOSFET input capacitance ................. . 112 Representative input voltage waveforms with identical Elmore times, M 1 ... 112 Critical range of output voltage. ........ ............. 114 Approximating circuit for computing Vstep(t) . ............ .114 Transistor driver cell linear circuit equivalents. ....... ...... 118 SPICE simulation of true inverter and linear circuit equivalents ........... 119 Full Adder Karnough map with output transition possibilities .. .. ...... 120 Macromodel extraction test circuits . . . . . . . . . . . . . . . . . . . . . . . . . 121 Test input waveform ............ .. .. 122 Approximate linearization of a macromodel function ................. 130 Conducting transmission cell .. .. ... ....... 131 1............. Switching transmission cell . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 Linear circuit equivalents for a conducting transmission cell .132 Conducting transmission cell macromodel extraction circuit ............ 134 Linear circuit equivalents for a one-transistor switching transmission cell. ..... 135 Second order linear circuit equivalents for a two-transistor switching transmission cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 6-20 Test circuit for extracting switching transmission cell macromodel values .... 137 7-1 Circuit model levels. ............. .... 148 166
........

B-1 Circuit representation during gaussian elimination .................
C-1 Macromodel plot of critical region waveform slope vs. X 2 and X 3

175

List of Tables
2-1 2-2 2-3 3-1 3-2 3-3 4-1 6-1 6-2 6-3 7-1 7-2 7-3 Interconnection characteristics of sample technologies. ............... Comparison of maximum coupling capacitance ratios of 1.5 pm and 0.5pm process ....................................... ..... Transmission line characteristics of sample technologies. ................ 33 39 41

Terms of moment representation for one transition. .. . .............. 50 Laplace transforms and waveform representation terms for simple functions ... . 54 Common Assumed Waveform Shapes ......................... 57 Equivalent computations of examples for each method ............ Macromodel functions and scalar values of a third-order macromodel set. ... Number of single precision floating point numbers for a macromodel set ...... Simulation time in CPU seconds ........................... Parameters for complete system CPU time estimates. ............... Simulation times for different circuit model levels in hours/MIP. ......... Third-order circuit model translation times in hours/MIP ............. ... 92 . 119 128 144 153 153 154 162

A-1 Maximum number of floating-point operations for polynomial operations ....

13

__L

I

14

1*

r;

0

-

1

Introduction
VLSI circuitry'has created enormous possibilities for digital system design, but has also created a new set of design problems. A system must be extensively evaluated before fabrication of even a prototype, since parts are not off-the-shelf and may take valuable months to make. Determining the performance of digital circuits before fabrication is an essential task. VLSI circuit designers must rely on Computer Aided Design (CAD) tools. Most often, the performance of a VLSI system is determined through simulation. General, numerical simulators (like SPICE [1]) are accurate, but are too slow for simulating large circuits. Popular alternatives to SPICE are simulators with simple circuit models that are computed rapidly. Previously, estimating speed performance through simple models was relatively easy. Circuit speeds of older MOS technologies was controlled by transistor drive and total load capacitance. Circuit speeds of bipolar technologies were mainly controlled by the same parameters. Printed circuit board delays were largely ignored since chip output switching times have exceeded printed circuit board interconnection times. Increasingly, however, the performance of all VLSI technologies is being dominated by interconnection performance. As transistor dimensions shrink, device speed performance improves. However, interconnection delays across an entire chip are becoming much longer. This is true for MoS, bipolar and GaAs technologies, even though interconnection circuit models are quite different. With faster switching chips, propagation delays on printed circuit boards and chip carriers are also increasingly significant. As chips and printed circuit boards become more complex another difficulty is increasingly observed on all VLSI technologies-cross-talk noise between coupled interconnections. Coupling on silicon MOS chips can intensify by the increased relative sidewall heights of finer linewidth interconnections, and as always, coupling is observed between overlapping conductors. Coupling is far greater on GaAs and Silicon-on-Sapphire chips than silicon chips because of semiinsulating substrates. On printed circuit boards, increased coupling is due to finer linewidths and spacings, an increased number of layers, and faster transitions. Chapter 2 discusses interconnection propagation delay and coupling in detail, and in general, shows why it is becoming 15
_^I____IIUUI__LIII__LII -·-11_--11^-1^1

16

CHAPTER 1.

INTRODUCTION

more important to examine interconnection performance. This thesis focuses on circuit modeling methods that can be used for fast computer simulation of interconnection behavior-that is, the circuit modeling is optimized for circuits with interconnection dominance. The modeling in this thesis determines voltage waveforms on any node, which can subsequently be used for determining delay times and noise levels. The problem of extracting an equivalent circuit from layout geometries is not considered in this thesis. It is assumed that interconnection behavior can be modeled by linear circuit elements (distributed or discrete) and that these can be extracted from physical layouts. Circuit extraction from interconnections is discussed in [2,3,4,5] and circuit connectivity extraction is discussed in [6,7].

1.1

Existing Performance Extraction Techniques

First, we will examine existing simulation and performance modeling methods for interconnection circuits. 1.1.1 Direct Method Simulation

Currently, direct method circuit simulators like SPICE [1] and ASTAP [8] are the mainstay of IC circuit designers for simulating circuit performance. These flexible simulators accept almost any circuit with linear or non-linear, discrete elements and determine the voltage waveform on any node. Direct method simulation is much too costly for simulating complete chips and certainly for simulating complete systems or system backplanes. For instance, the circuit size of SPICE simulations is effectively limited to hundreds of nodes, thus, limiting these simulators to analysis of individual cells. As circuit performance moves from transistor dominance to interconnection dominance, direct method simulators need to devote less time to costly non-linear transistor model evaluation. But, with direct method simulators, distributed elements of interconnections must be broken into a series of discrete elements, adding excessively to the already limiting number of circuit nodes. Relaxation and iteration simulation methods [9,10,11] offer a simulation speed and circuit size improvement over direct methods for Mos digital circuits. This is achieved by breaking circuits, usually on capacitive boundaries, and solving the sub-circuits separately, where the waveform on one sub-circuit controls the simulation of the next sub-circuit, which control the next, and so forth. When the interaction between separate cells is strong, the sub-circuits must be solved iteratively. Relaxation methods enable circuit size to be increased to thousands of nodes-still a size prohibiting entire chip simulation. An even more comprehensive simulation method solves Maxwell's Equations for interconnections. These simulators perform the most accurate simulation of interconnections, including non-TEM transmission line effects, skin effect, etc. But, they are limited to very small circuits,

1.1.

EXISTING PERFORMANCE EXTRACTION TECHNIQUES

17

Wt) - ?f YVi-V

I
II

1

d

time

FIGURE 1-1:

Elmore delay of a waveform.

in some cases they are able to simulate just a single crossing of two interconnections. 1.1.2 Specialized Simulators

Because of circuit size limitations with direct method simulators many specialized, faster simulators have been developed-usually at the expense of accuracy. A prime example of this is RSIM [12] for MOS circuits. This program started as a switch-level logic simulator, and simple delay models were added to it. Each logic state transition on a node causes a delay model computation for a time estimate of the transition. The delay models in RSIM are based on transistor resistance and load capacitance-models which are inadequate for interconnection dominated circuits. Improved delay models have been developed which can be built into MOS switch-level simulators. The next sections describe improved delay models which are specific to interconnection dominated circuits. 1.1.3 Waveform Bounding of RC Trees

Waveform bounding methods are used to find an Elmore time approximation, a low bound and a high bound of the voltage waveform on a circuit node. The Elmore time [13] actually equals the area under the step response waveform if the initial and final values are shifted to 1 v. and 0 v., respectively. That is, the Elmore time equals the shaded area in Figure 1-1. The Elmore time can be used to make a waveform estimate, most often in the form of an exponential, i.e., in the form of
v(t) = Voet/ td.

These methods were first developed by Penfield et al. [141 for RC tree circuits consisting of resistive tree networks, with a capacitance to ground at each node. Distributed RC elements

__

1__1 _

_II

I

____

18

CHAPTER 1.

INTRODUCTION

are also allowed. Later, the class of permissible circuit was extended to include RC meshes [15] and general RC networks [16]. The tightness of the bounds was improved in [17]. These methods have several limitations. First, on some nodes the Elmore time waveform estimates are poor and the bounds are loose. This is quite noticeable for nodes near the driven end of an RC line. Second, the RC circuit forms are limited and do not model all desirable interconnection situations for RC lines. These methods, for instance, cannot model capacitive coupling or resistive substrate effects (like those shown in Figure 2-1(e) and (f)). Third, nonlinear elements can only be modeled by linear element approximations. 1.1.4 Second Order RC Tree Model

Horowitz [18] has developed second order RC tree methods as an extension of the previous RC tree methods. Two things were added in this work. The first addition is improved, secondorder waveform estimates that match the Elmore time, the second-order moment (moment is extensively defined in Chapter 3) and the sum of the open-circuit time constants (or term bl of the transfer function, al+,l++b22+. ). The second addition is the ability to model switching pass gates in the middle of an RC tree. This work addresses the first limitation presented in the last section. However, it still contains the other limitations mentioned for RC tree methods. 1.1.5 Transmission Line Modal Analysis

Much effort has been devoted to modeling both lossless and lossy transmission lines with computationally faster algorithms. A good discussion of this is in [19]. Direct method simulation is particularly inefficient for transmission line circuits, since generally the distributed transmission lines must be modeled by a very large number of discrete nodes, more than is needed for RC lines. A much faster analysis technique is achieved with modal analysis. Modal analysis is possible in either the time domain or the frequency domain. Time domain modal analysis works only for lossless transmission lines and assumes a constant dielectric medium and constant coupling along the length of the transmission lines. 1 Time domain modal analysis is advantageous in that it is possible to simulate coupled networks and non-linear drivers and loads (if solved with direct methods), The major disadvantage is that lossy lines cannot be simulated unless the line is divided into many sections connected by discrete resistors [22]. Frequency domain modal analysis can simulate lossy lines, but only with linear driver and load networks. Again, it assumes a constant dielectric medium and constant coupling along the length of the transmission lines. To operate in a time domain simulator, an FFT interface
'Transmission line analysis with varying coupling coefficients has been addressed in [20] and [21].

1.2.

SIMULATION WITH THE MOMENT REPRESENTATION .

19

is needed to translate between the time domain and frequency domain. Mild frequency domain modal analysis has been investigated by [23]. Both time domain and frequency domain modal analysis has been added simulators. Accordingly, performance is often constrained by other features These methods are incorporated into the simulator methods presented in this ter 5) and operate with much improved speed.

non-linearities in to direct method of the simulator. thesis (see Chap-

1.2

Simulation with the Moment Representation

In general, the specialized interconnection simulation methods described in the previous sections suffer several drawbacks. The most noticeable one is that no one method can be used universally for all configurations of interconnection simulation. A different method must be applied to each propagation class (i.e., LC vs. RC propagation) and to each type of circuit stimulation (i.e., a single-ended driver vs. a switched transmission gate vs. a noise spike ...). Additionally, many of these methods have limited capacity to simulate non-linear circuit elements. Most use a linearized approximation for non-linear drivers and loads. This often leads to approximate solutions with large errors, particularly when input waveforms fluctuate over a wide range of input slopes. Direct method circuit simulators have the flexibility to overcome these drawbacks, but these simulators are too slow to accommodate the large scale simulations needed for VLSI design. The moment representation simulation methods, introduced in this thesis, address these drawbacks. The moment representation simulator uses nodal analysis, so, like direct method simulators, the circuit configurations can be very flexible. It can simulate both LC and RC interconnections with or without coupling, charge sharing circuits, single-ended drivers, pass gates and so forth. A major difference, however, is that direct methods operate in the time domain while the moment representation simulator operates in the moment representation domain, which is a subspace of the frequency domain. The moment representation domain better accommodates linear interconnection circuits, especially with distributed circuit elements. While the frequency domain usually precludes non-linear circuit elements, this thesis presents a moment representation macromodeling method which very accurately constructs a linear circuit equivalent for a non-linear transistor circuit. The equivalent is valid through the entire duration of any transition. The linear equivalents have variable circuit elements with values that are macromodeled functions of input signal slope and output load. This macromodeling method permits very rapid and accurate simulation of non-linear elements and is favorable for combined linear and non-linear circuits. Several features of the moment representation allow very rapid simulation of circuits: 1. An entire logic transition is solved in the moment representation simulator with one matrix equation solution. On the other hand, direct methods require at least one matrix

_I

)·)_

LI----l--·

L·LIL_

·-- I^ --

----- _·

111 --^--

- --L---

20

-CHAPTER 1.

INTRODUCTION

transition 1 transition 2 transition 3 transition 4
5

v(:) 0

FIGURE

1-2: Transitions of node voltage, v(t).

equation solution at each incremental time-step-several dozen time-steps may be needed for each logic transition. 2. The macromodeling algorithms for non-linear circuits are much faster than NewtonRaphson iteration used in direct methods. 3. The response of circuits can be compiled by a preprocessor into a very compact moment representation form. This is analogous to finding a linear circuit transfer function, except that non-linear elements are also permitted. An experimental simulator was developed to test the moment representation simulation methods. The moment representation algorithms were embedded in an event-driven logic simulator in much the same way that RSIM's simple timing models were added to a switch-level logic simulator [12]. The logic simulation algorithms are well-known, so they are discussed in the thesis only in the briefest fashion. Details of event-driven logic simulation are found in [12,24]. Waveform related issues of event-driven simulation, such as what to do when events overlap or when events cancel, are detailed in [25,26]. The simulator algorithms were tested on digital circuits containing Mos transistor and interconnection models. Simulator results are interspersed throughout the thesis at appropriate locations. The following paragraphs briefly outline the operation of the experimental simulator. The voltage on any node is broken into a series of transitionsseparated by periods of d.c. voltage, as shown in Figure 1-2. Each transition has a starting time, designated t through t4 in Figure 1-2, a d.c. transition value, and a waveform. The simulator models a node voltage by transitions-at the starting time of a transition, the node voltage is defined by the waveform portion of the transition; when the waveform decays to a final, constant value, 2 the node voltage is given by a constant d.c. value. The simulator must keep track of the d.c. value and update it at the end of each transition. As shown in Figure 1-2, the transition can represent any type of perturbation in the waveform, and is not always a logic transition.
an asymptotically decaying waveform this point is taken to be where the voltage decays to within 2% of the final voltage.
2For

1.2.

SIMULATION WITH THE MOMENT REPRESENTATION

21

User Input Waveforms (arbitrary shape)
I

11
I!

Separate into Transitions
.

Output Waveform Segment Time Domain

Convert to Moment Rep.
8i

Moment Representation Domain

Convert to Time Domain

lr
j

1 1

L
if

Queue Transitions

for each transition

if node is 'probed' Convert to Time Domain
1

for each sub-network connected to node
.......... ......... ......... ......... ......... ........

Simulate Sub-network if signal t ransition and circuiit not com7i'led Convert Non-Linear to Linear Elements

I0

, _ __

z

-_

If signal transition

and circuit
compiled

if noise
transition

Fetch Ma acromodel Re:suits

Compare Against Noise Margins
lif

Solve Linear Network -~~~~~~~ .
...................
.......... .. ................. .................................... .........

'exceeded
... .......... ...

queue each sub-network output transition(signal and noise)
FIGURE

Warnings

1-3: Waveform modeling in the simulator.

---- ^^L1_-··IYISII

-I-___

_-_

-_I

1--_I

^I·I

-

22

CHAPTER 1.

INTRODUCTION

Within the event-driven simulator, transition waveforms are represented in two forms: in the time domain and in the moment representation domain. The different forms are used in different places in the simulation algorithms to gain maximum efficiency in both simulation time and simulation memory requirements. Figure 1-3 shows the general flow of operations in the simulator and also shows locations in the simulation algorithms where the two waveform representations are used. The double lines indicate where the time domain is used, all other places use the moment representation. Initially, the user supplies a set of input transitions to the simulator. These are converted to the moment representation domain and are inserted into the transition event queue. During simulation, transitions are pulled from the queue sequentially by starting time. The node on which the transition occurs is said to be activated. The moment domain waveform of the transition is then converted to the time domain. As we will see in Chapter 6, this is required for macromodel function evaluation. Chapter 6 also describes how an MOS circuit is split into disjoint sub-networks. Each sub-network with an input connection to the active node is simulated separately. The choice of simulation algorithm depends on whether the transition represents a signal change or noise spike and whether the sub-network has a compiled circuit model. For a noise transition, the peak noise voltage is compared against noise margins for the active node. A warning is issued to the user if exceeded. For a signal transition, if a compiled circuit model exists, then precomputed simulation results are fetched from macromodel tables, otherwise, the sub-network must be solved, first by converting non-linear elements into equivalent linear networks, and then by solving the linear network. In either case, if the signal transition on any sub-network causes an output change, then the new transition(s) are added to the event queue. The user may select to probe the output waveform of any node. All output transitions for a probed node are converted to the time domain and are assembled into a single, continuous waveform for user viewing.

1.3

Overview of Remaining Chapters

Chapter 2 discusses interconnection properties, and demonstrates the importance of examining interconnections of advanced technologies. The information in Chapter 2 is not crucial to understanding later chapters and may be skipped. Remaining chapters describe the moment representation simulation algorithms. Chapter 3 defines and characterizes the moment representation. It presents the methods for converting between the time domain and moment representation domain and discusses the transition model for waveforms. There are several advantages to circuit modeling with the moment representation methods; the major advantage is presented in Chapter 4. It shows a method for solving any linear circuit

1.3.

OVERVIEW OF REMAINING CHAPTERS

23

composed of resistors, capacitors, inductors and independent sources in any configuration. Furthermore, distributed circuit elements, such as distributed RC's or LC's which are so prevalent as interconnection models, can be included as simple two-terminal elements without loss of accuracy. Chapter 5 outlines some special algorithms for solving transmission line circuits with the moment representation. It shows that existing transmission line modal analysis methods can be used with the moment representation to give very good results. The macromodeling feature of the moment representation simulator is introduced in Chapter 6. First it describes how Mos transistor circuits are divided into subnetworks, and then it describes an accurate method for converting a non-linear circuit into an equivalent linear circuit. The linear circuit is then suitable for solution with the methods of Chapter 4. A final feature of the moment representation is presented in Chapter 7. It shows that a circuit that is to be simulated through many input transitions can be compiled into a small macromodeled moment representation description. Subsequent simulations of compiled circuit models are much faster.

1 ·_·X_



__

_

1_-----1·--1

1 --

24

CHAPTER 1.

INTRODUCTION

r,

I

2

VLSI Interconnection Properties
When studying VLSI circuits, many types of interconnections must be considered which have dissimilar signal propagation behaviors. In this chapter, propagation characteristics will be studied, first in a general manner, then for specific VLSI technologies.

2.1

Propagation Characteristics of VLSI Interconnections

Interconnections on VLSI chips, printed circuit boards and high-density ceramic chip carriers have different properties. For our purposes, all interconnection properties can be illustrated by equivalent lumped element circuit approximations. We will assume that circuit elements are constant over all time and frequency. The lumped element circuit approximation of a general RLGC interconnection is shown in Figure 2-1(b). If a very large number of these two-port circuits are chained together, the propagation behavior resembles the behavior of its equivalent interconnection. Partial differential equations describing propagation along a general RLGC interconnection are:

a i(z, t)
ox

C +C

v(,

t)

Ot
i(z, t)

+G v(z,t)= 0,

Ov(,t) + a V( + t)L
or in the frequency domain, di(x, j)

+ Ri(.r. t)= 0,

(2.1)

dx

+ jw C v(x, jw) + G v(x, jw) = 0,

d v(x, jw) + jw L i(x, jw) + R i(x, jw) = 0. dx

(2.2)

Typically, one or more of the terms can be neglected, depending on the signal frequency, w (which is approximated for a transition with rise or fall time, r, by w ~ 2r/r) and on values of R, L, G, and C; the line resistance, inductance, conductance and capacitance per unit length, respectively. Accordingly, different propagation classes result-the more prevalent classes are listed below. We will always ignore G since only good insulators are assumed. 25

_____1_IIII Y_·_l·_l

·II

26

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

i(x,t)
I.-

R
- 1-lq

L

-1-1--

--

groundplane

v(X, t)

TC

(a)
R
t Van

(b)
L

?
Ed

T
(d)

o

(c)
L
.

v

l ...

rrmy
I . .

Il r

C2

(e)

(f)

p
O,

~~ Ti0
_

(g)
FIGURE 2-1: Lumped element circuit approximations for propagation classes. (a) transmission line, (b) general RLGC propagation, (c) RC propagation, (d) TEM propagation, (e) and (f) resistive substrate propagation, and (g) tracking propagation.

2.2.

COUPLING CHARACTERISTICS OF VLSI INTERCONNECTIONS

27

* RC propagationprevails as the most common propagation class for silicon Mos integrated

circuits. These interconnections have (1) very fine line widths, leading to large R's, and (2) a closely spaced groundplane, leading to small L's, thus, R > wL. With the G and L terms absent in this class (Figure 2-1(c)), Equations (2.1) reduce to the diffusion partial differential equation-also applicable for describing heat flow, impurity concentration movement, etc. * LC propagation or Transverse Electromagnetic (TEM) propagation contains only the L and C terms of Equation (2.1) (also illustrated in Figure 2-1(d)) since wL > R. These interconnections are lossless transmission lines. Because of its faster, wave-like propagation, LC propagation is more desirable than RC propagation. Efforts have been made to ensure
this propagation class in Wafer Scale Integration circuitry [27] and in VLSI packaging interconnections [28], mostly by raising the interconnection higher above the groundplane.

This propagation class also exists in GaAs technologies, but not for MOS technologies,
as it is difficult to reduce the R term below the L term at typical Mos dimensions and switching speeds. * As one would expect, there is a transition region between the previous two propagation classes where the resistive and inductive components have comparable magnitudes. The resulting differential equations are more difficult to solve with heuristic methods and are often neglected in interconnection analysis. Interconnections that exhibit wave-like propagation but have a non-negligible resistive component are lossy transmission lines. Some consideration is given to this propagation class in later sections. * Hasegawa [29] has studied signal. propagation on metal lines above a highly resistive silicon substrate. Due to the non-perfect ground plane, the transmissions line models more resemble those of Figure 2-1(e) and (f). Despite the harder analysis, Seki [30] has demonstrated some speed advantages to a lossy substrate. * If the interconnection time constant is much shorter than the input signal time constant, it suffices to consider an interconnection as a single node in which propagation is instantaneous. In this tracking propagation class, an entire interconnection is modeled by a single lumped capacitor as shown in Figure 2-1(g). This propagation class is included here for completeness. But, as we will see in future sections, this type of propagation is becoming less pertinent to VLSI interconnections.

2.2

Coupling Characteristics of VLSI Interconnections

As we will soon see, coupling characteristics of VLSI interconnections are also becoming important with technology improvements. In general, coupling between two interconnections may

I_-----L·l ^-llL_--1··.._· ·· ·^^--IC-1 I

L_

_

28

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

have inductive, capacitive and resistive components as shown in Figure 2-2(b). The behavior on line 1 is described by
jw) d il(z, jw) + jwC1 v1(z, - jw C12 v 2 (, jw) - GI, vi(z, Jw) + G12 v 2 (X, jW) = 0 dz

dV1 (x, jw) + jw L 11 i 1(x, jw) + jw L dx where

2

i2 (, jw) + RI i1 (x, jw)

=

0

(2.3)

C11 = Clo + C12, ll = Lo - L1,

and
Gl = Glo + G 12 .

In matrix form the equations for all lines are

d i(x, jw)+ jwa C v(x, jw) - G v(x, jw) = 0,
dx + jw L i(x, jw) + R i(x, jw) = 0. (2.4) dx These equations are the telegrapher's equations. Again, for all examples in this thesis we assume perfect insulators around the interconnections, and the G terms vanish. The arguments are the same here as in the previous section for neglecting either the resistive or the inductive components or both. We will consider the components depending on the relative magnitudes of R and wL. * With RC .propagation, inductive terms disappear, leaving the lumped element circuit approximation shown in Figure 2-2(c). * LC propagation leaves only the L and C terms as shown in Figure 2-2(d). * Tracking propagation has only the lumped capacitors shown in Figure 2-2(e). Coupled RC and LC interconnections have the circuit "symbols pictured in Figure 2-3.

2.3

Interconnection Propagation on Sample Technologies

In this section, interconnection characteristics of various VLSI technologies are examined. A propagation class is linked to each technology. Technologies we will consider are: 1. silicon MOS, 2. silicon bipolar,

2.3.

INTERCONNECTION PROPAGATION ON SAMPLE TECHNOLOGIES il (x, )

29

'

-

S~~--7
+ vl(x.t)

+

C

groundplane

v2(X, t)

I
(a)

I710
R
0

T:G _
5-1U

-

I
-

l_

_0 I
I,

_1

_

~ ~

I

LL

I
-

n

m r

R1
_o A A 11 W W V v _ Q~~-

pl=.

L 12 ( R2 R2 L2 0 h

C12
-

m

I. -_1z
4 6------^

C 12 0R2
I,c

,_
-

20

b

T
(b)

G20

-

C20

T
(c)

I
W

_

I

0--l

_

m m

C1o
C 12

L 10
i

C12

0

i

L

L2 0

C 12
_

_

o 20 C20

A-----------------

6--------------%

C 20

T
(d)
FIGURE

I
(e)

2-2: Lumped element circuit approximation for coupled lines.

(a) actual, coupled transmission lines, (b) general RLGC propagation, (c) RC propagation. (d) TEM propagation, and (e) tracking propagation.

--- ·- ·--

-------

·----

·---------

·

-------

11

111-

30

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

I

-'
I

ii---a

-

I-

I-I

I

I

I

I

a ,
I L_ _ _ - -; v_ I _ __I _

RC LC FIGURE 2-3: Two-port circuit symbols for coupled RCand LClines.
3. silicon-on-sapphire (SOS),

4. GaAs, 5. an improved interconnection technology for Wafer Scale Integration (WSI), and 6. a ceramic chip carrier technology. The first four technologies are chip level technologies and assume a lithography capability of about 1 Mm linewidths. Aluminum metalization is assumed; but the exact metalization material is not crucial in this cursory examination. The last two technologies require some explanation. While most wafer scale integration circuitry uses existing metalization for inter-chip communication, the WSI technology considered here uses a coarser interconnect metalization on top of the fine-lined chip interconnections. This enables faster communication between chips, since conventional IC lines exhibiting RC signal propagation are unacceptably slow over complete wafers. Bergendahl [27 has suggested placing eight thick-film layers on a wafer, two layers for power, two for z and y direction wiring and four for vias between layers as shown in Figure 2-4. To achieve LC propagation, Bergendahl suggests a minimum metal thickness of 10 Mm with an insulator thickness of 5-10 pm. Metal widths and spacings may be as low as 5 pm. The ceramic chip carrier technology considered here is an advanced technology developed at
IBM for mounting and interconnecting integrated circuits [31,32]. As shown in Figure 2-5, it has 33 metalization layers of which sixteen are signal distribution lines spaced 0.5mm horizontally

and between 0.15 mm and 0.2 mm vertically. The remaining layers are used for voltage reference planes, power distribution and local signal distribution. Now we will match each interconnection technology to a propagation class. Table 2-1 lists approximate values for relevant technology parameters. Parameters for conductor-to-groundplane spacing, H, are illustrated in Figure 2-6 for the chip technologies. Notice that while the same

conductor dimensions are assumed, H is quite different between silicon and both SOS and

I

-

2.3.

INTERCONNECTION PROPAGATION ON SAMPLE TECHNOLOGIES

31

VDD plane layer Via 4 layer X signal layer Via 3 layer Y signal layer Via 2 layer Groundplane layer Via 1 layer
wafer bonding point 621--

10 um polyimide metal
local interconnect wafer

T

FIGURE 2-4: Eight layer Wafer Scale Integration interconnections.

There are eight planarized metal layers, four for interconnections and four for vias. This figure shows a wafer-to-y-signal connection, a y-signal-to-x-signal connection and a x-signal-to-surface connection.

Rcdisinbutln layers

i, *

/, =7o ' ,
-- - -"

= $, ,
p

|Signal
distribution

_e
-

~ ~

; .,

By_,-~~~

-1

~

· u

I

layers

_

*

Mu

.

4

11 -__ j~~~~~~~

Power distribution layers

FIGURE 2-5: Multi-layer ceramic substrate technology.

From [31].

32
T = -1

CHAPTER 2. VLSI INTERCONNECTION PROPERTIES

T

--

T

-

T

l, + um n/

T

-

T= l.Oum)
H = 0.7m SiO2

T

.0umT=

H = 300um
Si

-t

I =300um.
Sapphire

11

X It1
A_

'.' X%

GaAs

FIGURE 2-6: Integrated circuit groundplanes. GaAs. This is due to the insulating properties of the sapphire and GaAs substrates. This analysis assumes that silicon forms a good groundplane at its top surface.1 Values for transition time, r, are approximate values for a switching device driving a long interconnection. In some cases r ranges over an order of magnitude. This range is also reflected in the wL estimates. The bottom line of this table is the expected propagation class for each technology. It stems from a comparison of the series resistance and series inductive impedance estimates. We see with these estimated interconnection parameters that we can expect (1) RC propagation on silicon MOS interconnections, (2) transmission line or LC propagation on GaAs, wafer scale integration and ceramic chip carrier interconnections, and (3) a mixture or RLC propagation on SOS and silicon bipolar interconnections. Because of the different nature of RC and LC interconnections, they are considered separately in the next sections.

2.4

Analysis of Silicon MOS Interconnections

To date, propagation on metal MOS interconnections has only marginally limited IC performance. This chapter shows that as MOS interconnection linewidths are scaled down, the intrinsic propagation delays along maximum length lines are becoming significant, and that the coupling between adjacent lines is also increasing to a noticeable level. Reasons for this are best understood through the scaling theory.

'Inductance values are also computed by assuming that the silicon surface is an ideal groundplane. Evidence suggests that this is not strictly true, and that the magnetic field extends into the silicon substrate [33], effectively increasing the inductance of silicon MOS and bipolar technologies.

2.4.

ANALYSIS OF SILICON MOS INTERCONNECTIONS

33

Silicon MOS H (/um) T (pm) r (nsec) ER,insulator
/- R,insulator

Silicon bipolar 0.7 1 0.1 3.9
1

0.7 1 1.0 3.9
1

Silicon on Sapphire 300 1 1.0 10.5
1

GaAs 300 1 0.01 - 0.1 12
1

Wafer Scale Integration 10 10 0.1 - 1.0 3
1

Ceramic Chip Carrier 200 - 1600 70 0.01 - 1.0 9.4
1

C (pF/m) L (A H/m) wL (fi/m) R (!Q/m) Propagation class H T

190 0.23 1.5K 19K RC

190 0.23 15K 19K RLC

63 1.9 12K 19K RLC

72 1.9 117K-1.17M 19K LC

95 0.35 2.2K - 22K 260 LC

110 0.93 5.9K - 590K 25 LC

ER,insulator AR,insulator

C L wL R

conductor to groundplane distance conductor thickness dimension approximate transition time relative dielectric constant of insulating medium relative permeability of insulating medium conductor ground capacitance per unit length series inductance per unit length series inductive impedance per unit length series resistance per unit length

Table 2-1: Interconnection characteristics of sample technologies.

34 2.4.1

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

Effects of Classical Scaling on Interconnections

The classical Mos scaling theory proposed by Dennard [34] predicts how Ic layouts and operating ranges will change as inevitable improvements in IC technology occur. The theory
assumes a proportional reduction of all dimensions; the amount of reduction is denoted by a > 1 such that any dimension I 1' = I/a. (Values after scaling are identified with a prime.) It

also assumes retention of constant electric fields, resulting in a voltage reduction by v' = v/a. Classical scaling of geometries is illustrated in Figures 2-7(a) and 2-7(b). With the scaling theory we can predict interconnection propagation times for a scaled design. By computing the change in line resistance and capacitance: R' = p
and

wt

p

t

a = aR,

(2.5)

C =

'w'' ew 1 , = T'

=

C/,

(2.6)

we see that interconnection propagation times determined by the RC product remain constant, since R'C' = RC. While the scaling theory correctly predicts that MOS transistors gain in speed, interconnections do not. Without altering the classical scaling scenario, interconnection delays will dominate at some point in the scaling process. The classical theory states that interconnection line lengths reduce by a. But, in practice,

the larger number of circuit elements is usually accompanied by an increase in average interconnection length relative to the minimum feature size [35,36]; that is, Ive > I/a. 2 Conceivably, some interconnections (clocks, busses, etc.) span the chip's entire length. Thus, for worst case interconnections, ,,madoes not scale with a, but remains roughly constant. 3 Thus, the maximum delay for classically scaled interconnections now grows to approximately a 2 RC. It is this worse case propagation time which is of most concern. We now investigate the above effects in more detail by examining the sample circuit in Figure 2-8(a)-a typical circuit configuration for an interconnection. It contains a driving gatemodeled as in Figure 2-8(b) with a stepped voltage source, an equivalent drive resistance, Rd, and drive capacitance, Cd-a uniformly distributed RC interconnection and a load capacitance,
C/d. We can approximate the propagation time from the driving gate to load with the Elmore time, which for this circuit is Td = Rd (Cd + Cld + CI) + RICid + 2 R CI.

(2.7)

2In [36] it is shown that in some circuits, the average interconnection length does not vary with a larger number of circuit elements, but in most cases, the average interconnection length is proportional to GI, where G is the number of gates, and n is a circuit-dependent value larger than zero. 3 This assumes constant overall chip dimensions. Actually, the maximum chip dimension has tended to increase making the situation worse.

2.4.

ANALYSIS OF SILICON MOS INTERCONNECTIONS

35

- WL-F

sl/--

W(b)

t

(b)
(a)

ta[me[c
(C)
FIGURE 2-7:

Scaling of IC interconnections.

(a) original structure, (b) classical scaling of the structure by the amount a, and (c) a more realistically scaled structure with increased height-to-width ratio.

36
, pe

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

-

'J.
V0

}

(a)
Rd RI
V0

(b)

FIGURE 2-8: Sample circuit and model for studying delay. The Elmore time is discussed in Sections 1.1.3 and 3.2. It suffices to say here that if the step response is sharp enough or symmetric enough, Td closely matches the delay time when vo(t) passes through the important, logic threshold range. Figure 2-10 shows a plot of the five additive terms of Equation (2.7) versus interconnection length, I. Values are calculated from a representative minimum-width, first-level metal line of the 1.5 /Am process shown in Figure 2-9. The first and second terms of Equation (2.7) have no
dependence on I and in fact by themselves represent the delay if no interconnection is present.

These terms are lumped together into the self and fanout delay term. Both the third term (representing the charging of the line capacitance through the drive resistor) and the fourth term of Equation (2.7) (representing the charging of the load capacitance through the line resistance) have a linear dependence on line length. The fifth term is the intrinsic delay of the RC line. This delay cannot be reduced by increasing driver strength and only marginally by increasing linewidth. For long line lengths-above 6.5 mm for this example-the intrinsic delay dominates over all other delays. However, this length is close to the maximum line length defined by the maximum chip dimension.
Next, we look at the effects of scaling on Equation (2.7). Calculating new, scaled transistor drive resistances and transistor capacitances gives:
bRt_ Vd., R'nd~ = Vds = Vd /= &/-Rd,

Cd=

A'

= Cld/a,

and likewise C = to
EA' ox

= Cd/a.

_II_ _

2.4.

ANALYSIS OF SILICON MOS INTERCONNECTIONS

37

silicon

FIGURE 2-9: Interconnection dimensions of 1.5 pm process. These dimensions are close to those reported in [37] for a representative 1.5 m nMOS technology.

11T d

100

RC

2 10 . self and fanout delay
= Rd ( Cd+Cld)

,

total delay
RC
....................

.1

.1

I

r
100 1000 10000 line length (urn) FIGURE 2-10: Delay vs. line length for 1.5 m process.

38

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

1
100

Td

11

10 .

1

.1

100

1000

10000

line length (um) FIGURE 2-11: Delay vs. line length for 0.5 pm process. Figure 2-11 illustrates the effects of scaling down the 1.5 pm process to a 0.5 pm process (a = 3). The intrinsic RC interconnection delay begins to dominate at a shorter line length (0.7 mm)-at a line length well below the maximum line length. 2.4.2 MOS Scaling in Practice

For reasons described above, conductor thickness and height are usually not shrunk as readily as the width and spacing dimensions as shown in Figure 2-7(c). One investigation [381 estimates that conductor thickness is scaled down by t' = t/V. Scaling the conductor thickness by a factor less than a-i.e., increasing the thickness-to-width ratio-decreases the line resistance, thus reducing propagation delays. Increasing the height-to-width ratio has a smaller affect on ground capacitance. In the above example, improved scaling with t' = tv~
and h' = h/v/G reduces resistance by 42% and ground capacitance of an isolated conductor by

25%. This more realistic scaling of mIos circuits has, however, enlarged another problem. A greater amount of capacitance is observed between the sidewalls of adjacent conductors. Figure 2-12 plots the ground and coupling capacitance components of an interconnection parallel to other equi-spaced interconnections on both sides. It shows that as the spacing shrinks, the coupling capacitance increases, and the ground capacitance decreases. The total capacitance also increases at smaller spacings. The two plots show the relative ground and coupling capacitances

2.5.

ANALYSIS OF VLSI TRANSMISSION LINE INTERCONNECTIONS

39

poly-poly metall-metall

separation (m) Coupling ratio (2CcI/C) separation (m) Coupling ratio (2C,/Cg) separation (pm) Coupling ratio (2CcI/C)

1.5 m 1.5 19 % 1.0 58 % 1.8 40 % 1.8 60 % 2.4 52 % 54 % 53 %

0.5 /im 0.5 33 % 0.33 79 % 0.6 65 % 0.6 77 % 0.8 72 % 43 % 55 %

metal2-metal2

separation (m) Coupling ratio (2Cc/Cg) separation (pm) Coupling ratio (2CC/C9 )

metall over poly metal2 over metall

Coupling ratio (CC/Cg,m,) Coupling ratio (CcICg,m2)

Table 2-2: Comparison of maximum coupling capacitance ratios of 1.5 tsm and 0.5pm process. for the original 1.5 m and the scaled 0.5 im process with conductor thickness scaled only by v. After accounting for scaling, the -axis covers the same separation range. This shows that considerably more coupling capacitance exists for the finer linewidth process. This is also shown in Table 2-2. On an integrated circuit, increased coupling capacitance effects two performance measures: delay time and coupling noise. Increased total delay time arises primarily from increased total capacitance. As scaling progresses as described in this section, checks will be needed for a larger number of nodes-nodes which the designer may not suspect of having potential crosstalk problems. The luxury of simulating the noise with a time-consuming simulator cannot be afforded over the hundreds of thousands of nodes on a VLSI circuit.

2.5

Analysis of VLSI Transmission Line Interconnections

This section analyzes technologies which are dominated by LC propagation on interconnections. Silicon bipolar and SOS technologies are included in this discussion, but lossless transmission is assumed. We will see that interconnection propagation time over the length of a circuit is indeed a concern. We will also see that coupling effects of VLSI transmission lines is a major concern in the design of these systems.

2.5.1

Transmission Line Propagation

Table 2-3 shows simple calculations for interconnection propagation times and circuit propagation times for each technology. Comparing the two propagation time figures shows in all

----

40 CHAPTER 2. VLSI INTERCONNECTION PROPERT--V

,

First-level metal of 1-.

,

Separation (um)

nurn

First-level

metal of 0.5 um process with increased vertical-to horizontal ratios FIGURE 2-12: Ground capacitance vs. COupng and Conductorspacing.

'-. .8 Separation (urm)

'7

.

2.5.

ANALYSIS OF VLSI TRANSMISSION LINE INTERCONNECTIONS

41

Silicon bipolar u (m/nsec)
Imax (m)

0.151
0.01

Silicon on Sapphire 0.091
0.01

GaAs 0.085
0.005

Wafer Scale Integration 0.173
0.1

Ceramic Chip Carrier 0.099
0.15

Tinterconnect (nsec)
'circuit (nsec)
U
'max

0.066
0.1

0.110
1.0

0.059
0.01 - 0.1

0.578
0.1 - 1.0

1.52
0.01 - 1.0

transmission line propagation velocity (1/VE) approximate maximum line length
propagation time over max

interconnect
7

Tcircuit

approximate circuit switching time

Table 2-3: Transmission line characteristics of sample technologies.

T = .Oum /H = 0.7um

T

T

T

K
T = 1.Oum

T

T

T

-

-f7\
a

I

SiO2 H = 300um
Si ,Ior

GaAs

FIGURE 2-13: GaAs dimensions contrasted with silicon's. cases, except for SOS, that the signal propagation time across the maximum dimension of the wiring surface is comparable to or exceeds the propagation time of the switching devices. For the ceramic chip carriers, interconnection propagation time can be quit significant when
4*

mounted with chips from a high-speed technology. 2.5.2 Transmission Line Coupling

Transmission line coupling has been the subject of much recent investigation. This is largely due to the increased interconnection density which is needed to support smaller circuitry. In GaAs and SOS technologies, the fact that substrates are semi-insulating adds to the coupling capacitance. An examination of typical GaAs interconnection dimensions (Figure 2-13) shows that the line-to-line spacing is much less than the line-to-groundplane spacing. the field Si0 2. The reverse is true for silicon circuits, since the line-to-groundplane spacing is only the thickness of

---

42

CHAPTER 2.

VLSI INTERCONNECTION PROPERTIES

Vin

Ix-o
d

_

-

x=3mm

.u

V? in

.8 .6

(volts)
.4

.2

0.0

-.2 I
%-

[0

50

100

150

200

250

300

350

time (psec.) FIGURE 2-14: Transmission line coupling waveforms. In a 1982 study [33], the coupling capacitance between similar adjacent lines on silicon, sapphire and GaAs substrates was measured. The lines were 1 pm wide, spaced by 1 pm and were only 0.1 pm thick. The amount of coupling per unit distance between two adjacent lines was found to be C . 5.6% for Silicon,
cotple
-

45%
49%

for Sapphire,
for GaAs.

Conductors with a larger thickness would have greater coupling. Figure 2-14 shows the effects of transmission line coupling on two, 3 mm long GaAs interconnections with 50% coupling. The driving ends of the lines are ideally terminated in this example to eliminate reflections. The loading ends have a small capacitance. A substantial noise spike

I

2.6.

DIscussIoN

43

is seen on the coupled line at the loading end. If the loading ends were ideally terminated, no noise would exist on the loading end, but voltage swings on the signal line would be halved. A noise spike would still exist at the driving end. The coupling effects of interconnections on GaAs substrates is further studied in [39,40,41]. Coupling effects on the IBM ceramic chip carrier has been the subject of several studies. Rubin [42] investigated the cross-talk noise in the 'presence of reference plane meshes with varying grid spacings. Gu [43] has investigated signal and coupling noise of interconnections in the presence of evenly-spaced crossing lines. The crossing lines add a large number of evenly spaced discontinuities. It is shown that for very sharp transitions ( < 50psec.) the distortion on the line of 2 cm or more is too large.

2.6

Discussion

The major conclusion to be drawn from this chapter is that interconnections will play an increasingly dominant role in affecting the performance of digital VLSI circuits. The speed of switching circuits will no longer be the limiting factor for many circuits. As linewidths decrease on Silicon MOS IC's, interconnection resistance increases. Some of this can be traded off for increased inter-nodal capacitance. Either way, interconnection problems must be analyzed. Coupling effects on semi-insulating substrate technologies, SOS and GaAs, is larger than on silicon substrate technologies. Inter-chip communication is already a major factor in limiting system performance. Signal propagation and noise degradation on chip carriers or printed circuit boards now must be analyzed much more closely.

_111

_

II

I_·_·I____

I

I_

________

_I _

_

I

44

a

_

I

3

The Moment Representation
The moment representation is used to describe both waveforms and circuits. In this chapter, we will look at the relationship between waveforms and the moment representation. In following chapters we look at the relationships between circuits and the moment representation. The first section of this chapter describes the usage of waveforms in this thesis. The next section defines the moment representation. We will see that the moment representation forms a subspace of the Laplace transform. For purposes of simulation, the moment representation is preferred to the Laplace transform because of its simpler computer implementation. The moment representation also forms a superset of the earlier Elmore time representation and closely relates to the second order representation used by Horowitz in [18]. Thus, it characterizes responses more accurately than these earlier representations. There exists a simple many-to-one projection of the Laplace transform to the moment representation. Thus, most moment representation properties are derived from known Laplace transform properties. These properties are covered in this chapter. As illustrated in Figure 3-1, there is a closed form, one-to-one mapping between the time domain and the Laplace transform and a projection from the Laplace transform to the n t h order moment representation domain. Hence, it follows that there is an exact projection from the time domain to the moment representation domain. As we will see, this is through moment integrals. There is not, however, a direct mapping from the moment representation domain to the time domain. The last chapter showed that the simulation algorithms need such a translation. This chapter concludes with a presentation of fast heuristic algorithms that are possible by assuming a shape for the time domain waveform.

3.1

Node Voltage Transitions and Waveforms

The node voltage of a logic circuit is composed of a series of transitions. For instance, the representative logic circuit node voltage, (t), in Figure 3-2 is composed of five separate transitions, vl(t) through v 5(t). (A hatted variable, as in t, indicates a global quantity, whereas 45 ___ll___i_____I__1 _·__ ·1_·111__11__1_1_11l__l

46

CHAPTER 3.

THE MOMENT REPRESENTATION

series

FIGURE

3-1: Interfaces between representation domains.

an unhatted variable indicates the quantity for an isolated transition.) Each of the transitions is caused by a change of logic state somewhere in the circuit. Transitions are classified and tagged at their creation as one of two types: signal transition: Two conditions must exist for the simulator to declare a signal transition. First, the transition must be the result of a change in input state on the circuitry that drives the node. Second, the transition must have sufficient d.c. change to cause a logic shift. noise transition: A noise transition is defined as anything else. A noise transition may arrise from coupling effects or from charge sharing. It is often characterized by a zero d.c. change, but in some cases may have a sufficiently large d.c. change to cause a logic change. The motivation for tagging transitions into these types involves the actions taken for each type. Noise transitions cause warnings and indicate a potential circuit error. Signal transitions control the flow of the logical simulation, as their affects are propagated. The first two transitions in Figure 3-2 are normal logic state transitions. The third is a noise transition caused perhaps by a logic transition on a neighboring node. The last two transitions are, again, normal logic state transitions of this node; but the transitions are closely spaced in time such that they overlap. The net result of the last two transitions is a spike resembling the noise waveform of v 3 (t). The different modeling arrises from different causes for the waveforms. As seen later in this chapter, transitions are also classified as d.c.-shifted or non-d.c.-shifted depending on whether or not the waveform initial and final voltages are equal. The moment representation is a means of expressing the waveform for a single transition. Each moment representation waveform has its own time and voltage scale (denoted without

3.1.

NODE VOLTAGE TRANSITIONS AND WAVEFORMS

47

Iq

v(t)
r i-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~si~~~~~~~~~~b

I0

- I

I

I

I

I

I

0 0 V (t) --5
=U.

10

20

30

40

50

t

. _ rs~~~~~~~~~~~~~~~~~~~~~~~

t

5 V2(t)
n

-

t
: .

~L_-

5

v3 ()
t =O-

Lp~

t>~~~~~o.~

-

~~~

V4 (t)
-

5

I
V (t) -I
t U

C

A'

FIGURE 3-2: Individual transitions of node voltage,

(t).

48

CHAPTER 3.

THE MOMENT REPRESENTATION

hats) as shown in Figure 3-2, and described in the next two sections. Using the moment representation algorithms presented in this thesis, each transition waveform is computed individually. Then, the total waveform is constructed by summing individual transition waveforms. For the particular example in Figure 3-2, five moment representation waveforms are needed to construct the total waveform. In general, a node voltage in the moment representation simulator is a d.c. voltage interspersed by a chronological series of transitions. After each transition, the d.c. voltage is updated to reflect the d.c. voltage change of the transition. Most discussion and examples in this thesis focus around single transitions. While it is often assumed that only one transition occurs between t = 0 and t = oo, all discussions can be generalized to include many transitions where the individual transitions are combined.

3.2

Representation Definition

We now assume that (i) has only one transition for all t > 0. This assumption holds for the remainder of this chapter so that we are not troubled by upper time bounds in the following analysis. The moment representation of this waveform is defined through the Laplace transform of the waveform's derivative. The Laplace transform pair of its derivative, V'(t), is v'(t) V(s)
e~ t I(t) di

(3.1)

Any initial delay between the global time origin, t = 0, and the start of the transition is removed from the Laplace transform integral by defining a new time origin, t = 0, where the transition begins, as shown in each transition of Figure 3-2. The variable to denotes the delay from the global origin to the transform origin, or = t + to. With the new time origin, Equation (3.1) becomes b'(t + to) , V(s) = e


(j

et

v'(t) dt)

.

(3.2)

In general, it is best to move the origin, t = 0, as close as possible to the start of the transition, in order to keep the best approximation in the next step. Expanding et of Equation (3.2) into a Maclaurin series,

V(s) = s t

a

ao s

00

t'tii)

d(t)d-

2
2!

'

3 a -+ 3! s 'd t

t +... d3!
(3.3)

and finally defining the integral quantities as M 0 , M 1 , M 2, etc., gives

V(s)e = e

to

M - s h +

M2.

M3f+u

(3.4)

The Mo, M, ... terms are the moments of the v'(t) function. It is also useful to talk about the

normalized moments, ft = M/Mo, M2 = A,12/Mo, etc. The normalized moments are similar

3.2.

REPRESENTATION DEFINITION

49

to the moments of a probability density function-the first moment relates to the mean of a function, the second moment relates to the mean and variance of a function, and so forth. 1 also equals the Elmore time constant presented in Section 1.1.3 and discussed in the RC tree literature [13,14,44].
For any initial delay, to, we find the n th order projection of any Laplace transform, V(s), into the moment representation domain by taking the Maclaurin series expansion (Taylor's series expansion around 0) of V(s) with respect to s and truncating the terms with polynomial order greater than n. That is, V(s) _==- to e
fo

- Ms + M

2

.-..

+ Mn n)

(3.5)

The n th order moment representationis defined as the set of numbers, {to, Mo, Ml,... Mn}

I and n is the approximation order.
As shown later, a greater approximation order results in a more accurate waveform approximation, but requires more computation when performing operations on the waveform. An approximation order of three is typical for the simulation examples in this thesis, and gives close approximations to true circuit waveforms. The polynomial portion of Equation (3.5) by itself is referred to as the moment polynomial. From this point onward, a function of s with a tilde, as in V/(s), indicates a moment representation or moment polynomial, differentiating it from the Laplace transform, V(s). A subscript, as in V(s),, indicates an n th order moment representation.

3.2.1

Expressed in terms of v(t)

It is useful to express the waveform representation in terms of the original waveform and not its derivative. To guarantee that moments of the original function are defined, we shift the function such that the final value asymptotically approaches zero, as in the transitions of Figure 3-2. The shifted function is denoted v(t), where

v(t) = (t)d d

(o).

This does not change the analysis of the last section, since

v(t) =

v(t) = u'(t).
All waveforms in this thesis meet this

Furthermore, we must ensure that the moment integrals are finite. For an order n approximation this requires requirement.1
' Reasons for this statement being true may not be clear at this point, but, in Section 3.6, all assumed waveform shapes obey this requirement, and circuit waveforms are forced to this requirement by restriction 3 on Page 70.

fo7

t" v(t)dt to be finite.

------ --------------

------------·--

-

--- ·--

-----------

·-------

· ·---

------· ' ·-

---

--

50

CHAPTER 3.

THE MOMENT REPRESENTATION

term to

i'(t) waveform delay

-v(t) waveform delay

Mo Ml

fv i '(t) dt
fo t '(t) dt
first moment

-v(0) = (oo)d.c. transition

(O)

fo°[-v(t) dt
area under -v(t) waveform Elmore time constant

M2

fo0 t 2 '(t) dt second moment fO t3 (t) dt

2 fo t [-v(t)] dt
twice first moment 3 fO t2 [-v(t)]dt

M3

third moment

three times second moment

Table 3-1: Terms of moment representation for one transition. By using the above restriction, it is easy to convert Equation (3.3) to a form with v(t). Integrating by parts, we know that

tn d()dt

d (t)

= [tn v(t)]

-

n j

tn-

1

v(t) dt.

The tnv(t) term vanishes at both t = 0 and t = oo (using the restriction). Thus, Equation (3.3) becomes: (S = ' t a ~ - (O)+ t)dt a
t (t) dt

V

P

V(t) dt - ' "

I

(3.6)

Equating the s °, s,

s,2 ... terms of Equations (3.4), (3.3) and (3.6) gives

Mo =

'(t)dt = -v(O),

- Ml =

-jtv'(t)

dt

jv(t)

dt,

M2 = q

v(t) dt

t V(t)dt,

and so forth. The terms of the waveform representation are summarized in Table 3-1 and Figure 3-3. Here the moments are easier to see with the negative of the waveform, -v(t) = (oo) (t).

3.3.

PROPERTIES OF THE MOMENT REPRESENTATION

51

- v(t)

vl(t)
A< #
a Lar 2 =M2-Ml 2

!

_ .

t FIGURE 3-3: Graphical meaning of some moment representation terms.

t

3.2.2

Expressed in terms of the V(s) rational function

It is also useful to express the moments in terms of the constants of the more common rational function form for the Laplace transform,
= ) ao + al s + a2 s 2 + a3s 3 + ...

1 + bl s + b2 s 2 + b3

3

+ ...

(3.7)

The moments are easily found by taking terms from the Maclaurin series projection of Equation (3.7) into the moment representation domain: Mo = M1 = [V(s)]S,= = ao _ [d V(s)]

M2 =
M3

L

= aobl - al

d V(S)=0 d2V[ds2 = 2(aobl - aob2 - a l bl + a 2 ) ds2 1 [d 3 V(s) 3

ds

6[ao(b 3 - 2bib 2 + b) + al(b2 - b2 ) + a 2 bl - a3] ,=0

and so forth.

3.3

Properties of the Moment Representation

Since the waveform representation is a projection from the Laplace transform, the well known Laplace transform properties can be used to derive a list of moment representation

- -

-- · - - ----·------

--- ·-------

-------------------- ----- --------------

··-

52

CHAPTER 3.

THE MOMENT REPRESENTATION

properties. The Laplace transform properties are derived in most any circuit theory textbook, such as [45]. 3.3.1 Shifting in Time

Shifting a waveform in time results in a multiplication of the Laplace transform by a constant:
v(tr)
+

e

V(s).

This fact was already used in going from Equation (3.1) to (3.2). From Equation (3.3) we see that it is easy to time shift a waveform representation by changing to:
to,shifted = to + T.

Sometimes it becomes necessary to hold to constant and change the M terms. In these cases, the moment polynomial of Equation (3.3) is multiplied by the Maclaurin Series expansion of e - s = 1 - Sr + + .2. . and exact terms of VAhited are
MOV,hifted Ml,V,hifted = =

M o,
Mot + M1 (3.8)

M2,V,hifted
M3,Vshifted

=
=

Mor 2 + 2M 1 + M 2 ,
Mo
3

+ 3M 1r2 + 3M 2 T + M3.

3.3.2

The Linearity Property

Laplace transforms exhibit the linearity property:
a v(t) + b v2(t)' a V(s) + b V2(s).

This property easily projects into the waveform representation, provided the two to terms are equal. If not, they must be equated with the second time shifting method described in the previous section, using Equation (3.9). (Usually, the waveform with greater to is shifted backward, so the resulting waveform's starting point is the earlier of the two original starting points.)
With this provision, the new waveform terms of
to,Vtott = min(to,vl, to,v 2 ) shifted by to,v...
Vtotal(s)n

= a 1(s) + b V2 (s), are:

to,v,,, - to,vma,)

(The waveform with the largest to is time
itotal(O) Mo,vtot,, M,vtotal M2,Vtotal M3,Vto,,t = = =

a

1 (0)

+ b

2 (0)

a Mo,v + b Mo,v 2 aMl,v, +b Mi,v2

(3.9)

= aM 2 ,v, + bM 2 ,v2 = a M3 ,v, + b M3 ,V

3.3.

PROPERTIES OF THE MOMENT REPRESENTATION

.

53

This operation should be used with some caution. As we will see later, inverse transforms assume a single, smooth transition, so one cannot indiscriminately combine different waveforms with widely separated starting times. 3.3.3 Derivatives of Waveforms

Using the Laplace transform pair for the time derivative of a function,
d v'(t)

,

V(s) -

(O) = -(O)

+ Mos - Ml 2 +

2! 3

(310)

we see that the following substitutions can be made:
iMO,Vderiv = -v(0)

M,Vderit
M2,Vderiv MV3,Vdcriv

=
= =

-Mo
-2M1 -3M
2

(3.11)

This is in agreement with Table 3-1 of Section 3.2.1.

3.3.4

Linear Network Properties

The great advantage of using the Laplace transform in linear circuit analysis is that circuit elements and networks can be represented by Laplace transforms. Furthermore, circuit calculations with Laplace transforms are very simple-any independent linear circuit described by its impulse response transform H(s) responds to an input waveform described by transform V(s) with an output waveform described by transform Y(s) = V(s) H(s). This fact projects into the moment representation domain. The response of a linear network is easily found in terms of the moment representation parameters with
Y(s)n = V(s)n H(s)n = es(t, v+tOH) Mo, v - Mlv s + M,
Sn

Mo,H - M,H + M2,H2!

+ Mn

(3.12)

The next chapter describes the link between circuits and the moment representation in much detail.

3.3.5

Non-Linear Network Properties

This is where the helpful list of Laplace transform properties ends. Analysis of non-linear networks with Laplace transforms is cumbersome, to say the least. However, in Chapter 6 a macromodeling method is presented for converting a non-linear digital circuit into a linear circuit equivalent. After this conversion, the moment representation again becomes beneficial.

1-

a -

_

__

I__·

I

^_I_

I

I

1^1

__

_UI____I

II_1II__II1_IIL___I-L·PllslY·-LIPII

54

CHAPTER 3.

THE MOMENT REPRESENTATION

3.4

Representations of Simple Waveform Functions

Table 3-2 shows some well-known Laplace transform pairs for simple waveform functions, as well as the unshifted waveform representation parameters. These transform pairs, particularly the exponentials, will be used in the next sections.

3.5

Time Domain to Moment Representation Conversion

A necessary step of the simulator is converting between the time domain representation, b(t), and the moment representation, V(s). This section presents the time domain to moment representation conversion method, and the next section presents the moment representation to waveform conversion methods. The ability to convert a time domain waveform to moment representation is needed (1) as an interface routine to the user's input should an input waveform be specified by an arbitrarily shaped waveform, and (2) in the macromodel parameter extract routines, where macromodel parameters are extracted from SPICE waveforms. Inner loops of the simulator program do not rely on this algorithm, so efficiency of this conversion is not crucial. This conversion method is readily seen in the last column of Table 3-1. The to (defined where the waveform first deviates by more than a few percent from the initial voltage), (O) and Mo representation parameters are easily picked off of the waveform. Then, the waveform is shifted from (t) to v(t), and the integrals for M 1 , M 2 , ... M, are evaluated numerically.

3.6

Moment Representation to Time Domain Conversion

Conversion from the moment representation to time domain representation is needed substantially throughout the simulation program as demonstrated in Section 1.2. Unfortunately, this conversion is more arduous, since there is no unique direct technique to undo the projections shown in Figure 3-1. The overall accuracy and computation time of the simulator are greatly dependent on the accuracy and efficiency of this conversion method.

3.6.1

Basic principles

While general inverse Laplace transform methods exist [46], they are not appropriate for the moment representation. Strictly speaking, the inverse Laplace transform of the moment polynomial would yield impulses, doublet (double impulses), etc. Too much information is lost in the Maclaurin series approximation to use the general inverse transform methods. Specifically, the general inverse transform methods need both Pa(s) and Qm(s) of a Laplace transform, QPn-. The Maclaurin Series merges P and Q into a single polynomial.

3.6.

MOMENT REPRESENTATION TO TIME DOMAIN CONVERSION

55

-v(t)
I -v(t)

v'(t)

V(s)

Mo

M 1

M2

M

113

t

1 - u(t)
-v(t)

6(t)

1

1

0

0

0

t

[1·[u(t)I

t]
u(t)]

r[U(t)-

u(t

-

7)]

e

- s

r

-

1

1

r

1 2 2T2

1 3

-v(t)

t
_ b
-

?-7

t

1 Te

1 +,rs

1

7

2r

2

3!r 3

t
, >~~~~~1

tn e-

n! r+l

s

0

n!

n+

2(n+1)!

n +2

3(n+2)!T

+3

[-v(t)

t
-

MV

w

--

e-

t

cos/3t
.

e-at

1
. .

-7-7

O

2(

22 ,2

3!

3-3c3a2 (a +p)

·(a cos pt + P sin /3t)

Table 3-2: Laplace transforms and waveform representation terms for simple functions.

·----------

----------------------------~ ··· ~~~~~~~~~~~~-----·~~~~~~~~~~~~~-·--------

---------------

--- ~~~~~~~~~~~~~~~~~~~

56

CHAPTER 3.

THE MOMENT REPRESENTATION

Instead, a technique analogous to the method of undetermined coefficients is adopted. This technique (1) assumes a waveform shape, g(t), which may be linear, exponentially decaying, underdamped decaying, etc., and (2) computes various coefficients and parameters of g(t) such that the first n moments of g(t) equal the first n moments of V(s)n:
Mi.g = Ml,v,

'12,

= M2,v,

Mlng

=Mn,v

g(t) is said to be an assumed waveform shape of order n. A greater approximation order generally yields a better approximation to the true waveform, but generally requires more computation. Ideally, the number of variable parameters in g(t) equals n, the number of constraints on the waveform. In some cases, this is not true, and heuristic methods must approximate some parameters. The success of this method depends on how well the assumed waveform shape captures the form of all real waveform shapes that it models. It is found, for instance, that most logic transitions are modeled quite well by exponential functions. Commonly used assumed waveform shapes are listed in Table 3-3. Most have a fixed orderonly the last has an arbitrary order. Restrictions for some waveforms are noted in the fourth column. The restrictions apply to the d.c. change. (If the waveform's final value returns to the initial value, then Mo = 0.) Conversion with some assumed waveform shapes-those requiring special algorithms-are described in the next sections of this chapter. The last section discusses how a good choice of g(t) can be made.

3.6.2

Polynomial Exponential

The polynomial exponential assumed waveform shape is the most general of the entries on Table 3-3. Is has an arbitrary approximation order, and as n increases, the approximation becomes more exact. Because of its general nature and its ease in computation, this method will be discussed in more detail. This method does not, in general, give the most accurate match to true waveforms, so it is not always the prefered method. The polynomial exponential waveform approximation, described by g()= ) o~kl 2-+... +k e-,7 (3.13)

assumes a dominant real pole at -1/r*. If the true waveform being modeled has any perturbations away from a single pole (exponential) waveform, these are reflected in the polynomial terms with n > 0.

_

3.6.

MOMENT REPRESENTATION TO TIME DOMAIN CONVERSION

57

waveform shape
linear

g(t) A[1][u(t) - u(t)]

method d.c. approz. restriction order - A =Mo 1 Mo O T = 2 M1 / Mo

single exponential

Ae-

Mo $O

1

A =Mo r = M / Mo

n = round (
erlang e AtA n - 1-e-;

M,

--

)

Mo = O

2+ A=
M

A= Mo
underdamped
signal
2M.-M2

Ae-r cos 3t

Mo $0

2
2
2

exponential

-M 2

12 M2

227M2-24M M3

underdamped noise exponential

T'-

A e-; sin O3t

Mo =

3

Ml27 M -24 Ml M3 2 M M3 -3 M 2 3M
2

-2 MIM3

double exponential

(kl + k 2 t)e- ra +(k 3 + k 4 t)e

3
'b

see Section 3.6.3

polynomial exponential

[ko + ki I + k 2 ( ) 2 + .·. + kn(v)n] e-

n
. .

see Section 3.6.2

I~~~~~~~~~~~~~~~~~~~~~~~~~~

Table 3-3: Common Assumed Waveform Shapes

------.--1111111-.1----11

_111 _11_11·11_11_----_11---·11

--

58 Estimating r

CHAPTER 3.

THE MOMENT REPRESENTATION

A value for r. must be estimated from the moment representation parameters, M 0 , M 1 , ... , M,. For finding ,r we assume the true waveform is described by a series of exponentials,
P
t t t + + Ce rn.

v(S) = (

-

)(S -2)

... (

-

~)

v(t) =

c.e- r

+

e

r

This assumption differs from the assumed waveform shape; we configure this part of the problem differently, since overall, there is one more parameter than the number of moment constraints. The i th order moment of the above waveform is 1
Mi =

i!(csr

+ C2 r2 +

...

+ Cnr).

(3.14)

If r. is the dominant time constant, then
> 7, ,*n 7.

particularly for large i, 2 and therefore Thus,fororder momen anapproximation r.epresentation is a nh goodfrom Thus, a good approximation for r. from an nik order moment representation is
1
1

Mn

Mn

(3.15)

n Mn-1

In reality, our estimate of r is just a ratio of moments, but it serves as a very good time constant approximation for the true waveform's asymptotic decay. Computing the polynomial Once an estimate of r. is computed, the polynomial terms of Equation (3.13) are computed from a linear combination of a set of basis functions, {fo(t), fi(t), ... , f(t)}, i.e.,
g(t) = ao fo(t) + al fi(t) +
...

+ a, fN(t).

Figure 3-4 shows one possible set of basis functions. The key to efficient computation with this method is for basis function fi(t) to have all moments of order less than i be equal to zero. Then, the a coefficients can be computed in increasing order; each is computed without affecting the lower-ordered coefficients.
Suppose fV(s) = MO- M s + A S2
... + M

sn is the initial, moment representation

approximation. The conversion begins by setting ao = Mo.
The non-dominant r's may be complex. In this case, r. must be larger than the inverse of the complex pole's magnitude.
2

3.6.

MOMENT REPRESENTATION TO TIME DOMAIN CONVERSION

59

F(s)

i
0
1

fi(t)
ett e r
T

MM M
1 0
7

M 2 /2!o M 3 /3!
72 r-3

M 4 /4!
r4

T

2T 2 2r 2

3T 3 3r 3

4T

444

2

[(

T

-

2T] er r0 6( )2 + 6 ] e- r 0
0

0

2J2

6r 3

12T4

3
4

[( T

3 -

0
0

0
0

6r 3
0

24r 4
24r 4

[(t)4 - 12( )3 + 36(t)2 - 24t] e-

.5

.4

.7/2

.3
.2

........ -fY /2 -

7f/6

4/24

.1 0.0
10 -.1
tl

FIGURE 3-4: Basis functions for the polynomial exponential waveform approximation. The i t' order basis function is fi(t) = know that if f(0) = 0 then fi(t) -, the first i moments are zero.
( e-

). From (3.10) we

si F(s), thus guaranteeing that

11_1_111_- 1_1^. --111_-1·1-_111 1111·_ 1-

_

_ __

L

60

CHAPTER 3.

THE MOMENT REPRESENTATION

Then the transform of.the first basis function, Fo(s), is subtracted, giving the transform of the unmatched waveform V (s) = V(s) - aoFo(s)
=

0- (M

- aoMI,Fo)s' + (M2 - aoM2

)

-

+ (Mn - aoMn,Fo)

Next the s' term of V,(s) is zeroed by subtracting
V(8)a F(s)V2,

where
Mi,vi
M1,F

The process is continued where, in general,
i th term of Vi(s) it h term of Fi(s)

and
Vi+(s) = Vi(s) - ai Fi(s).

After n repetitions, V,(s) = 0, and g(t) is found by g(t) =
=

aofo(t)+ al fi(t)+ a2f 2 (t)+ ... + a, fn(t)
ao[ +al 1 rt le ]et

+a2[
+a3 [

-2 t
6t

+
-

1
6t

t2
2

]e+
t
3

1e-

[ko + kit + k 2 t 2 +

+ ktn] e'

r

Figure 3-5 shows the effects of increasing the approximation orders of polynomial exponential approximations.

3.6.3

Double Exponential

The double exponential assumed waveform shape,

(kl + k 2 t)e-

+ (k 3 + k 4 t)e-

rb

(3.16)

is harder to compute, but in many cases gives better results than the polynomial exponential shape with the same approximation order. The fit of the double exponential is better, in particular, if the true waveform exhibits a strong two-time-constant behavior as is seen in some RC circuits [26]. The double exponential waveform has not d.c. change restriction, since it may

3.6.

MOMENT REPRESENTATION TO TIME DOMAIN CONVERSION

61

1.0

(volts)
.8
-

:.,.,
.6

t~-actual 1Ist order polynomial ............ 2nd order polynomial . -.- . .- 3rd order polynomial . -------- 4th order polynomial

'-_:.-,

.4
'

.2

,"'
'''

0.0 0
5

10

15

20

25

30

time (nsec.) time (psec.)
,
.

0

10

20

30

40

50

60

70

80

90

-50

-100 (mV)
-150

-200

-250

----------

............ 2 order polynomial 3rd order polynomial 4-- order polynomial th

FIGURE 3-5: Polynomial exponential waveform approximations.

62

CHAPTER 3.

THE MOMENT REPRESENTATION

or may not be monotonic. For these reasons, it is the preferred waveform shape for most pure RC circuits. This assumed waveform shape has two more parameters (kl, k 2, k 3, k 4, ra and rb) than constraints (Mo, M1, M 2 , M 3 ), so two parameters, ra and Tb, are estimated and the rest (kl, ... , k 4 ) are fitted exactly to the moment constraints, based on the estimates for ra and rb. Estimating the time-constants The method for estimating the waveform's time constants is similar to the one for estimating the polynomial exponential time constant (Section 3.6.2) where we assume the waveform is described by any series of exponentials as in Equation (3.14). But, now we need two dominant time-constants, ra and rb. Neglecting all but these two time constants, Equation (3.14) becomes
M ; (caTr' + cb T) (3.17)

The second and third order moments are used to approximate r, the dominant pole:
M3/3! - cb M2I2! - cb 7b2' M 3 /3! T3

(3.18)

b
Tb:

(3.19)

and the zeroth and first order moments are used to approximate M -Ca Ta,
Mo- Ca
cb = Tb

(3.20)

.

(3.21)

The calculation of each time constant requires a guess for the other, so an iterative process is
used, where the above sequence of equations, (3.18) through (3.21), is followed with cb = rb = 0,

initially. This iterative process attempts to find a solution to Equation (3.17) for the first four moments.
The values for ra and rb do not need to be exact! So, while one iteration suffices, a few iterations are better, and more than five only marginally improve results. Figure 3-6 shows these effects. Since the hard constraints are placed in the next step (computing the k's), the pole locations can vary by as much as 20% without affecting the resultant waveform substantially. Computing the k's Now we go back to assuming the double exponential waveform shape of Equation (3.16). The first four moments of the are:

Mo =
M1 = =

k1
kiTa k 1 Ta

+
+ + +
2T

k3
k3Tb + k 4 b2

+ + +

m

k 2 2a3
k 2 37,4

= k1

k 3 Tb2 + + k3 T

k 4 2Trb
k 4 3T4

3.6.

MOMENT REPRESENTATION TO TIME DOMAIN CONVERSION

63

1.0

Tau b .297 .357 .391 .430 .472 .532

.8 (volts)

.6

.4

.2

0.0

time (ns;ec.) This example demonstrates the iteration affects in finding time constants. The affects are more observable when the fit is harder to achieve, as in this example of fitting exponentials to a straight line. For real circuit-like waveforms, the solution converges very rapidly. Note, also that the waveform shape is rather insensitive to precise pole locations.

rnm

in (

oC &t

\

0

-50

-100

-150

-200

-250
FIGURE 3-6: Effects of iterating to find double exponential poles.

64

CHAPTER 3. THE MOMENT REPRESENTATION

These form a set of linear equations, which is solved for kl, k 2, k 3 and k 4. 3.6.4 Choice of g(t)

The choice of g(t) for any given waveform depends on these factors:

* approximation order. If the user wants quick but inexact results, a g(t) with small n is
appropriate, whereas for accurate results, a larger n is appropriate. This factor must be decided by the user. An approximation order must be selected for the simulation. All subsequent moment polynomial calculations are made to that order. Different approximation orders can be given to particular circuits if differing degrees of accuracy are desired. Example circuits in this thesis all have approximation orders of three.

* transition type. As shown in Table 3-3, some assumed waveform shapes are applicable only
to transitions with a non-zero d.c. change and others are applicable only to waveforms with the same initial and final value. Which waveform shape to apply is easily determined by examination of the Mo moment representation term. * circuit type. An intelligent choice of g(t) based on the circuit type yields better results. For instance, a CMOS circuit with only RC interconnection will have no ringing, and its waveforms can be best approximated by real exponential function. A circuit expected to have ringing may be best approximated by complex exponential functions. A general procedure has been developed for selecting a g(t) based on the first two factors. It is also based on observations of how well each of the assumed waveform shapes in Table 3-3 matches to real waveforms in MOS logic and interconnection circuits. Figure 3-7 illustrates the procedure for both transition types. The value for order on the left indicates the user-selected approximation order. Initially, the procedure assumes a damped waveform. The chart gives the preferred choice for g(t)-a third order preferred g(t) for a transition with a d.c. shift is the double exponential, for instance. In some cases the initial g(t) choice fails to give a satisfactory approximation, because the time-constant waveform parameter, r, is negative. This condition indicates an underdamped waveform and requires an alternative assumed waveform shape. The arrows in Figure 3-7 show the path of alternatives to take in these conditions. The paths reflect these observations: * When an error condition exists for a transition with a d.c. shift, little is gained by trying lower ordered, damped waveforms, and a direct jump to the underdamped waveform is prudent. * An error condition for a non-d.c.-shifted transition is often handled by either an underdamped noise exponential or an erlang.

3.6.

MOMENT REPRESENTATION TO TIME DOMAIN CONVERSION

65

order >3

damped polynomial exnonential
- -.

underdamped

double exponential polynomial exponential

2
1

exponential single

polynomial

polynomial underdamped
> signal exponential

exponential
error With d.c. shift (Mo 0) error

order
>3

damped
polynomial exnnential double exponential

underdamped

IL
polynomT .underdamped polynomial exponential --exponential

noise

I
erlang <3 error
Without d.c. shift (Mo = 0)
FIGURE 3-7:

4
erlang error

Procedure for selecting assumed waveform shape.

66

CHAPTER

3. THE MOMENT REPRESENTATION

When the path of preferred g(t)'s ends in an error condition, it indicates that insufficient information is present in the moment parameters to reconstruct the waveform with the list given in Table 3-3. In general, this can be corrected by moving to a higher approximation order. Note for instance that a non-d.c.-shifted waveform always results in an error with an approximation order less than three. The error condition was never reached while correctly using the experimental simulator on real circuit waveforms-it was reached only while contriving waveform parameters which are known to be troublesome.

Example 3.1 Different waveform approximationsfor a sample logic transition waveform.
5.0

" -'O'k
I

4.0 .

3.0 .

true waveform ....... (1) line -.... single exponential (1) - - - - polynomial exponential (2) ......... double exponential (3)

2.0 .

,.L
1.0 .

0.0
I
0 5

.

I
10

I
15

I
20

time

(nsec)

3.7

Discussion

In this chapter we have seen that the moment representation has a link to both the time domain and the frequency domain Laplace transform. The moment representation is actually

3.7. DscUSSION

67

a projection from the Laplace transform domain. This allows us to easily translate a number of Laplace transform properties to useful moment representation properties.
The link between the time domain and the moment representation domain is through moment integrals. The time domain to moment representation conversion domain is exact. The moment representation to time domain conversion is more relevant to the simulator operation and is done by heuristic approximations. A waveform shape is assumed, and then waveform parameters are computed such that its moments match the moment representation values.

68

CHAPTER 3.

THE MOMENT REPRESENTATION

4

General Linear Network Solutions for the Moment Representation
In this chapter, we examine the first of two techniques for solving linear networks in the moment representation domain. It is capable of finding the moment representation solution to almost any linear, reciprocal circuit containing R's, L's and C's, but is particularly useful in solving (1) circuits with coupled or uncoupled RC interconnections, (2) circuits with MOS transistor macromodels (described in Chapter 6), and (3) any RLC circuit with damped responses. The second linear network technique-discussed in Chapter 5-applies to coupled or uncoupled LC transmission line circuit. While the technique of this chapter is possible for transmission line circuits, the second technique offers a better solution. The technique presented in this chapter is based on a new, Moment Polynomial Nodal Analysis (MPNA) method for computing the voltage response time moments of a linear circuit. The moment polynomial refers to just the time-moment terms, M 0 , M 1 , ... , of the moment representation. In fact, this chapter deals only with these terms, and assumes a constant to and v(0) between input and output transitions. In a more limited sense, the problem addressed in this chapter has been the subject of much recent research. Penfield [47], Wyatt [15] and Lin and Mead [16] have shown methods for computing the normalized first moment (Elmore delay) only of RC trees, RC meshes and RC networks, respectively.' Horowitz [18] has developed a second order method which computes the first and second moments of RC trees. The trees in these cases could also contain switching elements, thus being able to model charge sharing circuits [48]. The method presented in this chapter is much more general. It is capable of finding the moment polynomial of the voltage on any node of any circuit containing linear resistors, capacitors, inductors (including coupled inductors) and independent sources, provided the circuit
'Penfield and Wyatt also compute bounds on the waveform, which is not done here.

69

70

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

satisfies the following minimal set of constraints: 1. The circuit forms a solvable, connected network. By solvable we mean that sources do not impose an impossible constraint on the circuitas two, series current sources with different values do. By connected we mean that no two nodes are completely isolated from each other. There is always a path of circuit elements between any two nodes. 2. Independent voltage sources form part of a Thevenin equivalent (a voltage source in series with a R, L, or C circuit element). 3. The step response node voltages have no impulses, and settle asymptotically to a final value. This restriction precludes only some pathological circuits such as a switched current source connected in series with an inductor or a d.c. current source connected in series with a capacitor. All circuits studied in previous RC modeling methods are a subset of allowable circuits for the MPNA method. In addition, the MPNA method allows sources to have any waveform shape that is representable by a moment representation. This is untrue of some other RC circuit methods with moment orders larger than one. The MPNA method presented in this chapter computes the moment polynomial to any arbitrarily large order, p, without algorithmic change. Thus, if p = 0, then only the d.c. responses are computed, if p = 1, the d.c. responses and Elmore delays are computed, if p = 2, the d.c. responses, Elmore delays and second moment waveform information are computed, etc. The previous chapter demonstrated that as p increases, the true waveform can be reconstructed with greater accuracy. The MPNA method solves a linear network with nodal analysis in the moment representation domain. From Chapter 3 we know that the moment representation domain is a subspace of the Laplace transform domain, but where a moment representation is a truncated Maclaurin series expansion of the Laplace transform. Nodal analysis of the circuit yields a matrix equation, which is then solved using gaussian elimination or LU decomposition. The matrix equations are set up and solved in the same fashion as in a standard, direct method circuit simulator. The difference, however, between standard simulations and MPNA is that the MPNA matrix elements are polynomials in s, or moment polynomials. One note shall be made here on the use of the term polynomial. In the last chapter and in general usage, "polynomials" do not have negative ordered terms, but in this chapter negative ordered terms are allowed for moment representation admittance functions. Negative ordered polynomial terms are still not permitted for waveform representations, which in short, translates to circuit restriction 3 above.

4.1.

FORMULATING THE MOMENT POLYNOMIAL MATRIX EQUATIONS

71

I(s) = Y(s) V(s)
Vks)

Y (S

FIGURE 4-1: Thevenin and Norton equivalent circuits.

In comparing and contrasting MPNA methods with direct simulation methods, we make three observations: * The similarity in formulating circuit equations accounts for the increased circuit flexibility
of MPNA methods over previous RC circuit methods.

* Circuit restriction 2 on Page 70 is necessary since modified nodal analysis-common in standard circuit simulators-is not practical with the moment representation method. * The computational savings with MPNA arises from the fact that only one matrix equation solution is necessary per input signal transition, whereas many are needed for standard circuit simulators-one at each time step. The next two sections describe how MPNA matrix equations are set up and solved.

4.1

Formulating the Moment Polynomial Matrix Equations

The first step in formulating the nodal analysis equations is to convert all voltage sources from their Thevenin equivalent form to their Norton equivalent form (see Figure 4-1). This leaves current sources as the only source elements in the circuit. Before writing the equations, one node is chosen as the datum (or ground) node. All node voltages are defined relative to the voltage on the datum node. Next, the Kirchoff's current law equations in the Laplace transform domain are written for each circuit node. For a circuit with n + 1 nodes, n equations are written. (The datum node is ignored.) In matrix form, Y(s) v(s)= i(s) (4.1)

where Y(s) is the n x n Laplace transform admittance matrix, v(s) is the n x 1 node voltage matrix, and i(s) is the n x 1 source current matrix. Element v(s) of v(s) is the Laplace transform of the node voltage at node m. Element i,(s) of i(s) is the Laplace transform of the net source current flowing into node m. Projecting Equation (4.1) into the moment representation domain, each of these matrices becomes a polynomial matri--a matrix with polynomial elements. Polynomial matrices can

____

72

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

circuit element

matrix template

resistor g
q?

r

g

***

-g

O ,(s) = O

r

q

-g

...

g

capacitor
r

Cs

...

-Cs

Cs v 0

r

-

V

0

+

q

-Cs

-..

Cs

-Cs

vo

inductor L
q
io

r

-ts
.

....

io

ri
q

L-a
0 i(s)
-i(s)

current source

i(s) q o r

r

0
0

-

q

mutual inductance

n
p

L2S

- 1

L

-

-

.-

Ms

- 1

O O O

M

L2 s-1 L 1 L 2 -M2

q
p

-Ms-1
L1 L2 -M Ms - 1 L 1 L2 -M 2

L s- 1 L1LM 2 MS-1 L1 L2-M 2 -M - 1 L1 L2-M

Ms - 1 L1 L2 -M Li s- 1 L1L2-MZ -L 1 s- 1 L1 L2 -M

2 L1 L 2 - M

or

r

L11 - M2

L1 -1

O

FIGURE 4-2: Circuit Element template patterns.

_

___

I

4.1.

FORMULATING THE MOMENT POLYNOMIAL MATRIX EQUATIONS

73

be split into scalar matrices. For instance, the admittance polynomial matrix can be split into three scalar matrices,

rs) = rs- + G + Cs.
The scalar matrices r, G and C are the inductive, conductive and capacitive admittance matrices, respectively. (r has values of , hence the inverted L.) An important advantage of the Yis) matrix is that it can be inverted, even though neither r, G nor C is invertible. More is said about this later. The procedure for constructing Y(s) from knowledge of the circuit branch elements is identical to the procedure used in SPICE and described in [49]. It goes as follows. Initially, empty matrices are created for i"s) = 0 and i(s) = 0. Then, one by one the contributions of each branch element are added to the matrices. Each branch element type has a template pattern for its contributions into the matrices. These are illustrated in Figure 4-2 for discrete element types. Notice that both inductors and capacitors may have non-zero initial conditions. Taking one of the element types-the inductor, for instance-we see that the inductor moment representation relation (equal to the Laplace transform relation),
ir = - q =

1 Is(v

- vq)- i

is reflected in the template pattern. If one of the element nodes is the datum node, the matrix entries for that node are not included in the matrices, since vdatum = 0. When all of the branch element contributions have been added to the matrices, MIs) and i(s) are the desired result.

Example 4.1 Write the Laplace transform nodal analysis matrix equations for the circuit below.
in n1 (-l%

V(s)= 1

1

__

_

__

I

74

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

The Thevenin equivalent is converted into a Norton equivalent with Iquiv(s) = V(s)/L s =

5s-1. 58- 1 -1 0 0
-1 2+s 0
0

V1 v2 V3 V4

5s

-1

-1
1 + 2s
-s

0
-s

0 0 0

-1
0

2s

Example 4.2 Write the Laplace transform nodal analysis matrix equations for the circuit below.

I

(4.2)

0
1

1

O

1

O

G=.5

3

1+s -1 0 0

-1 2+s -1 0

o
-1 1.5 + s -0.5

0
0 -0.5 0.5 + 3s
vz V2 V 3 0 0 $

(4.3)

v4

3s

4.1.1

Distributed Circuit Elements

It is also possible to include distributed circuit elements in the MPNA equations, provided the elements can be described by a moment polynomial admittance matrix. This includes a large number of elements that cannot be included directly into time-domain circuit simulators like SPICE. For instance, the distributed RC element of Figure 4-3 is described by Laplace transform equation, [50]
'/coth((V') 2(s) ] =
-V/ -

csch(v/-)

csch(

)

?/

coth(v/rs)

[li(s) J v
V 2 (s)

Taking the Maclaurin Series gives the moment representation matrix entries shown in Figure 4-3.

4.1.2

Moment Polynomial Matrix Properties

At this point we want to consider how to solve the MPNA equations. But, first, we must take a little detour to examine some matrix properties. All of these properties have been developed

____

4.1.

FORMULATING THE MOMENT POLYNOMIAL MATRIX EQUATIONS

75

r = total resistance c = total capacitance P q

1+
q _ -

c2 r 2 S

2c 3 r2 + 31

3 3

1 1+ +

c

7c2 r 2 cr2

3

3 31c r2

+

312

FIGU360RE 6

Distributed3 15120

element 45RC template945

FIGURE

4-3: Distributed RC element template

in linear algebra texts (such as [51]), so only the interesting results are presented here. First we start with a definition. A field is a numbering system in which the operations of addition, subtraction, multiplication and division (except by 0) are performed without restriction. More precisely: A field is a set of numbers, F, and dyadic operations + and , such that if a, b and c are any elements of F, then: 1. The + and · operations are commutative and associative, 2. a + b and a b exist in F, 3. there exists a unique 0 E F such that 0 + a = a + O= 0, 4. there exists a unique (-a) E F such that a = (-a) = (-a) + a = 0, 5. a.(b+c)= ab+a.c and (b+c)-a= b a+ca,

6. there exists a unique 1 such that 1

$0

and a 1 = 1· a = a,

7. if a $ 0 then there exists a unique (a-') E F such that a a-' 1 = a -1 · a = 1. Obviously, the sets of real numbers and complex numbers form fields. So does the set of infinite degree moment polynomials, given that we allow negative-ordered polynomial terms. Appendix A'shows details of moment polynomial operations. The set of moment polynomials truncated to a fixed order does not form a field, since one can easily violate condition 2. The notation Fmx, is used for a matrix with elements from F arranged in-m rows and n columns. For these matrices, we shall define addition, multiplication, inverses and determinants in the standard fashion in which we are familiar with for real number matrices. The following theorems are valid for matrices of any field.

* If A E

nxn~

and b and x E cnxl, then the solution to Ax = b is

= A-lb.

__11_1_

1_

.II_-IIIUCI

I-

76

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

* The solution to Ax = b is unique if the following equivalent statements are true: - A has an inverse, - det(A) # 0, - Ax = 0 has only the trivial solution. Three elementary row operations are defined for
mxn,:

Row operation 1: Two rows are interchanged. Row operation 2: A row is multiplied by c E Y where c

$

0.

Row operation 3: A row is replaced by itself plus k times another row, where k E F. One last useful theorem involving these row operations on matrices of F is: * Any elementary row operation on the n x n + 1 matrix [Alb] will not affect the solution of Ax = b.

4.2

Solution of the Moment Polynomial Matrix Equation

The motivation of the preceding section was to show that matrix solution techniques using row reduction are not limited just to matrices of real numbers. The same row reduction techniques can solve any matrix with elements from a field number set-including the infiniteorder moment polynomial number set. We are now prepared to look at methods for solving Equation (4.1). 4.2.1 Gaussian Elimination

Gaussian elimination is an efficient row reduction algorithm for solving a matrix equation like Y. v = i. It is a well-known algorithm discussed in any linear algebra text on in [49]. It will be presented here only with an example. A dual purpose of the example is to demonstrate the applicability of matrix algorithms to the infinite-order moment polynomial number field.

Example 4.3 Solve the matrix Equation (4.2) of Example 4.1 using gaussian elimination. Step 1-forward elimination: Reduce Y(s) to upper triangular form by successively zeroing out the lower triangular terms by row operations
Yiowk (5)
i-

Yrowk(S) -

(

(S)

Y rowj (s),

for k > j

4.2.

SOLUTION OF THE MOMENT POLYNOMIAL MATRIX EQUATION
or
Ykm(S) N.(s) Y
(j(S))Yi

77

(s)

for k, m > j

(4.4)

and (8) k\YI` i(S) Z(YI--

((s)

yjj(s)

i j(s)

for k > j.

(4.5)

To zero the first column's lower triangular elements, row 2 giving
58 - 1

row2 - (is-

+

)

row1 = roW2 -

1 5

-- +

1 2 1 3)rOW - _ ... )ow 25 125

-1
2 + 5 + 255 2 4s 1
...

0 -1 1+ 2 -s

O 0 -s 2s (s)=

58 - 1

0 O 0 0 O
O

1 -5S+ 252...
0 0 O
O

-1 0

Row 3 and 4 were initially zeroed and thus are left unchanged. To zero the second column:
row
3

I

-

roW

3

-(

-1

row 2 = row

3

(-.

1

1 5

7 100 ... )row2

giving
5

-1

-1
2+ 4s + 1 S2 . .

0 -1
1 11s_ 7 2

0 0
-8

58 - 1

0 0 0

0 0

(S) =

11 _ 2

+ S2 ... +s
3 + 13 2 . 10 100 O

-s

2s

Lastly, column 3 is zeroed in row 4 by
roW4
-

row

4

-

-s
11

5

-

100

7

2..

-)

roW3 = roW4

- (-2s + 5

44 2.)row3

.)row

3

giving
58-1

-1 0 0
1 11

0 -1
7S2

0 0
-S

0 0 0
O

·b(s)

.

0
58-1 5

2s - 2s2 + 22S3...

25

(4.6)

2 S

-0

lo 100+

5 2 + 112S3. ..

--------·-----------

·--- -·

----

--- I

I

I--

I

78

CHAPTER

4.

GENERAL LINEAR NETWORK SOLUTIONS

Step 2-backward elimination: Solve for v(s) terms starting with the last and working upward, with

k() Dk zka/ = (8)Thus, V4 is calculated first:
v4 =

nk+ 'W(4.7) :km(s) m(8) M> =k+l kk(s) 1+ 2

2s - 2s + 144.s3 + ...
2+
+

S=- 5 2 + 112S3 ... + +* 2

--

2

2s+7s2+...

Then,

(1

3 s + 13

.)-

2 (-S)(2- 2s + 7S + . .)
+

and so forth, giving a final solution

1 - 22 +... 1 - 5 + 82 +
1 - 4s + 142 + ... 2s + 72 +
...

4.2.2

LU Decomposition

In many standard circuit simulation programs, (like SPICE and ASTAP) LU decomposition is implemented for matrix solutions [49]. LU decomposition is a slight modification of gaussian elimination. It progresses through the same sequence of elementary row operations, the difference being that intermediate row multipliers are preserved during the forward elimination process. Rather than placing unnecessary zeros in the lower triangular section of multiplier, (/) (s), the row in Equation (4.4), is placed in ykj. The net effect is to generate the sum of a lower triangular matrix (without the diagonal 1's) and an upper triangular matrix

[\]
where

=L- I+ U A =LU.

(4.8)

LU decomposition is advantageous if the same linear circuit (Ys)) is solved for many different source currents and initial conditions ((s)). The circuit matrix, I(s), is LU decomposed once, thereafter containing all of the information needed to solve Y(s)(s) = (s) for any number of (s)'s with Equations (4.5) and (4.7). In considering LU decomposition for the infinite polynomial number field, the relevant point of this section was that LU decomposition of the matrix is subjected to the same elementary row operations. polynomials. Thus, LU decomposition is perfectly suitable for infinite-ordered moment

4.2.

SOLUTION OF THE MOMENT POLYNOMIAL MATRIX EQUATION

79

Example 4.4 What is the LU decomposed matrix for '[s) in Equation (4.2) of Example 4.1? By putting the row multipliers found during forward elimination in Example 4.3 into the appropriate locations of the matrix in Equation (4.6), we have

I

5s-1

-1

0

0

+
°
0

21 ... 2+ 4s -_II
5

1 2...--1
1i 0 2

0

+ 1

S

S2.

2

-2

S..

S

0

-2s+ 44S2

2s -

2s2 +

22

...

4.2.3

Finite Truncation in Moment Polynomial Gaussian Elimination

The previous section demonstrates that gaussian elimination and LU decomposition can solve MPNA equations if no polynomial truncation is performed. Obviously, this is impossible in practice, for just about any moment polynomial division operation potentially yields an infinite degree polynomial. And yet, it is not sufficient to truncate all polynomials at the same order of s. We can easily see this by considering the zero moment solution (d.c. solution) to Example 4.2. If all polynomials are truncated past the s terms, this is equivalent to solving the resistive admittance matrix, G, only. Clearly, this will not do, since the capacitances play a significant role in determining the d.c. response. This section shows that if we chose the truncation order wisely during gaussian elimination, the final solution for i,(s) will have moment polynomials guaranteed to be accurate to a prespecified order, and computed with a minimal number of floating point operations. To start, a few definitions are made. All orders are moment polynomial orders of s. * The minimum order of a polynomial, denoted by

[a(s)J for polynomial

(s), is the order

for the lowest ordered, non-zero term of a(s). If a(s) = 0, the minimum order is undefined.

* Result order, p, is the highest desired moment order of the terms in v(s).
* An operation truncation order, T [a(s) op b(s)], is the highest necessary order of the calculated result of a(s) op b(s). Truncation rules are given in Appendix A for truncation orders for addition, subtraction, multiplication and division of moment polynomials. * A circuit element order is the minimum Laplace transform order of the circuit element's admittance. The circuit element order of an inductor is -1, of a resistor, 0, and of a capacitor, +1. It is also defined for a connection of elements as the minimum moment polynomial order of the combined admittance function.

_l1ls-··-·11111111I

____ ----

·----

---C·--

I--

80

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

* The node order of node j, 8j, is the minimum over all paths between node j and ground of the maximum circuit element order along the path. In forming the paths, independent sources are zeroed, i.e., voltage sources are shorted and current sources are opened.

Example 4.5 What are the node orders for the nodes in the circuit of Example 4.1?

81 = -1,

2 =

3 = 0,

4= 1

Example 4.6 What are the node orders for the nodes in the circuit of Example 4.2?

[31 = 82 = 83 = 84 = 1

____

The truncation orders for Gaussian Elimination are based on a circuit's node orders. Basically, when calculating any new term of row j of Y(s) or (s), it must be calculated to order p, the desired result order, plus the node order of node j. By definition of p, any new term of v(s) must be calculated to order p. The following important theorem states this more precisely-in terms of the gaussian elimination equations:

I

4.2.

SOLUTION OF THE MOMENT POLYNOMIAL MATRIX EQUATION

81

Theorem 4.1 To guarantee exact b(s) moment terms to order p, it is sufficient to calculate the intermediate results during gaussian elimination to these orders: * during forward elimination with equations:
Lnm(S)= km(S)Yjm(s)

and
k(S) = k(S)j() (S)j(S)

the truncation order for

subtraction
division

= p + Bk
= p + 3k - LYkk]

multiplication = p+ Bk

* during backward elimination with equation:
k(S) = k()m=k+l kk(S) m() Ykm()

the truncation order for:

division
multiplication

=p
= p+ 3k

summation and subtraction = p+ Bk

I

The proof for this is non-trivial, and is included in Appendix B. It is based on the properties of admittance matrices of reciprocal networks. One can start to see a justification for this by understanding, for instance, what information is needed for computing just the d.c. response to a circuit (p = 0). If a node is resistive (j only the inductance and resistance information is needed (s - 1 and so = 0), terms), not capacitance.

Thus, terms with order greater than 0 are not needed for its nodal analysis equation. If a node is capacitive (Bj = 1) then the d.c. response is determined by a ratio of capacitances; thus, a truncation order of 1. In algorithmic form, the gaussian elimination solution for moment polynomials looks just like a gaussian elimination algorithm for real number matrices, with two differences. below, these statements are marked with a "=". First, a few procedure calls are added to set a global truncation order variable. In the algorithms Second, all arithmetic operations on matrix elements are polynomial operations. These are distinguished from scalar operations with a box. Procedure LUDECOMPOSE converts the Y(s) matrix into an LU factorization as described in Equation (4.8). Procedure SOLVE-LINEAR solves 1Ys)u(s) = (s) for v(s) from i(s) and the LU decomposition of MTs). The node-order parameter to both routines is an integer array,

III

· _·L-YI·IIIXa·^·IIII

-·--III- I1

82

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

where the jth element is Bj. The algorithm for computing node-order is the topic of the next section.

Algorithm 4.1 pvector = array [polynomial] pmatrix = array [array [polynomial]] procedure LUDECOMPOSE (Y. pmatrix, n: integer, node-order: array[integer], p: integer) returns (pmatrix) begin { Gaussian elimination of Y} for j from 1 to n - 1 do begin diagonal: polynomial := Y[j, j];
if ISZEROPOLYNOMIAL(diagonal) then error ("matrix is singular");

for k from j + I to n do begin
SETTRUNCATIONORDER(p + node.order[k]POLYNOMIAL.LOWORDER(diagonal));

mult: polynomial := yIk, j] diagonal; Y[k, j] := mult; if not(ISzERO_POLYNOMIAL(mult)) then begin
SETTRUNCATIONORDER(p + nodeorder[j]); -

I

for m from j + 1 to n do begin

ylk, m] := YIlk, m] [
end end end end

mult [] 1[j, m];

if ISZEROSPOLYNOMIAL(Y[n, n]) then error ("matrix is singular"); return (1); end

Algorithm 4.2 { solve a system of equations from the L U decomposed array and vector i. } procedure SOLVELINEAR (Y pmatrix, i: pvector, n: integer, node-order: array[integer], p: integer)
returns (pvector) begin

{ create v }
v: pmatrix := create pvector(n);

{ account for the forward elimination steps on i; for j from 2 to n do begin

4.2.

SOLUTION OF THE MOMENT POLYNOMIAL MATRIX EQUATION

83

SETTRUNCATIONORDER(p + node.order[j]); 4

sum: polynomial:= ZEROPOLYNOMIAL(); for k from 1 to j- 1 do begin sum:= sum jli, k] Ml 'v[k]; end

Ed

v[j] :i[j]
end

sum;

{ back substitution } for j from n to 1 by -1 do begin SETTRUNCATIONORDER(p+ nodeorder[j]);:= sum: polynomial:= ZEROPOLYNOMIAL(); for k from j + 1 to n do begin sum := sum 5 Yfj, k] v[k]; end sum := v[j3 FJ sum;
SETTRUNCATIONORDER(p); 4=-

V[j] := SUm F Mj, j]; end return (v); end

4.2.4

Computing Node Orders

The node order of each node is computed prior to solution with gaussian elimination or LU decomposition, as it is needed in setting the truncation orders. Conceptually, node orders of a circuit are found by first constructing an undirected graph. There is a vertex (or node) in the graph which corresponds to each node of the circuit. Also, an edge is placed in the graph between a pair of vertices corresponding to each circuit element. An edge is labeled with a
"-1", "0" or "+1" depending on its corresponding circuit element's order.

Node orders are assigned by tracing, first, all nodes connected to the ground node through 1 edges. These nodes are marked with node order "-1". Then all previously unmarked nodes connected to ground through any path of edges labeled 0 or less are traced. These nodes are marked "0". Lastly, all previously unmarked nodes connected to ground through any edge are marked with node order "+1". At this point, any unmarked node represents a floating node, and indicates an unsolvable network. The node tracing algorithm is done with a modification of the standard depth-first search algorithm described in [52]. It is expressed algorithmically below, where 5 represents the undirected graph of the circuit.

-~~

1___~__IC_

---

l~·II

II

_

·I_·__

I_ _

_

_

84

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

Algorithm 4.3 procedure COMPUTENODEORDERS (:

graph) returns (array[integer]) begin

nodeorder: array[integer] := CREATEARRAY(n);

for each vertex v in graph 5 do nodeorder[v] := "unknown"; SEARCH(, nodeorder, "ground-vertex", -1); { inductive nodes } SEARCH(g, node-order, "ground-vertex", 0); { resistive nodes } SEARCH(g, nodeorder, "ground-vertex", 1); { capacitive nodes } return (nodeorder); end

Algorithm 4.4 procedure SEARCH (: graph, node-order: array[integer], v: vertex, order: integer) begin nodeorder[v] := order; for each vertex w through edge x adjacent to v in graph G do if (node.orderw] = "unmarked") and (LABEL[X] < order) then SEARCH(g, nodeorder, w, order); end

The undirected graph is constructed concurrently with the admittance matrix. As each element's template is added to Ms), a new edge is added to 5. While almost all of the information in 5 is contained in

Ms)

(all but the ground connections), a separate linked list structure is

maintained for 5 to minimize the node order computation time at the expense of some memory. The time required to compute node orders is insignificant in comparison to gaussian elimination time. 4.2.5 Pivoting for Accuracy

To avoid numerical roundoff problems found in stiff simulation problems, matrix solutions usually employ a pivoting algorithm where rows and/or columns are interchanged during gaussian elimination. The need for this is diminished with nodal analysis, since the pivot, or diagonal term is always the dominant element of any row or column. There are cases, however, where finite precision arithmetic can affect the solution's accuracy. For instance, the solution to the circuit of Figure 4-4, described by
1000001 + s
-1000000

-1000000
-1000000 + s (s

I 1
0

4.3.

EXAMPLES

85

R=1

()R=10

()
1

V=

FIGURE 4-4: Circuit requiring node pivoting. yields a solution,
bl(s) =
2 (s)

= 0.88889 - 1.5802 s + 2.8093 s2

-

with 22-bit mantissa arithmetic precision. Full pivoting or partial pivoting strategies cannot be used in the MPNA solution algorithms, since this can disrupt the diagonal-term minimum polynomial orders which are needed for Theorem 4.1 to operate correctly. Instead, diagonal pivoting is used where both rows and their corresponding columns are swapped. This equates to simply renumbering nodes. With diagonal pivoting, during any stage of forward elimination the best choice for the next pivot is yjj(s) with the maximum lyjj(s)j - b or when more than one node has the same b, to choose the node with minimum value of yjj,b. Thus, in the above example, the second node is eliminated first, and a true solution of {i(s) = 2(s) = 1 - 2s + 4s 2 is computed. - -

4.2.6

Pivoting for Sparsity

Matrix pivoting for purposes of achieving sparsity in the LU decomposed matrix is hindered for the same reasons as pivoting for accuracy. Once again, only rows and columns can be interchanged together. In some instances, it may be advantageous to move a heavily connected node to a lower position in a matrix. It may also be advantageous to number nodes of a ladder type network in consecutive fashion, since these form a band-matrix, where only the diagonal, and terms one away from the diagonal are non-zero.

4.3

Examples

On the following pages are several examples of results obtained from the algorithms described in this chapter. All are representative of circuit topologies which model VLSI circuits or interconnections. Namely, the topologies match models for * connecting RC trees, * charge sharing circuits,

* lumped RC trees,

1__11

_11_

_I

-

-

-

86 * distributed RC trees, * discrete coupled RC lines, and

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

* discrete coupled RLC lines (damped). Each of the following examples shows a plot of the simulation results of SPICE (in solid lines), and the moment polynomial method calculated to order 3 and with a double exponential inverse (in dotted lines).

4.4

Computational Requirements

In this section, the computational requirements for the MPNA algorithms are compared against the computational requirements for direct methods, and where applicable, against the computational needs of the RC tree algorithms of Penfield [47] and Horowitz [18]. Chapter 7 shows a method for moving linear network solutions out of the simulation loop and into the preprocessor step. So, this computation time is not a major concern. This discussion is included here for completeness. The quantitative value for computation in this section is based on the number of floating point operations needed to compute one waveform or closed-form waveform expression. This figure of merit is chosen over CPU time for two reasons, (1) to first order, it compares the algorithms more directly, rather than the efficiency of compilers, and (2) some of the simulation times are extremely small and difficult to measure. To generate a single number for equivalent computations, each type of floating point operation is scaled by approximate relative computation times, i.e., the number of equivalent computations is (# additions) +(# subtractions) +3 (# multiplications) +4 (# divisions) +10(# square roots) Table 4-1 shows the number of equivalent computations for each circuit. The three columns given for MPNA are computed with different result orders. Direct method estimates are computed as follows. The number of floating point operations for one matrix solution is determined using the same circuit matrix, the same set of matrix operations, and the same pivoting for both MPNA and direct methods. First order numerical integration is assumed. The number
of time-steps is estimated by running SPICE simulations where the automatic time-step control keeps node voltages within 5-10 % accuracy at all times. These accuracies may conceivably be worse than the moment polynomial method. SPICE waveforms shown in the preceding examples used several times more time-steps than this number to give an accurate number. From Table 4-1 we see that the special RC methods are more efficient computationally, but these are also very limited in ability. The RC tree method for instance applies to only

4.4.

COMPUTATIONAL REQUIREMENTS

87

Example 4.7

(

7 vv

1K

(

1K

VJyi--v 0svIL7
I

()

2K
-

0(

1iF. rP .

7 I

7-

FJL-

1

-

-

"0

.
IV.

-I

j Pr

'

1T

V.LV..ydpL

1.0

.8 SPICE ........ MPNA
.6

.4

.2

5

10

15.

20

25

30

35

40

45

time

(nsec)

FIGURE 4-5: Two connecting RC trees

_11__·_111____1____··l__l__·---··

1--

ISIII

-X-l

III

88

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

Example 4.8

()
1 pF

1K :, , F

(

1K

," , ,kA.

'c

(0)

2K 'VIA.

() ; = 3pF

1pF

_I

1.0

.8

.6

.4
-

SPICE

........ MPNA
.2

2

4

6

8

10

12

14

time

(nsec)

FIGURE 4-6: Charge sharing

4.4.

COMPUTATIONAL REQUIREMENTS

89

Example 4.9

50

O

50

(0

50

0
pF

I

50

e ?

1v. L
Ov.

I.pF
T''

1.0

.8

.6

SPICE

........ MPNA

.4

.2

.1

.2

.3

.4

.5

.6

.7

.8

.9

1.0

time

(nsec)

FIGURE 4-7: 10-stage RC line

1----·I -·--I --PI1 -

-- I-I-·-_i___

-II

_ 111_-·1·--·1·--·1Il-L-

90

CHAPTER 4. GENERAL LINEAR NETWORK SOLUTIONS

Exampl
.

.

1 pF

1K

r=1K (D c=.5pF

r= K c=1pF

@
= pF

IpF

1.0

I

.8

.6
SPICE
.4

........ MPNA

.2

5

10

15

20

25

30

35

40

45

50

time

(nsec)

FIGURE 4-8: Distributed RC tree

4.4.

COMPUTATIONAL REQUIREMENTS-

91

Example 4.11

pF

pF

.05 pF
.. .

1.0

.8

.6 10 5
.2
SPICE ........ MPNA

.4

-.2

20 I .5 I
1.0

I
1.5

I
2.0

I 2.5 time

I
3.0

(nsec)

FIGURE 4-9: 10-stage coupled RC lines

_C__IX_

Y___

_

1 · 11··.--s__llll ------1·····slBl^1-----·141_-1---··

92

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

Example 4.12

1 pFJL

2K
1 v. Ov. L

(

1,,i

T

H pK 1

2K

0

luH
pF

2K 1 pF

2K

( 1

1.0

.8

.6

.4

SPICE

........ MPNA
.2

-.2 I 0 5 10 15 I 20 I 25 I 30 I 35 I 40 I 45 I 50

time

(nsec)

FIGURE 4-10: Two-stage coupled RLC lines

4.5. DIscUSSION

93

Penfield Example Example Example Example Example Example 4.7 4.8 4.9 4.10 4.11 4.12

Horowitz 100

50 45

180

MPNA p= 1 83 150 500 440 1500 2200

MPNA p= 2 200 310 1000 940 6000 4200

MPNA 2 p=3 370+400 510+400 1700+400 1700+400 15000+400 7400+400

direct methods 1600 1600 5800
_90003

54000 13000

Table 4-1: Equivalent computations of examples for each method two example circuits, and computes only first moment information. The RC tree models of Horowitz are equally limited, and only compute first and second moment information. Neither of these is capable of computing important coupling information. Another thing to observe in Table 4-1 is that in all cases, the moment polynomial method requires less computation than direct methods. This is particularly true when modeling distributed elements, since these are treated as one element with MPNA equations. For instance, in Example 4.10 the computation requirements are 5-20 times less than direct methods, depending on result order. Two final observations are made regarding the computational complexity of the MPNA algorithms. First, for a given circuit, each increase in order results in an increase of computation by two on average. Second, for a fixed result order and a variable number of nodes, n, the number of computations varies between O(n) and O(n 3 ). O(n 3 ) occurs only for a completely filled admittance matrix, which rarely happens with interconnection circuits. Figure 4-11 show more realistic complexity orders for interconnection circuits which vary between O(n
O(n l.9).
0 5)

and

4.5

Discussion

In this chapter we have seen that one can solve linear networks for the moment representation of all node voltage waveforms. By following the truncation order for intermediate calculations, the moment representations are guaranteed to be accurate to any desired order. Unlike other simulation algorithms, the type of circuit is not constrained to just RC trees, meshes, or to circuits with grounded capacitors at each node, etc.

This figure is separated into two numbers, the first for the matrix solution time, the second for the number of operation to find one double exponential inverse, (about 400). 3 Based on 3-stage lumped approximation for each distributed RC section.

2

-

-·------------

------------

-

-'-~-

- -----s----

94

CHAPTER 4.

GENERAL LINEAR NETWORK SOLUTIONS

,P
10000.
V p.'. P. JV *
10

*

1000.

1 %__
i

1

I .I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I

2

10

20

n FIGURE 4-11: Computations vs. node count for n-stage RC lines (-) and -stage coupled RC lines (- - -).

5

Transmission Line Solutions for the Moment Representation
This chapter presents some special considerations for finding solutions to transmission line circuits. It relys on the previous chapter's methods, but improvements can be made for much. better solutions. In this discussion, we will consider only lossless, coupled or uncoupled transmission lines which are in a homogeneous medium along their length. We also allow arbitrary networks at the transmission line ends. Abrupt changes in transmission line direction, coupling or dielectric surroundings can be modeled by two connected sections. The advantage of the improved transmission line modeling is easily seen by considering the voltage response on the uncoupled, uniform LC line shown in Figure 5-1. The ends are ideally terminated to eliminate reflections. The voltage response at some distance, lx, due to input Vin(s) is 1 vi(s) = V(s) · e(5.1)

where u = 1/VLT-C is the propagation velocity. We could model this distributed transmission line in the moment representation domain as described in Section 4.1.1 by taking the Maclaurin series of Equation (5.1): l(s) = in(s) 1 xI X s2 (1 - -~-5 3 + s 2u u )

But, since this response (aside from multiplying by the transmission coefficient of one-half) represents just a signal delay of EL, an exact solution is easily computed by incrementing the to term of the moment representation, tov, = to,vi, + EL, or V 1(S) = Vin(S) e
[o se

The moment polynomial portion of the transfer function has one term, () SO 95

__

___Y(

C_

I_

___I

_II1IICI

--

1-·111·111

96

CHAPTER 5.

TRANSMISSION LINE SOLUTIONS

VmJ

FIGURE

5-1: Response of single transmission line.

This solution is far easier to compute than a solution with MPNA, and is more accurate. Figure 5-2 shows an extreme example of what may occur with an MPNA solution. The waveform starting location is not updated, and the resulting double exponential waveform is far from the correct waveform that is obtained by increasing to. The above example demonstrates the basic technique for transmission line solutions with the moment representation-incrementto rather than the moment polynomial. To handle circuits with reflections or coupling we turn to previous work on modal analysis of transmission lines.

5.1

Modal Analysis of Coupled Lossless Transmission Lines

In this section we consider a set of N coupled, lossless transmission lines. One common configuration is shown in Figure 5-3. The theoretical basis for this coupled transmission line modeling is well developed, and was introduced in Section 1.1.5. Here, we look at these existing methods more thoroughly. Any excitation applied at one end of N coupled conductors activates a set of N modes which propagate to the opposite end at different velocities. In this thesis the two ends are designated as the transmittingand receiving ends, and variables are given t and r subscripts, respectively, to distinguish between quantities at the two ends. While this designation is arbitrary, we will assume that signals originate at the transmitting end. With the new method, mode strengths are computed for any specific input excitation, hence the name modal analysis. The modes propagate to the receiving end at their specific mode velocities; the mode strengths remain constant while making the end-to-end transition. At the receiving end, some energy reflects back to the transmitting end, depending on external circuitry connected to the transmission lines. The telegrapher's equations (Equation (2.4)) with R and G absent reduce to an eigenvalue problem. Modal propagation velocities on coupled transmission lines are related to the eigenvalues of the matrix product, LC, where L is the inductance matrix per unit length of the
h conductors and C is the capacitance matrix per unit length [53]. If the mn eigenvalue of LC

is Am, then the propagation velocity of mode m is
U, = 1/rv-n.

5.1.

MODAL ANALYSIS OF COUPLED LOSSLESS TRANSMISSION LINES

97

r-i

1.0 .
U-B

Vin (t)
.8

V 1 (t)
.6

[MPNA solution]

.4

Vl (t)

[exact solution]

.2

0.0
I

__

0.0

.1

.2

.3

.4

.5

.6 time (nsec.)

FIGURE 5-2: Waveforms from MPNA and modal analysis of transmission lines.

All waveforms are third order double exponential inverses of a sample output waveform.

VVo~L
Vr 2 + o-fir

1·11111111111111111II

2
-

LC line N ne 2
lm

V.

+ Vr N

0001!m-o

--

grunuplane
-

FIGURE 5-3: Coupled transmission line geometries.

------- --

---- - ---c------I-`

I -

I

-----

98

CHAPTER 5.

TRANSMISSION LINE SOLUTIONS

The strength of mode m is designated hmr±(t), where a "+" subscript indicates propagation in the +x direction and vice versa. At any x position, transmission line voltages and currents are related to mode strengths through the modal matrices, Mv and MI, by v(x, t) = Mv h(x, t) i(x, t) = Mr h(x, t) where h(x, t) is the vector of total mode strengths at x, hl+(t h(t (5.2) (5.3)

h(x, t)=
hN+(t-

+
) hN(t
-

)

-

The voltage modal matrix, Mv contains eigenvectors of LC, where column 1 contains the eigenvectors corresponding to A1 , column 2 contains the eigenvectors corresponding to A2, and so forth. In this discussion, the eigenvectors may be scaled by any non-zero value. In cases where the N eigenvalues are not all distinct, care should be taken to ensure that the eigenvectors are linearly independent. The eigenvalues and eigenvectors may be found with any standard algorithm such as those described in [54]. The voltage and current modal matrices are related by MI = L1 My

A,

My = C - 1 Ml A, where l/u2u A=
0 1/UN

0

Figure 5-4 depicts the modal analysis method. First, a set of voltages applied to the transmitting end, is mapped into mode strengths with the voltage modal matrix. Next, the modes are propagated to the receiving end at their individual speeds. At time t = 1/um mode m reaches the receiving end and is mapped back into transmission line voltages. Thus far, we have not considered the effects of the transmitting or receiving circuitry. This circuitry and the transmission line characteristic impedances must be considered when calculating reflections and transmissions at endpoints. The common technique for computing interface behavior is to substitute the equivalent circuit of Figure 5-5 for each uncoupled mode transmission line in Figure 5-4. As shown in the equivalent circuit, each mode has a characteristic impedance, Z, = Lm/um where L' = M T L MI. The sources in Figure 5-4 are activated when a propagating signal reaches the endpoint, i.e., jt(t) = 2 hm(t- /u,) Zm _ jm(t-

5.1.

MODAL ANALYSIS OF COUPLED LOSSLESS TRANSMISSION LINES

99

VtN

+

o-

I
-I
I I

+

hN+

+

hN.

VrN

Vt2

+

0I

MV
h, + .

My

I

+

Vr2 Vrl

Vtj

+
_

I+

uncoupled modes FIGURE 5-4: Modal analysis equivalent representation.

I +

_

_

_

_

_

_

_

_

_

_ .

_

_ .

_

_ l c

itm

I

+

htm

'vUZm

1I

I

4
, |

Zm4

I ! ! !

I

L

……………-- - - - - - - - - - - - - - - - _- - - -- -

-- -,I,

FIGURE 5-5: Method of characteristics equivalent circuit.

------------- -----·-

-··---·--------··--- ---··-··

-------------------------

100

CHAPTER 5.

TRANSMISSION LINE SOLUTIONS
I

hN-

,z

,\

transmit interface circuit

uncoupled mode signals

receive

interface circuit

FIGURE 5-6: Modal analysis circuit.

- I/). Zm This method, known as the method of characteristics, was first presented in [55] for a single

jrm(t) = 2 htmjtm(t

transmission line. The circuit that results from the above substitutions can be transformed into the circuit shown in Figure 5-6 by moving the transmission line impedances and sources outside of the modal matrices. The resulting transmission line impedances and sources are now represented by a characteristic admittance matrix, Yo, and a pair of current source vectors, it(t) and

i,(t). These connect directly to the external transmit and receive circuitry. The characteristic
admittance matrix is found directly from the transmission line properties, e.g.,

Yo = L - 1 (LC)-y = A-' Ml 1C = L My A '
1.

Signals still pass from end to end as mode strengths with h+(t) and h_(t). The current source values are computed at the transmit and receive ends by
it(t) = 2 MI h_(t /urn), and

i,(t) = 2 MI h+(t - 1/u).
The reflected mode strength from each is computed from the voltage at the interface network and from the incoming mode strengths: h+(t) = Mv1 vt(t) - h(t-), (5.4)

--

5.2.

MODAL ANALYSIS WITH THE MOMENT REPRESENTATION

101

h_(t) = MA1 v,(t) - h+(t -

Urn

).

(5.5)

Considering two conditions of signal excitation on the transmitting end: * when the excitation is caused entirely by the transmitter circuitry, only the first term of the right hand side of Equation (5.4) is non-zero, * when the excitation is caused by a signal propagating from the receiving end, the reflected signal is computed by the difference between the first and second terms of Equation (5.4). When the first and second terms are equal, the transmitting end is ideally terminated since the two terms cancel, leaving no reflected signal.

5.2

Modal Analysis with the Moment Representation

Modal analysis methods translate easily into the moment representation domain. To develop the method, we will consider a signal initially generated by the transmit circuit with the transmission lines at rest. The moment representation simulator performs the following steps: 1. Solve the entire transmit interface circuit (see Figure 5-6) for v(s) using the methods of Chapter 4. The voltage excitation comes from the transmit circuit, and since the transmission lines are at rest, the current source vector, t(s) = 0. The transmission line admittance matrix is resistive, so in the moment representation domain of this portion of the circuit is Yo s° . 2. Find the moment representation mode strengths with

h+(s) = Mfj's 0 it(s),
which is derived by rewriting Equation (5.2) in the moment representation domain. 3. Compute each mode's arrival time at the receiving end, tm = t + /u, for mode m,

(5.6)

and queue each mode's arrival on the other end as a separate transition in the simulator's global event queue. The individual mode signals on the opposite end are formed by zeroing all but one term of the h+(s) vector and then shifting it in time by incrementing the moment representation to term, i.e.,
O

hm+(S)

= eStm

hm+(s)

0

102

CHAPTER 5.

TRANSMISSION LINE SOLUTIONS

If the arrival times of different modes are equal or nearly equal, as is often the case, then their separate transitions can be combined into a single transition. We use the moment representation time shifting algorithm of Equation (3.9) to match all of the moments to a global starting time. To combine modes m and n, for instance,
hm+,n+() = estm [hm+(s) + {1-S(tntm) +

2(t _ t)2

}

hn+()]

The notation will refer to a mode strength vector containing one or more individual modes all time shifted to a common starting point, tn. The advantage of combining transitions is to decrease the number of transitions which otherwise could be very numerous if signal reflections remain strong at both ends. Caution must be used in deciding which transitions to combine, since too much shifting can smear distinct signals into an inaccurate single waveform. It is usually safe if the difference between arrival times is small relative to the waveform durations, or if
Itn - tm < Ml,hm-lMO,hm-

4. When a signal reaches the receiving end, convert the mode strength(s) into the current source waveforms
Zi(s) = 2Mih{m}+().

5. Solve the receive interface circuit, using the methods of Chapter 4. 6. At this stage we are repeating the cycle started in Step 1 above. Appropriate modifications to terminology are easily made to account for the fact that we are the receiving end, rather than the transmitting end. But first, one additional feature must be added to calculate the reflected signal strength at any interface. This is achieved by modifying Equation (5.6) in Step 2 to mirror Equation (5.4) in the moment representation domain, or h+(s) = MVlso' t(s), - hfm}_(s). After some number of reflections, the magnitudes of the mode signals decay to an insignificantly small value. Before any mode transition is added to the event queue, this condition is tested, and the signal is terminated if it is too small. The algorithm for calculating the waveforms at either endpoint is stated concisely below.

5.2.

MODAL ANALYSIS WITH THE MOMENT REPRESENTATION

103

Algorithm 5.1 Excitations can come from the external circuit or from within the transmission line or both. The procedure parameters are: h{m}q: Excitations from within transmission line or 0 if none. i=: Excitations from external transmit or receive circuit or 0 if none. Y: Interface circuit admittance matrix, equal to Yezternal + Yo. M: Current modal matrix. M, 1 : Inverse voltage modal matrix. t: Mode propagation times for length of transmission line. All matrices are polynomial matrices. procedure LCIJNTERFACESOLVE(h{m}:, i, Y, MI, M1', t) begin { Compute source currents as the sum of externally applied sources and the incident modes equivalent currents. } i := i + 2MI h{m}; { Solve the interface circuit. }
V := SOLVE(Y, i);

{ Compute new mode strengths. } { Delay modes by propagation times for length 1. } for each mode, n do

ho[n] := e-"t[n] h[n];
for each set of closely spaced transitions, hn};, at time, tn in h do begin
if MAGNITUDE(h{n(,}) > threshold then
n:); QUEUETRANSITION(tn,

end end

104

CHAPTER 5.

TRANSMISSION LINE SOLUTIONS

Example 5.1 (Two coupled transmission lines.)
What is the moment representation solution to the circuit below?

Vt 2

LC line 2
_w j T7

V ,

Vrl

R= 500
-

"W , rlIn rrl l &b% UtAL %aFJL"

L

[ 2.0

1.5configuration, 3.6this

15 ]pH/m;

C=

72 -30

-30 ]pF/m 50

For this configuration, Mv= 1.0 [ -0.0439 0.4391 1.0

1

M [ 7.3933 0.1401 and circuits the below-3.2466 3.1913 interfaceshown are as and the interface circuits are as shown below.

1
'

675 328 237

R = 675 R = 328 R.= 237
R= 500

transmit interface circuit

receive interface circuit

5.3.

DISCUSSION

105

Propagation times are 49.6 picoseconds for mode 1 and 57.7 picoseconds for mode 2. Since transition rise times are longer than the difference between propagation times, both modes are combined into one transition in this example. The solution through the first internal reflection from the transmit end is shown below in dotted lines. The response from SPICE is shown in solid lines. The SPICE solution did not use modal analysis, and was done with 50 stages of coupled LC equivalent sections. The SPICE waveform ringing is an artifact of this, and does not reflect the true solution. For this example the moment representation solution is more correct than SPICE.
1 1. SPICE ........ MPNA .6 L s

A_-an

-

~-



Vrl Vt,
f'`

.4

-

?i

Vt 2 (volts)
.2 Vt2
r_^

:1

--

Vr 2 ---

-

--

--rr rrrr-

-

0.0

-

1

-

--

I

0.0

25.0

50.0

75.0

100.0

125.0

150.0

time (psec.)

5.3

Discussion

This chapter has presented a modal analysis method for simulating lossless coupled transmission lines in the moment representation domain. This special modeling is needed because transmission line circuits tend to retain sharp transitions even through large delays. If the large delays are contained in the polynomial portion of the moment representation-as happens when we use the methods of Chapter 4-the time domain waveform approximations are

106-

CHAPTER 5.

TRANSMISSION LINE SOLUTIONS

poor. The modal analysis methods operate by adjusting the to time delay term of the moment representation, rendering a much improved fit to the true solution. Coupled transmission lines are simulated by modeling mode strengths in the moment representation domain. The interfaces at both ends of a set of coupled transmission lines is modeled by an equivalent resistive network, and is simulated using the linear circuit methods presented in Chapter 4. Each reflection is treated as a separate transition, or set of transitions in the event of widely varying mode velocities. The computational requirements for moment representation modal analysis depend on several factors: * the number of individual conductors contained in the coupled transmission lines, * the number of reflections before a signal decays to an insignificant level, * the closeness of the propagating mode velocities, and * the complexity of the transmit and receive circuits. During simulation the linear network solution time for the interface circuits is the most complex step. Chapter 7 shows a method for removing this computation time from the simulation steps. One final note is made regarding lossy transmission lines. Lossy transmission lines have been modeled in the past by using an extension of time domain modal analysis [22] where many sections of lossless transmission line are connected in series with approximating resistors. The number of sections depends on the amount of attenuation; more attenuation requires more discrete sections. This type of modeling can be applied to moment representation simulation.

rs

6

Macromodels for Non-Linear Networks
Clearly, non-linear circuits, cannot be simulated with the linear network methods described in Chapter 4. Yet, non-linear transistor elements are a significant building block in digital circuits. In this chapter a macromodeling method is presented which translates a transistor circuit into an equivalent linear circuit that causes the same response. The linear circuit element values do not remain constant and are functions of the transistor circuit input waveform and output loading admittance. So, like SPICE, simulation time is increased for non-linear circuits. However, an advantage of combining macromodeling and the moment representation is that for a given circuit, the input-output characteristics can be precompiled into a small set of macromodel functions. Simulation speed is then considerably improved. This feature is demonstrated in the next chapter. The macromodeling techniques in this thesis are based on the successful methods developed by Brocco [26,56]. The methods are modified to fit into the moment representation framework. Because of the more precise circuit and waveform specification ability of the moment representation, the macromodeling is improved even further over the previous methods. A major issue in macromodeling is the number of macromodel function parameters. On the one hand, we desire as few as possible for efficiency reasons, but on the other hand, we desire enough to ensure an accurate performance characterization. In this work, two parameters describe the environment of an MOS transistor circuit with good accuracy. These are, roughly, the time for the input and time for the output waveforms to traverse through critical operating regions of the transistors. The output waveform parameter is mapped into an effective load capacitance parameter. The macromodeling converts a non-linear circuit into a sub-circuit of linear elements. The macromodel functions describe values for the circuit elements. The above synopsis shows the steps taken during simulation: (1) a moment representation waveform is converted to the time domain, (2) time domain parameters are used to look up 107

108

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

macromodel function values, and (3) an equivalent linear circuit is formed using the macromodel function values. Macromodel functions are constructed by extracting moments from real waveforms of the non-linear circuits. Most commonly, the waveforms are from SPICE simulations. Different circuit models are needed for the two types of transistor cells. First we look at MOS transistor circut decoupling, and examine what constitutes a macromodel cell.

6.1

MOS Network Decoupling

Digital MOS circuits are divided into sub-circuits for different reasons. Two types of subcircuits-cells and sub-networks-are discussed next. 6.1.1 Cells

A cell is a portion of a circuit which performs a well-characterized circuit function. A cell's boundary is usually defined by the circuit designer, and has input and output signals passing across its border. A typical cell may constitute an inverter, a NOR gate, an adder circuit, or an ALU. A cell may contain nothing more than interconnection lines, or may call other cells hierarchically. Since cell hierarchy and cell structure are not primary subjects of this thesis, and since the subject could occupy an entire chapter, if not thesis, on its own, it will suffice to say that any MOS circuitry can be composed of the following elementary cell types. Interconnection cell: A portion of a circuit representing one or more interconnections. It is composed of nodes connected by linear circuit elements. These cells do not contain non-linear circuits. Transistor driver cell: An output node driven to a high or low voltage through a transistor path to VDD or ground. The transistors are controlled by one or more controlling inputs to the cell. A logic gate output is modeled by a transistor driver cell. Transistor transmission cell: Two nodes connected by a path through one or more transistors. The transistors are controlled by one or more controlling inputs to the cell. A CMOS transmission gate is, for instance, modeled by a transistor transmission cell. 6.1.2 Sub-networks

A sub-network is a portion of a circuit consisting of a set of nodes and elements which are connected through MOSFET sources and drains, resistors, or inductors. Basically, a sub-network is the smallest set of tightly connected or conducting nodes which must be solved as a unit if iteration is to be avoided. The boundary of a sub-network is computed by the preprocessor program with the algorithm described by Bryant in [52]. Bryant refers to sub-networks as

6.1.

MOS NETWORK DECOUPLING

109

transistor groups-the different term is used here, since resistors and inductors also connect pieces of the sub-network.' When circuit designers connect cells together, they almost certainly form sub-networks which are different from the cells. The notion of a sub-network is usually only useful in circuit simulation. Many simulators for MOS circuits [52,10] exploit the fact that a signal waveform can be closely determined by simulating sub-network circuits individually with known input signals applied to transistor gates in the sub-network. The moment representation simulator exploits this same feature for calculating signal waveforms. The preprocessor program regroups circuit components into sub-networks. During simulation, each sub-network is solved independently; the only link between sub-networks is achieved by passing the output waveform of one sub-network to the input of another sub-network. Coupling noise waveforms are computed with more than one sub-network, since capacitively coupled nodes are not typically in the same sub-network. A special simulator feature added for calculating capacitive coupling noise is outlined in this paragraph and is depicted in Figure 6-1. If the node of one sub-network undergoes a signal transition, and if this node is capacitively coupled to a node or nodes of another sub-network, then the circuit formed by the combination of the two sub-networks is solved for the noise waveform. All other capacitively coupled subnetworks are ignored (with the exception of extremely noise sensitive nodes) hence, their nodes are assumed to be held at constant voltages. If a sub-network is capacitively influenced by more than one sub-network at the same time, then the influences are calculated individually (i.e., still only two sub-networks are combined at once) and then the waveforms are summed. Only the negligible effect of double coupling (where one line couples to a second line which couples to a third line) is not treated.

6.1.3

Macromodel Cells

Circuits are macromodeled on cell boundaries. A macromodeled cell is best utilized when replicated many times since much preprocessing is needed for each macromodeled cell, and sharing this among many circuits makes the most efficient use of the preprocessing. The best boundary for a macromodel cell is at the corresponding boundaries of the circuit cell or layout cell. Of the cell types defined above, transistor driver cells and transistor transmission cells are macromodeled, while interconnections are not. One restriction exists in forming macromodel cell boundaries and in connecting macromodel cells: circuit feedback paths must not cross cell boundaries. That is, a circuit feedback loop must be entirely contained within one macromodel cell. (See Figure 6-2.) This restriction does not
'The sub-network can also be defined by the terms given in Chapter 4. A sub-network is a set of nodes connected through circuit elements with order 0 or less. MOSFET source-to-drain connections have circuit element orders equal to 0 and MOSFET gate-to-source and gate-to-drain connections have element orders equal to +1.

110

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

sub-nei twork 2

sub-network 3
I : ,

.................................

I

I i I
I
:I :I

.;

I : I
.I I

I
-1 I I

I
I

.11-V

;

'
.1I

.-

'
· · ·- L

It

~.: ·

__-' r

· : I.

A

·

d : ..

.

:

---

,_ :

LT--_- -' ,-r---~--

:

:

I
---

_____-------.-- _-----------_---_

I ..

inverter cell *

:...................................... :

interconnection cell : ::

.......................................

NAND cell

sub-network 1
FIGURE 6-1: Sub-network boundaries.

To find the coupling noise caused at node x by a transition at node a, the circuit formed by combining sub-network 1 and 2 is solved independently of sub-network 3. apply to clocked logic feedback, as in the case of a clocked finite-state machine.

6.2

Fundamentals of Macromodeling

The motivation behind macromodeling is to reduce a computationally expensive task to a simple table lookup task. Table values are computed once, by the expensive method, but then can be accessed quickly, any number of times. A macromodel function is any function with respect to important, controlling input parameters, Pi, p2,
...

P,. Sample values of an n-dimensional macromodel function, F(pl, P2, * pn),

are stored in an n-dimensional array, at discrete, closely-spaced increments of the input parameter data points. When a macromodel value is fetched from the tables with an input parameter located between two data points, some form of interpolation is used. In this thesis, linear interpolation is assumed, and only one- and two-dimensional functions are used. Previous macromodeling efforts for circuit simulation have macromodeled 1. logic gate output waveform delay time and slope versus input waveform slope and output load capacitance [57,26,25],
2. MOSFET id, versus d, and vg,, [9,58],

6.3.

TRANSISTOR DRIVER CELL MODEL

111

I

I

(a)

(b)

FIGURE 6-2: Illegal (a) and legal (b) macromodel cells for a cross-coupled inverter circuit.

3. ECL gate drive values versus effective load capacitance and input pulse duration [59]. In this thesis, macromodel functions describe moment representation values or circuit element values versus the input waveform slope and output driving-point (or load) admittance. Transistor driver cells and transistor transmission cells are modeled slightly differently. Transistor driver cells are discussed in detail. In the next sections, the circuit model, input parameters, macromodel functions and macromodel extraction of driver cells are covered. Then, transistor transmission cells are covered briefly.

6.3

Transistor Driver Cell Model

Figure 6-3(a) depicts a general transistor driver cell connected to load admittance, Yload(s), which includes all circuit elements in the sub-network. It is modeled by the circuit of Figure 6-3(b). The elements surrounded by a dashed line are macromodeled. Transistor driver cells have distinct inputs and outputs, which are in separate sub-networks. The inputs' sub-networks are solved first, and then the output's sub-network. We assume that the output response has no effect on the input sub-network, which to a good approximation is true for CMOS gates. Miller feedback capacitance of single level logic gates is the only connection between inputs and outputs. 6.3.1 Input Capacitance

A capacitance exists on any cell input that connects to a MOSFET gate. The transistor capacitance is modeled by a single grounded capacitor, Ci,, even though it actually connects to the source and drain. The Cin approximation completely decouples the input and output

112

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

sub-networks. For any input transition an equivalent capacitance, Cin is calculated by Cin

A

Aqi-

=

Cgd(AVin - AVd) + Cgs(AVn - AVs)

where the voltage and charge terms are defined in Figure 6-4. The values of AVd and AV, depend on the input transistor's circuit configuration, so it's often best to determine Cin by measuring Aqin directly while the macromodel extractions are made.

6.4

Macromodel Input Parameters

The transition behavior of a transistor driver cell is governed by two things: (1) the input waveform slope and (2) the loading circuit connected to the output. By carefully quantifying the input signal waveform, Vin(s), and load admittance, Yload(s) with a single value apiece, macromodel functions are kept compact and fast. Now, the question arises how we can accurately characterize a waveform representation (,(s) or Yload(s)) with a single value. Let us first consider the possibility of using the lowest-ordered, unassumed term in the moment polynomial. By this, we mean M 1 of the input signal waveform 2 and M1 of the driving-point admittance3 . These equal the input waveform's Elmore time and the load's total ground capacitance, respectively. These values as macromodel parameters work well for some circuits, but, as shown in [56], can lead to errors of 100% or more for circuits with large line resistances. Thus, M 1 of V,(s) and Yload(s) are not good macromodel parameters.

6.4.1

Input Waveform Parameter

The waveforms of Figure 6-5 demonstrate why M1 of Vin(s) is a poor parameter. Both waveforms are representative of MOSFET and/or RC interconnect waveforms, and both have identical M 1. However, if these waveforms drive an inverter input, for instance, the responses are noticeably different. The critical section of a voltage waveform which defines an inverter response is the section which passes through the inverter high-gain input voltage region. Thus, a better macromodel parameter for input waveform shape is the amount of time for the waveform to pass through the high-gain voltage region. More precisely, the input waveform macromodel parameter is
tr,in -

Vcr 2

-

crl

(6.1)

where Vr, , Vcr2, tr, and Vr2 are the critical voltages and times defined in Figure 6-5. 1
ifo is the d.c. transition voltage and is always -(Vhigh - Vow) for a logic transition. The load on the macromodel driver cell has no resistive or inductive paths to ground, and is only capacitive. From Theorem B.1 we know that M1 is the lowest ordered, non-zero term.
3 2

6.4.

MACROMODEL INPUT PARAMETERS

113

:..... ........... ........... ..................... o---;-0-40--

Yload (s)

=
-T-

1-2

(a)

0constant inputs I

Yload (s)

0transition input

I

. -1 Ci :. . .. . .. . . .. . .. . . (b)

Yload (s)

Rdc

0-40O*

.

-I

Vdc

(c)
FIGURE

6-3: (a) General macromodel driver cell, (b) Linear network equivalent for a changing

output, (c) Linear network equivalent for static output.

114

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

d
Cgd

+ Vd -

Vin Cgs gs
s

Vin

Cin

+ Vs

I

FIGURE

6-4:

MOSFET

input capacitance.

5

4

3

2

}
.

inverter high-gain voltage region

1

1.5

2.0

2.5

3.0
time

FIGURE

6-5: Representative input voltage waveforms with identical Elmore times, M 1 .

6.4.

MACROMODEL INPUT PARAMETERS

115

This macromodel parameter was first used in [26] and is also used in this thesis. Two things are readily seen. First, the overall delay of the critical line segment can vary. Another input waveform parameter, td,in, is extracted from the input waveform, and the cell output delay is adjusted by adding td,in to correct for the overall shift in input time. Secondly, if the input waveform is in the moment representation, it must be converted to a time domain representation. The possibility of using many moment representation terms (more than just M 1 ) for macromodel input parameters has also been considered. An advantage of using M 1 , M 2 and M 3 , for instance, is that we can avoid the time consuming task of converting each moment representation waveform into the time domain with the double exponential assumed waveform shape. This idea was rejected, for three reasons: first, macromodel functions with third order moment representation terms as input parameters are not smooth. The accuracy of macromodeling is largely affected by the smoothness of the functions; it is difficult to interpolate accurately on macromodel functions that jump around alot, and hence function evaluations are inaccurate. Second, the size of macromodel function tables is extremely large, since (1) table dimensions must be increased to at least three for third order moment representation modeling, (2) to acheive any type of accuracy, very closely spaced macromodel data points are necessary, and (3) moment representations terms may span a broad range of values, even when intelligently "normalized". Third, it is hard to extract macromodel functions from circuit data. Appendix C discusses this topic in more detail.

6.4.2

Output Load Parameter

Unlike other macromodeling efforts, the output load macromodel parameter for this thesis is also based on the time for a waveform-in this case the output waveform-to pass through a critical region. This critical region covers (1) the region where the driving transistors are conducting most, and (2) the critical regions for inputs to succeeding stages. swing as shown in Figure 6-6. To use a time, t 75 % - t0 %, based on the output waveform as a macromodel parameter brings out two problems: 1. the output voltage waveform must be presupposed before the output voltage macromodel functions are known, 2. performing test simulations to compute macromodel functions at regularly spaced intervals of t7 5% - to% is difficult, as this would require iteration to find the correct input to achieve a specific output transition time. Hence, another macromodel parameter, effective load capacitance, Cbf, is chosen for the macromodel parameters. Cff is, very approximately, the capacitance which can replace Yload (), The output voltage critical region is selected as the voltages between 0% and 75%, of the output voltage

116

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

Vcrl = Vo 5
4

critical

output voltage range

3
2

V, r-it= 1.25 v.
c. ,JuL

1

input
0

FIGURE

6-6: Critical range of output voltage.

such that the output voltage waveform of the cell passes through the same end points of the critical output voltage range as the real output-namely, the output voltage passes through Pi and P2 of Figure 6-6. During simulation, effective load capacitance is computed as follows: 1. For each occurrence of a macromodel driver cell, an approximate step response waveform, Vstep(t), is computed for the output node with a simple equivalent circuit substituted for the macromodel cell (Figure 6-7(a)).

2. The effective load for a step input is computed such that the output voltage of Fig-

,.......

:.
: :a

Rd

'
*.

Rdc
+

:*~~ L~

A -e

-t Rdc Cload ~

..................................
(a)
FIGURE

: :...............................

(b)

6-7: Approximating circuit for computing Vstep(t).

6.4.

MACROMODEL INPUT PARAMETERS ures 6-7(a) and 6-7(b) are the same at t = 0 and t = tcr,out, i.e.
tcr,out

117

Cst

=

Rdc ln(Vcr,out/Vo)

where Rdc is the static incremental output resistance
aVtep Rd = R step
1

alout

tep=Vmm

3. Cstep equals Ceff only if the inverter response is fast compared to the interconnect step response, Vstep(t). If the inverter response is slow compared to Vstep(t), then Yload is better
approximated by Cload = Ml,Xad, the total load capacitance to ground.

For each output transition during simulation, the effective load capacitance is computed in the range between C.tep and Cload.4 This is done by comparing the time constants of the macromodel voltage source, Vmm(s), (the derivation of Vmm(s) is described in the next section) and the step response, Vtep(s). Ceff is approximated by
Ceff = Cstep + (Cload - Cstp) 1 + rtp/

1 + step/Tmm

where
rstep MiVtep/MOVstep

and
Tmm - Ml,Vmm /Mo,,
m. -

Note that steps 1 and 2 require more computation, but only once per circuit, whereas step 3 requires little computation, but more often; once per circuit transition.

Example 6.1 What is Ceff for the circuit below when the inverter output time constant, mm, is O.01ns, O.ns and 1.Ons?

static inverter macromodel r= 10k c =.1 pF
0-

,..................................

R dc 961

-

Vinv

I

.02 pF

: Vm mm
0 $

:....................................

:

4

For RC loads Cte p

<

Cltod, and if the load capacitance is a single capacitor to ground, then Ctep = Ctoad.

118

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

Attach the inverter's load to the static inverter macromodel, and solve for Vi,,(s) with V,m(s) = 1, a step input. This gives
Vatep(s) = 1 - 0.106 x 10-9 s + 0.0535 x 10- 8 s2 - 0.0305 X 10 - 2 7 S3 which is plotted with a solid line below. 1.0 (6.2)

.8
.6

.4 .2 0.0 .0
From the value of t,,
Ctep =-

Vstep (t)

25.0

50.0

75.0

100.0

time (psec.)
R ln(.25)t
=

0.0245 pF

which gives the approximate response plotted with a dashed line above. From inspection of the circuit, the total ground capacitance of the load is Cload = 0.12 pF. From (6.2) above, ,tep(S) = M,v,,,, = 0.106 ns, and finally, from Equation (3)
Ceff

=

0.0245 +

1 + (0.106/Tm.)

0.10/955

pF

0.0327 pF for 7mm = 0.01 ns
=
<0.0709

pF for rmm = 0.1 ns
for ,mm 1.0 ns =

0.1108 pF

__

_

It is important to adjust the load capacitance parameter particularly for lines with much resistance. This is demonstrated in Example 6.6 at the end of this chapter, where the input voltage conditions set Ctff to be much different from Cload. Propagation delay errors are about five times less while using Ceff as the macromodel parameter instead of using Clrod as the macromodel parameter.

6.5.

MACROMODEL OUTPUT FUNCTIONS

119

6.5

Macromodel Output Functions

Figure 6-8 shows the linear circuit equivalents for a transistor driver cell in MOS technology. The value of a circuit element enclosed in a dashed box is a macromodel function. The complexity of the circuit differs depending on the order of the analysis. A higher ordered linear circuit equivalent yields a better fit to the true circuit response. Figure 6-9 demonstrates one instance of this by showing simulation waveforms of an inverter and of the three transistor circuits from Figure 6-8. The second order fit is very close in this example. Circuit elements of the linear circuit equivalents are described below: * The no-load voltage source, Vl, equals the open-circuit cell output voltage. fl/,(s) is a moment representation with constant Mo and macromodeled to, M 1 , M 2 , M 3 , ... These macromodels are one-dimensional functions of the input voltage slope, tr,,vn. It is often the case with all but the fastest inputs that V,l traces out the d.c. transfer function between input and output. * The d.c. resistance, Rdc, is the incremental resistance observed at the output after the transition is completed. That is,
Rd = V1 o dc Iout vot

where V,,t = Vo,, for a falling transition and V,,t = Vhigh for a rising transition. * The L,,mm and C,,mm circuit elements adjust the cell's output admittance during the transition. Their values are macromodeled functions of t, vi, and Ceff,Yoad. These macromodel functions and scalar values model the cell output given any input or load condition in the desired range. These functions and scalars (summarized in Table 6-1) form a driver cell macromodel set. A different macromodel set is needed for each transition type caused by a different set of input conditions. For instance, an inverter has one set for a falling output transition and another set for a rising output transition. A full adder circuit may need as many as 24 macromodel sets for the sum output signal and 12 macromodel sets for the carry output signal. Figure 6-10 shows a full adder Karnough map, and marks each input transition that causes a different output transition. Depending on circuit implementation, some macromodel sets may be shared, if they are equal. Embedded in the moment representation simulator is a logic simulator. Each cell has a procedure to calculate the output logic states. Any change in an output state causes the output transition waveform to be computed with a specific macromodel set. The operation of the logic simulator is described by Brocco [26], which also discusses the issues of conflicting and overlapping transitions.

1_----rrmlllli_111_.111111111111_1_1

_11___11_111_1_111I

120

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

Rdc
-1I

output

Cin

p1

Vm mm I
L

I

I

(D.C. resistance approximation)

input
or

Rde

output
I
L
._ _I

Cin

I
I

V.
t_ _. _ ::

%_

[I
C

Vin

Vmm'

mm
or

._

-- LL,-,,

I

(First-order approximation)

Lmm input
0Vu

I T 7__ ___. L ----

output

-J

I

C,

._

Vin

-in?

Vmm

I
L .j,

I I

' i .iIL

Cmm
.,

(Second-order approximation) FIGURE 6-8: Transistor driver cell linear circuit equivalents. Elements in dashed boxes are not constant, and depend on input waveform and output load.

I

-

'6.5. MACROMODEL OUTPUT FUNCTIONS

121

5

(volts)

time (nsec.)

FIGURE 6-9: SPICE simulation of true inverter and linear circuit equivalents.

t0 ,nl(tr, V ) Mo,nl

M1,nt( t, in) M 2,nl(t r, Vin)
M3,nl(t, vin)

Rdc
Cmm(tr, Vn , Ceff, Yload) Lmm(tr, vjn, Cef, Ylod)

Table 6-1: Macromodel functions and scalar values of a third-order macromodel set.

I_-·I_

1_1_11111111_. - -1__·11___

^-

122
PaE

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

Cm\ 00
0 1

01

11

10

Cin,\ 00
0 0 I
0

AB

01
W e

11
1
|

10
In

TY

AI

0A

IL IO

IT

1-

-f -+;

I

-

'L0I ;-

-

I

1

.4

1
Cot out

I

Sum

FIGURE 6-10: Full Adder Karnough map with output transition possibilities. Each arrow represents a macromodel set for an output transition. The sum function has 24 macromodel sets-the maximum for a 3 input combinational function. The carry function has 12 macromodel sets.

6.6

Extracting Macromodel Function Values

This section describes the procedure for calculating values in a driver macromodel set. Computing macromodel numbers is called macromodel extraction. The amount of computation needed for macromodel extraction is not a critical concern, since this is done once per cell. The computation may, in fact, be considerable. This will be detailed later. Macromodel numbers are found from any source of transistor cell waveform information. Namely, the macromodels can be extracted from waveforms generated from SPICE simulations of the cell, or from waveforms measured on the real cell circuit, if possible. All macromodel functions presented in this thesis derive from SPICE simulations. Test circuit (a) of Figure 6-11 extracts the scalar value for Rdc = aVout/Alout. This test circuit is done under static conditions. The procedure for extracting the macromodel functions is to conduct macromodel extraction tests with closely spaced increments of macromodel parameter data points. Test circuit (b) of Figure 6-11 extracts Vnl(t) waveforms of a transistor driver cell. The response at Vut is measured when transitions with different tr,i,, are applied at the input. It has been observed that the input waveform shape which gives the best overall matching to true waveforms is a combination of a ramp and exponential tail, as shown in Figure 6-12. The output waveform moments are extracted from the time domain waveforms as described in Section 3.5. The macromodel function to,v,(tr,v,,) is defined as the time delay between td,in of the input waveform and to of the output waveform. Test circuit (c) of Figure 6-11 extracts the admittance macromodel parameters, Cmm and Lm,m. These tests are performed with different combinations of input signal slope and load The output load is a pure capacitance in the tests, so Cff = Cload. For each capacitance.

test with specific load capacitance and input waveform slope, the measured output waveform

6.6.

EXTRACTING MACROMODEL FUNCTION VALUES

123

Vlo w or Vhigh

{

00--C

constant
inputs

C

CELL transition input Vlo w or V high -

output

out A Vout V Vout 1+-

Vlow or Vhigh

(a) Test circuit for extracting Rdc.

Vlo w or V

ut r,Ln

nl

(b) Test circuit for extracting Vn,(s) =
2

eto.I v-)Mo,"a- Ml,nL (tr, V,,) s + M2,,l(tr, ,

S

T.- '

V low or Vhi

Cload t i r,Ln

(c) Test circuit for extracting Cmm(tr, vin, Cff,yoad) and Lmm(tr,?v,
FIGURE 6-11: Macromodel extraction test circuits.

Ceff,Yload)

-----~cll

'P~--

-·-

-I---··-C11111

· IIX·lll-

I

-- I

--

---

124

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

5

4

Exponential Tail
3 2

Linear Portion
1

5

15 ame nsec.)

FIGURE 6-12: Test input waveform.

is converted from a the time domain into a moment representation. Values for C,,mm and Lmm,, are found such that the second order moment representation of V,t(s) is the same for the cell test circuit and the second order linear equivalent circuit in Figure 6-8. For this to be true,

1 + Rdc(Cmm + Clod)S + Lmm(Cmm + Cload)

2 '

In terms of moment representations (with e-' to suppressed),
S
2

2

+

Mo,v. - Ml,vIs + M2 ,V, 1 2 1 + Rdc(Cmm + Cload)s + Lmm(Cmm + Cload) s2

This equation necessarily means that A 4o,v., = Mo,vt as we expect. Solving for Cm, and
Lmm,

AM
Cram =

Rd

Cload,

(6.3) (6.4)

Lmm =
where

Cmm

Mlout = M1,vo,,/Mo,

AM1 = Mlvo, - Ml,t

Mo

and

AM2 = M2,Vout - M 2 ,,Vn,

2Mo

6.6.

EXTRACTING MACROMODEL FUNCTION VALUES

125

Example 6.2 Plot macromodelfunctions for the following CMOS inverterfor a falling output.

Vdd = 5v. L= 1.6 um W==8um input output L = 1.6 urn W =4um

1-

Using SPICE5 for values of Ceff =0.1, 0.2, 0.5, 1.0, and 2.0 pF, and t,i, =0.02, 0.08, 0.2, 0.8, 2.0, 5.0 and 8.0 sec/v., a total of 35 simulations, the following macromodel set is derived. The scalar values are: Mo = -5v., Rd, = 961Q.

n-channel SPICE parameters: Vto = 0.75v., po = 520 cm 2 /v sec, -y = 0.16 v1/ 2, t,, = 250A, Xj = 0.2pm, 3 2 16 = 0.2 x 10-3pF/Pm, Cgso = Cgdo = Ld = 0.16/m, Nub = 1 X 10 cm-3, C) = 0.23 x 10- pF/pm , Cj, 2.2 x 10-4pF/pm, R,h = 52.5Q.
5

2 p-channel SPICE parameters: Vo = -0.75v., po = 190 cm /v sec, y = 0.55 vl/2, to, = 250A, X, = 0.25pm, 2 16 - 3 = 0.6 x 10-3pF/pm, Cgo = CgdO = Ld = 0.2pm, N,,b = 1 x 10 cm , C = 0.67 x 10-3pF/Jm , C, 2.8 x 10-4pF/pm, Rsh = 120Q.

i

--------------------

------------------

--·-

----------------------

-..

"Il--~ll-~~~~Y~"~I---

----·LI

126

CHAPTER 6.

I

-

MACROMODELS FOR NON-LINEAR NETWORKS

--

--

d

*

(nsec) 6.

4-

2.

0O 0 , 2 , 4 , 6

8
8

tr,in (nsec)

V,I macromodel functions vs. input transition time. The square root and cube root of M2 and M 3 are stored as the macromodel functions respectively. This makes all units be time, and keeps the macromodel functions closer to linear.

I

6.6.

EXTRACTING MACROMODEL FUNCTION VALUES

127

5:
CM (mm

!

(pF)

4

3

2

1

0
II

I

1
-

I
%

r
X

0

2

4

~~--

8

trin (nsec)
Cm,, vs. input transition time and Cff.

1.5
Lmm

(uH)
1.0

.5

-

0.0
1 · -. . _

0

4

6

tr,in (nsec)
Lmm vs. input transition time and Ceff.
. . .~~~--

128

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

Example 6.3 Plot macromodel functions for the shown path of the following CMOS circuit.

0 0.2 pF
: ..
· .......

0.4 pF
_.

................................................................................

SPICE

simulations using the same transistor models and macromodel input parameter data

points give the following functions. The scalar values are: Mo = -5v., Rd = 961R.
14.
-

L

*

(nsec)
12
10

8.

6.
4-

2.
0.
9 LI

4,, I~I

i ----

A

0

2

4

6 tr,in

·

8 (nsec)

r

T V a macromodel functions vs. input transition time.

6.6.

EXTRACTING MACROMODEL FUNCTION VALUES

129

1.2
"-ofL

{Ceff = 2 pF}

1.0

Cmm (pF)

{Ceff = 1pF)
* ,~~~~

.8

L**

*

*

__

.6
-" -A: 4-

{Ceff = .5 pF)
.. .--

.4

ra
.2

a -n

{Ceff = .2 pF)
Qn .

.'m
0

4

x {Ceff= .I pF} 6
tr,in

--

-

8
(nsec)

I

Cm
.7 .6 .

vs. input transition time and Ceff.

(Ceff = 2 pF)

Lm (uH) .5
,b

(Ceff = 1 pF)

*

L* .4

*

*

.3
_ _

--

Ik.

{Ceff= .5 pF)

.4

.2

-

A

.1
Y
_

ICeff = .2 r Fl
--

i

)

{Ceff=.l pF} ~~_ ~___
'

-

V L

o

2
t r,in

(nsec)

Lmm

vs. input transition time and Ceff.

130

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

order maximum floating- minimum floatingpoint numbers point numbers 1 2
37

77 140
150

18 30
34

Table 6-2: Number of single precision floating point numbers for a macromodel set.

From the above two examples, we can make these interesting observations: * In the first example, the lV,l(s) macromodel functions are very close to linear functions of time. This is to be expected since V,,(t) traces out the same d.c. transfer function at linearly increasing rates.

* In the second example, the AMl,vnl, M2,v,,, ... macromodel function values are small,
indicating Vnl(t) is approximately a voltage step. Also, tov,, is much larger for the multistage macromodel than for the inverter macromodel. * In the second example, admittance macromodel functions are independent of the input slope. This observation and the last observation are true because there is significantly more restoring logic between the input and output.

6.6.1

Macromodel Extraction CPU Time

The CPU time required to extract a complete macromodel set depends heavily on the cell's circuit complexity. The macromodel examples in this chapter require approximately 5-40 minutes for SPICE simulation on an HP 9000/350 workstation 6 per macromodel set. The same workstation required less than one-half minute to extract the macromodel functions for one macromodel set from the simulation waveforms. To extract all macromodel sets for a cell may require several hours of CPU time. The SPICE simulation and macromodel extraction is done automatically, and is controlled by UNIX's "make" program facility.

6.6.2

Macromodel Memory Requirements

Macromodel functions are stored as one-dimensional and two-dimensional arrays. parameter data point values are stored in one-dimensional arrays, and index the macromodel function tables. Each third-order macromodel set takes no more than about 150 floating point numbers for all macromodel functions and data points (see Table 6-2).
8 7

The HP 9000/350 has approximately a 3 MIPS processor. With 2 nd order admittance model.

6.7.

TRANSISTOR TRANSMISSION CELLS

131

For very linear functions, the size of a macromodel set can be reduced automatically with a macromodel trimming program. The trimming program tries to locate two macromodel values that are separated by as much as possible, provided all intermediate macromodel points are offset from the line between the end-points by no more than a prespecified fraction (e.g., 1%) of the total macromodel function range. This type of trimming can considerably reduce the macromodel function array size in Example 6.3, for instance. The size of a macromodel set is further reduced in some cases by raising the macromodel parameters to a power. This linearizes some macromodel functions that are not originally linear. For instance, the C,, function of Example 6.2 can be approximately linearized as shown in the three-dimensional plots of Figure 6-13. The procedure for this is automatic, and is outlined below: 1. Find logarithms of macromodel scale values. 2. Perform a linear regression on the macromodel functions with the logarithm scale. 3. Find function slope with linear regression, and raise scale values by the slope. 4. store the slope values in the macromodel set, so future macromodel functions calls use the same parameter. For the inverter of Example 6.2, two macromodel sets are needed, totalling to about 220 floating point numbers or 0.86 KByte. In comparison, a three input, full adder needs about 3300 floating point numbers or about 3.2 Kbyte. While it is true, in general, that as the number of cell inputs and internal logic states increases, the internal logic complexity increases and the macromodel sets become simpler; it is also true that the number of macromodel sets increases exponentially, effectively limiting the number of cell inputs to around a dozen.

6.7

Transistor Transmission Cells

Transistor transmission cells are used to model the non-linear effects of isolated transmission gates or pass transistors. Their prevalence in MOS circuits makes this an important cell type. Brocco [26] was the first to incorporate transmission gate macromodeling into RC tree solutions. Once again, these methods are joined into the moment representation simulation methods. The macromodel parameters are basically the same. The principle difference is in the waveform and circuit representation. The moment representation allows for a more accurate solution, since the methods in [26] are effectively a first-order macromodel and a second order linear network solution. A large number of issues must be addressed to correctly model MOS transmission gates properly. The reader should consult [26] or [56] for a thorough understanding of these. These

I__I.__11I

-sl^lllp--·-----I·

^Illlllly-

·ll*Y

1I^._-·--I_

··^1.

·11YXIII..· -1I·II---1---·-^I

·IIIP--.·--···IX^I

.---

*·lll··__·lllllp·ylC·llll·lllllll·l

132

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

rin

Cef

0.5
n l

efJ

FIGURE 6-13: Approximate linearization of a macromodel function.

__

6.7.

TRANSISTOR- TRANSMISSION CELLS

133

Y drive

conducting pass cell

Y load

m

m

FIGURE 6-14: Conducting transmission cell

--

unchanging node states Y drive

I

changing node states Y load

pass cell

-"

V high

or
Vlow
i m m m

FIGURE 6-15: Switching transmission cell

issues are discussed briefly here, except where significant differences arise in using the moment representation. Solutions for transistor transmission cell simulations separate into two distinct problem types depending on where the input signal transition is applied to the circuit. In a conducting transmission cell problem the transition is applied to the driving gate as shown in Figure 6-14; in a switching transmission cell problem the transition is applied to the controlling inputs of the transmission gate as shown in Figure 6-15. The two problem types are discussed separately below. 6.7.1 Conducting Transmission Cell

The d.c., first and second order linear circuit equivalent models for a conducting transmission cell are shown in Figure 6-16. They are, in short, just the admittance portion of the linear circuit equivalents for a transistor driver cell. The macromodel parameters for the linear circuit elements are, once again, a signal tran-

_____·

_1

__11_1

1111

11

1

__·1_1·_Ll··___·____111_··

11

11·-(IIIII-I1--·-1111^---1·.

I1_LI1--l_-.

IPI·--·ll

--·II_·_

-·I

I

_

134

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NETWORKS

input
wT~"'---------'-_

Rdc
AAA

output
-

'V V

(a)

input

Rdc
A -A A "J J
VVV

output

Cin

.,_

!I

C mm

(b)

Lmm

input
0C

dc

L
l

Cin

I I

X , L,( r _ ___

output
! I I

, = I

I I .

I
I I

,

Cmm

L__

(c)
FIGURE 6-16: Linear circuit equivalents for a conducting transmission cell Elements in dashed boxes are not constant, and depend on input waveform and output load.

6.7.

TRANSISTOR TRANSMISSION CELLS

135

sition time and an effective load capacitance. The procedure for computing the parameters is described below. * A precursory, first order simulation is performed on the sub-network with Rdc substituted for the transmission cell (Figure 6-16(a)). terminals of the transmission cell. This gives- approximate waveforms at both

* The input transition time is the time required for the signal, Vl(t), on the driving end of the transmission cell to traverse through a critical region. The actual parameter is defined, as in (6.1) and Figure 6-5 as
tcr2 -tcrl Vcr 2 - Vcrl

* The effective load capacitance is defined for Yload in the same way as for an driver gate, and as described in Section 6.4. The behavior through the critical region of V2(t) determines
the value of Ceff.

* For both parameters, critical voltages at 0% and 75% of the total transition are used. Fewer macromodel functions are needed for transmission cells than for driver cells. For a conducting transmission cell, these are:
Rdc

Cmm (tr,V
Lmm(tr,V,

Cff )
Cff )

To determine the macromodel functions, experiments are performed on the circuit in Figure 6-17. As with transistor driver cells, the experiments can be done with SPICE or with real transmission gate circuits, and the input signal slope and load capacitance are stepped through the range of expected values for circuit operation. The method for computing the macromodel function values from experimental waveforms is the same as for a transistor driver cell, and is described in Section 6.6.

6.7.2

Switching Transmission Cell

Switching transmission cells can be difficult to model. Single transistor transmission cells which are typically found in NMOS circuits are more easily modeled than the more complex two transistor cells of CMOS circuits. Single transistor transmission cells are modeled with the linear circuit equivalent models shown in Figure 6-18. The switch closes at time to, where to depends on the input waveform,
to = to,mm(tr,Vc) + t d,Vc-

A non-zero d.c. voltage on Vth delineates a threshold drop on the pass transistor for the particular transition. The other circuit elements model the admittance properties of the pass transistor

___

1 _________1____111_·1--·-_1__1----_--

1_11111

--- -

--.- _i_·-

--

.·-.·^--

-·_1---1---11111

136

CHAPTER 6.

MACROMODELS FOR NON-LINEAR NET


更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图