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.