[SOUND]. So, here in Lecture 11.8, we're going to continue our exploration of Implementation Mechanics for the Maze Router. This is the third of our three lecture sequence on Implementation Mechanics. One of the things that's been true so far is that whenever we did this expansion process from one source cell. You know we expand outwards searching in the grid to some other target in the grid. We basically have this search process sort of omnidirectional, you know I mean we search north, south, east, west equally. It just sort of, you know it goes out sort of like dropping a rock in a pond. But, but, you know, that seems a little inefficient. I mean, if I have, a, a point over here and I'm attempting to connect a path to a point over here, why am I expanding in the wrong direction? Well, it turns out you don't actually have to expand in the wrong direction. You can actually add some more interesting mechanism. To the maze router, you can add a predictor to actually predict of how expensive it's going to be to actually get you to the target. You can change the structure of the cost function again in a very cleaver way. You can do something called debt first search which preferentially biases the search wave front. In the router process sort a, kind a, sort of in the direction of the target. And just like our previous discussion of consistent and inconsistent cost functions, there are ways you can do this that don't mess things up and there are ways you can do this that do mess things up. And people in the industrial world do it both ways. Which is very interesting. So, what we're going to look at in this lecture, the last of our implementation mechanics lectures, is depth-first search, the purpose of which is to make the basic maze router core run faster. So, in this, the third of our three lectures on the implementation mechanics for maze routers. I want to talk about one specific enhancement to the expansion process. So, so here's just a true cat, a true fact. You expand lots of cells to find one path to the target, and the CPU time is proportional to the number of cells you expand. And so if you have a great big grid, and you have a source and a target that are really kind of far apart, well you know, you're going to expand a lot of cells. In the maze routing method, until you actually go, you know, find that, find that target. And there's really not any attempt to search in the direction of the target first or preferentially. So there's a question, which is can you bias the expansion so you just sort of head toward the target? as opposed to searching you know, read first manner. Or away from the target. Just assuming that maybe that's a little more efficient. And you know, kind of a side question. Based on all of our discussion of consistency and inconsistency. Can you do this in a way, that keeps any of the guarantee's of reaching the target with a minimum cost path. Now ignore the inconsistent cost function thing. Just assume it's a concistent cost function. can I do this at all? Can I do this in a way that doesn't mess up any of the nice properties of, you know, this sort of minimum cost search stuff? the answer is yes, which is interesting. So I'm, I'm just showing you a, an example here of a, again, the six by six grid, source sort of in the middle, target bottom right. And I'm showing you the path cost labels in the grid, again for simplicity, and so there’s a, a diamond of 2's around the source. And then an outward going diamond threes around the source and then a diamond of 4's around the source and then so on. And the point of the diagram is that all of this stuff that's going to the west and to the north would appear to be expanding away from the target and maybe that's a waste of time. And we might be a little precise about defining what toward the target is I'm just going to shade the box. Which is the smallest box. The bounding box just like in placement. The bounding box of the source and target pin. This is often called the source-target box. And I'm going to say you know I just as soon like to search in the yellow box before I search outside the yellow box. Okay. That's a perfectly good definition of what it means to be searching toward the target. Is it possible to do that without messing up any of the other guarantees of how the minimum cost search algorithm works, and it turns out the answer is yes. so there's two parts to the idea we're going to add a predictor function to the cost to direct the search to the target. So instead of just having the basic path cost, the additional second part is the predictor. So in a plain maze router, you add a cell c to a wave front with a cost that measures what? It measures the cost of the partial path that goes from the source to the cell c. In a smart maze router we're going to add a cell c to the wavefront with a cost that estimates the entire source-to-target cost of the path through cell c. And the trick is that we're going to estimate this as the path cost from the source-to-cell c. We know that plus a predictor. And I'm circling the predictor. The predictor's an estimate. And i'm just going to write estimate here. The predictor is an estimate. And today we recognize this. This is actually something famous. It's the difference between a smart depth first search with a predictor versus a classical breadth first search, and in fact this is a very famous application of a very famous idea. If you've done any artificial intelligence kinds of coursework this is A* search. This is exactly what this is but applied in the context of a maze router. So, let's look at Plain maze routing. And we know how this works. We expand from the source. We get to a cell. We expand it. We put it on the wayfront. We pull it off the wayfront, and we expand that cell, so that cell is Gray here, and there's a big, sort of squiggly blue line that says we got here somehow. We're expanding the gray box, we're reaching the yellow box located underneath it. What does it cost to reach that cell? And the answer is the path cost of the source to the cell being expanded and the cost of the newly reached cell. And that's how it goes on the wave front. Path cost plus cell cost. There's a different way you could do it. We could add one more term, we could add an estimate of the path cost from the newly reached cell to the target. And so roughly speaking, this says that Instead of putting things in the wavefront indexed by how much it costs to get there. We're going to put things in wavefront indexed on how much we think the whole route that touches the target and completes the wire costs. Well, we haven't touched the target and we haven't completed the wires, so what do we do? Right? We have something that we know, the path cost and the cost. And we have something that we estimate. What is an estimator? Well, a typical estimator would be, you compute the distance to the target. And that's just like you, you compute something like, a bounding box in a half perimeter wire length router. You know, delta x plus delta y in the grid. That's the distance to the target. That's the length of the shortest wire that will get you from the cell to the target. Multiply by the smallest cell cost because, you know, what's a simple model of the rest of the wire? And the answer is, it's the shortest possible wire. Made up of the cheapest possible cells. So that's the distance to the target multiplied by the smallest cell class. People do actually much fancier things with this. for example, if you know you have to change layers, you will include the cost of the simplest, cheapest vias that will get you onto the layer that you need. If you know that you need to make a band to get to the. the target. You will calculate the bend. If you know there's three or four different ways you could get to the target, you'll calculate the three or four different ways and take the best cost. Alright, people really do fancy things in real routers here, but the simple thing is how far away is the target? How cheap is the cheapest cell? Multiply those 2. That works. And, there's some technical results. As long as the predictor is a lower bound on, which is to say it is less than, the extra pathcost you will add to reach the target. we guarantee you will still get the minimum cost path. That's a wonderful thing. That's the basic, the technical foundation of A-Star search, a very famous result. What does this actually to, in a real router. It alters the order in which you expand the cells. So you won't get a different answer necessarily, you'll touch the cells in a different order. It prefers to expand the cells that are closer to the target first. So let's go look at that. So here's my 6 by 6 grid again with a source in the middle and a target at the bottom. And there's the source to target box which is a three by three set of cells in the middle is highlighted in yellow. And the source cost is one. And we're just going to you know, run a little bit of the search process with this predictor thing. And well, then turn to the observations on the right. So, you know, what actually happens when we actually do this. Well let's let's expand the cells to the East and to the South. Right, well the pathcost is a 2, for those cells, because it's 1 plus 1. And then there's a distance to target. And the distance to target, which is in this case is our estimate of the predictor, right? Is just basically that that, that wire costs one unit, two units, three units. Right, that's the predictor for both of those two. And that predictor has a cost of three, we're just using the distance of, you know. the predictor here is the distance to the target times 1 in this particular grid. So, that's what the predictor is. so they cost 5. what if we actually expand in the other direction, oh. Well those cost 7. Why do they cost 7, because the estimate for the wire to get to the target 1, 2, 3, 4, 5. That predictor is 5. And so those sell the pathcost is 2, right? and the predictor is a 5, as opposed to the other case where the predictor was a 3. So what happens is, they both get searched, they both get reached, both kinds of cells get reached. They both get a cost associated with them, they both go in the wavefront. If we need to use the cells that are outside the source to target box, we will. we'll just expand them later. Now an interesting thing is that the, turns out that all the cells of the source of the target box, now cost the same thing. Which is to say all the cells in the yellow region cost the same thing because the pathcost, the source to target, the source to sell. Plus the pathcost from the cell to the target and that's the, basically, the predictor, okay, as constant. And in this particular case, you know our predictor was just defined to be the same as the distance to the target. So that's just in this simple case with units cost and grinds that's what happens. When you have complicated cost and the girds and other things going on it's not so, not so clear. But in this most simple of examples where it's unit cost and the predictor is just the distance to the target, it wants to expand everything in the yellow box first. That's kind of what you wanted except there's some classical cases when it's not what you want. So here again, is my 6 by 6 grid, the source is now in the upper left, the target is kind of in the lower right. And there's a big black obstacle around the target. And one of the problems is that this very simple expansion scheme wants to expand all the cells in the source to target box before it will go outside the box to find the path. And it turns out you cannot route this source to target inside the source to target box, you have to go out. And so that makes this particular case a little inefficient. Oh well you know, every interesting technical innovation sometimes has unintended consequences. It does still do the right thing. It tries to search... Generally toward the target before it goes off in other directions. And generally that's a very good thing. And there are other heuristics that you can add that will actually even impact that behavior. here's just a tweak. You reach the, the reach cell goes on the wavefront with this cost. It's the path cost. Of the source being expand, of the cell being expanded. It's the cost of the newly reached cell being added in. It's an estimate of the pathcost from the reached cell to the target multiplied by a constant. That's what the big K with the yellow is. what is that? The idea is that we insist that the expansion toward the target Is always cheaper, right? and so what we do is we put a little bit of extra factor in there that makes the distance to the target hurt more in this cost index. So you go away from the target. It hurts more. You go close, close to the target. It hurts less. People will usually take the k thing and make it a kind of a small number, and you play with it. It's a tuning parameter. you will force the paths to go toward the, toward the target that's good. Your router will be faster. That's good. Your paths will not be as optimum as if you didn't do this. you know, sometimes that's okay. Sometimes it's better to get all the paths embedded and have them be a little bit imperfect than to wait forever to have it be searching so far in the wrong directions. So, that's depth first search, that's maze routing search with an a star like predictor. That's a very famous thing. And again, all real routers do something like this to preferentially guide the expansion search toward the target for CPU time efficiency.