You should complete the VLSI CAD Part I: Logic course before beginning this course. A modern VLSI chip is a remarkably complex beast: billions of transistors, millions of logic gates deployed for computation and control, big blocks of memory, embedded blocks of pre-designed functions designed by third parties (called “intellectual property” or IP blocks). How do people manage to design these complicated chips? Answer: a sequence of computer aided design (CAD) tools takes an abstract description of the chip, and refines it step-wise to a final design. This class focuses on the major design tools used in the creation of an Application Specific Integrated Circuit (ASIC) or System on Chip (SoC) design. Our focus in this part of the course is on the key logical and geometric representations that make it possible to map from logic to layout, and in particular, to place, route, and evaluate the timing of large logic networks. Our goal is for students to understand how the tools themselves work, at the level of their fundamental algorithms and data structures. Topics covered will include: technology mapping, timing analysis, and ASIC placement and routing. Recommended Background: Programming experience (C, C++, Java, Python, etc.) and basic knowledge of data structures and algorithms (especially recursive algorithms). An understanding of basic digital design: Boolean algebra, Kmaps, gates and flip flops, finite state machine design. Linear algebra and calculus at the level of a junior or senior in engineering. Elementary knowledge of RC linear circuits (at the level of an introductory physics class).
Interconnect Timing: Elmore Delay Examples
Loading...
Из курса от партнера University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
25 оценок
Из урока
Timing Analysis
You synthesized it. You mapped it. You placed it. You routed it. Now what? HOW FAST DOES IT GO? Oh, we need some new models, to talk about how TIMING works. Delay through logic gates and big networks of gates. New numbers to understand: ATs, RATs, SLACKS, etc. And some electrical details (minimal) to figure out how delays happen through the physical geometry of physical routed wires. All together this is the stuff of Static Timing Analysis (STA), which is a huge and important final "sign off" step in real ASIC design.
Познакомьтесь с преподавателями
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[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]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
