So here in 11.3 we're going to advance to the next step in our exploration of routing. In the previous lecture we showed you how to route nets that have exactly too points. But as we learned in the placer problem, not all nets actually have two points. Nets can have lots of points, they can have lots of points, pins, because there are fan outs, right? You have a logic gate that's driving a whole bunch of other input gates. So you can have wires, nets that actually have lots of pins on them. How do you route a multipoint net? Roughly speaking, you route the first pair of pins and then you take the entire wire and you expand it to reach the next nearest pin and you repeat to go until you find all of the paths. It looks very much like the two point problem and one of the things that's really cool about the maze routing methodology is that the foundational method is very straightforward but it's incredibly flexible and adaptable. We can keep adding piece functionality features or, you know, interesting stuff. And so the first thing we're going to add is how do you do multi-point nets so let's go take a look. >> So our first feature addition to the maze routing core is multipoint nets. I've got one source and if you like many targets. And look, you're going to get this in any net that represents fanout. So I have let's say a gate here and I have a net and the net connects to, you know, an inverter over here. And a nine gate over here And an exclusive NOR gate over here. And whatever else, I'm, I'm going to have fanout. That has to be able to deal with arbitrary numbers of pins on my net. And there's a surprisingly simple strategy that works okay. we'll talk through it in English. And then we'll, we'll show you a, an illustration. You pick one point as the source. And you label all the others as targets. So this is the first new thing, several targets. And they use the maze-routing algorithm to find a path from the source to something, the nearest target. You don't know which one it is. You're going to route until you find a target, alright? Then you relabel all the cells on the found path as sources. And then you rerun the maze router using all of the sources simultaneously. That requires a picture to illustrate. And you just repeat this for every unconnected target point until you connect all the targets. So, here's my problem. I've got a grid my friendly little six by six grid, and I've got a source in the upper left, I've got two targets sort of on the bottom left, and kind of the middle on the right. and I want to find a short path connecting the source to all of the targets; I want one wire. That does that, okay? And so, the first segment of the path, I'm just going to run the maze router to find the closest target. So I'm going to start at the source, which is in the upper-left, and I'm just going to go until I find the target. So here we just animate that in. So, let us label all of the path, all of the cells that are on the end of a path that's one unit long, and that's the source, so the source cell gets a 1. Let us find all the paths that are two units long. Okay, those are the north, south, east, and west neighbors of the 1, the little diamond shape. Let's find all the paths that are three units long, so those are the 3s that are one unit away, north, south, east, and west from the 2. So the diamond is sort of expanding to the kind of lower left, lower right side of the, of the grid. Let's find all the cells that are on paths four units in length, well the diamond is getting a little bigger and continuing to sort of expand toward the bottom right corner. Let's find all of the paths that are five units in length, so the diamond continues to get a little bigger, the wave front continues to grow and oh, look. I have hit the target with a five, what is it that I know? What I know is that there is a path of length five that will do the job. I know that there is a path of length five from the source to the target and I can just continue to run my algorithm. Now look, remember, I didn't know which target I was going to hit when I started. because you know, this, this layout could be filled with obstacles. So even the fact that the target is close, doesn't mean I know which one I'm going to hit. So, this is the target I hit. I hit the one on the bottom left. Now what? I backtrace, and the backtrace is, you know the process by which I figure out the physical cells in the path and so I'm going to walk backwards from the label five. From the five I'm going to find a four, from the four a three, a three and two and so on, right, so we'll just animate that in. So I'm going to find a five. The four I choose to find is the four to the west, so I'm doing the horizontal thing first, and then I safe that to continue to decrease the numbers, i have to go north. And some that I call north and so there's my path so the path is 1, 2, 3, 4 cells verticals and 1, 2 cells horizontal it's kind of an L shaped path from the source in the upper left to the target in the bottom left. Now there's something new and interesting. I am not done. I am not going to label this as an obstacle. This thing that I've just traced, this path that I've just traced, becomes the source for the next phase of the algorithm. I'm going to label everything in here as a source, all of these cells are going to become the source, and I am going to continue the algorithm. Okay, so what happens? I put an S on every one of those cells, and then I'm just a little bit careful when I do the maze routing step, you know? I'm not going to try to take an S and expand it from a 1 to a 2 by labeling another S, right? I'm only going to look at the empty cells. So going forward this is the scenario. That L shapes wire that was in the left part of the grid, all of those things are sources now. We're going to expand this entire set of source cells to find the next segment, so it doesn't need to be the case that the source is just the cell. The source can be a bunch of cells. And all we have to do is have you know an appropriate semantics for how we label the adjacent neighbors. And the answer is we start by labeling all of the cells that are one unit in length. Right? And that's going to be just what you think, it's going to be all the source cells. They're one unit in length, which is to say, what are all the paths that are one unit away from a source? And the answer is those are the source cells. Right. Now we're going to find all the paths that are two units away. Alright, and the rule is you're allowed to label an empty square. You're not allowed to empty a square that's got a number in it already. So we're not going to try to take a one and overwrite it with a two. So what are all the cells that are two units in length on a path from a source? And the answer is it's sort of a little halo around the source cells. And I'm just going to kind of draw that in a little bit, you know just because it's kind of interesting. Okay. It's this little halo. if the source is a cell, a single cell, the halo is kind of a diamond. If the source is a complicated shape, the halo is kind of a diamond that got kind of smeared over all of the source cells. Right, so those are all of the cells on a path two units in length that starts from any source, and you just keep going. What are all the cells that are three units in length? Well there they are, it's another sort of a halo around all of the twos, and what we can see is that the halo is kind of marching across to the right. What are all the cells on paths of length four from any source? Well the halo continues to march across to the right. And it's kind of vertically going all the way from the top of the grid to the bottom of the grid. What are all the cells on paths of length five form any source cell. And, you know, it continues to march, and in fact the grid is almost completely filled up at this point. And Oh look, we have hit the target, or we've, we've hit a target, in this case we've hit the single remaining target. And next, we're going to do just what we did before. We're going to take the five that we just labeled the target with. And we're going to find a four, and then a three, and then a two, and then a one, and we know that when we hit a one, we have found a source cell. What's interesting is we don't know which source cell, we're going to find the most appropriate source cell. In this case the closest source cell, which when expanded will find a path of length five to hit the target. So, I'm drawing it just like I did before, we started with a 5, 4, 3, 2, 1. The pink thing, which is sort of almost the entire horizontal width of the six by six grid, sort of in the top third, connects the target on the far right to the source on the top left, and there we go. That's the next segment on the path. And like I said, we didn't know which part of the source we were going to start with, that's the right part. So what we do next, we do the final cleanup phase, which is we take the paths, we, the path we found. When we're all done finally with all of the expansions to all of the targets. We label all of the segments that we found as an obstacle because this entire thing is a wire. So this entire multi point, in this case 3 point net, is a wire, all of the subpaths we have found are in obstacle and it all just works. So what have we done? We've just embedded a multipoint net and we've rendered it an obstacle for future nets. So, just a quick aside. does this method give us a guaranteed shortest multi-point net? I mean, is this optimal in any sense? And the answer is no. And that might be really surprising because that looks like a, just a spectacularly clever and good heuristic for doing the multi-point nets. So I'll give you just a little terminology. The optimal path has a name. it's called a Steiner tree. Alright. how hard is it to get a Steiner tree. Exponentially hard. almost everything that's, that's, that's really valuable in the CAD business is, is just really hard. So just another example of why CAD is full of touch and interesting problems to solve. just a quick example. Suppose I have these four points to connect. So I've got a little yellow box with four pins in it. The points are, you know, kind of in the, you know, the upper left, the upper right, the kind of the middle left and the lower right. There are four pins to connect. And the optimum connection is called the Steiner tree, so it's in this case it's a graph. Or it's a, it's a set of paths whose wires are only horizontal and vertical, that has the absolute minimum length, in this case red wires, red lines, the minimum length. and what's hard about this problem is that as you can see here, the wire just like the wire we routed with our little maze routing algorithm. It's not going to be the case that all of the wire segments start on one of the black pins and end on one of the black pins. Some of the wire segments are going to start in the middle of other wire segments. Those points at which the wire segment connect have a special name. They're called Steiner points and one of the things we did in our little heuristic for multi-point wiring was we found a Steiner point. When we did the final trace back of the second target. We connected in the middle of the first wire segment, the point we connected at was a Steiner point. You know, why this is hard in general is you don't know at the start where the right Steiner points are. And, depending on the order in which you pick the first point, and the order in which the expansions happen, and you know some other stuff you know the heuristic is. going to give you a pretty good answer, the heuristics is absolutely not guaranteed to give you the best answer, and that's just the way it works. So simply heuristics worked okay but there's no guarantee that you're going to get the best possible Steiner point. Nevertheless, the heuristic that we showed you It's perfectly good, and you can use it to route multi-point nets. So, let's continue adding functionality to the router. [SOUND]
