1 00:00:00,8 --> 00:00:08,206 [SOUND]. 2 00:00:08,206 --> 00:00:11,781 So, here in Lecture 9.2, we're going to start talking about the real technical 3 00:00:11,781 --> 00:00:17,372 part of ASIC placement. And to first order any placer for logic 4 00:00:17,372 --> 00:00:23,56 gates optimizes things. And what it optimizes is an estimate of 5 00:00:23,56 --> 00:00:28,395 the amount of wire it's going to take to connect all those gates. 6 00:00:28,395 --> 00:00:31,418 That estimate is usually called the Wirelength, right? 7 00:00:31,418 --> 00:00:35,123 And the reason we estimate it is because the actual physical act of connecting 8 00:00:35,123 --> 00:00:38,828 those wires, which is called routing those wires, is computationally pretty 9 00:00:38,828 --> 00:00:42,512 complicated. So, we actually have to build some 10 00:00:42,512 --> 00:00:47,50 appropriate mathematical estimators that our optimization algorithms can use. 11 00:00:47,50 --> 00:00:50,826 So, to start things off, talking about the technology of ASIC placers, we're 12 00:00:50,826 --> 00:00:55,548 going to start with some classical forms of wirelength estimation. 13 00:00:55,548 --> 00:00:59,726 So, let's go see how that works. The easiest way to talk about how a 14 00:00:59,726 --> 00:01:06,680 placer works is to build, so let's build a very simple basic placer to start. 15 00:01:06,680 --> 00:01:09,767 And so, we need to start with a simple model of the chip surface itself, and so 16 00:01:09,767 --> 00:01:16,330 the simplest thing is to just use a grid. So, think of this as like a chessboard. 17 00:01:16,330 --> 00:01:24,20 there is a set of slots, or cells that we can use. 18 00:01:24,20 --> 00:01:27,380 And the gates, which are the cells from our standard-cell libraries can go in the 19 00:01:27,380 --> 00:01:31,350 grid slots. And any gate can go in any slot. 20 00:01:31,350 --> 00:01:34,30 You're allowed to put exactly one gate in each one of those slots, and it's okay if 21 00:01:34,30 --> 00:01:37,500 the slots are empty. This is a very simple model of the gates 22 00:01:37,500 --> 00:01:40,790 because it assumes that the gates are all exactly the same size. 23 00:01:40,790 --> 00:01:45,161 And that is extremely unrealistic. But it dramatically simplifies things. 24 00:01:45,161 --> 00:01:47,744 And so, we're just going to go with that in order to get started on, on looking 25 00:01:47,744 --> 00:01:52,640 how we, how we deal with a real placer. So, a grid. 26 00:01:52,640 --> 00:01:56,950 Every slot can hold exactly one gate or exactly zero gates. 27 00:01:56,950 --> 00:01:59,550 It's not okay to put more than one gate in a slot. 28 00:01:59,550 --> 00:02:04,210 All of the gates are the same size. So, we know what the representation is. 29 00:02:04,210 --> 00:02:08,63 What are we trying to do? What does a placer do? 30 00:02:08,63 --> 00:02:13,70 A placer optimizes the ability of the router to connect all the nets. 31 00:02:13,70 --> 00:02:16,974 That's the first thing a placer does. But, the router, which is the tool that 32 00:02:16,974 --> 00:02:20,628 actually puts the wires down and finds paths to make all the wires, you know, 33 00:02:20,628 --> 00:02:23,938 possible. Routers are computationally expensive 34 00:02:23,938 --> 00:02:26,570 things. You can't run one inside the placer. 35 00:02:26,570 --> 00:02:31,164 I need a simplifying approximation. And so, what every real placer does, and 36 00:02:31,164 --> 00:02:36,120 this is no exaggeration, what every real placer does is it minimizes an 37 00:02:36,120 --> 00:02:42,872 appropriate mathematical model of the expected wirelength. 38 00:02:42,872 --> 00:02:46,959 And, to be more precise about that, for each wire in the design, there is an 39 00:02:46,959 --> 00:02:52,720 estimate, an approximation of the expected length of the routed wire. 40 00:02:52,720 --> 00:02:56,878 And we add all of those expected lengths together, those estimated lengths 41 00:02:56,878 --> 00:03:01,683 together for every single wire. So, we sum over all of the wires in the 42 00:03:01,683 --> 00:03:07,390 design, the estimated length of the wire, we add them up and we minimize that. 43 00:03:07,390 --> 00:03:12,270 That is what a placer does. A placer optimizes the estimated lengths 44 00:03:12,270 --> 00:03:18,702 of the wires and solves for locations for the gates that minimize that estimated 45 00:03:18,702 --> 00:03:23,114 wirelength. That's what a placer does. 46 00:03:23,114 --> 00:03:26,896 And, you know, to first order, you could actually categorize the very many 47 00:03:26,896 --> 00:03:31,105 different kinds of placers that there are by the mathematical model they choose to 48 00:03:31,105 --> 00:03:36,438 use for the wirelength. Now, we need a little terminology so that 49 00:03:36,438 --> 00:03:40,598 we can all talk about these things the way people who really do ASIC layout talk 50 00:03:40,598 --> 00:03:45,180 about them. So, the first common term is that the 51 00:03:45,180 --> 00:03:51,310 term for a wire in a layout is a net. So, we call them nets. 52 00:03:51,310 --> 00:03:55,278 And the whole set of gates and wires together is called the netlist. 53 00:03:55,278 --> 00:03:59,686 So, the thing that comes out of multi-level logic synthesis, and then 54 00:03:59,686 --> 00:04:04,162 followed with technology mapping is a netlist. 55 00:04:04,162 --> 00:04:07,999 The thing that goes into your placer is a netlist. 56 00:04:07,999 --> 00:04:11,299 And nets are actually categorized by how many things it connects, and we tend to 57 00:04:11,299 --> 00:04:14,586 call these points. So, I've got a nice simple little example 58 00:04:14,586 --> 00:04:16,934 on the left. I've got a grid that goes from 0 to 4, 59 00:04:16,934 --> 00:04:19,942 it's got five columns on the x direction and the y vertical direction, it goes 60 00:04:19,942 --> 00:04:23,375 from 0 to 5. It's got, you've got six rows and I've 61 00:04:23,375 --> 00:04:26,537 got a two-point net, so I've got a gate at x,y, 1,4, and I've got a gate at 3,1, 62 00:04:26,537 --> 00:04:30,440 and I've got a little blue wire connecting them. 63 00:04:30,440 --> 00:04:33,938 And so, it's really clear that this is a two-point net because there's two gates 64 00:04:33,938 --> 00:04:37,920 that it's connecting. and if everything in every netlist looked 65 00:04:37,920 --> 00:04:41,160 like this, we probably wouldn't be talking about this and we wouldn't be 66 00:04:41,160 --> 00:04:45,712 giving it special terminology. But the problem is they don't look like 67 00:04:45,712 --> 00:04:47,820 this. They also look like this. 68 00:04:47,820 --> 00:04:51,400 So, on the right-hand side, I'm showing you a four-point net. 69 00:04:51,400 --> 00:04:53,440 And so, again, the x grid goes from 0 to 4. 70 00:04:53,440 --> 00:04:57,422 The y grid goes from 0 to 5. There's a gate at 1,4, there's also two 71 00:04:57,422 --> 00:05:00,520 gates at 3,1 and 3,3, and another gate at 4,5. 72 00:05:00,520 --> 00:05:05,990 This is a four-point net because there is a wire connecting four separate points. 73 00:05:05,990 --> 00:05:08,643 This is, in some sense, why we don't just call it a wire. 74 00:05:08,643 --> 00:05:11,587 Because there's a lot of wires that are going to get created to actually route 75 00:05:11,587 --> 00:05:14,520 this thing and connect this thing all together. 76 00:05:14,520 --> 00:05:17,922 And in answer to the first maybe obvious question, which is how is it the case 77 00:05:17,922 --> 00:05:21,756 that there are actually things like wires that have more than two things that they 78 00:05:21,756 --> 00:05:25,300 connect? the obvious answer is, there's fanout. 79 00:05:25,300 --> 00:05:29,260 And I've even got it drawn with the gates sort of showing their directions as 80 00:05:29,260 --> 00:05:31,968 though. There's a little AND gate at each one of 81 00:05:31,968 --> 00:05:34,950 these grid cells, and the inputs appear to be coming from the left. 82 00:05:34,950 --> 00:05:37,40 And the output appears to be going to the right. 83 00:05:37,40 --> 00:05:40,49 And so, there's a gate in the 1,4 location in this grid that appears to be 84 00:05:40,49 --> 00:05:45,37 driving the inputs to three other gates. The ones at 3,1, 3,3, and 4,5. 85 00:05:45,37 --> 00:05:48,900 So, how is it possible to have things with more than two pins, two points? 86 00:05:48,900 --> 00:05:54,232 The answer is fanout. And in modern[UNKNOWN] there are lots of 87 00:05:54,232 --> 00:05:57,970 things that happen to connect to many things at the same time. 88 00:05:57,970 --> 00:06:01,804 So some, some elements of scan chains and the testability components of logic you 89 00:06:01,804 --> 00:06:07,140 know, there are things in the clocks that actually synchronize all the flip-flops. 90 00:06:07,140 --> 00:06:10,926 There's some very, very high fanout nets. In fact, there are often special kinds of 91 00:06:10,926 --> 00:06:13,60 routing technologies to connect those things. 92 00:06:13,60 --> 00:06:17,13 So, it's not just like you can have K.net where K is 4 or 5, you can have K be 93 00:06:17,13 --> 00:06:22,664 hundreds. So, about the wirelength estimation, 94 00:06:22,664 --> 00:06:29,70 there are many, many different kinds of estimators. 95 00:06:29,70 --> 00:06:33,762 And in fact different placers depend for their foundational methods to a large 96 00:06:33,762 --> 00:06:38,685 degree on the kind of wirelength estimator that you pick. 97 00:06:38,685 --> 00:06:42,885 So, why is it hard to estimate the length of wire that's going to be used to 98 00:06:42,885 --> 00:06:47,26 connect the nets? And the answer is that multi-point nets 99 00:06:47,26 --> 00:06:50,940 can be routed in many different paths. And in a dense layout, nets do not all 100 00:06:50,940 --> 00:06:54,502 get routed in their shortest path. I mean, the inside of an ASIC and the 101 00:06:54,502 --> 00:06:58,570 inside of a 20 million or 50 million gate ASIC, it's a very crowded place. 102 00:06:58,570 --> 00:07:03,200 Even with lots of physical layers for wiring, it's a very crowded place. 103 00:07:03,200 --> 00:07:06,924 Nets just don't get to go in at their minimum possible length. 104 00:07:06,924 --> 00:07:09,966 So, a concrete example here. I've got the same diagram that I had on 105 00:07:09,966 --> 00:07:12,240 the previous slide. a grid. 106 00:07:12,240 --> 00:07:15,650 x goes from 0 to 4 on the bottom. y goes from 0 to 5 on the top. 107 00:07:15,650 --> 00:07:18,950 There's a gate at 1,4. Gates at 3,1, 3,3, and 4,5. 108 00:07:18,950 --> 00:07:22,969 And there's a very straight little wire connecting them. 109 00:07:22,969 --> 00:07:25,545 You know, this is basically about the best I can do to wire this, this 110 00:07:25,545 --> 00:07:28,680 particular design. I can't really probably do better than 111 00:07:28,680 --> 00:07:32,854 this than this, this little example here. But in the middle, I'm showing something 112 00:07:32,854 --> 00:07:35,996 that you know, it's a kind of a different looking wire. 113 00:07:35,996 --> 00:07:41,550 Now does this have a little more wire? Yeah, this is, this is just a slightly 114 00:07:41,550 --> 00:07:45,320 longer than the, you know, than the previous wire is just because of the way 115 00:07:45,320 --> 00:07:49,442 things escape from the, from the topmost gate. 116 00:07:49,442 --> 00:07:53,950 But, you know, this is still okay. I, I would even say maybe this is good. 117 00:07:53,950 --> 00:07:55,340 You know, this is a particular, this is a good path. 118 00:07:55,340 --> 00:07:57,810 You know, it's just a little bit worse than the previous path. 119 00:07:57,810 --> 00:08:01,527 But now on the right-hand side, I'm showing an appallingly bad gate 120 00:08:01,527 --> 00:08:05,178 wirelength. it's again, the same example you know, x 121 00:08:05,178 --> 00:08:09,882 is you know, 0 to 4, and y is 0 to 5. but the, the wires are snarled all over 122 00:08:09,882 --> 00:08:12,840 the place. They seem to go way out of their way to 123 00:08:12,840 --> 00:08:15,722 connect things. And, and there's nothing else to say 124 00:08:15,722 --> 00:08:19,557 other than, you know, this is pretty bad. And the reason this is pretty bad is 125 00:08:19,557 --> 00:08:23,451 probably there's 20 million other wires that are trying to get routed, and this 126 00:08:23,451 --> 00:08:27,390 one just didn't get able to be routed short. 127 00:08:27,390 --> 00:08:32,183 And in real designs, that just happens. So, estimating what the length of the 128 00:08:32,183 --> 00:08:37,940 wire is, is actually quite challenging. We have to estimate something that is a 129 00:08:37,940 --> 00:08:41,850 reasonable model of what the wire might actually be. 130 00:08:41,850 --> 00:08:46,990 And so, what we tend to do is, is estimate a best wirelength. 131 00:08:46,990 --> 00:08:49,678 We tend to estimate the best and then we, we do some other techniques to sort of 132 00:08:49,678 --> 00:08:53,512 deal with the fact that they're not always going to come out this good. 133 00:08:53,512 --> 00:09:01,352 So, the most famous estimation for a wire is called the Half-Perimeter Wirelength, 134 00:09:01,352 --> 00:09:08,459 and sometimes abbreviated HPWL. But it's also called the Bounding Box 135 00:09:08,459 --> 00:09:13,60 Wirelength, usually BBOX, BBOX. And you'll see us using them 136 00:09:13,60 --> 00:09:16,528 interchangeably in this lecture. The idea is pretty simple. 137 00:09:16,528 --> 00:09:20,414 I'm going to describe it in words first. You put the smallest bounding box you can 138 00:09:20,414 --> 00:09:24,124 around all the gates. So, let's assume in the little grid 139 00:09:24,124 --> 00:09:27,752 things that I'm showing you. The gate lives in the center of the grid 140 00:09:27,752 --> 00:09:30,416 slot. And the coordinates that are labeling x 141 00:09:30,416 --> 00:09:34,260 equals 0, 1, 2, 3, 4 in the example I'm showing on the bottom left, y equals 0, 142 00:09:34,260 --> 00:09:38,836 1, 2, 3, 4, 5. Let's assume the xy coordinates are the 143 00:09:38,836 --> 00:09:42,770 center of the cell, the grid. And that the gate lives on that, that 144 00:09:42,770 --> 00:09:45,480 coordinate. And so, what we do is we put the smallest 145 00:09:45,480 --> 00:09:49,760 possible box around all of the gates. And then, we measure the width of the 146 00:09:49,760 --> 00:09:52,532 box, delta x, and the height of the box, delta y, and we add them together, and 147 00:09:52,532 --> 00:09:57,304 that's our wirelength estimate. So, for this little example where there's 148 00:09:57,304 --> 00:10:00,952 a gate at 1,4 and a gate at 3,1, the first thing we do is we put a bounding 149 00:10:00,952 --> 00:10:04,595 box. And so, the box goes from x equals 1 to 3 150 00:10:04,595 --> 00:10:08,390 and y equals 1 to 4. And then, we simply we do the math. 151 00:10:08,390 --> 00:10:13,210 Delta x is 3 minus 1, that's 2. Delta y is 4 minus 1, that's 3. 152 00:10:13,210 --> 00:10:18,244 We add them together, 3 plus 2 is 5. The half-perimeter wirelength is 5. 153 00:10:18,244 --> 00:10:21,956 And one of the great things about the half-perimeter wirelength is that it's 154 00:10:21,956 --> 00:10:26,361 easy to do a multi-point net. So, here's a four-point net again on the 155 00:10:26,361 --> 00:10:31,420 x equals 0 to 4, y equals 0 to 5 grid gates at 1,4, 3,3 3,1, 3,3, and 4,5. 156 00:10:31,420 --> 00:10:38,413 We again put the smallest bounding box, and that goes from x equals 1 to 4 and y 157 00:10:38,413 --> 00:10:44,300 equals 1 to 5. And then, we again, we can do the math. 158 00:10:44,300 --> 00:10:48,572 Delta x is 4 minus 1, that's 3. Delta y is 5 minus 1, that's 4. 159 00:10:48,572 --> 00:10:53,280 The half-perimeter wirelength estimate for this gate is 3 plus 4, is 7. 160 00:10:53,280 --> 00:10:56,520 So, the great thing about the half-perimeter wirelength, it's easy and 161 00:10:56,520 --> 00:11:00,950 it works for multi-point nets. So, more generally, the half-perimeter 162 00:11:00,950 --> 00:11:05,240 wirelength, the general formula that I'm showing here is, you look at all of the 163 00:11:05,240 --> 00:11:09,792 x-coordinates of all your gates, you take the max. 164 00:11:09,792 --> 00:11:14,17 You look at all the x-coordinates of your gates and you take the min and you take 165 00:11:14,17 --> 00:11:18,783 the max minus the min. Then, you look at all the y-coordinates 166 00:11:18,783 --> 00:11:21,627 for your gates, you take the max. You look at all the y-coordinates for 167 00:11:21,627 --> 00:11:23,956 gates, you take the min. You take the max minus the min, and 168 00:11:23,956 --> 00:11:26,946 that's what you add together. The maximum, the x-coordinates for the 169 00:11:26,946 --> 00:11:29,466 gates minus the min of the x-coordinates for the gates plus the max of the 170 00:11:29,466 --> 00:11:32,196 y-coordinates for the gates minus the min of the y-coordinates for the gates, 171 00:11:32,196 --> 00:11:38,145 that's the half-perimeter wirelength. One of the important things to note is 172 00:11:38,145 --> 00:11:42,399 that this is always a lower bound on the real wirelength. 173 00:11:42,399 --> 00:11:46,624 Which is to say, it is always less than or equal to the real wirelength no matter 174 00:11:46,624 --> 00:11:52,580 how complex the final routed path is. You need at least this much wire. 175 00:11:52,580 --> 00:11:56,340 And look, this just makes sense. You need to go from the gate on the far 176 00:11:56,340 --> 00:12:00,723 left to the gate on the far right. That's delta x amount of wire from the 177 00:12:00,723 --> 00:12:03,537 previous diagram. And you need to go from the bottom most 178 00:12:03,537 --> 00:12:06,850 gate to the top most gate, and that's delta y amount of wire. 179 00:12:06,850 --> 00:12:10,74 And no matter how you route this path, you need delta x plus delta y amount of 180 00:12:10,74 --> 00:12:13,704 wire. So an important aside to note is that, 181 00:12:13,704 --> 00:12:18,96 all of the wiring on big chips and most of the wiring on big printed circuit 182 00:12:18,96 --> 00:12:23,9 boards is strictly horizontal and vertical. 183 00:12:23,9 --> 00:12:25,648 There's no arbitrary angles for manufacturing reasons. 184 00:12:25,648 --> 00:12:29,104 That's rigidly true for integrated circuits these days, big modern digital 185 00:12:29,104 --> 00:12:32,874 SOC designs. there is some funny all angle wiring to, 186 00:12:32,874 --> 00:12:37,290 to do things like get out of complicated pin arrangements underneath the big 187 00:12:37,290 --> 00:12:41,272 chips. But once you escape from the pins near 188 00:12:41,272 --> 00:12:45,178 the chip then you know, it already actually go across the board strictly 189 00:12:45,178 --> 00:12:50,364 horizontal and strictly vertical. So that's just another reason the HPWL is 190 00:12:50,364 --> 00:12:53,730 a good estimator because it just does a nice job of estimating the lower bound on 191 00:12:53,730 --> 00:12:57,591 the amount of wire. No matter how many points you have, no 192 00:12:57,591 --> 00:13:02,4 matter how many pins you have, no matter how many gates you have on your net. 193 00:13:02,4 --> 00:13:06,832 this is just interesting, this is what the actual half-perimeter wirelength 194 00:13:06,832 --> 00:13:11,590 estimation distribution looks like for a little design. 195 00:13:11,590 --> 00:13:16,37 So this is old data. So this is 165,000 gate ASIC from the 196 00:13:16,37 --> 00:13:20,908 late 1990s from Jens Vygen's group at Bond/g. 197 00:13:20,908 --> 00:13:25,640 this is 181,000 net. So you know, call it about 200,000 nets. 198 00:13:25,640 --> 00:13:30,942 I'm showing you this because it's just sort of an, an interesting piece of data. 199 00:13:30,942 --> 00:13:37,40 the horizontal axis here shows a histogram buckets for the wirelength. 200 00:13:37,40 --> 00:13:44,179 So, 0 to 0.5, 0.5 to 1, 1 to 1.5, 1.5 to 2, 2 to 2.5, 2.5 to 3, 3 to 3.5, etc., up 201 00:13:44,179 --> 00:13:52,353 to 4, 4.5, 5, 6, 7, 8, 9, 10. And then, note at the end the buckets get 202 00:13:52,353 --> 00:13:56,297 bigger, 10 to 15, 15 to 20. this is actually in millimeters, this is 203 00:13:56,297 --> 00:13:59,148 a really old chip. So, it's one of the things to be aware of 204 00:13:59,148 --> 00:14:03,601 is that this is a really old chip. so don't think about this as being 205 00:14:03,601 --> 00:14:07,930 anything other than a a normalized number. 206 00:14:07,930 --> 00:14:11,425 And note that the vertical scale is a log scale, right? 207 00:14:11,425 --> 00:14:15,600 So, the vertical scale is a log scale. The vertical scale says, how many nets 208 00:14:15,600 --> 00:14:17,970 have this length? So, you know, question. 209 00:14:17,970 --> 00:14:21,372 How many nets are the shortest possible length between 0 and 0.5 in whatever 210 00:14:21,372 --> 00:14:24,944 units are appropriate? And the answer is 100,000 of almost 211 00:14:24,944 --> 00:14:28,1 200,000 nets. How many nets are between 0.5 and 1? 212 00:14:28,1 --> 00:14:31,683 and the answer is, as far as I can tell, probably about 30 or 40,000. 213 00:14:31,683 --> 00:14:34,35 Remember, this is a log scale, maybe 20,000. 214 00:14:34,35 --> 00:14:38,124 the idea is that most nets are short, most nets are very short. 215 00:14:38,124 --> 00:14:42,150 But unfortunately, there's a really long tail, and there are nets out here that 216 00:14:42,150 --> 00:14:46,298 are you know, 40 times longer than the shortest net, and those nets are not zero 217 00:14:46,298 --> 00:14:50,821 in number. So, real routers deal with the fact that 218 00:14:50,821 --> 00:14:56,370 most of the nets are short but there's a non-trivial number of nets that are long. 219 00:14:56,370 --> 00:15:00,632 And so, is just an interesting data that shows you that in a concrete way. 220 00:15:00,632 --> 00:15:05,393 [MUSIC]