[SOUND]. So, here in Lecture 12.4, we're going to do a big example. In a previous lecture, we showed you how to build the delay graph and we defined these very important values. Arrival times, required arrival times, and slacks or as they are called AT's, RAT's, and Slacks. Right. We're going to actually take a fairly detailed example. We're going to walk forward through it and build the AT's. Walk backwards through it and build the RAT's. We're going to subtract things appropriately and build the Slacks. We're going to look at the worst case, worst delay paths through it. And one of the big things we're going to see is that Slack is a hugely important concept. When you know the Slacks, when you know the worst case Slacks, really, you know, everything bad and problematic happening in your logic network. So, let's go take a look at a detailed example to see how all of this works. >> So, let's look at a bigger example to see how these ideas work. So, what's the first thing we need? Well, we need to know the clock cycle, so let's just say it's 12. And we need a graph, and so I've got a little graph here shown below. 1,2,3,4,5,6,7,8,9,10,11 nodes, SNK at the right, SRC at the left. lots of edges with delays on them. And small lowercase letter under each node, so we can identify and talk about it. So first three nodes on the left, a,b, and c have zero edge from the SRC to them, going to the right, nodes d and e. a connects to node d with an edge of 1. C connects to node e with an edge of 2. going further to the right, node f. D connects to f with a 5. B connects to f with a 4. C connects to f with a 1. Further to the right, g and h, two nodes. D connects to g with a 3. F connects to h with a 4. E also connects to h with a 4. Going further to the right, nodes j, k, and n. G connects to j with a 2. F connects to j with a 2. F connects to k with a 3. H connects to k with a 3. H connects to n with a 5. And then j, k, and n all have a 08 edges to the sync on the right. So, the primary inputs here are really a, b and c. The primary outputs here are really, j, k, and n. and there's little three gray boxes by each one of these, it's where we're going to fill in all the values. So, let's just remember that the AT is the longest path from the SRC to the node. The RAT is 12, the cycle time minus the longest path from the node to the SNK. And the Slack is the RAT minus the AT. And for now the problem is small enough, we're just going to look at the mixes, the minimum and maximum delays, by eye, we're just going to figure it out and write it down. So, here's the same graph a, b, c, d, e, f, g, h, j, k, n. SRC on the left, SNK on the right. we're going to compute AT's, RAT's, and Slacks. But on this slide, we're going to compute the AT's. And so, that's going to be the left box on the little gray box by all of these nodes. And we're just going to compute this. And let's remember this. This is just the longest path the longest delay, the longest set of adding them together numbers on the red edges from the SRC. So, we can do that by eye. So you know, what is the longest path from the SRC to itself? And the answer is 0. What's the longest path to the a, b, and c nodes that have 0 weight edges from the SRC? Also 0. what are the longest paths to d and e? Well, there's only one edge to each of them. So it's, you know, 1 and 2, the numbers on the edges. what's the longest path to f? Well, now we actually have to calculate something, you know, because you know, you could go you know, through the d node, 1 plus 5. you know, or you can go from the b node with a 4 or you can go from the c node with a one and so, you know, you're going to get 5 plus 1 is a 6, for node f. what about nodes g and h? Well, node g, there's only one way to get there. So, you go from d with a 3. 1 plus 3 is 4. Node h is actually, it's, it's going to be either 6 plus 4 coming from f, or 2 plus 3 coming from e, so it's going to be the 10. and similarly we can calculate, you know, the longest way to get to node j is a 7. Okay? The longest way to get to node k is a 12. and for that one, you actually have to go from f, right, with the 6 down to h with the 4 and up with the 2. Right. That's the worst thing that can happen there. And the worst way to get to node n is 10 plus 5 is 15. And then, since all those edges have zero weight to the SNK, the SNK is just the biggest of those, and so it's 15. And so, those are the AT's. Longest delays from the SRC. How about the RAT's? So, the RAT will be the middle number on all of these boxes. And the RAT's are best thought of as starting from the SNK and going backwards to the SRC. And the RAT's are just 12 minus the longest path from the node to the SNK. And so, it's sort of the same thing but just backwards. You've got to follow the edges in the other direction. All right. So what's the RAT for the SNK? It's the cycle time. What's the RAT for all of the nodes j, k, and n that have a zero weight connection to the SNK? Also 12, the cycle time. What about node g? Well, there's only one edge going out of that. So, you know, the path to the SNK is length 2. So, 12 minus 2 is 10. load h, you know there's actually a couple of ways back. The longest way back to the SNK is 5, 12 minus 5 is 7. And so, we can just continue this. for node f. [BLANK_AUDIO][SOUND]. I write that for node f. the RAT is going to be 3, 4, nodes d and e respectively, negative 2 and 4. Again 12 minus the sort of longest path back, for nodes a, b, and c respectively. Negative 3, negative 1, and negative 2. 12 minus longest path to the SNK. And again, the SRC has just zero weight. Edge is going to be the worst one of those numbers, negative 3. So, those are all the RAT's. So, what are the Slacks? The Slacks are easy to, to calculate. the slacks are just the RAT minus the AT. and if we can just, you know, go, go look at the, the AT numbers which are blue, the RAT numbers which are twelve, we can just do those easily on every node and we can calculate everything. And the first thing we'll see is immediately the worst thing that appears because the, everything that I said the the worst thing that can happen is you have negative Slack. The worst thing that can happen is, is in this case negative 3. So, we've got, you know, node, the SRC node has a negative 3 Slack. A has a negative 3. B has a negative 1. C has a negative 2. D has a negative 3. E has a 2 node. F has a negative 3. g has a 6. H has a negative 3. J has a 5. K has a 0. n has a negative 3 and the SNK has negative 3 as well. what's interesting is that we can actually trace the worst path from the SRC to the SNK. And the way you can do that is just go look at the negative Slacks. Go look at the worst case Slack. what are all the nodes that actually have negative 3? And the answer is the SRC node, the a node, the d node, the f node, the h node, the n node and the SNK node. Those all have negative 3's. That is, in fact, the worst path there is. That is the longest path. That's the path that's messed up. That's the path that's 15 units long. Okay? That's the path that gets there 3 units after that capture edge of the clock. Right? That's actually really interesting because, let's think about it, kind of what we did. We did a sort of a forward pass through this graph from the SRC and we label all the AT's And then, we did a backward pass through this graph and we labeled all the RAT's. And then, we sort of, at every single node, we just said, all right, look. You know, what's the RAT minus the AT? And we got a number, and then, what I told you, which is really kind of magical is, you know the worst thing that is happening in this graph? Go find the worst negative Slack number trace that stuff from the input to the output, that's your worst path. And, indeed, that's your worst path. Lots of interesting things going on with the Slacks. a negative slack in an output means a missed requirement. That's not a surprise. Right? you know, we have a you know, we have some negative 3 Slacks going on there. That means something shows up 3 units of time after the capture edge on the clock. A negative slack on an internal node means it feeds a problem primary output. So, there is a path from that internal node to some problematic primary output. And the big result is that the negative Slack appears along the entire worst case path. Your worst timing violation is at an output, primary output, with the most negative Slack value. And you can always trace a path with this exact slack value back to the primary input and every node on that path has that exact same worst case slack. This is a hugely result, an enormously useful result. So, slacks are a very important. But beyond just knowing what is the worst case path Slacks tell us the problem gates on the path. Remember, positive Slacks means you have margin. You can make the gates slower. You can make it have less power, maybe, like, have less silicon area. You know, it's a good thing. Negative Slacks tell you you have a problem, something's got to go faster. And a bigger negative Slack tells you something's got to go a lot faster. You're going to have to put some more energy in. You know, make something go faster. So Slacks are extremely, extremely useful. [SOUND]
