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.