1 00:00:00,025 --> 00:00:08,372 [SOUND]. 2 00:00:08,372 --> 00:00:13,081 So, welcome to Lecture 11. Where we are in the class, you know a lot 3 00:00:13,081 --> 00:00:17,809 about logic and synthesis and optimization and representation. 4 00:00:17,809 --> 00:00:21,980 You know how to place the logic. We now know as of last week that there's 5 00:00:21,980 --> 00:00:24,840 a magic step between the synthesis activity and the placement activity which 6 00:00:24,840 --> 00:00:28,883 is called technology mapping. That takes the stuff that comes out of 7 00:00:28,883 --> 00:00:32,417 synthesis and turns it into a real gates available as standard cells in the 8 00:00:32,417 --> 00:00:37,183 technology library. And you know how to place things, so 9 00:00:37,183 --> 00:00:40,010 what's next? What's next is routing things. 10 00:00:40,010 --> 00:00:43,997 You actually have to connect the wires. You actually have to connect to the 11 00:00:43,997 --> 00:00:47,470 logic, so the outputs go to the inputs of the next gates. 12 00:00:47,470 --> 00:00:53,490 A large ASIC can easily have 10 million or 20 million wires. 13 00:00:53,490 --> 00:00:56,794 That's a whole lot of work. It's an interesting algorithmic universe 14 00:00:56,794 --> 00:01:00,140 for how we do that. And in this lecture sequence, we're 15 00:01:00,140 --> 00:01:03,522 going to actually explore that. So, let's start with sort of a basic 16 00:01:03,522 --> 00:01:06,825 overview of what's going on in the routing task. 17 00:01:06,825 --> 00:01:12,369 So, we have figured out how to place all of the gates that are created by logic 18 00:01:12,369 --> 00:01:20,536 synthesis and then technology mapping. From our technology library, and we have 19 00:01:20,536 --> 00:01:24,980 the new problem of figuring out how to connect the wires. 20 00:01:24,980 --> 00:01:28,660 So this is the routing problem. And in our, you know, our big ASIC, you 21 00:01:28,660 --> 00:01:32,860 could have thousands of macro blocks representing you know, memories and other 22 00:01:32,860 --> 00:01:37,390 predefined chunks of things like processors and such. 23 00:01:37,390 --> 00:01:40,920 Millions and millions of gates, and millions of wires literally. 24 00:01:40,920 --> 00:01:45,241 A big ASIC. A big ASIC could be 20 million wires or 25 00:01:45,241 --> 00:01:49,278 40 millions wires. You're going to end up with, literally, 26 00:01:49,278 --> 00:01:52,460 kilometers of wire on the surface of the chip. 27 00:01:52,460 --> 00:01:56,270 It is physically impossible to do any of that stuff manually. 28 00:01:56,270 --> 00:01:58,640 We need tools, we need software to do this. 29 00:01:58,640 --> 00:02:00,385 So, this is what we're going to start talking about. 30 00:02:00,385 --> 00:02:05,800 So, one of the basic filing problems that we have to think about. 31 00:02:05,800 --> 00:02:10,080 Like I said, the first is scale. Big chips have an enormous number. 32 00:02:10,080 --> 00:02:15,392 Millions of wires, and not every wire gets to take an easy path to, connect its 33 00:02:15,392 --> 00:02:19,100 pins. So it would be nice, if you have a wire 34 00:02:19,100 --> 00:02:23,384 that you know, just sort of, goes in some nice simple path but you know, it might 35 00:02:23,384 --> 00:02:29,025 have to do something. Kind of unpleasant to actually get 36 00:02:29,025 --> 00:02:31,120 connected. You must connect them all. 37 00:02:31,120 --> 00:02:33,020 You can't afford to imbed any wires manually. 38 00:02:33,020 --> 00:02:37,245 It's just too difficult and we have a lot of geometric complexity now too at the 39 00:02:37,245 --> 00:02:41,849 nanoscale with, with, You know, wires that are some number of 40 00:02:41,849 --> 00:02:45,725 tens of nanometers across, the geometry rules are incredibly complex just, just 41 00:02:45,725 --> 00:02:50,950 to make the physics work. And that really makes the routing hard. 42 00:02:50,950 --> 00:02:53,988 nevertheless we're going to do what everybody does when we start talking 43 00:02:53,988 --> 00:02:58,290 about routing, we're going to use a simple grid representation of the layout. 44 00:02:58,290 --> 00:03:01,755 It turns out that's the right place to start, and in fact the way real routers 45 00:03:01,755 --> 00:03:05,420 The work is they, they have a sequence of tools. 46 00:03:05,420 --> 00:03:08,340 So just like placement, we got rid of some detail. 47 00:03:08,340 --> 00:03:11,980 We, for example, pretended the wires were two point springs, we pretended the gates 48 00:03:11,980 --> 00:03:15,560 had no physical size. And then we dealt with the, the massive 49 00:03:15,560 --> 00:03:18,836 scale part of the problem and then we circled back later and we did some other 50 00:03:18,836 --> 00:03:23,950 work to, to deal with the physical problems like the gates overlapping. 51 00:03:23,950 --> 00:03:26,410 When people build real routers we do the same thing. 52 00:03:26,410 --> 00:03:30,210 We make geometric abstractions like everything's on a grid. 53 00:03:30,210 --> 00:03:32,810 We deal with most of the problems with the simple geometry. 54 00:03:32,810 --> 00:03:35,995 And then we go in very close and we deal with, the, the detailed problems of, of, 55 00:03:35,995 --> 00:03:38,980 you know, rectangles and nanoscale physics. 56 00:03:38,980 --> 00:03:40,780 So we're not going to be able, to, to do that. 57 00:03:40,780 --> 00:03:42,630 We're going to do the big macroscopic problem. 58 00:03:42,630 --> 00:03:45,350 There's also a lot of electrical complexity to deal with. 59 00:03:45,350 --> 00:03:48,200 it's not enough to just make sure you connect all the wires. 60 00:03:48,200 --> 00:03:50,540 You have to ensure that the delays through the wires are not too big. 61 00:03:50,540 --> 00:03:54,430 That there are any wire to wire interactions, so, electrical cross talk. 62 00:03:54,430 --> 00:03:57,679 A signal on one wire very close to another wire effect the electrical 63 00:03:57,679 --> 00:04:00,550 outcome. Lots of interesting rules to worry about. 64 00:04:00,550 --> 00:04:03,030 Lots and lots of interesting rules to worry about. 65 00:04:03,030 --> 00:04:05,110 We don't have time to talk about all of these things. 66 00:04:05,110 --> 00:04:08,694 We're mostly going to try to deal with a scale problem, how do you actually route 67 00:04:08,694 --> 00:04:12,563 a lot of wires with a simple geometric representation. 68 00:04:13,680 --> 00:04:16,386 So, the first physical assumption to, to be aware of is that there's many layers 69 00:04:16,386 --> 00:04:19,010 of wiring available for routing at any real asic. 70 00:04:19,010 --> 00:04:21,760 So they are made of metal today, they're, they're copper. 71 00:04:21,760 --> 00:04:25,070 and we can connect wires across different layers with things called vias. 72 00:04:25,070 --> 00:04:28,812 And so, these are, you know, literally. Little plugs of metal that go from one 73 00:04:28,812 --> 00:04:32,130 layer of metal wiring to another layer of metal wiring. 74 00:04:32,130 --> 00:04:36,368 Here's a real simple view. This is a standard cell, a single 75 00:04:36,368 --> 00:04:40,290 standard cell, something like an NAND gate drawn in a kind of a 3D 76 00:04:40,290 --> 00:04:44,540 representation. And, you know, standard cells would 77 00:04:44,540 --> 00:04:47,600 typically be using metal on layers 1 and 2 to sort of connect things on the 78 00:04:47,600 --> 00:04:51,158 inside, right? So in this particular case Things that 79 00:04:51,158 --> 00:04:54,180 are going in this direction are, are the metal one. 80 00:04:54,180 --> 00:04:57,925 So that's things like this. And things going in this direction, like 81 00:04:57,925 --> 00:05:00,958 that would be the metal two. And then there's some other stuff 82 00:05:00,958 --> 00:05:03,290 happening, going again in the other direction up here. 83 00:05:03,290 --> 00:05:06,615 That's, that's a metal three. you know, the standard cell's internals 84 00:05:06,615 --> 00:05:10,940 would be, you know, routed down metal one and two, maybe metal three. 85 00:05:10,940 --> 00:05:14,438 the routing of the wires that would be connecting the logic gates would be up 86 00:05:14,438 --> 00:05:17,247 on, you know, 3, 4, 5, 6, 7, 8, maybe even 9 and 10, depending on the 87 00:05:17,247 --> 00:05:22,400 particular technology. The upper most layers of the wiring are 88 00:05:22,400 --> 00:05:26,430 often reserved for special things like the clocks, global signals, power 89 00:05:26,430 --> 00:05:34,065 distribution, things like that. Here's a typical example from about 2000, 90 00:05:34,065 --> 00:05:38,810 this is just from Wikipedia so I'm allowed to show it. 91 00:05:38,810 --> 00:05:46,099 this is a cross section of the way a five layers of routing of ASIC might look. 92 00:05:46,099 --> 00:05:48,304 Little bit of terminology if you look closely at the picture, and on the next 93 00:05:48,304 --> 00:05:52,820 slide we'll zoom in here. FEOL, that's what it says over here. 94 00:05:52,820 --> 00:05:56,126 That's Front End Of Line. And the line means the fabrication line, 95 00:05:56,126 --> 00:05:59,882 the manufacturing line. The front end stuff are the chip 96 00:05:59,882 --> 00:06:03,630 fabrication steps that make the transistors on the silicon wafer. 97 00:06:03,630 --> 00:06:08,290 Now that's as opposed to this label over here, the back end of the line. 98 00:06:08,290 --> 00:06:11,040 Those are the fabrication steps that make the wires. 99 00:06:11,040 --> 00:06:13,965 And what you can see is that in terms of the vertical space, it's mostly back end 100 00:06:13,965 --> 00:06:16,592 of line. Because all of these wires are, you know, 101 00:06:16,592 --> 00:06:19,601 separate layers. This particular picture's cross sectional 102 00:06:19,601 --> 00:06:22,940 view of both the front end and back end of line stuff for five layers of wiring 103 00:06:22,940 --> 00:06:26,438 will always have stuff happening up at the top which is actually some packaging 104 00:06:26,438 --> 00:06:30,682 stuff. That's the big blob up at the top that's 105 00:06:30,682 --> 00:06:33,752 the sort of bump. We are going to talk about this just a 106 00:06:33,752 --> 00:06:37,890 little bit more on the next slide. So here's the same picture again but now, 107 00:06:37,890 --> 00:06:42,596 let's just talk about this a little more carefully with a little more labeling. 108 00:06:42,596 --> 00:06:45,833 So again, the stuff at the bottom, those are the transistors. 109 00:06:45,833 --> 00:06:49,172 That's how we make the switches that actually make up the insides of our gate 110 00:06:49,172 --> 00:06:53,720 level logic. And then what we have, the orange things, 111 00:06:53,720 --> 00:06:57,050 are levels of metals. And so there's a layer 1 metal down at 112 00:06:57,050 --> 00:06:59,941 the bottom and then on top of that a layer 2 metal, and then on top of that a 113 00:06:59,941 --> 00:07:04,474 level 3 metal. And if you look very closely it will say 114 00:07:04,474 --> 00:07:09,860 something like CU1, CU2, CU3. CU means copper. 115 00:07:09,860 --> 00:07:14,076 So this is copper layer 1 metaling, copper layer 2 metaling, copper layer 3 116 00:07:14,076 --> 00:07:18,496 metal This is the wiring for the logic, this is how you connect stuff to make the 117 00:07:18,496 --> 00:07:24,764 logic. On top of that there are yet more layers 118 00:07:24,764 --> 00:07:28,518 of metal, metal 4 and metal 5. And if you look very careful with this, 119 00:07:28,518 --> 00:07:32,117 one of the things you'll see is that the metal layers at the top are a little 120 00:07:32,117 --> 00:07:37,870 wider and they're a little thicker. And there's a reason for that. 121 00:07:37,870 --> 00:07:42,330 This is a designed part of all modern ASIC kinds of technologies. 122 00:07:42,330 --> 00:07:45,102 They're designed to be a little wider and a little thicker so they offer less 123 00:07:45,102 --> 00:07:47,990 electrical resistance. And the reason is for that is because 124 00:07:47,990 --> 00:07:50,490 you're going to be doing some special stuff up there. 125 00:07:50,490 --> 00:07:53,470 Like routing the clock that connects all the flip flops. 126 00:07:53,470 --> 00:07:56,746 And routing the power distribution and so you really care about things like 127 00:07:56,746 --> 00:08:00,284 resistance being low. And the way you do that is by making 128 00:08:00,284 --> 00:08:06,704 things thicker and wider, up at the top. Now there are also vias, and so what you 129 00:08:06,704 --> 00:08:10,466 see is between every layer where there's sort of a big orange thing right, which 130 00:08:10,466 --> 00:08:15,764 is some little piece of some wire. There's a small orange thing, and this is 131 00:08:15,764 --> 00:08:19,469 basically a little plug where, you know, more or less, you can imagine this is a 132 00:08:19,469 --> 00:08:23,060 hole that goes from one layer above layer k plus one to a layer below layer k of 133 00:08:23,060 --> 00:08:26,480 the metal that you fill in with the appropriate metal and so you actually 134 00:08:26,480 --> 00:08:32,570 make a connection. So, there are vias that connect from 135 00:08:32,570 --> 00:08:37,980 metal 1 to metal 2, metal 2 to metal 3, metal 3 to metal 4, metal 4 to metal 5. 136 00:08:37,980 --> 00:08:40,230 That's what those little yellow circles are. 137 00:08:40,230 --> 00:08:43,794 And, up at the top, we've actually got a little piece of something interesting, 138 00:08:43,794 --> 00:08:48,227 this is package level interconnect. Because the wires, you know, on the chip 139 00:08:48,227 --> 00:08:51,671 need to connect to electrical connections off the chip. 140 00:08:51,671 --> 00:08:54,120 And they are at a much larger physical scale. 141 00:08:54,120 --> 00:08:57,800 And so, what that thing is up at the top is a solder bump. 142 00:08:57,800 --> 00:09:00,570 And that's just literary a big blob of metal. 143 00:09:00,570 --> 00:09:05,050 Which is the appropriate electrical connection to a pin on a printed circuit 144 00:09:05,050 --> 00:09:11,450 board somewhere so you can take this chip, put it in the appropriate package. 145 00:09:11,450 --> 00:09:14,302 Okay, and you know, connect it to its package and connect the package to the 146 00:09:14,302 --> 00:09:15,768 board. Okay? 147 00:09:15,768 --> 00:09:20,324 So, cross-sectional view of five layers. the only difference between this and 148 00:09:20,324 --> 00:09:23,544 today is that today, you know, you could have ten layers of metal, maybe 12 layers 149 00:09:23,544 --> 00:09:29,054 of metal, depending on the technology. So, a little bit about placement versus 150 00:09:29,054 --> 00:09:30,760 routing. There are lots of different kinds of 151 00:09:30,760 --> 00:09:33,050 placement algorithms. I mean, there are iterative methods. 152 00:09:33,050 --> 00:09:36,830 They're most used for floorplanning these days, but, but you know, they're around. 153 00:09:36,830 --> 00:09:39,100 There are lots of different kinds of analytical methods. 154 00:09:39,100 --> 00:09:42,360 I should you one, the so-called quadratic method. 155 00:09:42,360 --> 00:09:44,990 There's lots of different quadratic placement methods. 156 00:09:44,990 --> 00:09:48,620 They're other methods that involve creating very large systems of non-linear 157 00:09:48,620 --> 00:09:51,980 equations and then solving them with clever means. 158 00:09:51,980 --> 00:09:54,785 honestly there are not quite so many routing algorithms. 159 00:09:54,785 --> 00:09:58,815 there's a small selection of critical algorithms for the, for the, for the 160 00:09:58,815 --> 00:10:02,422 routing tasks. what they really are they're lots of 161 00:10:02,422 --> 00:10:05,824 routing data structures, there's tons of innovation, tons of interesting 162 00:10:05,824 --> 00:10:09,604 proprietary stuff, where people innovate around how one represents the structure 163 00:10:09,604 --> 00:10:15,770 of the surface on which we're routing. To represent the challenge efficiently, 164 00:10:15,770 --> 00:10:19,130 but there's one very, very big idea and since I only get you for a week for a 165 00:10:19,130 --> 00:10:24,068 couple of hours, to talk about everything interesting in routing. 166 00:10:24,068 --> 00:10:27,428 There's one very big idea and that's the right thing to talk about in this 167 00:10:27,428 --> 00:10:30,487 lecture. And so this is the big idea called maze 168 00:10:30,487 --> 00:10:33,950 routing. From one amazing early paper from EF 169 00:10:33,950 --> 00:10:39,246 Moore, The Shortest Path Through a Maze from, wow, 1959. 170 00:10:39,246 --> 00:10:44,084 EF Moore's Wikipedia page. Very famous guy, worth, worth taking a 171 00:10:44,084 --> 00:10:49,020 look. And, as an aside, yes, it's that Moore. 172 00:10:49,020 --> 00:10:52,680 The Moore of Moore state machines, as opposed to Mealy state machines. 173 00:10:52,680 --> 00:10:54,780 It's that Moore. He's a really famous guy. 174 00:10:54,780 --> 00:10:58,245 And it's a very famous method, and depending on what computer science kinds 175 00:10:58,245 --> 00:11:02,754 of courses you've taken in the past. You might have actually built something 176 00:11:02,754 --> 00:11:06,758 that finds a path through a maze, because it's a beautiful, simple idea. 177 00:11:06,758 --> 00:11:10,575 And it's the basis for just tons of useful stuff in the chip design space. 178 00:11:10,575 --> 00:11:14,550 So let's talk about how we get from a maze to a wire. 179 00:11:14,550 --> 00:11:18,271 So we're going to make a huge geometric assumption which is called a gridded 180 00:11:18,271 --> 00:11:21,658 routing. The layout surface is a grid of regular 181 00:11:21,658 --> 00:11:26,402 squares, and a legal wire path is a set of connected grid cells. 182 00:11:26,402 --> 00:11:31,794 Through unobstructed cells in the grid. And, so we can mark obstacles, things 183 00:11:31,794 --> 00:11:35,634 that obstruct, which we also call blockages, which are places we're not 184 00:11:35,634 --> 00:11:39,715 allowed to route. So, more or less simply put, we mark in 185 00:11:39,715 --> 00:11:43,180 the grid where we're not allowed to route, and everything else in the grid is 186 00:11:43,180 --> 00:11:48,524 a place we are allowed to route. And so, for example, there is an 187 00:11:48,524 --> 00:11:50,750 obstacle. You know? 188 00:11:50,750 --> 00:11:58,990 Just a big black box that blocks things. And, here is a wire. 189 00:11:58,990 --> 00:12:02,934 Okay, and the wire starts at a cell labeled with an s and it goes to a cell 190 00:12:02,934 --> 00:12:07,219 labeled with a t. And it goes Left and right, and then up 191 00:12:07,219 --> 00:12:11,336 and then to the right and up. Now, this there's a reason the wire looks 192 00:12:11,336 --> 00:12:15,990 this. So for us, wires are strictly horizontal 193 00:12:15,990 --> 00:12:20,531 and vertical. There are no diagonals or funny angles, 194 00:12:20,531 --> 00:12:23,706 no 45 degrees. And it's often the case that we'll 195 00:12:23,706 --> 00:12:28,136 describe paths by compass Directions. And so this is just a set of compass 196 00:12:28,136 --> 00:12:32,491 directions, north on the top, south on the bottom, west on the left, east on the 197 00:12:32,491 --> 00:12:36,036 right. And so sometimes I'll say top and bottom 198 00:12:36,036 --> 00:12:38,640 and left and right, but when I'm trying to be more precise, I'll use compass 199 00:12:38,640 --> 00:12:42,530 directions, which is actually quite common in the router business. 200 00:12:42,530 --> 00:12:48,565 So, north is the top. The grid assumption is a pretty critical; 201 00:12:48,565 --> 00:12:50,548 assumption. It applies a surprising amount of 202 00:12:50,548 --> 00:12:53,632 restraints on the wires. So it applies that all the wires are 203 00:12:53,632 --> 00:12:57,120 roughly the same size, in, in terms of their width. 204 00:12:57,120 --> 00:13:00,522 Or more precisely that the wires and their vias which connect from one layer 205 00:13:00,522 --> 00:13:04,730 to another all fit in the grid. Without any rule violation. 206 00:13:04,730 --> 00:13:07,190 So the spacing rules are appropriately met. 207 00:13:07,190 --> 00:13:12,065 So, for example, I can put you know, this wire on the left in this pair of grid 208 00:13:12,065 --> 00:13:16,340 cells vertically and this wire on the right in this pair of grid cells 209 00:13:16,340 --> 00:13:20,830 vertically. And so there's just this little grid 210 00:13:20,830 --> 00:13:23,090 here, you know, four cells across, two cells high. 211 00:13:23,090 --> 00:13:27,280 I've got two blue wires going up the middle two columns. 212 00:13:27,280 --> 00:13:29,910 And, and then there are vias in the top of the middle two columns. 213 00:13:29,910 --> 00:13:33,170 And that apparently connects to a red layer, which looks like it's below. 214 00:13:33,170 --> 00:13:36,744 that goes to the left and the right. So let's say layer K plus one is the blue 215 00:13:36,744 --> 00:13:38,790 layer. Layer K is the red layer. 216 00:13:38,790 --> 00:13:43,550 One of the things that I could do right now is I could put another wire. 217 00:13:43,550 --> 00:13:46,160 and I'm just sort of drawing it in the left hand column here. 218 00:13:46,160 --> 00:13:50,680 I could put another wire on layer k plus 1, and that would be legal. 219 00:13:50,680 --> 00:13:52,802 Right. And I know that would be legal because 220 00:13:52,802 --> 00:13:57,910 the grid is set up so the spacing rules are all just satisfied. 221 00:13:57,910 --> 00:14:00,640 So I can put a v anywhere I want in this grid. 222 00:14:00,640 --> 00:14:03,040 I can put a wire anywhere I want in this grid. 223 00:14:03,040 --> 00:14:07,700 I don't have to worry about leaving any blank grid cells when I route things. 224 00:14:07,700 --> 00:14:12,824 The gird is set up so that I can use any unobstructed grid cell to put my wire 225 00:14:12,824 --> 00:14:19,456 down and it'll all just work. Another thing that's true is all the pins 226 00:14:19,456 --> 00:14:22,642 we want to connect to also have to be what is referred to as on grid, which 227 00:14:22,642 --> 00:14:27,090 means they are in the center of one of those grid cells. 228 00:14:27,090 --> 00:14:30,807 So if I route a wire into a grid cell and you tell me there's a pin there, we both 229 00:14:30,807 --> 00:14:34,583 just agree that I connected it, because we agree that the pins are right in the 230 00:14:34,583 --> 00:14:39,990 middle of the grid cells. So it implies a lot of sort of precise 231 00:14:39,990 --> 00:14:43,620 low level geometry kinds of assumptions and it's often an approximation of 232 00:14:43,620 --> 00:14:46,642 reality. but as it turns out it's a good 233 00:14:46,642 --> 00:14:50,162 approximation of reality, because you know when you've got 20 million wires 234 00:14:50,162 --> 00:14:55,020 you've got to simplify some stuff to be able to make some progress. 235 00:14:55,020 --> 00:14:58,422 So we simplify some things. We solve most of the problem with a 236 00:14:58,422 --> 00:15:02,160 little bit of geometric simplification. We'll cycle back later. 237 00:15:02,160 --> 00:15:05,640 We'll put the extra detail at the end. It's a good engineering approach to 238 00:15:05,640 --> 00:15:06,890 things. It works. 239 00:15:09,030 --> 00:15:10,870 So what are we going to do in the maze routing business? 240 00:15:10,870 --> 00:15:15,490 Well here's our, our high level roadmap for the rest of this lecture. 241 00:15:15,490 --> 00:15:18,452 So we're going to talk about, first about function. 242 00:15:18,452 --> 00:15:22,352 You know, the things we want to router to do the first thing is two-point nets in 243 00:15:22,352 --> 00:15:26,492 one layer where everything costs the same so called unit cost that's the most basic 244 00:15:26,492 --> 00:15:30,235 router. Then we are going to talk about 245 00:15:30,235 --> 00:15:34,450 multi-point nets because not every net has two points or two pins on it. 246 00:15:34,450 --> 00:15:37,586 Then we are going to talk about routing in multiple layers because real ASICs 247 00:15:37,586 --> 00:15:41,466 have more than ten layers of wiring. And then we're going to do something 248 00:15:41,466 --> 00:15:43,940 interesting, non-uniform costs in the grid. 249 00:15:43,940 --> 00:15:47,060 We're going to actually show how yo can change the structure of the routing 250 00:15:47,060 --> 00:15:50,336 surface to encourage wires to take paths and shapes that you think are good, 251 00:15:50,336 --> 00:15:56,560 rather than bad. That's the discussion of functionality. 252 00:15:56,560 --> 00:15:59,628 We're then going to move on to a discussion of implementation mechanics, 253 00:15:59,628 --> 00:16:02,379 right. And for that, we're going to talk about, 254 00:16:02,379 --> 00:16:06,889 like How do you actually build code and what are the data structures? 255 00:16:06,889 --> 00:16:08,164 Right? So we're going to talk about the 256 00:16:08,164 --> 00:16:11,330 expansion method, which is sort of the heart of maze routing. 257 00:16:11,330 --> 00:16:12,720 We're going to talk about the data structures. 258 00:16:12,720 --> 00:16:17,508 We're going to talk about a surprising idea that there are some constraints on 259 00:16:17,508 --> 00:16:24,590 the way the cost model works and if you Do not violate those constraints. 260 00:16:24,590 --> 00:16:27,236 There's some beautiful things that are true about the structure of how your 261 00:16:27,236 --> 00:16:30,176 algorithm works and if you violate those constraints, the way your algorithm works 262 00:16:30,176 --> 00:16:33,500 gets a little bit a little bit more difficult. 263 00:16:33,500 --> 00:16:35,932 And interestingly enough in real engineering routers, everybody violates 264 00:16:35,932 --> 00:16:38,890 the constraints and it's just tough, you just have to live with it. 265 00:16:38,890 --> 00:16:41,530 And then we're going to talk about some mechanisms that make the router go fast, 266 00:16:41,530 --> 00:16:44,713 something called depth-first search. And then for just a little bit at the 267 00:16:44,713 --> 00:16:46,970 end, we're going to talk about the fact that there's actually some really 268 00:16:46,970 --> 00:16:50,900 interesting divide and conquer that happens in this universe as well. 269 00:16:50,900 --> 00:16:54,143 There's something called global routing which is different than the first part of 270 00:16:54,143 --> 00:16:57,245 this lecture, which is something you will find out at the end is called detailed 271 00:16:57,245 --> 00:17:00,910 routing. And that's how we'll end. 272 00:17:00,910 --> 00:17:04,040 So that's our very interesting high-level road map for routing. 273 00:17:04,040 --> 00:17:07,282 So let's get going and start talking about how real routers work. 274 00:17:07,282 --> 00:17:13,206 [SOUND].