[SOUND]. So, welcome to Lecture 11. Where we are in the class, you know a lot about logic and synthesis and optimization and representation. You know how to place the logic. We now know as of last week that there's a magic step between the synthesis activity and the placement activity which is called technology mapping. That takes the stuff that comes out of synthesis and turns it into a real gates available as standard cells in the technology library. And you know how to place things, so what's next? What's next is routing things. You actually have to connect the wires. You actually have to connect to the logic, so the outputs go to the inputs of the next gates. A large ASIC can easily have 10 million or 20 million wires. That's a whole lot of work. It's an interesting algorithmic universe for how we do that. And in this lecture sequence, we're going to actually explore that. So, let's start with sort of a basic overview of what's going on in the routing task. So, we have figured out how to place all of the gates that are created by logic synthesis and then technology mapping. From our technology library, and we have the new problem of figuring out how to connect the wires. So this is the routing problem. And in our, you know, our big ASIC, you could have thousands of macro blocks representing you know, memories and other predefined chunks of things like processors and such. Millions and millions of gates, and millions of wires literally. A big ASIC. A big ASIC could be 20 million wires or 40 millions wires. You're going to end up with, literally, kilometers of wire on the surface of the chip. It is physically impossible to do any of that stuff manually. We need tools, we need software to do this. So, this is what we're going to start talking about. So, one of the basic filing problems that we have to think about. Like I said, the first is scale. Big chips have an enormous number. Millions of wires, and not every wire gets to take an easy path to, connect its pins. So it would be nice, if you have a wire that you know, just sort of, goes in some nice simple path but you know, it might have to do something. Kind of unpleasant to actually get connected. You must connect them all. You can't afford to imbed any wires manually. It's just too difficult and we have a lot of geometric complexity now too at the nanoscale with, with, You know, wires that are some number of tens of nanometers across, the geometry rules are incredibly complex just, just to make the physics work. And that really makes the routing hard. nevertheless we're going to do what everybody does when we start talking about routing, we're going to use a simple grid representation of the layout. It turns out that's the right place to start, and in fact the way real routers The work is they, they have a sequence of tools. So just like placement, we got rid of some detail. We, for example, pretended the wires were two point springs, we pretended the gates had no physical size. And then we dealt with the, the massive scale part of the problem and then we circled back later and we did some other work to, to deal with the physical problems like the gates overlapping. When people build real routers we do the same thing. We make geometric abstractions like everything's on a grid. We deal with most of the problems with the simple geometry. And then we go in very close and we deal with, the, the detailed problems of, of, you know, rectangles and nanoscale physics. So we're not going to be able, to, to do that. We're going to do the big macroscopic problem. There's also a lot of electrical complexity to deal with. it's not enough to just make sure you connect all the wires. You have to ensure that the delays through the wires are not too big. That there are any wire to wire interactions, so, electrical cross talk. A signal on one wire very close to another wire effect the electrical outcome. Lots of interesting rules to worry about. Lots and lots of interesting rules to worry about. We don't have time to talk about all of these things. We're mostly going to try to deal with a scale problem, how do you actually route a lot of wires with a simple geometric representation. So, the first physical assumption to, to be aware of is that there's many layers of wiring available for routing at any real asic. So they are made of metal today, they're, they're copper. and we can connect wires across different layers with things called vias. And so, these are, you know, literally. Little plugs of metal that go from one layer of metal wiring to another layer of metal wiring. Here's a real simple view. This is a standard cell, a single standard cell, something like an NAND gate drawn in a kind of a 3D representation. And, you know, standard cells would typically be using metal on layers 1 and 2 to sort of connect things on the inside, right? So in this particular case Things that are going in this direction are, are the metal one. So that's things like this. And things going in this direction, like that would be the metal two. And then there's some other stuff happening, going again in the other direction up here. That's, that's a metal three. you know, the standard cell's internals would be, you know, routed down metal one and two, maybe metal three. the routing of the wires that would be connecting the logic gates would be up on, you know, 3, 4, 5, 6, 7, 8, maybe even 9 and 10, depending on the particular technology. The upper most layers of the wiring are often reserved for special things like the clocks, global signals, power distribution, things like that. Here's a typical example from about 2000, this is just from Wikipedia so I'm allowed to show it. this is a cross section of the way a five layers of routing of ASIC might look. Little bit of terminology if you look closely at the picture, and on the next slide we'll zoom in here. FEOL, that's what it says over here. That's Front End Of Line. And the line means the fabrication line, the manufacturing line. The front end stuff are the chip fabrication steps that make the transistors on the silicon wafer. Now that's as opposed to this label over here, the back end of the line. Those are the fabrication steps that make the wires. And what you can see is that in terms of the vertical space, it's mostly back end of line. Because all of these wires are, you know, separate layers. This particular picture's cross sectional view of both the front end and back end of line stuff for five layers of wiring will always have stuff happening up at the top which is actually some packaging stuff. That's the big blob up at the top that's the sort of bump. We are going to talk about this just a little bit more on the next slide. So here's the same picture again but now, let's just talk about this a little more carefully with a little more labeling. So again, the stuff at the bottom, those are the transistors. That's how we make the switches that actually make up the insides of our gate level logic. And then what we have, the orange things, are levels of metals. And so there's a layer 1 metal down at the bottom and then on top of that a layer 2 metal, and then on top of that a level 3 metal. And if you look very closely it will say something like CU1, CU2, CU3. CU means copper. So this is copper layer 1 metaling, copper layer 2 metaling, copper layer 3 metal This is the wiring for the logic, this is how you connect stuff to make the logic. On top of that there are yet more layers of metal, metal 4 and metal 5. And if you look very careful with this, one of the things you'll see is that the metal layers at the top are a little wider and they're a little thicker. And there's a reason for that. This is a designed part of all modern ASIC kinds of technologies. They're designed to be a little wider and a little thicker so they offer less electrical resistance. And the reason is for that is because you're going to be doing some special stuff up there. Like routing the clock that connects all the flip flops. And routing the power distribution and so you really care about things like resistance being low. And the way you do that is by making things thicker and wider, up at the top. Now there are also vias, and so what you see is between every layer where there's sort of a big orange thing right, which is some little piece of some wire. There's a small orange thing, and this is basically a little plug where, you know, more or less, you can imagine this is a hole that goes from one layer above layer k plus one to a layer below layer k of the metal that you fill in with the appropriate metal and so you actually make a connection. So, there are vias that connect from metal 1 to metal 2, metal 2 to metal 3, metal 3 to metal 4, metal 4 to metal 5. That's what those little yellow circles are. And, up at the top, we've actually got a little piece of something interesting, this is package level interconnect. Because the wires, you know, on the chip need to connect to electrical connections off the chip. And they are at a much larger physical scale. And so, what that thing is up at the top is a solder bump. And that's just literary a big blob of metal. Which is the appropriate electrical connection to a pin on a printed circuit board somewhere so you can take this chip, put it in the appropriate package. Okay, and you know, connect it to its package and connect the package to the board. Okay? So, cross-sectional view of five layers. the only difference between this and today is that today, you know, you could have ten layers of metal, maybe 12 layers of metal, depending on the technology. So, a little bit about placement versus routing. There are lots of different kinds of placement algorithms. I mean, there are iterative methods. They're most used for floorplanning these days, but, but you know, they're around. There are lots of different kinds of analytical methods. I should you one, the so-called quadratic method. There's lots of different quadratic placement methods. They're other methods that involve creating very large systems of non-linear equations and then solving them with clever means. honestly there are not quite so many routing algorithms. there's a small selection of critical algorithms for the, for the, for the routing tasks. what they really are they're lots of routing data structures, there's tons of innovation, tons of interesting proprietary stuff, where people innovate around how one represents the structure of the surface on which we're routing. To represent the challenge efficiently, but there's one very, very big idea and since I only get you for a week for a couple of hours, to talk about everything interesting in routing. There's one very big idea and that's the right thing to talk about in this lecture. And so this is the big idea called maze routing. From one amazing early paper from EF Moore, The Shortest Path Through a Maze from, wow, 1959. EF Moore's Wikipedia page. Very famous guy, worth, worth taking a look. And, as an aside, yes, it's that Moore. The Moore of Moore state machines, as opposed to Mealy state machines. It's that Moore. He's a really famous guy. And it's a very famous method, and depending on what computer science kinds of courses you've taken in the past. You might have actually built something that finds a path through a maze, because it's a beautiful, simple idea. And it's the basis for just tons of useful stuff in the chip design space. So let's talk about how we get from a maze to a wire. So we're going to make a huge geometric assumption which is called a gridded routing. The layout surface is a grid of regular squares, and a legal wire path is a set of connected grid cells. Through unobstructed cells in the grid. And, so we can mark obstacles, things that obstruct, which we also call blockages, which are places we're not allowed to route. So, more or less simply put, we mark in the grid where we're not allowed to route, and everything else in the grid is a place we are allowed to route. And so, for example, there is an obstacle. You know? Just a big black box that blocks things. And, here is a wire. Okay, and the wire starts at a cell labeled with an s and it goes to a cell labeled with a t. And it goes Left and right, and then up and then to the right and up. Now, this there's a reason the wire looks this. So for us, wires are strictly horizontal and vertical. There are no diagonals or funny angles, no 45 degrees. And it's often the case that we'll describe paths by compass Directions. And so this is just a set of compass directions, north on the top, south on the bottom, west on the left, east on the right. And so sometimes I'll say top and bottom and left and right, but when I'm trying to be more precise, I'll use compass directions, which is actually quite common in the router business. So, north is the top. The grid assumption is a pretty critical; assumption. It applies a surprising amount of restraints on the wires. So it applies that all the wires are roughly the same size, in, in terms of their width. Or more precisely that the wires and their vias which connect from one layer to another all fit in the grid. Without any rule violation. So the spacing rules are appropriately met. So, for example, I can put you know, this wire on the left in this pair of grid cells vertically and this wire on the right in this pair of grid cells vertically. And so there's just this little grid here, you know, four cells across, two cells high. I've got two blue wires going up the middle two columns. And, and then there are vias in the top of the middle two columns. And that apparently connects to a red layer, which looks like it's below. that goes to the left and the right. So let's say layer K plus one is the blue layer. Layer K is the red layer. One of the things that I could do right now is I could put another wire. and I'm just sort of drawing it in the left hand column here. I could put another wire on layer k plus 1, and that would be legal. Right. And I know that would be legal because the grid is set up so the spacing rules are all just satisfied. So I can put a v anywhere I want in this grid. I can put a wire anywhere I want in this grid. I don't have to worry about leaving any blank grid cells when I route things. The gird is set up so that I can use any unobstructed grid cell to put my wire down and it'll all just work. Another thing that's true is all the pins we want to connect to also have to be what is referred to as on grid, which means they are in the center of one of those grid cells. So if I route a wire into a grid cell and you tell me there's a pin there, we both just agree that I connected it, because we agree that the pins are right in the middle of the grid cells. So it implies a lot of sort of precise low level geometry kinds of assumptions and it's often an approximation of reality. but as it turns out it's a good approximation of reality, because you know when you've got 20 million wires you've got to simplify some stuff to be able to make some progress. So we simplify some things. We solve most of the problem with a little bit of geometric simplification. We'll cycle back later. We'll put the extra detail at the end. It's a good engineering approach to things. It works. So what are we going to do in the maze routing business? Well here's our, our high level roadmap for the rest of this lecture. So we're going to talk about, first about function. You know, the things we want to router to do the first thing is two-point nets in one layer where everything costs the same so called unit cost that's the most basic router. Then we are going to talk about multi-point nets because not every net has two points or two pins on it. Then we are going to talk about routing in multiple layers because real ASICs have more than ten layers of wiring. And then we're going to do something interesting, non-uniform costs in the grid. We're going to actually show how yo can change the structure of the routing surface to encourage wires to take paths and shapes that you think are good, rather than bad. That's the discussion of functionality. We're then going to move on to a discussion of implementation mechanics, right. And for that, we're going to talk about, like How do you actually build code and what are the data structures? Right? So we're going to talk about the expansion method, which is sort of the heart of maze routing. We're going to talk about the data structures. We're going to talk about a surprising idea that there are some constraints on the way the cost model works and if you Do not violate those constraints. There's some beautiful things that are true about the structure of how your algorithm works and if you violate those constraints, the way your algorithm works gets a little bit a little bit more difficult. And interestingly enough in real engineering routers, everybody violates the constraints and it's just tough, you just have to live with it. And then we're going to talk about some mechanisms that make the router go fast, something called depth-first search. And then for just a little bit at the end, we're going to talk about the fact that there's actually some really interesting divide and conquer that happens in this universe as well. There's something called global routing which is different than the first part of this lecture, which is something you will find out at the end is called detailed routing. And that's how we'll end. So that's our very interesting high-level road map for routing. So let's get going and start talking about how real routers work. [SOUND].
