[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]
