1:24

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.

4:19

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.

13:22

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.

16:17

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.

18:39

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.

21:22

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.

25:06

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]