0:00

[MUSIC].

So here in lecture 12.7, we're actually going to get the delay result that we

want. And so, what we did in the previous

lecture is we said, you have a routed wire.

It's got a complicated geometric shape. The only way to really analyze that is to

turn it into a circuit. We turn it into a special kind of a

circuit called an RC Tree, it's a tree made of resistors.

And at every intermediate node, there's a capacitor hanging off.

What we're going to show you is that there is a very special formula, it has a

famous name. It's called the Elmore delay.

and the Elmore delay is, a number, it's a time, it's a delay which we can calculate

through one walk from the root of the tree, to the leaf of the tree that's the

gate. The driven gate to which you want to know

the delay. There's a very simple walk from the top

of the tree to the bottom of the tree. Using the resistor and capacitor values

we calculated for the geometric wire, that will get us a delay.

So what we're going to do in this lecture is we're going to show you how to take

the RC tree use it to do something interesting to calculate the Elmore delay

for the wire. So, once we have the definition of the RC

tree, we can actually do a lot of interesting analysis.

One of the things we could do is, we could do some electrical engineering kind

of detail and I could actually derive at the circuits level, the very interesting

delay result we're going to show. but, since not everybody in the class

necessarily has a circuits oriented background, I'm just not going to do

that. So, the really nice thing about the RC

tree model is that even though it starts as a circuit it turns into a simple tree

object, I mean it's really a data structure.

And there's a special computational walk on the tree that gives us all the delay

information we need. So it is fair to say that there is almost

no circuits for us. There's just the computational recipe for

how you use the tree. So let's go see how that works.

So here's the RC Tree in it's general form.

It's a tree of resistors, and, and so I'm showing you the tree again.

But now I'm actually labeling the nodes so we can actually talk about it.

So, you know, there's a resistor from a to b, b to c, and c to e, a resistor from

b to d, and d to f, it's a tree. and there are capacitors hanging off all

the intermediate tree nodes at a, b, c, d, e and f and what hanging off means to

a circuits person is disconnecting the node to ground.

The Root of the tree is where the signal is input, and so that's the A node.

The Leaves of the tree are the driven outputs, and so those are e and f

respectively. And, you know, for a second we might just

redraw this like a graph, so that, you know, to just take away this sort of the

circuits feel of it. And so it's again, it's the same tree.

There's resistors, there's a box labeled R and there's a capacitor, a box labeled

C. And there's a tree of resistors from a to

b, b to c and c to e, b to d and d to f. And at a, b, c, d, e and f.

There's a c box hanging to the ground. So this looks a little less like a

circuit and a little more like a graph, if that makes you feel more comfortable.

there's two missing pieces of detail on the circuit side, which is that you have

to model the driver and you have to model the driven gate.

So the thing that I'm showing, you know the thing in the middle of this diagram,

a, b, c, d, e, f, nodes in it, resistors and capacitors, that's the wire.

You still need to model the gate that drives the wire, that's the driving

input, and that turns out to be modeled as, as basically a battery, a voltage

source that turns on at time zero. With a voltage of 1, through a driving

resistance. I'm just going to put a star by the

resistance. and, you have to model that gates that

are being driven, and each of those things actually just gets modeled as a

capacitor. So, you build the RC tree for the wire,

you need one more resistor to model the source gate.

You need, two, a capacitor for each of the target driven gates.

And then, you can actually do the analysis on this thing.

4:04

So, just to sort of, you know, summarize in a sort of a cartoon.

I've got a wire, i've got a, a gate driving a wire, driving another couple of

gates. I turn that into a tree, it's a tree of

resistors. In this case, a, b, c, d, e, f is the

nodes. And at every intermediate node, a

capacitor hanging off of it. I add to that another resistor and a

voltage source. That models the gate that's driving

things. I add to that also, another capacitor for

every gate that is, being driven by this wire.

And what I'm actually going to be bale to do is a very simple computation on the

tree to calculate a delay number for each output of the tree.

And one of the things that's really great is I'm going to get a unique number for

every output. So I'm going to really physically model

the shape of the wire. And so I'm going to get maybe a long

delay to some outputs, and a short delay to other outputs, depending on what is

correct and physical for the shape of the wire.

So this is this sort of very famous result, we're heading toward and this has

a name. It's called the Elmore delay.

So it's named after a physicist, famous Physicist Elmore.

this was derived, amazingly, way back in the 1940's for certain kinds of circuit

applications. And then it was sort of resurrected, like

40 years later, by Penfield, Rubinstein, and Horowitz for these RC trees because

it turns out to be useful for, for you know designing modern integrated

circuits. It's famous enough that if you type

Elmore delay into Wikipedia, you will get an article on it and you can see all the

original references and things like that. For our purposes, what's wonderful is

that it's very simple and very useful and has a very easy computational recipe.

So, here's the tree again, and I've got the input driven gate modeled by the

resistor with a 5 on it. And I've also got the 2 capacitors at

nodes e and f at the output added. So I've got the driving gate and the

driven gates and it's, again, a little tree of resistors with nodes a, b, c, d

and e. There is a resistor of size 2 which we

know is a and b resistor 4 between b and c resistor 1 between c and e resistor 1

between b and d resistor 3 between d and f.

And there's a capacitor of size 1 at node a, 2 and node b, 1 at node c, 1 at node

d, 3 and node d, and 1 at node f. So, this is the example, we're going to

see this several times and there's a very simple computations, so the Elmore delay

is tau to time. We said tau is to be 0 and you walk down

the path of resistors from the root to the leaf where you want to calculate the

delay. And at every resistor you do the

following, you take the resistor value, you are on and you[COUGH] multiply it by

a number. And that number is the sum of all the

capacitors you can see downstream. And we are going to talk about what this

means. what's a downstream capacitor?

it's any capacitor reachable in the tree below this resistor.

So if current is going through this resistor and heading to the bottom of the

tree it's any capacitor that can take that current.

Alright, so let's be concrete on this example.

I've got resistor Ri equals 2 between nodes a and b.

Alright, what are the downstream resistors for node Ri?

And the answer is, the capacitors at node b, c, d, e, and f.

So, the resistors at node is between nodes a and b, what is the downstream

capacitance? Alright, any current going through node

through resistor Ri equals 2 could end up on capacitors at nodes b, c, d, e or f.

So you're going to take Ri is 2, and you're going to multiply it by 2 plus 1

plus 1 plus 1 plus 3. You're going to add that term and you're

going to keep doing this computation. So, simple as that.

So this is just a version in words. You know, Ri is equal to Ri is to the

resistor in the tree. The term we would add to the Elmore delay

is 2 times 2, plus 1, plus 1, plus 1, plus 3, okay?

So let's just take a look at it. So here's the tree again, a, b, c, d, e,

f, is the nodes. we want to calculate the delay to a

particular point in this tree. So, where do we, where are we looking?

we want to go down the resistor, the 5, the resistor that goes into node a, a to

b, b to c, c to e. We want to calculate the delay for the

capacitor that's at node e, alright? and so we just use the formula.

And the formula says you set tau to be equal to zero and then, you start walking

down the resistors. So you walk down the resistor that's a

value five. And you add together all the capacitors

down stream, which in this case is all the capacitors, 1 plus 2, plus 1, plus 1,

plus 3, plus 1, okay? And then you go further, and you go to

the resistor with a value of 2 between a and b, and you add all those resistors

down stream, 2 plus 1, plus 1, plus 3, plus 1.

and then you keep going, so we're going to go down the resistor of value 4,

between b and c. While the resistor, the capacitors you

see now in front of you are 1 and 3, so 4 times 1 plus 3.

And then you get the resistor of value 1 between c and d, multiply that by the

capacitor 3. 45 plus 16, plus 16, plus 3, if I did it

right, it's 80, 80 is the delay to that note, it's as simple as that.

if you're not, very knowledgeable about the circuits let me offer you an

alternative analogy. So this is like a, like a branching

stream. So I've got a little picture of a stream

here, sort of dividing, and dividing, and dividing.

An the goal is that you are downstream, and you are trying to fill your bucket,

okay? And what you care about, is how fast you

can fill your bucket. Now unfortunately, at every branch point,

somebody else has a bucket, and so the farther you are downstream, the less

water you can get. Alright, so just to sort of draw this,

there's water going in, it's a fixed supply up at the you know mouth of the

river, the source of the river. And there you are with your bucket way,

way down at the, one of the ends of the branch points of the river.

And unfortunately, everybody else at each one of those branch points has a bucket

and so the water that's going in that's a fixed limited supply is filling up

everybody's bucket. What you want to know is how fast you can

fill your bucket. All right, how fast can you do that?

So what matters? What matters is the width of the upstream

branches, because that's going to tell sort of like how much water can go down

those branches. And the size of everybody else's bucket.

11:43

And y'know your bucket is the gate that is being driven.

How fast you can fill your bucket is how fast the signal will lets say rise, going

from a logic 0 to a logic 1, is how fast you can get a 1 from the source, to the

sink in this design. So, the analogy is, you know kind of

soft, but it's actually surprisingly good for this particular example.

So, a little bit of a circuits aside, if you actually care about this you know,

what exactly is the Elmore Delay Modeling?

imagine that you could model the path from the input to the output of this

particular circuit, so here's my tree again and I'm modeling the path From the

driver, through a, b, c, d, e. Imagine that you could actually model

that path with a circuit that had exactly one resister and exactly one capacitor.

It would be a so called equivalent circuit, you know what I mean?

The real circuits got lots of resistors and lots of capacitors.

But suppose you decided to model that, you know, the, the path from the input to

this one output, with everything else in the tree accounted for, with a single

resister and a single capacitor. any circuit that has a single resister

and a single capacitor, has a, a response when you sort of you know, close the

switch, current flows, you charge the capacitor.

You get a, you get a mathematical form that looks like you know, the voltage

asymptote that it's going to go 2 times 1 minus e to the minus t over tau.

Right, and that tau is basically you know, one resistor, one capacitor

circuit, the resistor times the capacitor, okay?

if you were to model the input to the output with everything else in the tree

accounted for as a single R and a single C and you get a single so called Time

Constant, tau, what tau would that be? And the answer is, it would be the Elmore

Delay. That's exactly what this thing is.

If you want to model this thing as the best approximating circuit that is

pretending to have one resistor and one capacitor that circuit has a time

constant, that's the Elmore delay. So it's a real interesting circuits

derivation which unfortunately we don't have time to do.

But if you don't know any circuits you don't need to know any circuits.

All you need to know is that you can walk the tree.

Multiply resistors by sums of capacitors in front, downstream.

And you can get a real delay to any given point on the wire.

So that's a wonderful and useful thing. Let's go see what we can do with it.

[SOUND].