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: STA Delay Graph, ATs, RATs, and Slacks
Loading...
From the course by University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
30 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.3, we're going to really get to the computational heart of
the, logic side timing analysis, static timing analysis.
We're going to show you how to take the gate-level network and turn it into an
appropriate graph, something called the delay graph that we can analyze and we're
going to look at a form of analysis that's a node-oriented form of analysis.
All of the node elements in this graph are going to get labeled with some very
important values. The arrival times, how long it takes it
gets to the launching clock edge, the required arrival times basically, how
long is it going to take to get to the capture clock edge?
The concept of slack, which is hugely important, which you can think of as the
amount of margin you have for either making a gate go a little bit slower, and
not hurting your overall timing. Or if the slack is negative, uh-oh, I
have a big problem here. These are the places I need to focus on
immediately because these are my problems in the overall timing analysis.
So let's go build the graph, look at all of the ways we imitate the graph, with
arrival times, required arrival times, and slacks.
And look at how we can use this to go forward to do detailed timing analysis.
So let's start talking about how we actually represent a gate level logic
network in a form where we can actually formulate the timing questions that we'd
like to be able to answer. The basic representation for the static
timing analysis is something called a delay graph.
And you start with a gate network and you build the graph.
So I've got a nice little network here, very simple.
It's an and gate feeding an or gate. And the and gate's got two inputs, a and
b. And they are primary inputs, so they so
the graph says pi is a pi is b there primary inputs because there inputs to
the entire logic network. The output on the and gate is c it feeds
the or gate the other input to the or gate is d it comes from the outside.
The output of the or gate is e, it's a primary output, it goes to the outside so
the first thing we have to say is what do we know about the delays for this logic
network. And the answer is we know the delay is
from input pins to output pins and so I'm just labeling them here.
So, there's an input to output delay, a to c in the and gate the delay is delta
is two. Ditto, a delay from b to c, the delay is
two. And I'm just drawing that as a little
area with a delta, delta is two. And the same, the delay from c to e, and
the delay from d to e in the or gate is three.
So, there's a little arrow that says delta equals three.
Now, look, in a real logic network, these numbers aren't all the same.
Right. They can be anything that's appropriate
to model the physical reality of the gate.
I'm only doing this because it makes things a little bit simple.
Now, just a little bit of, of terminology for you.
Those little edges that go from the gate to the gate output have a name.
They're often called Cell arcs. now, they're called arcs because arc is
just another word for edge, and so there edge is a special kind of a graph.
And they explain the timing. And we built these things for every cell
in our technology library, which is the library of standard cells.
So, that is why the are called cell arcs, because we build them from input pins, to
output pins for the cells in our technology library, and they're, they're
edges, edges in a special graph. Okay?
Now, what's very interesting about the delay graph is that what we use for the
nodes in the delay graph are the wires in the gate level network.
So, the gates don't make the nodes, okay? the gates actually make the edges.
And, you know, so think about this for a second, this makes sense.
What's interesting in, in the delay universe is that the delays are things
that happen from input pins to output pins.
From wires to wires. An so, what we're going to do is
represent the nodes of the graph, as, the wires, and the, cell arcs, like the
delays are the edges. So let's just sort of draw it.
I've got primary inputs a an b going into the and gate, so I've got two nodes, a
and b. I've got two wires going into the or
gates c and d. c is the output of the n gate, d is a
primary input. So I've got two nodes, c and d.
And then I've got an output e from the or gate, and so I've got a node e.
and now I can start drawing edges because the edges are the delays.
So I've got two cell arcs that go from a an b respectively to the output c.
So I've got an edge with a two on it that goes from a to c, and an edge with a two
on it that goes from b to c. An similarly, I've got two cell arcs, on
the inside of the or gate that go from c to e and d to e labeled 3.
Okay. So this is the skeleton of the delay
graph but there's a little bit more that's, that's helpful in common.
Okay. the pretty common convention is to add
two special nodes, one of them is called the source and one of them is called the
SNK. You add 1 source node that has a 0
weighted edge to every primary input. And you add 1 SNK node with a 0 weighted
edge from every primary output. Or, the other way to say this is, you
look in the graph that I just built. Every node that doesn't have an edge
going into it, you connect that to the source and you look at this graph.
Every node that doesn't have an edge going out of it, you connect that to the
sync. So I'm just going to sort of let this
come in. So here's this source node that I'm being
drawn on the left. Its got a 0 edge to a, a 0 edge to b, and
a 0 edge to d. And here's the SNK node.
It has a zero edge from e to the SNK. why am I doing this?
this is not strictly necessary, but one nice thing about this for our purposes is
now the network has exactly one entry point, okay, and that, that entry point
is the source. And it has exactly one exit point and
that exit is the SNK. Now all the longest path questions that
my, I might ask from any primary input to any primary output.
I can ask the same question about just saying, so what's the longest path from
the source to the SNK? And I'll figure out whatever the primary
input is that's, you know, causing me the problem.
And I'll figure out what the primary output is that's causing me the problem.
And I don't have to worry about it. All right, so I'm just going to be able
to couch every question I ask in terms of, so what's going on from the source to
the SNK. So this is really common and I think just
sort of conceptually helpful. Now, I still don't have any wire delays
in here, what about the interconnect, what about the physical wires that my
router puts in. And it turns out there's actually a
pretty simple answer. You can still use a delay graph.
We're just got a model each wire as kind of a special gate that just has a delay.
And so I'm against showing you a logic network, and the logic network has an and
gate and an or gate. and you know, nominally the and gate
still has you know inputs a and b and output c, and the or gate has input c and
d and output e. But now, every single wire in this logic
is replaced by in, in this diagram it looks sort of like a big tube.
which is just you know, an object that has a delay, so.
You know, there's a primary input a, and a primary input b, and they each go
through one of these delays to become inputs that I'm now calling x and y that
go into the and gate, which still has a delay of two.
And the, and gate, has an output c which goes into a delay tube and becomes w.
And input to the or gate and primary input d goes through one of these delay
models and becomes z which goes into the or gate.
Which makes e as its output, which goes into another delay.
So you know, what's the delay on the wire from a to x?
It's 1.2. What's the delay on the wire from b to y?
It's 1.6. What's the delay on the wire from c to w?
It's 1.5. What's the delay on the wire from d to z?
It's 1. What's the delay on the wire from e to
the final output which we're now calling q the primary output 1.8.
this thing can be just modeled by a delay graph, right.
Every, wire, you know, pin, is a node, and every delay, which in this case are
everything where there's a delta, is an edge.
and so, you know, it's a little more complicated.
So there's an a and a b input and so there's an a and a b node.
those things go through delay models of wires to become x and y inputs, so
there's an x and y node. there are c and d, c as in output of the
and gate, d as in input, a primary input, so there's a c and a d node.
w and z are the new inputs to the or gate, they're the outputs of delay models
on wire, so there's a w and a z node. There's an e output from the or gate.
which goes, which is modeled and there's a q node now, which is the, the big
primary output. And so, then there's just all of the
delays. Right.
a goes to x for the 1.2 because there's a, there's a delay of a wire with 1.2.
b goes to y with a delay of 1.6, because there's a, a delay like that.
x and y each go to c because the pin to pin delays in the and gate are 2.
c goes to w with a 1.5, d goes to z with a 1.0, those are wire delays.
w and z respectively go to e with a delay of three because those are gate delays,
those are cell arcs, and e goes to q with a 1.8 because there's a wire delay.
And then similarly you again put in the source and the SNK node, the source node
goes with zeroes to a, b, and d. The SNK node goes from q to the output
and there we go. It's a bigger graph, it's got a lot more
stuff in it, but it's still just a delay graph and everything interesting that I
can ask is, so what's going on with longest paths from the source to the SNK?
Now you can imagine that if you have millions and millions of logic gates, and
you have millions and millions and millions of wires, and they've all got
delays, and you've got all of those cell arcs, because they've all got action
happening with respect to delays from pin to pin, this is a pretty big graph.
And yes, its a pretty big graph. So when we process this graph to answer
questions on it It better be something we can do really fast.
And as we're going to see, you can actually do this really, really fast.
It's a really nice thing. So I have now built the delay graph, and
I can put wired delays in if I chose, and I can already model the gate delays.
how do I use this graph to do timing analysis?
well alright so look. Here's what we don't do.
We don't try to enumerate all the source to SNK paths.
and then just kind of pick the ones that look like they're problems.
there's no way to actually enumerate all the source to SNK paths in any rational
way. it's going to be an exponential explosion
in the number of paths, even for a small graph.
Here's a tiny little graph. It's got node 0, 1, 2, 3 to n.
Written left to right in a row, and every single node has two arrows going to the
right. So node 0 has two edges out going to node
1. Node 1 has two edges out going to node 2,
etc. To the end node, node n.
How many paths are there from node 0 to node n?
And the answer is at every node you can make a choice to take the arrow on the
upside or the arrow on the downside, so you know, this basically 2 to the n paths
here. you know, basically, you know, from the
beginning of this network to the end of this network.
you know, clearly I need a smarter answer.
and the smarter answer is something called node-oriented timing analysis.
and what's interesting about node-oriented timing analysis, is that
we're going to find for each node in the delay graph the worst node along any
path. And we're going to label the node with
some interesting information in a very efficient way.
You know, a couple of walks through a, through a, through a graph.
and once we know that information on the node, each node in the delay graph, we're
going to be able to do all of the analysis that we need.
It's actually very nice and very convenient.
So, we need to define some stuff. And here's what we need.
We needed to find some special values on the nodes in the delay graph.
So I've got a little picture here. I've got the source node at the left, and
the SNK node at the right. And I've got a kind of a squiggly line
that says other paths. And I've got a highlighted node that says
n on it. And I've got a squiggly path from the
source. And a squiggly path to the SNK.
There's all kind of stuff in front of n. And all kinds of stuff after n.
But n is the node I want to talk about. And so here are the things that we're
going to have to define. We're going to define something important
called the arrival time at node n. And that's actually written as capital
AT. And it's actually called an AT.
Right, so we talk about ATs at a node. And AT of n, AT of n, is the latest time
the signal can become stable at node n. So, you know, the signal leaves the flip
flop. q goes through a bunch of logic, wiggles
around for awhile and becomes a stable value.
How long does that take? So the way to think about that is that's
sort of like the longest path from the source, and sometimes called the delay to
the node or the delay to node end. Now on the other side there's something
called the required arrival time or the RAT which is actually called a RAT.
and so they're called RATs. And so, RAT n, the required arrival time
is the latest time the signal is allowed to become stable at node n.
So you can kind of think of that as kind of like the longest path to the SNK.
sort of, and I'm going to emphasize the sort of because as we're going to see
very shortly. AT's a reference from the start of the
clock period. RAT's a reference from the end of the
clock period. which means that they, they have a
special form when, when you get computed as a number.
But thinking of that as the longest path to the SNK is still sort of the mentally
right model, there's sort of like the delay from the node to the other edge of
the clock. And then we have a new concept a very
very important concept the slack at node end and the slack is the RAT minus the
AT. So if you can compute the arrival time of
the node and then compute the required arrival time at the node, you take the
RAT you subtract the RAT and you get the slack.
And this amazingly important concept in timing analysis.
The slack is the amount of timing margin for a signal positive is good and
negative is bad. It's determined by the longest path
through the node. So I've got the same picture at the
bottom, the source node at the left, the SNK node at the right, a squiggly line
that says other paths. And I've got a, an arrow that says ATs
going to node n and an arrow that says RATs going from node n to the SNK.
And it's sort of from the source to the ATs to the n to the RATs to the SNK,
that's sort of where all the action is. You compute the AT for every node.
You compute the RAT for every node. RAT minus AT is slack.
Everything that's interesting is in a slack.
you know, what can we say about the slack?
The slack is the amount by which a signal can be delayed at a node and not increase
the longest path through the network. So, it's kind of timing margin.
You can increase the delay of a node that has positive slack and do something
useful like maybe minimize the power or minimize the circuit area.
and not degrade the overall performance. So it tells you where you have extra
margin that you can use to you know, sort of maybe optimize the circuit.
And similarly negative slacks are bad. Those are the places where you've got
real problems. So, slack, is the RAT, minus the AT.
That's the big thing to remember. More interesting information about slack,
slack is hugely important in timing analysis.
Slacks are always defined, so negative slacks are bad.
It indicates a timing problem, an it measures the sensitivity of the network
to this nodes delay. So if you have positive slack, that's
always a good thing. I can change something about this node
and not hurt the network's overall timing.
So, maybe I can make this node slower, maybe I can save some power and not hurt
the timing. Negative slacks are always bad.
You have negative slack at a node, you have a problem at a node.
And the more negative the slack, the bigger the problem you have at the node.
So you're looking for a node to help fix some timing because you've got some
timing problems go look at the nodes where you have negative slack.
Want to know the biggest problems you've got, go look at the nodes with the most
negative slack. Those are the places that effect the
critical paths the most. So it's a very useful concept.
How you compute these things, well you should you know should not be any
surprise you compute these things recursively.
So I got a diagram here. And so again I've got the source node at
the left and the SNK node at the right. And the source not fans out to a whole
bunch of highlighted nodes that are immediately in front of a node called n,
that's, that's, that's highlighted. And the source not fans out to a whole
bunch of highlighted nodes that are immediately in front of a node called n,
that's, that's, that's highlighted. And every single one of those nodes in
front of node n has an arrow. and that's basically between the source
and node n. And then between node n and the sync,
there's also a lot of nodes but they're all grayed out.
Okay. So, just some, you know, some terminology
here. the nodes that are immediately in front
of n, that are one edge away from n, are the predecessors of n.
And so we call that pred of n, pred of n. And I've got one of them highlighted
here. It's got a node, it's got a p on it.
And note that everyone of those nodes, that are the predecessors of n, has a
delay value. that's what the delta is.
So there's a delta p of n, which is the delay from node p to node n, in my delay
graph. And what's the formula for AT of n?
What's the formula for the AT? What is the formula for the arrival time?
The arrival time is the maximum delay to node n.
And it's, it's, you know? It's as simple as you would guess it is.
What's the maximum delay? Well, if this node is the source.
It's zero. You know what's the, you know, the
maximum path from the source, to the source 0.
Otherwise you compute it recursively, you look at all of your predecessors.
It's the maximum over all of the predecessors of the arrival time to the
predecessor plus the delay from the predecessor to me to node n.
So it's the max over all the predecessors p of the AT of node p plus the delta that
delayed from node p to node n. So as simple as that.
Very simple recursive definition. Are you the source?
Hey you're longest path is 0 by definition.
Are you not the source? Look at the longest path to the nodes one
in front of you. Take that number, add the delay from that
node to you. Take the biggest one that's what your
arrival time is. So, here's a, just a, quick concrete an
example of how to do arrival times. So I've got a source node drawn here, and
a bunch of fan outs. And then I've got three distinguished
noted, labeled p and q and r, that are all feeding another distinguished node n.
And I'm looking to calculate the arrival time for n, so what do I need to know?
Well, you know, at the very least I need to know the information about the arrival
times of my predecessors, my predecessors for node n are p, q, and r.
So what do I need. I need to know that the arrival time of p
is 5 and the delay from p to m is 7. I need to know that the arrival time of q
is 10 and the life from q to n is 1 and I need to know that the arrival time at r
is 5. And the delay from r to n is 5.
And then I can actually use the formula for what the arrival time at n is.
The arrival time at n is the maximum over the predecessors and I'm saying that this
is the maximum over x element of set p q r.
So x is a predecessor. The predecessors of p, q, r.
And what is it maximum over? AT of x, the AT of x the delay, the delta
from x to n. So this is the maximum over 5 plus 7.
That's the p node, 10 plus 1 the 1 node, and 5 plus 5, the r node.
So that's the maximum over 12, 11, or 10, and so that's a 12.
Right? So that's the worst thing that can
happen, the worst arrival at n, that's the 12.
And it happens to occur because of the delay, to node p, the predecessor with a,
an arrival time of 5 and the delay from p to n of 7.
So, you know, if you know that the log is path to the predecessor It's a simple
maximum operation to compute the longest path to n.
And yeah, it's just the Dijkstra thing again.
It really is. So, pretty simple to calculate the ATs.
So, how do you compute the RATs? Well, you compute the RATs also
recursively, but basically you're going to compute the RATs by going from
the SNK kind of backwards toward the SRC. So again I've got a diagram, the SNK is
on the left the SRC is on the left, SNK is on the right.
There are paths exiting and fanning out from the source to a bunch of nodes the
predecessors of node n. That have a delayed arrows into n.
n has an edge going out to a set of highlighted nodes.
One of them is distinguished and has an s one edge away from node n.
And the node s has an edged that's labeled delta n s.
And so again we have a little bit of terminology.
the successors of node n are succ, succ of n, successor of n, so those are the
nodes that are one edge away, outgoing from node n, alright.
Now I need a little more stuff to be able to calculate the RATs.
I need the cycle time on the clock, you have to tell me how long the clock is.
Alright, and the reason is that the RATs are defined relative to the clock's
cycle. And this isn't a problem with the AT's,
the arrival time because we just assume that the clock's starts at zero, okay.
but I actually need to know what the cycle time is on the clock because the
the RATs are defined relative to the end of the clock cycle.
So here's what we get. the RATs are the latest time in the clock
cycle where the signal at node end could change and the signal would still
propagate to the the SNK by the end of the cycle.
So how we calculate that is as follows, well if you are the SNK node then the
required arrival time is the cycle time when do you actually have to get if you a
logic signal to the sync node and the answer is in the cycle time.
That makes sense. Otherwise everything is sort of backwards
from the RAT. So, instead of the maximum it is the
minimum. We calculate the minimum over the
successors. s element of the successors at n of the
required arrival time of the nodes that are one edge closer to the SNK and then
we subtract the, delay, the delta from n to s.
Why is this a minimum? The answer is because we're trying to
figure out basically the longest path to the sync, and so we're interested, if
we're, if all of this stuff is relative to the edge of the final edge of the
clock, and we're trying to get a number in the clock cycle.
We're looking for the smallest time number, right?
because that's going to be the one that's the farthest away from the clock edge,
that's the longest edge from, that's the longest path to the T.
So, what's the RAT? It's the cycle time, if you're the SNK,
otherwise, it's the min, of over you successors of the RAT minus the edge
delay. So I've now got the AT and the RAT drawn
right next to each other. Just talk a little bit about you know
like, why are there these differences? Right, so, the formula on the left says
that the AT is zero if the node is the source.
Otherwise, it's the MAX over the predecessors of the AT plus the delay.
And the RAT formula says that the RAT is the cycle time, if n is the SNK.
Or it's the minimum of the RAT minus the delay.
So, you know, what's, what's going on here?
So, look. Let's just be clear that here's the
picture of the clock, and I've got sort of two up arrows.
And then, you know, kind of up, down, up. You know going in between.
The left most edge of the clock is launching the data out of the flip flops.
And then we go through the logic, hopefully you know in less time, then the
clock cycle takes. Right and we arrive at another set of
flip flops, and we are capturing things, so there is the launch edge and the
capture edge. The arrival time, is basically the
longest logic delay after the launch edge.
And so, it's easy to see that it's the maximum of, recursive arrival times, plus
delays. The required arrival time is basically
calculated backwards from the cycle time. It's calculated backwards from the
capture edge of the clock. So, you know, if you are the SNK node,
you, you know, the the required arrival time is the cycle time.
And when you're calculating it backwards, you take the required arrival time of
things closer to the SNK node. And you subtract the delays, alright.
And because you're looking for the longest thing to the capture edge, but
you're looking for a number like relative to the launch edge, you want the minimum
because you want the thing that's closest to the start that's farthest from the
capture edge. Right.
So that's why it works that way. You know, the ATs are defined relative to
zero, the launch edge. The RATs are defined relative to the
capture edge, which is a cycle time. The ATs are taking maximums and adding
things, because we're heading, you know, toward, toward the capture edge.
The RATs are minimums and subtractions because we're sort of subtracting
everything from whatever the number is, you know, 1 nanosecond.
So that's why there's that, you know, slightly strange-looking asymmetry.
Bad things happen when we see this. That's the, the big thing to emphasize
here, bad things happen when we see this. When the slack which is defined as the
RAT minus the AT is negative, bad things happen.
So I've got another picture of a clock, launch edge goes up clock goes up down up
I've got a capture edge and I've got the clock cycle.
Right, so here is the arrival time, right it starts at the launch edge and its a
little arrow that goes over and it sometime in the middle of the clock
cycle, that's the arrival time you know it's a number.
And let's remember that the required arrival time is another number, right the
big thing I am just going to put a little star here, the big thing is that the
required arrival time is not the length of a path.
The required arrival time is a number in the clock cycle.
Right? The arrival time is both a number in the
clock cycle, and the length of the path. Because we're all starting at zero.
The required arrival time is a number, right?
So many picoseconds after zero. Right, because it's calculated backwards
from the capture edge. If the RAT is bigger than the AT, right,
then you have negative slack. And what are you saying?
You're saying the signal arrives to late, and there's to much delay from where you
arrived at to the capture edge of the clock.
So the signal does not arrive at the flip flop input before the capture edge of the
clock. Right?
You say look it takes this long to get to the node, that's the AT.
That takes this much longer to get to the capture edge, that's the RAT.
And I'm sorry, but you know, those two things, you know, there's just not enough
time in the clock cycle. The signal's not going to arrive at the
capture edge, and you're going to lose that logic.
You're going to lose that value, its not going to get captured.
Your timing doesn't work, your logic doesn't work.
You have to go fix something. So that's why the RATs are defined the
way they are. That's why the ATs are defined the way
they are. That's why RATs minus ATs is what's
interesting. That's why negative slack is a terrible,
terrible, thing. You never wish it to happen to a friend.
Okay? And why, what we're going to do next is
show you how you can calculate ATs and RATs and slacks very, very quickly.
Even when you have a gigantic delay graph.
So let's go see how we do that. [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.
© 2018 Coursera Inc. All rights reserved.
