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).
Logic-Level Timing: A Detailed Example and the Role of Slack
Loading...
From the course by University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
86 ratings
From the lesson
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.
Meet the Instructors
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND].
So, here in Lecture 12.4, we're going to do a big example.
In a previous lecture, we showed you how to build the delay graph and we defined
these very important values. Arrival times, required arrival times,
and slacks or as they are called AT's, RAT's, and Slacks.
Right. We're going to actually take a fairly
detailed example. We're going to walk forward through it
and build the AT's. Walk backwards through it and build the
RAT's. We're going to subtract things
appropriately and build the Slacks. We're going to look at the worst case,
worst delay paths through it. And one of the big things we're going to
see is that Slack is a hugely important concept.
When you know the Slacks, when you know the worst case Slacks, really, you know,
everything bad and problematic happening in your logic network.
So, let's go take a look at a detailed example to see how all of this works.
>> So, let's look at a bigger example to see how these ideas work.
So, what's the first thing we need? Well, we need to know the clock cycle, so
let's just say it's 12. And we need a graph, and so I've got a
little graph here shown below. 1,2,3,4,5,6,7,8,9,10,11 nodes, SNK at the
right, SRC at the left. lots of edges with delays on them.
And small lowercase letter under each node, so we can identify and talk about
it. So first three nodes on the left, a,b,
and c have zero edge from the SRC to them, going to the right, nodes d and e.
a connects to node d with an edge of 1. C connects to node e with an edge of 2.
going further to the right, node f. D connects to f with a 5.
B connects to f with a 4. C connects to f with a 1.
Further to the right, g and h, two nodes. D connects to g with a 3.
F connects to h with a 4. E also connects to h with a 4.
Going further to the right, nodes j, k, and n.
G connects to j with a 2. F connects to j with a 2.
F connects to k with a 3. H connects to k with a 3.
H connects to n with a 5. And then j, k, and n all have a 08 edges
to the sync on the right. So, the primary inputs here are really a,
b and c. The primary outputs here are really, j,
k, and n. and there's little three gray boxes by
each one of these, it's where we're going to fill in all the values.
So, let's just remember that the AT is the longest path from the SRC to the
node. The RAT is 12, the cycle time minus the
longest path from the node to the SNK. And the Slack is the RAT minus the AT.
And for now the problem is small enough, we're just going to look at the mixes,
the minimum and maximum delays, by eye, we're just going to figure it out and
write it down. So, here's the same graph a, b, c, d, e,
f, g, h, j, k, n. SRC on the left, SNK on the right.
we're going to compute AT's, RAT's, and Slacks.
But on this slide, we're going to compute the AT's.
And so, that's going to be the left box on the little gray box by all of these
nodes. And we're just going to compute this.
And let's remember this. This is just the longest path the longest
delay, the longest set of adding them together numbers on the red edges from
the SRC. So, we can do that by eye.
So you know, what is the longest path from the SRC to itself?
And the answer is 0. What's the longest path to the a, b, and
c nodes that have 0 weight edges from the SRC?
Also 0. what are the longest paths to d and e?
Well, there's only one edge to each of them.
So it's, you know, 1 and 2, the numbers on the edges.
what's the longest path to f? Well, now we actually have to calculate
something, you know, because you know, you could go you know, through the d
node, 1 plus 5. you know, or you can go from the b node
with a 4 or you can go from the c node with a one and so, you know, you're
going to get 5 plus 1 is a 6, for node f. what about nodes g and h?
Well, node g, there's only one way to get there.
So, you go from d with a 3. 1 plus 3 is 4.
Node h is actually, it's, it's going to be either 6 plus 4 coming from f, or 2
plus 3 coming from e, so it's going to be the 10.
and similarly we can calculate, you know, the longest way to get to node j is a 7.
Okay? The longest way to get to node k is a 12.
and for that one, you actually have to go from f, right, with the 6 down to h with
the 4 and up with the 2. Right.
That's the worst thing that can happen there.
And the worst way to get to node n is 10 plus 5 is 15.
And then, since all those edges have zero weight to the SNK, the SNK is just the
biggest of those, and so it's 15. And so, those are the AT's.
Longest delays from the SRC. How about the RAT's?
So, the RAT will be the middle number on all of these boxes.
And the RAT's are best thought of as starting from the SNK and going backwards
to the SRC. And the RAT's are just 12 minus the
longest path from the node to the SNK. And so, it's sort of the same thing but
just backwards. You've got to follow the edges in the
other direction. All right.
So what's the RAT for the SNK? It's the cycle time.
What's the RAT for all of the nodes j, k, and n that have a zero weight connection
to the SNK? Also 12, the cycle time.
What about node g? Well, there's only one edge going out of
that. So, you know, the path to the SNK is
length 2. So, 12 minus 2 is 10.
load h, you know there's actually a couple of ways back.
The longest way back to the SNK is 5, 12 minus 5 is 7.
And so, we can just continue this. for node f.
[BLANK_AUDIO][SOUND].
I write that for node f. the RAT is going to be 3, 4, nodes d and
e respectively, negative 2 and 4. Again 12 minus the sort of longest path
back, for nodes a, b, and c respectively. Negative 3, negative 1, and negative 2.
12 minus longest path to the SNK. And again, the SRC has just zero weight.
Edge is going to be the worst one of those numbers, negative 3.
So, those are all the RAT's. So, what are the Slacks?
The Slacks are easy to, to calculate. the slacks are just the RAT minus the AT.
and if we can just, you know, go, go look at the, the AT numbers which are blue,
the RAT numbers which are twelve, we can just do those easily on every node and we
can calculate everything. And the first thing we'll see is
immediately the worst thing that appears because the, everything that I said the
the worst thing that can happen is you have negative Slack.
The worst thing that can happen is, is in this case negative 3.
So, we've got, you know, node, the SRC node has a negative 3 Slack.
A has a negative 3. B has a negative 1.
C has a negative 2. D has a negative 3.
E has a 2 node. F has a negative 3.
g has a 6. H has a negative 3.
J has a 5. K has a 0.
n has a negative 3 and the SNK has negative 3 as well.
what's interesting is that we can actually trace the worst path from the
SRC to the SNK. And the way you can do that is just go
look at the negative Slacks. Go look at the worst case Slack.
what are all the nodes that actually have negative 3?
And the answer is the SRC node, the a node, the d node, the f node, the h node,
the n node and the SNK node. Those all have negative 3's.
That is, in fact, the worst path there is.
That is the longest path. That's the path that's messed up.
That's the path that's 15 units long. Okay?
That's the path that gets there 3 units after that capture edge of the clock.
Right? That's actually really interesting
because, let's think about it, kind of what we did.
We did a sort of a forward pass through this graph from the SRC and we label all
the AT's And then, we did a backward pass through this graph and we labeled all the
RAT's. And then, we sort of, at every single
node, we just said, all right, look. You know, what's the RAT minus the AT?
And we got a number, and then, what I told you, which is really kind of magical
is, you know the worst thing that is happening in this graph?
Go find the worst negative Slack number trace that stuff from the input to the
output, that's your worst path. And, indeed, that's your worst path.
Lots of interesting things going on with the Slacks.
a negative slack in an output means a missed requirement.
That's not a surprise. Right?
you know, we have a you know, we have some negative 3 Slacks going on there.
That means something shows up 3 units of time after the capture edge on the clock.
A negative slack on an internal node means it feeds a problem primary output.
So, there is a path from that internal node to some problematic primary output.
And the big result is that the negative Slack appears along the entire worst case
path. Your worst timing violation is at an
output, primary output, with the most negative Slack value.
And you can always trace a path with this exact slack value back to the primary
input and every node on that path has that exact same worst case slack.
This is a hugely result, an enormously useful result.
So, slacks are a very important. But beyond just knowing what is the worst
case path Slacks tell us the problem gates on the path.
Remember, positive Slacks means you have margin.
You can make the gates slower. You can make it have less power, maybe,
like, have less silicon area. You know, it's a good thing.
Negative Slacks tell you you have a problem, something's got to go faster.
And a bigger negative Slack tells you something's got to go a lot faster.
You're going to have to put some more energy in.
You know, make something go faster. So Slacks are extremely, extremely
useful. [SOUND]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
