0:00

[SOUND].

So here in lecture 12.8, we're going to finish our exploration of timing.

And we're going to finish our exploration of the wire geometry electricity side of

timing by applying the Elmore delay to some interesting examples.

The thing that's really beautiful about the Elmore delay, is that, for any wire

that can be modeled as an RC tree. I can ask a really detailed timing

question, so you tell me all of the lengths of the segments, you tell me all

of the widths of the segments, you tell me what's driving the wire, you tell me

what the wire is driving the driven gates.

I can tell you many delay information you want.

You want to take one of those wires and make it a little bit longer?

I can tell you what happens. You want to take a segment of a

complicated piece of fan out kind of a wire and say oh, the router had a little

problem and it made that wire a little bit longer or a lot longer.

What did it do to my timing? I can answer that.

You want to go play some interesting electrical optimizations?

Grab a segment of a complicated distribution network.

Grab the wire and make it a little bit wider and ask what happens to all the

outputs. The Elmore delay can do that.

So, what we're going to do is we're going to do a lot of little examples of

wired geometry. We're going to walk the tree and we're

going to show what happens as we change element values, widths, and lengths of

the wire and show you how great the Elmore delay is for calculating that.

And then, we're going to wrap all of this stuff back together by saying, look, now

for a routed wire, I can get you a pretty accurate delay value, and so, I can put

that back in the delay graph to do the static timing analysis.

And so all of the questions we asked at the beginning, I synthesized it, I mapped

it, I placed it, I routed it, does it actually run at a gigahertz?

I can actually answer those things now in a pretty accurate way.

So let's go do a bunch of Elmore examples to finish off our analysis of timing.

So, let's go have some fun with the Elmore delay.

So first the Elmore delay formulas are just immensely useful and, you know,

hugely practical widely used. They're simple enough for layout folks to

use them in algorithms, but they're accurate enough that they beat simple

length-based sort of schemes. I will admit that it is not the only

model that exists. there are more sophisticated models.

and they're not so accurate that you can avoid some later verification with, with

more sophisticated electrical models. The Elmore model is a so-called single

time constant model. It says, if you were to model my circuit

as a, a, an equivalent circuit with one resistor and one capacitor.

What r times c value would you use? you know, you could also model it with

two equivalent r's and c's, three equivalent r's and c's, four equivalent

r's and c's. That's what a higher order model is.

You can get better models of more sophisticated behavior that way.

We don't need to do that. we're just going to go with a single the

single time constant model, because it's so easy to compute.

lots an lots of applications, but for us, you know, we can take a real, a real

routed wire with real geometry and we can build a real delay for it.

a unique delay to each of its pins. and we can use it for something like you

know, static timing. So here's a very simple little tree

circuit. the electrical parameters.

Lower case r is 1. Lower case c is 2.

So the resistance is lower case r times the length divided by the width.

The capacitance is c times the width times the length.

So it's just a little tree circuit, you know?

from node a to b, the width is 1 and the length is 20.

From nodes b to c and b to d, the width is 1 and the length is 5.

From nodes d to from c to e, c to f, d to g, and d to h, those four segments, the

width is 1 and the length is 2. if we just take one of those segments,

let's say the width equals 1, length equals 5, segment from node b to node d

the first thing you do is you calculate the resistance of the capacitance.

And you, you know, you build the r and the two c's of the pie model, so there is

nodes b and d, the resistor from b to d, and the two capacitors on the end.

If you just run the formulas, you'll find that the resistance is 5, the capacitance

is 10; we put half the capacitance at each node, so there's a 5 at b and a 5 at

d. And, of course, remember, that every wire

segment creates a capacitor on each end. Okay, so there's a couple of, more

capacitors you have to add at node d. There's three capacitors at node d, and

you have three capacitors to add together to get the, the final c value for that

node of the tree. So here's what you get, so here is the rc

tree for the interconnect alone I'm showing you the tree on the left, you

know, a, b, c, d, e, f, g, h. I'm again showing you the highlighted

wire from b to d, and on the right-hand side, I'm showing you the RC Tree, right.

So from a to b there's a resistor of 20, from b to c, and b to d there's resistors

of 5, from c to e and f, from d to g and h there's resistors of 2.

There's a capacitor of 20 at node a, 30 at node b, 9 at each of nodes c and d,

and 2 at nodes e, f, g and h. All right?

and I've got the highlighted five resistor, which is the bd resistor, just

so you, you can have, you can be calibrated.

All right? So that's what the core of the wire looks

like if we turn it into an RC tree. Now, we still have to add a driver and a

driven gate. So let's say there's a driver that adds a

new node at the top of tree, aa, with a resistance of 20.

and that there's a load representing each driven gate at nodes e, f, g, and h, with

a load 1. Well, I'm going to get the same tree

again from a, b, c, d, e, f, g, h. Only now, there's going to be a resistor

going from this new node aa at the top to node a of size 20.

Okay. So that's just, you know, where the

driver goes. And each load is going to load one more

to the capacitors at nodes e, f, g, and h at the bottom of the tree, so those

capacitors go from being size 2 to size 3, but everything else is the same.

And so, here's my RC tree. I can actually ask a delay question of

this. Now, since this is a symmetric tree, I've

only got to compute one path, I mean each path is the same.

There's a 20 resistor from AA to A, from A to B a resistor of 20, B to C or D a

resistor of five c to e and f, d to g and h resistors of 2.

symmetric capacitor, well, there's one capacitor at 20 at node a, 30 at node d.

But symmetric capacitors c and d are 9, and symmetric capacitors of size 3 e, d,

f, g and h. So remember the recipe, you said tau is a

0. You walk down the route to the leaf.

At every node, you multiply the resistor. You're on by all the capacitors in front

of you. So let's just walk down the right-hand

path to node h and what do you get, you know?

So you get the, the resistor of size 20 between aa and a, multiplied by 20 plus

30 plus two 9s plus four 3s. Going further, the resistor from node a

to b is 20 times the capacitor 30 plus two 9s plus four 3s, okay?

Resistor of size 5 between nodes b and d. one 9 and two 3s, that's the capacitance

resistor of size 2 from node d to h multiplied by single capacitor 3 in front

of it. Add that all up, if I did it right, 2881

inappropriate units. Right?

Very easy, very simple. I can calculate the delay to any node in

my RC tree. But wait, there's more.

There's other cool things. You know, the layout can do bad things to

your, to your placement. It can do bad things to your wiring.

what if the length of the wire gets bad? Right?

Or either even the width of the wire, we'll do that next.

So, you know, let's change the length on one wire segment, suppose we re-routed or

something. And suddenly it's a horrible wire.

So the wire from b to d is this horrible green snarl.

And so, instead of having a nice short length of 5 as it had previously, it has

a length of 40. Okay?

And so, if you run the formulas again, you'll get a resistor of size 40, and you

get capacitor also of size 40 at nodes b and d.

The resistance increases for this much longer wire.

The capacitance increases for this much longer wire.

This whole circuit is different. It is no longer symmetric.

now, let's go to right side and the left side.

So I've got a little tiny picture of the, of the sort of the, the wire segment on

the left side of this slide 85. let's ask the question, what's the delay

to the leaves? So things are a little different now, you

know, between node aa and a, there's still a resistor of, of size 20.

And at node a, a capacitor of 20. From a to b, a resistor of 20.

But now, from b to d a resistor of 40, and as opposed to from b to c, a resistor

of 5. You know, that, that green wire is

longer. The capacitor at node b got bigger.

It's now 65. The capacitor at node d got bigger, it's

now 44, because that wire is longer. It's got more capacitance.

This tree's not symmetric. The capacitor at node c is now 9.

All the resistors form ce to cf and dg to gh, those are all still two and the

capacitors at the bottom are all still three if you were to run the Elmore delay

formula down the right-hands side, you're going to find the delay 7606.

And if you've run it down the left-hand side, you're going to find that its 6851.

Well, that's interesting. I'm not surprised that the delay got

bigger on the right-hand side, because the wire is longer.

I am perhaps surprised that the delay got bigger on the left-hand side, why did

that happen? And the answer is I have a sophisticated

electrical model here. That big wire has a whole bunch more

capacitance. The current that's coming out of the

driving gate, right, has to fill everybody's buckets.

So as well as filling the buckets of the left-hand gates to sort of drive their

capacitors to a voltage that makes a one fast enough, I'm also filling the buckets

associated with the big green long detouring wire.

So what's interesting is that, even though you expect the wire to make the

gates on the right-hand side slower, the wire makes the gates on the left-hand

side slower too, just because it's got more capacitance.

And that's a real, accurate, honest sort of physical assessment of the problem.

The thing that's beautiful about the Elmore delay is that it just works.

Right? It works for the real, actual, physical,

geometric shape of the wire and it gets the delay from the driver to each of the

individual, fan out points in the wire correct.

That's a great thing. You can even do cool things like take the

width of the wire and make it wider. People plays games like this when they're

routing complicated electrical artifacts like clocks.

Okay? So what if we take the wire from b to d

and we make it wider now and not longer? Oh, what happens is that the resistance

gets smaller, but the capacitance gets bigger, so the right side has a delay of

six 6436. The left side, a delay of 6481, so you

know, yeah the right side delay is different than the left side delay but in

a different way. the outward delay allows us to play these

kinds of parameter games with our wires to balance things, to sort of compute

correct and reasonably accurate delays from the driving point to any of the

driven gates. It's a really great model and it's really

simple. So, we've sort of, sort of, finally

fulfilled the promise that we had at the start of this lecture, which is that if

you had gates and wires, I can actually model everything.

So the first half of this lecture was how do you deal with the gates?

ATs, RATs, Slacks, algorithms that walk through gigantic delay graphs with

millions of nodes, and touch them not, in a not very complicated way.

ATs, RATs, and Slacks, maze routing like algorithm so you can enumerate paths and

delay order, but you needed a delay model for the wires.

Oh, the Elmore delay, so perfectly good first-order model for the delay for the

wires, because you can go from any driving point a to driven point on the

wire. Do people really use this delay metric?

Yeah, absolutely. This is really famous and really helpful

and really widely used. Not the only delay metric people use.

It's the first real delay metric that people use.

So during placement I can estimate the wire shape.

Even with just like a simple Steiner tree, or a simple minimum spanning tree,

something that doesn't really require me to route the wire, I can get a very quick

delay estimate. And, and, you know.

Analytical placers will even do things like, make a very, sort of a crude, but

non-physical model of the wire build an Elmore delay for that model of the wire.

And then sort of use that to adjust the weights on the wires, you know, in the

quadratic placer, if it looks like wire is really long and its got really logn

delay up the weight on the wire so you cn try to rerun the placer and make the

gates get closer together so thats not such a bad thing.

So it's a, you know it's a beautiful simple analytical kind of a model.

It's easy to compute. It is like so many things in this class,

a walk on a tree which is kind of an amazing unifying theme for so many things

in this CAD class. and it makes it possible for us to

actually build a complete delay graph for a static timing model with a delay for

the gates and a delay for the wires and accurately handling things.

So, you know, in summary, interconnect has a huge impact on chip speed.

You cannot ignore the delays caused by the electrical properties of real wires.

And the layout tools are responsible for and a big part of the timing guarantee.

The upstream tools determine the levels of logic, the gate counts, the fanouts,

and things like that. The physical tools are responsible for

how long the wires end up and where the gates go and all of these impact the wire

length and distribution. So today to handle that sort of thing,

individual wires are really modeled as complex circuits.

The RC tree is the most useful model. It's a sort of the foundational model.

The Elmore delay is the easiest thing to compute.

There are other things that we can compute.

There are other estimators beyond the Elmore delay, but we don't have, as my

assumption of your background for this class, you don't have enough circuits for

me to, sort of, go talk about things. We can use these things for verification.

We can use these things for layout optimizations like optimizing clocks and

things like that. But here we are, we sort of, we come full

circle. we're sort of you know, wrapping things

up here with a logic side analysis, you know?

How do you deal with ATs, RATs, and Slacks?

And a layout side analysis for how do you actually you know, build the geometry of

a wire, build the tree, build the RC tree, walk the tree, and get a sort of a

detailed analysis. In the real world of CAD for, you know,

big, complicated ASICs, big, complicated systems on-chip, people are always going

back and forth between working on the logic, and working on the layout.

So I hope you now have a sort of a reasonable sense of, of you know how

these things sort of, sort of, sort of connect.

And so that's it for timing. [SOUND]