So here in lecture 11.5, we're going to look at non uniform grid costs. So, this is another feature addition to the basic maze router method, but maybe a little subtle one. one of the things that's been true in all of the grids that I've shown you so far, is that the cost of traversing one single cell was always 1. is that a requirement, is that a, a, a critical foundational part of the major router method? No, I'm free to put any cost value in any cell I like why would I do that? And what's interesting is that I can actually see that the routing edge with costs and drive the shapes, the geometry of the nets to do things that I like. I could put high cost values in a region of the grid representing some part of the trip that I would prefer the nets. As they are routed, avoid. I could put low-cost values in other parts of the grid representing the chip's surface, and preferentially sort of drive the nets to use those low-cost regions. It is an amazingly flexible method, it is actually the way all real industrial routers do their business. And it's a surprisingly simple feature add to the basic maze router methodology. So let's go look at what cool things we can do with non-uniform costs in our maze routing grids. So the next feature that we're going to add to our basic maze routing core is to allow the individual squares in the grid to cost something other than one. To use as a part of a path. So in the original way we specified this problem, each cell in the grid cost the same to cross it. So more or less, that means everything costs one, we say that this is the unit cost grid case, or uniform. Unit cost grid case. is this necessary? No. now give a source and a target and again, I've got my six by six grid shown here with a source in the upper left and a target in the lower right, I'm going to allow you to have different costs for each cell. So it will It will no longer be the case that when we do the expansion process to you know, sort of search for a path when I say find all the cells that are paths of length 6. Find all the cells that are paths of length 7. Length is not really what we're going to be looking at anymore. We're going to say, oh let's find the cells that are the cheapest to expand next and we'll figure out what they cost and what they cost will be based on the cost of the path to find them and the cost of the grid. That is used. So we need to find some different language for describing how this expansion process works. The process is going to be basically the same. The sort of the way we describe it is going to get a little bit different. What we're going to move toward is finding the minimum cost path. That connects the source to the target. So, what are we going to do? We're going to put some new cost items in the grid. So in my grid a great big set of orange squares has appeared. two cells high, three, four cells wide and they all have threes in them. So, it does not cost one, to add this cell to your path, it now costs three to add this cell to your path. So, you can think of this as being something that's expensive and we'd sort of like the path not to use it if it doesn't have to. Alright that's what you do with the cost. And so just to be clear, the shaded cells, the orange cells, cost three and the unshaded cells, the white cells, cost one. It's just easier not to put all the ones in the grid, it just makes it visually, sort of cluttered. So a white cell cost one, something that doesn't cost one I'm going to label it for you in some special way. So we needed to find a new metric for the quality of our paths, and that's just the path cost. And that's just the sum over all the cells in the path of the cost of each cell. It's really quite simple. Take all the cells you use in your path, add up the costs. So here on the left I've got my six by six grid again, with a 2 by 4 element of 3's, the high cost things in it. And I've got a sort of a straight simple path from the source in the upper left to the target in the lower right. It's just an L shape. Four cells in the vertical arm north to south, four cells in the horizontal arm west to east. What does this path cost, this bright red path cost? And the answer is, well, the source cell costs 1. The next cell costs a three, the next cell costs a three, the corner cell costs a one, and then the other cells that get you to the target cost a one. 1 plus 3 plus 3 plus 1 plus 1 plus 1 plus 1, that's 11. This path costs 11. So the short straight path costs 11. What's another path you might consider? Well, how about this path? This path avoids the high cost region. This path first goes to the west by one cell, then goes south four cells, then goes east five cells to make a connection to the target. It doesn't use any of the cells that cost three. What does this path cost? The answer is, well every cell on it costs 1. The source costs 1. The corner at the top left costs 1. The path down costs 1. The corner at the bottom left costs 1 and then all the cells on the path to the target cost 1. You add them up, there's eleven of them. I'm sorry, there's nine of them. This path costs nine. Oh, look, something interesting happened. The path on the left is short, but the path on the left is expensive. Why is it expensive? Because it used this high cost region and maybe we don't like that. The path on the right is long, the path on the right is cheap. Perhaps, we prefer the path on the right unless the wire Is in trouble. You know, it's got blockages all over the place. And the wire really urgently needs to use that piece of space. then okay, I'll put the wire there, even though I'll make it more expensive. But if you can, please find a path that doesn't use those, those high cost cells. This is an incredible important way. That you can change the, the, the fabric of the routing grid in ways that will encourage nets to take paths that you like. This is a big deal. This is very important. This is a really vital feature of all real routers. You use costs to encourage wires to take shapes that you prefer. So you can make the router avoid a congested area. Suppose you can do some analysis that says some regions of the chip are going to have way more wires that want to put their paths there. Then there is space to put paths there. You might put some big cost values in the grid so that the early wires you route don't just go there, and you leave enough space for the later wires to get through when you need it. You can make different layers have different costs to use. You can make different via's have different expense to use. You can make different directions of expansion more expensive. You know, you might decide that some layer you want mostly vertical wires, or some layer you want mostly horizontal wires, we'll talk about that later too. but it does have some some profound impacts on the search process of expanding out. So it's no longer the case that we're going to say, find all the paths that are find all the cells that are on paths of length six. And find all the cells that are on paths of length seven. Then find all the cells that are on paths of length 8. No, that's the way you started but now what we're going to say is, find the cells that are labeled, whose neighbors are not labeled. Figure out what it costs to reach the cells that are not labeled. When you do that then, find the new cells that are not labeld who have neighbors that are, find the new cells that are labeled with the cost that have neighbors that are not labelled with a cost. You get the same expansion of way fronts with costs but you're not really just searching all the paths of link k and then all the links of path of link k plus 1. and we get some, some technical questions. You know, what does it cost to reach one of the non-unit cells? What does it cost to put a v on a non-unit cell? So let's just go look at the mechanics. Here's our friend, the grid, 6 by 6 source in the upper left target in the lower right, 2 by 4 region of high cost cells that cost 3 in the middle. we can still start with the same language, right, you know. The source is going to cost 1, and we're going to find all the cells that are sort of you know 1 unit away, in distance. We're going to find all the neighbors of the source. But then we're going to have to find some different language for, for labeling things for the way this sort of works. So, you know when we start the source gets a cost of 1. That makes sense. And then we're going to look at the neighbors of the source that are not labelled with a cost value and say what does it cost to get there? And those are all the cells that are just next to it, you know, one cell away. So to go to the west, that costs two, one plus one. To go to the north, that costs two, one plus one. To go the the east, that costs two, one plus one. But to go to the south, that costs four. Right, that costs four because that's one plus three. I'm just going to put an arrow that says, that cell costs four because You expanded the source, which cost one, using the cell, which cost three. Right, so, so far this is all good. And, you know, there's nothing interesting here. And you wonder why I'm belaboring this point. But now, let's look at the cell that's to the south and the east of the source cell. We have not seen this situation before. In all of the previous examples that we did. Both of the neighbors of this red highlighted cell would have had the same number on them, they don't. The cell to the north costs 2, that's the minimum cost path to find it. And I could expand to the south to reach the cell. I could also use the cell to the west that costs 4 and I could expand to the east. what's the right answer. So, just to put this in words, what is the cell's pathcost to be reached? The highlighted red cell, that is the south and the east of the source cell, that is orange, that costs three. Is it 2 plus 3 equals 5, because I'm coming from the north? Or is it 4 plus 3 equals 7, because I'm coming from the west? And the answer is it costs 5. And it's important that you always, always want to label cells with the minimum pathcost to reach that cell because otherwise this whole idea doesn't work. I want to be able to search the grid to find paths of minimum pathcost, what that just means when you add up all the costs of the cells on the physical path I get the path with the smallest number for the pathcost. So the right answer is though cheapest way to get the cell. the red, highlighted cell is five. It's to go east through cell because it cost two, and then it goes south with the cell that costs five. We're going to have to get teh mechanics of this algorithm right so that it always does the right thing. Next, what if I have a via scenario? So, I've got basically the same scenario from the previous slide, where the source expanded. And, you know, there were some twos to the west and the north and the east. And a four to the south. And then there were some threes in a diamond around that, but there's five to the south and the east of the source. And suppose that five, the big red square, wants to expand to layer two. So I've got another six by six grid on the right side here. And its got a great big area of high cost that's two cells wide and four cells high. Sort of on the left of this is all those cells are real expensive, they cost six. And one of the things that's true is that cell that's red on the left on lalyer on that wants to but a via to go to layer to that's part of a high cost region. If you put a via in and you go to layer two, that cell costs six. So I have a question here. What does it cost to get to that cell? Okay. What does It cost to get to the same cell three rows down from the top, three columns over from left in layer two, if we expand from the cell that costs five in layer one? And the answer is I need to know what the via costs so I've got it highlighted here the via cost 20 so what does it cost to get to that cell labeled 6 because the cost of that cell is 6 in the layer 2 grid. And the answer is it costs 31. Why? The cell you started with cost a five. That was the pathcost to get to that cell on layer one. It cost 20 to put the via there. Why? Because I told you that it cost 20 and vias are expensive. The via gets you to layer two. What does it cost to use the cell that you land on in layer two? Answer, six. Why? Because I said so. That cell is expensive for some appropriate reason. What does it cost to get to that cell on layer two? 5 plus 20 plus 6, 11 plus 20, 31. It costs 31 to use that cell. Alright. So, what do we do? We're going to show you some mechanics to search these grids, parallel grids with complicated costs and complicated via costs, to find the minimum cost path. It's going to turn out, to be a surprisingly simple an elegant algorithm. So, here's a kind of a midpoint summary. What do we know? We know about this grid based expansion, one net at a time thing for maze routing. And that we can use costs in the grid to get different effects. And we know we can deal with complicated physical scenarios like multiple wiring layers and multi-point nets. But there's a bunch of stuff we don't know, and we just started to get to the point where not knowing it was a problem. Problem. I don't know real implementation strategies. I don't really know how I build this thing. I don't know what the real data structures are. I don't know how cells get touched during the search, that's the big thing. how do I expand cells, how do I reach cells? You know, it was good and easy when I said, find all the paths of length seven. Good. Find all the paths of length eight. They are one cell away. When these cost values start happening you know you gotta be a little more careful. And there are some subtle interactions between the cost strategy and the search strategy. And surprisingly enough, there are some cost mechanics we can put in that actually break the way the search works. And even though they break it, we do it anyway because it's actually really important to the physical stuff we're trying to accomplish with the router . So we've done sort of a discussion of the features that we want in routing from the point of view of the user, you know somebody trying to wire nets. Next, I got to look at the real implication mechanics. And so were going to put our Computer Science hats on and were going to say, hey algorithms, data structures, how do we actually make this stuff work? Let's go look at that next. [SOUND].