[SOUND]. So, here in 11.2, we are going to show you the world's simplest router. So, what's the world's simplest router? Everything lives on a simple grid. All of the wires have exactly two pins, so they have a starting point and an ending point which are traditionally called the source and the target. All of the routing takes place on one physical layer of material so think of that as one layer of metal available on an ASIC. You can't change any layers. And your only goal is to connect the first pin to the second pin. the mechanics of that are surprisingly straight forward. It's a maze search process, and depending on what computer science you've done in the past, you may have actually written code to do something like find a path through a maze. It's a famous classical problem, and interestingly enough, it's the basis for essentially all routing that we know in the ASIC universe. So, let's go look at the simple routing problem for 2 point next. So let's start our discussion of the most basic kind of maze router with just a little bit of history. I guess history, if you will, after Moore's Mazes. So 1959, Moore publishes this basic idea. A certain kind of a breadth first search through a grid, and it's really famous. In 1961 just a couple of years later, it gets applied to electronics, and in this case the wiring of print circuit boards, and so a person named Chester Lee at AT&T Bell Labs publishes a famous paper. An algorithm for path connections and its applications. And he basically says, you know, this idea for more for how you find the path through a maze that's kind of like routing things on print circuit boards with obstacles. And he gets famous for sort of making these connections and for something like a quarter of a century, all of the routers that are these kind of routers are called Lee routers. When I was in graduate school, these things were called Lee routers. In 1974, almost 15 years later, Frank Ruben who was working at IBM makes another interesting connection. He's reading some of the, early, early developments in artificial intelligence. People doing certain kinds of search algorithms, and he say's oh, some of these interesting ideas in AI can be applied to this particular search process and you can make it go much faster. And so, interestingly he says, you know the title of his paper is The Lee Path Connection Algorithm, which is again you know, Lee, that guy Chester. and that's another core technique that gets used in everybody's router today. And then in 1983 Dave Hightower, he's a very interesting guy publishes another paper called the Lee router revisited. And it turns out for something like a dozen or so years, people previously people had said in the industry you know, this Lee router thing is really great. But we just don't have enough memory in our computers to build the grids that represent the things we want to route. And so we're going to do some other interesting, clever kind of algorithms. And Dave Hightower got famous for another kind of a router and called a high tower router. and so it's a remarkable conversion when Dave publishes a paper that says, you know, modern computers, you know, computers with astonishing 8 MB of memory. And a virtual, memory, memory hierarchy. So you have a disc that can store things that are bigger than 8 MB. You know, if you have a modern computer, you can actually use a Lee router. You can actually use a grid. You can actually use this really great algorithm. It can route really big, really complicated stuff. And you know, it's sort of from that point thereafter, there's no looking back. You know, most modern routers use this kind of idea. So, a little really, really, really early history, if you care. So, the maze routing strategy at a high level is that we're going to route one net at a time. We're going to completely route the one net, and then we're going to move onto the next net. And we're going to optimize the path of the net. we're going to find the best wiring path for each one. And so there's some problems. early nets that are wired may block the path of later nets that's actually easy to see in the little example. You know, the optimal choice for any one net may not be good for a later net so, you know, I route this, this pair of two points with this wire on one layer. I route this pair of two points with a, with a, wire on one layer. Then I'd like to route those two pair of red points there, and you know, what do I see? I see that I can't do it. So you know, now I've got these two elbows that go up and to the right that are blocking basically the horizontal left to right accessibility in this little rectangle. Then I've got another little elbow that goes from below to above and those two blue wires are simply obstructing it and I can't get around them. On one layer I can't get around them. If I have multiple layers to route, I can get around them by going up to a different physical wiring layer, so that's a non trivial problem. We're going to have to figure out that. We'll talk about that later. So blocked. That's the word. It's blocked. So the basic maze router, the basic idea is you're going to give me a grid, and each square cell represents where one wire can cross. And we're going to start by connecting two points, and the points are historically and traditionally called the source and the target. You start from the source, and you route to the target. And the problem is to find a shortest path connecting the source cell and the target cell. And, so when using the cells, a wire can, for example it can cross the cell, so you can cross vertically. You can also cross horizontally, or you can bend, you can go into the cell and you can sort of turn and go out sideways. So you can do anything you want in a cell. As you can just assume that all the geometry is correctly set up so that any wire can cross any cell. So, that's how it works. So, what's the big core idea of a maze router, you start with a source cell, you know, just this single cell and then you find all the new cells that are reachable at pathlength one. And so what that means is what are the ends of all of the paths that start at the source that have exactly one unit of total length. Which is to say, that are one cell long. Mark them all. Well interestingly enough, it's just the one cell, right? What are all the cells that are one cell long that start at the source? And the answer is, the source. That's it. Well, but then there's the more interesting question, what are all the cell, the paths that are two cells long that start at the source. And the answer is, those are all of the cells that are adjacent in the north, south, east or west direction. Right, so there's the cell that's adjacent on the north. There's the cell that adjacent to the south. There's the cell that's adjacent on the east. There's the cell that's adjacent on the west. and basically it's all the cells in the grid that are immediately adjacent to the cell labelled 1. And so what you immediately see is this little diamond pattern, right. There is a one in the middle and there are a little sort of a diamond, 2 above, 2 below, 2 to the left and 2 to the right. Or if you like 2 to the north, 2 to the south, 2 to the west and 2 to the east. The big idea in Maze routing is you just continue this process. That's the big great idea. You find all of the paths that are three units in length, well those are the paths that one unit of cells farther away from the twos. You find all of the paths that are four units in length, those are all the cells that are one unit away from the threes. And you just keep going until one of those cells labels the target with a path cost, a pathlength and you found a path. So, we are going to do this one by me writing then we will do these with animation thereafter. But it is worth just sort of, you know, doing it yourself if you like. So what do we do? We start with the source cell. We say, what are all the paths of length one? And the answer is, it's that one. Okay, what are all the paths that have length two? And the answer is, it is this diamond of cells north, south, east and west of the source one cell. Okay, what're all the paths of length three? And the answer is, it's this diamond of cells right and when I say diamond I mean basically things that look like that. It's this diamond of cells that are one unit away from the twos. Okay, what are the paths that are of length four? And the answer is, it is all of the cells that are one unit away in the north, south, east or west direction from the threes. Okay, so there's a little more of the diamond, and one of the things you see is that I'm not getting the entire diamond because some of it, you know, I can't do fours on the north and the left side, the north and the west side of this chip because the source is up in the left corner. All right, where are the paths that are five units of word in distance the answer is they are one unit away from fours, so the time end is getting bigger. Where the paths there are six paths in the length, oh, well those are the ones that are one unit away from five. Where the paths there are seven units away oh, look they are also one unit away from sixes. Oh, look I have hit the target. I have labeled the target with a number, and the number I have labeled the target with is a seven. What does that mean? There's a path of length seven from the source to the target. Sound simple, that's the deal, right? there's a little bit of language we're going to revisit here. Each of these expansion steps, you know going from the threes to the fours, going from the fours to the fives, going from the fives to the sixes, creates a wave front of paths. And the analogy is usually you know, if you drop a rock in a pond, the waves, you know, sort of go out in a circle. Well in this case the waves go out if I kind of draw it here the waves go out in a diamond kind of a shape. So that's the core idea. now what do you do? Well, you do a step called back tracing, but before we do that, let's just do that previous step again. But we're just going to do it with animation so you can see it with nicer looking handwriting, right? So where are the cells on the paths of length one? It's just the source cell. What are the paths of length two, it's the diamond around the one. What are the paths of length three, it's the diamond around the twos. What are the paths of length four, one unit of cells away from the threes. What are the paths of length five, one unit away form the fours. Where are the paths of length six, one unit away from the fives. Where are the paths of length seven, one unit away from the sixes, and what we have discovered here is that I have labeled the target. I've labeled it with a seven, okay. Now what do I do? I do a next step called backtrace. Select the shortest path. Any shortest path, there is a couple of, there is actually several shortest paths. There is lots of paths between the source and the target, select one, mark the cells, so they can not be used again. In particular, we are going to mark them as obstacles, because this path once we embed it as a real wire and obstacle, the next wires I route can not use this space. And since there's many paths back, this optimization, optimization information can be used to select the best one. this particular case it's really easy. How do you do this? And the answer is just follow the path lengths in the grids. You want to find a path from the target to the source. The target is a seven. Find a six. From the six, find a five. From the five find a four, from the four find a three. Right, so we can simply do that and what will happen is, I'm going to choose the horizontal path seven to six to five to four on the slot of the second row of the grid on the bottom. And then continuing, I'm going to choose the vertical path four to three to two to one and so those pink cells are the back trace result. Once the target is labeled with a number, go look at the grid and follow the numbers backwards in decreasing order until you find the source cell, that's your path. Then what do you do? You do a step called clean-up, and clean-up is just what it sounds, clean-up says, get rid of all the stuff you put in the grid, so that the grid is in a state ready to route the next wire. So if you just put some path length numbers in the grid please go erase them all. And let's also just make sure that you relabel the path you just found as an obstacle because the next wire can not use any of those cells. So its got a big black l shaped thing right in the you know kind of in the middle of this grid saying oh look I have embedded a path. And now this grid is ready to route the next net. With previous nets represented as obstacles. Now the obstacles are, are, we sometimes call them obstacles. We sometimes call them blockages. Any cell you cannot use for a wire is an obstacle. An obstacle or a blockage. There may be parts of the routing surface you just cannot use, so before the problem even starts, we'll have labeled those things. But the biggest thing is you'll label each newly routed net as an obstacle and so future nets will route around. So as a little example, I'm showing a new source and a new target here. and if I was going to route this net I would be doing, you know, exactly the same sort of a thing. I would I would say, oh, look, you know, you put a one down, you find the paths of length two, they are one unit away. You find the paths of length three, they are three units away. And now you see, I've got an obstacle, I can't expand those threes any more. You find the paths of length four. Those are the ones that are adjacent to the threes. You find the paths of length five, and you see this interesting phenomenon here. Oh, look, I'm sort of going around around the obstacle. You find the paths of length six. Oh, look, I'm going around the obstacle. You find the paths of length seven. Oh, look, I'm going around the obstacle. You find the paths of length eight. Oh, look, I'm going around the obstacle. You find the paths of length nine. Oh, look, I found the target. Right? If I backtrace things back, what I'm going to find is a wire that probably looks something like that. And hey, I embedded the first wire. I made it an obstacle, and the maze routing idea of expanding outward as of length one, two, three, four, by just looking at the neighbor cells. I'll actually respect the obstacle, I'll actually respect the desire to find a shortest path. I can do very many interesting realistic physical things with a pretty simple algorithm. It's a beautiful thing, very famous, lovely, lovely result. So that's the basic idea. Summarizing the three big steps, expand a breadth first search to find all the paths from the source to target in path length order. Why do we call it a breadth first search? You find all the paths of length three before you find the paths of length four. You find all the paths of length four before you find all the paths of length five, and so on. Backtrace, walk a shortest path back to the source. Back to the source. And then mark the path cells as obstacles so that you can keep routing. And then clean-up erases all the other stuff you put in the grid, returning it to its original and pristine state, so that you can route the next net with the previous nets represented as obstacles. So that's the basic idea. It's pretty powerful. But to be honest, a little limited. Because there's just a lot of physical stuff and a real routing problem we haven't dealt with. How do I route something that has more than two point nets? How do I handle more than one routing layer? How do I deal with vias that physically connect form one layer to the other? And I haven't really told you anything yet about implementation, you know, do I really need a big grid, what information do I have to put in every cell in the routing problem? Do I really have to search the whole grid every time I do one of this? You know, I mean, there's some tricks that make it go fast? And, and the answers are, yeah, there's all kinds of tricks, there are things are make it go fast. So, we're going to look at both kinds of concerns. we're going to look at the applications and features, components for the first couple of lectures in the, in the next set to understand how you handle things that are really required in a router. And then we'll move on to the interesting deep implementation stuff , the sort of the more computer sciencey kind of stuff. Like what are the data structures look like and what do the algorithms look like. So let's get started on that. We're going to start adding some features to our core router next. [MUSIC].