[SOUND]. So here in Lecture 11.7, we're going to continue our exploration of Maze Router. And this is the second of three lectures in the sequence on the implementation mechanics of the Maze Router. We left you in the end of the last lecture with some pseudo code, so you know basically how it works. You don't really know what the data structures are yet. Now you, you certainly know that there's a routing grid. But, but to date in all of our little illustrations the routing grid has been sort of the only central actor In this process and honestly, the routing grid is part of the process but it's not the whole thing. You actually need something that just stores the cells in the routing grid that are active, in the sense that they are about to be used to find one of their neighbors to make the routing process sort of expand its search. We need to talk about what those data structures really look like. It turns out they're actually not very complicated. But there's a really core set of ideas that we need to talk about there. There's the first part of this lecture. The second part of this lecture is going to talk about some constraints on what you can do with costs, in the inter loop of the router. So we talked about, for example, that via's may have a higher cost. We talked about the fact that you know, we might seed areas of the routing grid with areas of higher costs. So that, perhaps we liked putting nets there, or perhaps we disliked to put up nets there. Are there some constraints to what I am allowed to do with the cost? And the answer is yes. And interestingly enough, they're are some very simple things that we might like to do to the router that sort of break things in some surprisingly big ways. and here's a really interesting one. What if we decide we'd like to put a little bit of extra cost on a wire that actually bends? What if we say we like wires that go straight, but this, this is a little more expensive. Something surprising happens. We break the cost functions in some rather deep ways. These things have a name, they're called the inconsistent cost functions. And it creates a surprising amount of havoc in the core of the routing engine. And why am I telling you something about havoc in the core of the routing engine? Because every industrial router in the world does this stuff, because it's essential. So I'm going to show you some interesting examples of things that real routers do and how real routers deal with some of the interesting mess that these inconsistent cost functions create. So we're going to first start with a little bit about the core data structures and then we'll talk about critical constraints on the cost structure of maze routers. So here in the next lecture on implementation mechanics, the part two of three, we're going to talk about data structures first. And there's really two key data structures, the routing grid itself, which is the routing surface which holds the costs of each cell. Non-uniform perhaps, non-unit. And also you mark those cells to know that what you've already reached. And you're also going to mark the predecessor stuff. So there's basically three things going on in the routing grid. What does it cost to use the cell. Have you reached it yet in the expansion process, and the predecessor for the back trace. We are not putting the path costs in here. We can do this with not very many bits. And the wavefront, which is this new thing from the previous lecture, which holds the active cells to expand the edges of the cell expansion process. The cells store pathcost information and predecessor information. And also, you know, information, you know, just about, you know, if you will, you know, the, the coordinates of the cell, obviously. it's indexed on the pathcost. You always expand the cheapest cell next. So for the data structures for the routing grid. an obvious data structure is the right thing. It's a two dimensional ray per layer. that's good, and it can even be an N dimensional ray if you have N routing layers. You index it by X and Y, and each grid cell C stores three things, the cost of C, which is typically a small number. Um,you know people actually do these things with, with, with bits. You know you might have 12 bits, or 11 bits, or ten bits. And you might put a ten bit number in there or you might say, I have a ten bit Index. And so I have a table with 2 to the 10 equals 1,024 cost values in it. And so, I look up the index of the cost, and then I look up the cost, and that's the pathcost. People do all kinds of tricks to save bits. There's a predecessor tag for at least the two level routing case north, south, east, west, up, down. And reached a bullion that says, have I reached this cell yet, yes or no? The wavefront, all right, I need something clever here. I need fast insert delete and I need it to stay sorted for this cost based indexing. What does every cell on the wavefront actually involve? What does it store? The coordinates in the grid of you know where the cell is. You know, you have to tell me that the cell is there. The layer, you know, that the cell is on in case there's a bunch of grids. you know layer 1, 2, 3. the path cost which is the sum of all the costs up to this cell and the predecessor tag, We're just keeping them in both places to be a little conservative, This, you know, this will work. You know, the nice thing about the wave front idea is that it's not a gigantically large data structure. So what do we use for the wave front? And the answer is, a famous data structure, a heap. which is also called a priority queue, consult your favorite data structures book. most programming languages, most modern programming languages, you know, C++, Java, things like that. they'll have a basically an object and a method you know, built into the library to do this. You can implement one yourself if you want, it's, it's, you know gosh, you know a hurdred lines of code, 50 lines of code to do a simple heap. but usually you don't have to you just use the one the language provides you. This is a classical data structure designed for fast insertion and retrieval of the lowest cost item. So all the operations, like add and delete, have a login complexity for N objects. So the thing that's cool about a heap is that the minimum cost item always stays on the top. And when you insert a new item it, it, it the word is often bubbles for something like a binary heap. It bubbles the items and the heap around to ensure that the cheapest item stays on top. So you don't know what else is going on inside your heap other than the cheapest thing is always on top. And when you add something it's not too expensive to rearrange the heap so that, the cheapest thing is on top. And delete also does the right thing. Key assumptions for our plain maze router. I will always expand the cheapest cell next. I will reach each cell just once. I will expand each cell just once and I'm guaranteed to find the minimum cost path. Alright, so the cheapest cell next that's easy. expand each reach each cell once, and expand each cell once, that seems kind of obvious. And the fact that I'm gaurenteed to find the minimum cost path, based on, you know, the fact that this is, basically, an implementation of the Dijkstra algorithm, that seems good. Here's a very strange question. What constraints must be true in order for this simple search strategy to actually get the best path, you know, to actually get the minimum cost path? Well if I say this to you in a different way is there anything we can do wrong that can break any of these nice assumptions? Okay, and the thing that's really quite amazing answers is yes, there really is. And if you choose to do the program that's associated with this assignment we will ask you to break things because it's just easier than the implement the case that doesn't break them. And your going to see it yourself in your routing benchmarks. So, there is a name for what we're talking about, for these constraints on the path cost and, and one of the names is consistency. And what consistency means is that. I want it to be true that the cost of adding a cell to a path, right, reaching it, is independent of the path itself. So I don't care how you got to Cell C on the routing surface. When you get to Cell C on the routing surface, there's only one pathcost it can be. And it doesn't depend on the shape of the path in the grid. Alright, and it turns out that if you have a consistency cost function it guarantees that you reach every cell once from the cheapest path and you expand every cell once it will all work. And the thing that's big surprise, is that its incredibly easy to create a cost scheme that is inconsistent which violates all these nice properties and which makes good, physical, geometric sense in a router. So, here it is. I'm going to put a big star over it. So, I've got my diagram again from the expanding reaching diagram. It's a little bit more to it. So there's a pink cell C, I'm sorry, a pink cell B. Which is on the wavefront and it's being expanded. And its pathcost is 12, and its predecessor is north, so I, I was reached from above B. And B is expanding to the east, to touch C. Reach C expand reach C, and B is expanding to the south to reach D. And C costs 3 and D costs 3. So we're expanding B, we're reaching C and D. Here's the new thing. I'm going to penalize paths with bends. I'm just going to add another cost whenever you reach a cell that requires you to turn. And that's actually really easy to tell. So, I'm just going to draw this sort of the wire. We know that cell B was reached from north because its predecessor is north. So the wire that sort of Got to cell B is coming from the north. If we keep expanding and we go into cell D, that wire is a straight line. Okay? But if we, you know, expand from cell B, and we turn and we go into cell C, that is bending. That's a wire with a bend in it. All right? And so we're going to penalize that. Now, technically, how do you check if there's a bend? you look at the predecessor label you're about to put in the re, in the new cell you're reaching. And you look at the predecessor of the cell you're expanding. And if they're different you made a bend. All right? It's, it's as simple as that. You know, B is the north. C is going to be a west. Those aren't the same. And it must be a bend. B is a north. D is going to be a north. No bend. And so here we are. We're going to compute the path cost of C and it's going to be 17. why is it 17. Well you know B's path cost is a 12, C's sell cost is a 3 but there's another 2 because there is a bend. 12 plus 3 plus 2 gives 17 and where does the bend penalty come from? We made it up. So it's an artifact. We decided it's a parameter. When we reach D and we put it on the way front. Well, that's going to have a cost of 15 and the reason for that is that B has a cost of 12, D has a cost of 3 and there is no bend. No bend. So there's no 2 added. And so, you know, we've got a problem here which is that it now depends on how you reached C. It depends on the path that you got to C. And it turns out that it's actually going to break some nice things about our router. But it's a perfectly good thing, because you know, bends are bad. We don't want to bend if we don't have to. If you can route something in a straight line, right, you know, do so. And, the particular thing that bend penaties prevent, okay, just to be sort of clear about it. Is that if I have two points that I'm routing, please do not show me this path going to say bad. Please do not route that path. Right? You know if you're going to route that wire, you know route that wire either you know like that or or route that wire like that. Don't route that wire with all those little scare step things in it. You know you prevent that? You put a bend penalty on your router. So let's try this tiny little example with a bend penalty of 2. And I'm not going to mark the reach bit in each grid, gre, sss, in each grid cell when you first touch it. and so I'm going to allow the search to revisit previously reached cells. So this grid is two grids high and three grids across. And the top row is 1, 1, 3, and the bottom row is 2, 1 1. The upper left corner is the source, and the bottom right corner is the target. And you know, there's only three paths Here. So one path goes south for two cells and then goes east for three cells, and it's cost is 1 plus 2 plus 2 plus 1 plus 1, and that 2 in the middle of that path cost that I'm putting n red, that's the been penalty. So ti's 1 plus 2 plus 1 plus 1 for the material cost, plus 2 for the bend... And the other way of doing it is, you could go east for three cells and then south for two cells and the path cost is 1 plus 3 plus 2 plus 1 which is 8. And the 2 that's in red is also a bend, and similarly you could take a path that has 2 bends in it. I'm just going to highlight them. Bends. 1 plus 1 plus 1 plus 2 plus two 2 plus 8. So that's sort, that path goes to the east for a cell, and then it goes south for a cell, and then it goes east for a cell. So that's a cheap end path. Clearly, I'd like the path with a seven. But, let's actually watch what happens when we do expansions. So, here's the grid again, drawn real small. And we expand the source cell, which costs 1. And so we expand the east neighbor, and it costs 2. And we expand the south neighbor, and it costs 3 because that cell's a little bit more expensive. And then, because we are doing a Dijkstra algorithm, we take the cheapest cell and that cheapest cell's a 2 and we expand it. And one of the things we can do is we can expand it to go to the self. Right? And that will cost 5. Why will that cost 5? Well, that costs 2 for the cell plus 1 for the cell plus 2 which is the bend. and you can also expand to the east a little bit more. That turns out I'm just not going to do it. I'm just going to show a subset of the full expansion process. It doesn't change anything. Okay. now that next cheapest cell in the grid is the three. Okay I'm circling that and so I'm going to expand that. When i expand the three I'm going to expand it to the east and it costs 6. Why does it cost 6? Well because its a 3, the cell costs 1, which is 4 and its got a bend. Okay, so write it in here. Bend exclamation point. Okay, so that's cell cost 6 because we are a Dijkstra's kind of algorithm we expand the cheapest cell so we're going to expand the 5. All right. The 5 expands and it reaches the target with a cost of 8, because it's got another bend in it. 5 plus 2 plus 1 is 8. And so we've got the target, we hit it, you know, and we think well, are we done? And the answer is no because you know one of the things we could do. We could come back and we could expand the six cell, which is still in the heap We could expand this cell. This excel expands to the east with a cost of 1. This does not have a bend in it, and we reach the target with a cost of 7 and that's actually the best path. Now, this is very strange. Look what happened, I reached the same cell. I reached it later. I reached it at a higher cost, but it was ultimately the cheaper source to target path if I ran the expansion process long enough. So there are some, you know, kind of scary implications on this inconsistent cost function stuff. You will reach cells multiple times at different costs. You will have the same cell in the wavefront multiple times at different costs. You can still expand the cheapest sell first, but you cannot quit when you reach the target. How do you know when you're done? How do you how to terminate the search? Well you can't quit until every cell in the way front has a cost so big that it's impossible to reach the target with anything cheaper than the current cheapest path. And so you may reach and expand a lot more cells with an inconsistent cost function, but you can do a bunch of cool things. Now you might be saying to yourself, Rob, this is terrifying. Do people really do this in real routers? And I am here to tell you that the answer is yes boys and girls, yes, they do. Every real router does something like this. Really. I'm really not kidding. Every real router does this, because every real router has to have something like a bend penalty. And there's some other things that do this as well. And, as soon as you put a bend penalty in, the strange stuff happens. So, how do people really know when to quit the search? usually some heuristic, if you expanded M cells to hit the target, you pick a number like, you know. 10% you know and you multiply M by 10% point 1. And you say I'm going to do not more than M prime additional expands and you take the best path you find. You know you don't usually search until you get the best possible path its usually too expensive. It adds a lot of complexity. Well a, a moderate amount of complexity to the core implementation, but it really does help with the quality. And for us it's good enough for you to know that this can happen. And if anyone is actually, actually lots of you are going to build the router. We don't expect you to implement any of this. You can play with it if you like but you don't have to. we're perfectly with the answers you get with inconsistent cost functions. [SOUND].