1 00:00:00,6 --> 00:00:11,280 So here in 9.7 we're going to continue our discussion of analytical placement. 2 00:00:11,280 --> 00:00:15,690 In the previous lecture, we talked about a different model, a different wirelength 3 00:00:15,690 --> 00:00:19,911 model, the quadratic model where we take the wires and break them apart into what 4 00:00:19,911 --> 00:00:25,992 amounts to two point springs. Characterized by their quadratic 5 00:00:25,992 --> 00:00:29,820 Euclidean length, and we add up all those lengths and we can write an equation to 6 00:00:29,820 --> 00:00:34,101 actually minimize it. So, in this lecture, we're going to show 7 00:00:34,101 --> 00:00:37,759 how the quadratic wirelength model makes it possible to actually build an 8 00:00:37,759 --> 00:00:43,495 analytical model of placement that we are actually going to be able to solve. 9 00:00:43,495 --> 00:00:47,783 So let's talk about how we go from the quadratic wirelength model, an analytical 10 00:00:47,783 --> 00:00:52,7 model of this problem, so a quadratic placer that creates a giant equation that 11 00:00:52,7 --> 00:00:56,231 we can actually solve to create a kind of a placement that's going to create some 12 00:00:56,231 --> 00:00:59,943 new kinds of problems that we're going to have to solve in the rest of this 13 00:00:59,943 --> 00:01:05,850 lecture. So, let's go look at how this works. 14 00:01:05,850 --> 00:01:11,394 So this is the same example that I showed at the end of the previous lecture. 15 00:01:11,394 --> 00:01:15,618 An example in detail of the quadratic wirelength model. 16 00:01:15,618 --> 00:01:20,729 So again two pads at 0,0 and 1,0.5. Two gates labeled 1 and 2. 17 00:01:20,729 --> 00:01:25,650 A wire from the 0,0 pad to gate 1. A wire from gate 1 to gate 2. 18 00:01:25,650 --> 00:01:29,934 A wire from gate 2 to pad 1,0.5, and the weights on those three wires, 1, 2 and 4 19 00:01:29,934 --> 00:01:36,130 respectively going left to right, bottom to top in this little example. 20 00:01:36,130 --> 00:01:39,37 And there are three quadratic wirelength terms. 21 00:01:39,37 --> 00:01:44,29 4 x2 minus x1 squared plus 4 y2 minus 0.5 squared, 2 x2 minus x1 squared plus 2 y2 22 00:01:44,29 --> 00:01:50,680 minus y1 squared, 1 x1 minus 0 squared plus 1 y1 minus 0 squared. 23 00:01:50,680 --> 00:01:54,524 We add those things together and we get a quadratic wirelength, and again, 24 00:01:54,524 --> 00:01:59,650 highlighting effect, there are no terms with an x multiplied by a y. 25 00:01:59,650 --> 00:02:03,110 This is a very, and maybe, surprisingly important. 26 00:02:03,110 --> 00:02:06,120 So what do I want to do? Okay? 27 00:02:06,120 --> 00:02:15,30 After I add this thing together, I want to minimize it. 28 00:02:15,30 --> 00:02:22,588 How do I do that? A very surprising answer. 29 00:02:22,588 --> 00:02:27,90 Calculus, basic calculus. Remember, in basic calculus, we said what 30 00:02:27,90 --> 00:02:30,618 is true about the extreme values of functions, the maximum of, of a function 31 00:02:30,618 --> 00:02:34,90 or the minimum of a function, and the answer was it was where the derivative 32 00:02:34,90 --> 00:02:38,264 was a 0. And if you took a first derivative and 33 00:02:38,264 --> 00:02:41,234 set it to 0, you could find a max or a min, and if you look at the second 34 00:02:41,234 --> 00:02:45,870 derivative, you could figure out if it was a max or a min. 35 00:02:45,870 --> 00:02:50,952 It turns out for these wirelength things, when you solve for the derivative and 36 00:02:50,952 --> 00:02:55,500 when you set it to 0, it's always a minimum. 37 00:02:55,500 --> 00:02:58,388 There's no maximum and so it just does the right thing. 38 00:02:58,388 --> 00:03:01,780 However, one of the things that may be a little bit complicated for you is that 39 00:03:01,780 --> 00:03:06,76 there are multiple variables. This isn't just a function of one thing 40 00:03:06,76 --> 00:03:10,440 like in x. Even more, perhaps frighteningly. 41 00:03:10,440 --> 00:03:14,940 This is a function of maybe a million x's and a million y's. 42 00:03:14,940 --> 00:03:19,35 So what do you do? You do partial derivatives, right? 43 00:03:19,35 --> 00:03:24,731 You differentiate the wirelength with respect to each individual x and each 44 00:03:24,731 --> 00:03:29,796 individual y. And you set the entire set of equations 45 00:03:29,796 --> 00:03:33,6 to 0. And it turns out that when all of those 46 00:03:33,6 --> 00:03:38,436 equations are 0 at the same time, that is a quadratic wirelength minimum. 47 00:03:38,436 --> 00:03:41,684 Now, one of the things that's very important that I showed you on the 48 00:03:41,684 --> 00:03:45,164 previous slide was that there are no terms that have x's and y's in them at 49 00:03:45,164 --> 00:03:50,188 the same time. And so, it is perfectly okay to pull out 50 00:03:50,188 --> 00:03:55,72 the x part of the wirelength and to the y part of the wirelength and deal with them 51 00:03:55,72 --> 00:03:59,10 separately. And so I'm doing that here. 52 00:03:59,10 --> 00:04:02,538 I have a curve line calling Q of X, which is the X part of the quadratic 53 00:04:02,538 --> 00:04:06,507 wirelength, 4 times x2 minus 1 squared plus 2 times x2 minus x1 squared plus 1 54 00:04:06,507 --> 00:04:13,45 times x1 minus 0 squared. And I've got a term that looks similar 55 00:04:13,45 --> 00:04:17,545 called Q of Y, which is the Y part, 4 times y2 minus 0.5 squared plus 2 times 56 00:04:17,545 --> 00:04:23,412 y2 minus 1 squared plus 1 times y1 minus 0 squared. 57 00:04:23,412 --> 00:04:27,59 Structurally, those equations are almost exactly the same. 58 00:04:27,59 --> 00:04:31,147 But the constants, okay? The things inside the parentheses are 59 00:04:31,147 --> 00:04:34,923 different because the pads, the fixed pads around the edges of the chip, they 60 00:04:34,923 --> 00:04:40,350 have different X and Y coordinates. So what do you do? 61 00:04:40,350 --> 00:04:42,792 You differentiate. So let's take the x part of the 62 00:04:42,792 --> 00:04:46,358 wirelength and differentiate with respect to x1. 63 00:04:46,358 --> 00:04:50,959 So, let's look, 4 times x2 minus x1 squared, okay? 64 00:04:50,959 --> 00:04:55,656 there's no x1's in that, so that's just a 0. 65 00:04:55,656 --> 00:05:00,212 2 times x2 minus x1 squared, well, that's 2 times, 2 times the thing inside, times 66 00:05:00,212 --> 00:05:06,676 the thing inside to the power of 1, times the derivative of the thing inside. 67 00:05:06,676 --> 00:05:12,288 Remember, how do you differentiate, you know, u of x, with respect to dx? 68 00:05:12,288 --> 00:05:17,480 It's, you know, you differentiate u and then you differentiate x, right? 69 00:05:17,480 --> 00:05:21,640 So, it's 2 times x2 minus x1 times 2, because the 2 exponent comes down to the 70 00:05:21,640 --> 00:05:25,480 power 1, and then the derivative of what's inside, which is as far as x1 is 71 00:05:25,480 --> 00:05:32,964 concerned, a constant minus x1. So, 4 times x2 minus x1 minus 1. 72 00:05:32,964 --> 00:05:37,160 Similarly, the 1 x1 minus 0 squared becomes 2 x1. 73 00:05:37,160 --> 00:05:40,469 You get a linear equation 6 x1 minus 4 x2 is 0. 74 00:05:40,469 --> 00:05:45,51 Similarly, if you different, differentiate with respect to x2, the 4 75 00:05:45,51 --> 00:05:49,515 x2 minus 1 squared term becomes 8 x2 minus 1. 76 00:05:49,515 --> 00:05:54,25 The 2 x2 minus x1 squared term becomes 4 x2 minus x1. 77 00:05:54,25 --> 00:05:59,410 And the derivative of what's inside is 1. And the 1 x1 minus 0 squared term, well, 78 00:05:59,410 --> 00:06:03,186 that's x1, it's a wrong variable, it's constant as far as x2 is concerned, you 79 00:06:03,186 --> 00:06:09,151 get a 0. you get another linear equation, 4 minus 80 00:06:09,151 --> 00:06:15,652 4 x1 plus 12 x2 minus 8 equals 0. And if you do it on the y side, same 81 00:06:15,652 --> 00:06:20,73 thing. The, the derivative with respect to y1 is 82 00:06:20,73 --> 00:06:25,350 0 plus 4 y2 minus y1 times negative 1 plus 2 y1. 83 00:06:25,350 --> 00:06:30,550 Another linear equation, 6 y1 minus 4 y2 is zero. 84 00:06:30,550 --> 00:06:34,44 Differentiate the y wirelength with respect to y2. 85 00:06:34,44 --> 00:06:38,70 Well, the first term turns into 8 y2 minus 0.5. 86 00:06:38,70 --> 00:06:42,556 The second one turns into 4 y2 minus y1. And the third term, it only has y1's in 87 00:06:42,556 --> 00:06:47,506 it, it goes away, you get a 0. Another linear equation, negative 4 y1 88 00:06:47,506 --> 00:06:52,858 plus 12 y2 minus 4 equals 0. So, hey, this is actually pretty 89 00:06:52,858 --> 00:06:57,10 impressive. I started with something that seemed very 90 00:06:57,10 --> 00:07:01,30 complicated, this quadratic wirelength thing, and I wrote a quadratic 91 00:07:01,30 --> 00:07:04,248 wirelength. And I said, well, I'd like to minimize 92 00:07:04,248 --> 00:07:06,580 it. And by minimizing it, I, I did calculus. 93 00:07:06,580 --> 00:07:09,720 I set all the partial derivatives to 0 and I got linear equations. 94 00:07:09,720 --> 00:07:15,20 That's gotta be good, and it is. Those are linear equations. 95 00:07:15,20 --> 00:07:18,560 We know how to solve linear equations, we are very good at solving linear 96 00:07:18,560 --> 00:07:22,25 equations. So again, this is just the Q of X 97 00:07:22,25 --> 00:07:28,132 wirelength and the Q of Y wirelength. Restated, 4 x2 minus 1 squared 2 x2 minus 98 00:07:28,132 --> 00:07:33,428 x1 squared 1 x1 minus 0 squared. For the Y term, 4 y2 minus 0.05 squared 2 99 00:07:33,428 --> 00:07:39,70 y2 minus y1 squared 1 y1 minus 0 squared. What did we do? 100 00:07:39,70 --> 00:07:41,730 We minimized them. We did calculus on them. 101 00:07:41,730 --> 00:07:45,146 We took the partial derivatives with respect to every x for the term on the 102 00:07:45,146 --> 00:07:49,970 left and every y in the term on the right and we got linear equations. 103 00:07:49,970 --> 00:07:54,0 And if we were to write that in a form that you should be familiar with matrix 104 00:07:54,0 --> 00:07:58,592 notation. What I get is a matrix times a vector 105 00:07:58,592 --> 00:08:02,808 equals a constant. And so I get a 2 by 2 matrix, because 106 00:08:02,808 --> 00:08:06,448 there's only two gates that are moving, and the matrix is 6, minus 4 in the first 107 00:08:06,448 --> 00:08:09,864 row and minus 4, 12 in the second row times a vector x1, x2 equals a vector 0, 108 00:08:09,864 --> 00:08:15,973 8 for the x side. And for the y side, 6, minus 4, minus 4, 109 00:08:15,973 --> 00:08:21,180 12 for the matrix. The same matrix times a vector y1, y2 110 00:08:21,180 --> 00:08:26,591 equals 0, 4, a different vector. You can solve that. 111 00:08:26,591 --> 00:08:29,630 x1 is 0.571, x is 0.857. You can solve the y. 112 00:08:29,630 --> 00:08:38,240 y is, y1 is 0.286, y2 is 0.429. And so, to summarize, what do you get? 113 00:08:38,240 --> 00:08:44,410 You get two matrix equations. Ax equals bx, AY equals BY. 114 00:08:44,410 --> 00:08:47,815 If you have N gates, the matrix is N by N. 115 00:08:47,815 --> 00:08:53,727 So, yes, you do get a 1 million by 1 million system of linear equations. 116 00:08:53,727 --> 00:08:58,572 If you have 1 million gates, the same matrix for the x and y solves, and 117 00:08:58,572 --> 00:09:04,352 interestingly, you solve for the x's in one solve and independently you solve for 118 00:09:04,352 --> 00:09:16,901 the y's, but you get different b vectors. So you solve Ax equals one thing to get 119 00:09:16,901 --> 00:09:21,180 the xs, ay equals a different thing to get the ys. 120 00:09:21,180 --> 00:09:24,657 The x, B, and y vectors all have N elements in them, so they are vectors 121 00:09:24,657 --> 00:09:28,899 with a million things in them. This is very interesting. 122 00:09:30,210 --> 00:09:34,220 So here is the placement result if I actually just draw it for you. 123 00:09:34,220 --> 00:09:38,869 So I'm showing you a picture of the unplaced layout again. 124 00:09:38,869 --> 00:09:44,582 on the left, you know, padded 0, 0 and 1,0.5 two gates 1 and 2. 125 00:09:44,582 --> 00:09:48,400 the 0, 0 pad goes to gate 1. Gate 1 goes to gate 2. 126 00:09:48,400 --> 00:09:50,910 Gate 2 goes to the pad. Right? 127 00:09:50,910 --> 00:09:54,324 And where does everything go? And the answer is, unsurprisingly, all 128 00:09:54,324 --> 00:09:58,472 the gates go on a straight line between the 0, 0 pad on the left and the 1, 0.5 129 00:09:58,472 --> 00:10:03,32 pad on the right. And I'm just showing you 1, 1, and so you 130 00:10:03,32 --> 00:10:07,360 see the chip corner up at the top. They're all on a straight line, but, 131 00:10:07,360 --> 00:10:11,357 they're not uniformly spaced. So it's not each sort of 1 3rd of that 132 00:10:11,357 --> 00:10:15,165 wirelength. And the reasons are one, that it's well 133 00:10:15,165 --> 00:10:20,192 the big reason is that they do not have uniform weights. 134 00:10:20,192 --> 00:10:26,166 The weight on wire 2 was a 4. That's big. 135 00:10:26,166 --> 00:10:29,551 Okay. The weight on the gate, the weight on the 136 00:10:29,551 --> 00:10:34,248 wire from gate 2 to the pad is 4, and what happens is that makes the wire very 137 00:10:34,248 --> 00:10:39,667 short. And the weight on the wire from gate 1 to 138 00:10:39,667 --> 00:10:47,450 2 is a 2, the gate, the weight on the wire from gate 1 to the pad at 0, 0 is 1. 139 00:10:47,450 --> 00:10:51,675 What actually happens is that you see this very significant shortening of the 140 00:10:51,675 --> 00:10:56,470 wire with the big weight on it, that's actually pretty cool. 141 00:10:56,470 --> 00:11:00,430 So the placement makes a visual sense. All the points are on a straight line 142 00:11:00,430 --> 00:11:04,27 between the pads. And the analog of what's happening here 143 00:11:04,27 --> 00:11:10,530 is that, is that in this model, each two point wire is like a spring, okay? 144 00:11:10,530 --> 00:11:15,428 Or like a rubber band, or an elastic band or whatever you want to think of as a 145 00:11:15,428 --> 00:11:20,405 stretchy thing that resists being stretched and pulls things in a straight 146 00:11:20,405 --> 00:11:25,220 Y. And what this placement does is it 147 00:11:25,220 --> 00:11:29,374 minimizes the lengths of all of the springs. 148 00:11:29,374 --> 00:11:33,364 And so, if you think that there's a spring from the 0, 0 path to gate 1 to 149 00:11:33,364 --> 00:11:37,564 spring from gate 1 to gate 2 and a spring from gate 2 to the pattern that the 150 00:11:37,564 --> 00:11:41,904 spring that goes to the right path is four times as strong as the spring that 151 00:11:41,904 --> 00:11:49,20 goes to the left path. You get this answer, it all makes sense. 152 00:11:49,20 --> 00:11:52,610 So you put a bigger weight on a wire, you can get a shorter wire. 153 00:11:52,610 --> 00:11:55,400 That gives us lots of control over the placement, that's actually a really 154 00:11:55,400 --> 00:11:58,766 wonderful thing. And the other thing that's nice is that 155 00:11:58,766 --> 00:12:02,0 you get the same matrix, but different right-hand side b vectors. 156 00:12:02,0 --> 00:12:03,766 Why? Because the pads have different x and y 157 00:12:03,766 --> 00:12:06,128 co-ordinates. So, you only get one matrix that you have 158 00:12:06,128 --> 00:12:09,282 to deal with. You just get two different right-hand 159 00:12:09,282 --> 00:12:13,407 side vectors. Now, it turns out that building the 160 00:12:13,407 --> 00:12:20,690 matrix A, and building the bx and by vectors is actually really easy. 161 00:12:20,690 --> 00:12:24,950 There's a really simple recipe. So let's start with a very simple net 162 00:12:24,950 --> 00:12:27,438 list here. It's a new net list. 163 00:12:27,438 --> 00:12:33,640 Okay and so, there are three placable gates 1, 2, 3 and a pad called P. 164 00:12:33,640 --> 00:12:38,696 and there's a weight of 5 on the wire between the pad and gate 1, a weight of 1 165 00:12:38,696 --> 00:12:43,357 on the wire between gate 1 and gate 2, and a weight of 4 on the wire between 166 00:12:43,357 --> 00:12:49,912 gate 2 and gate 3. So the first thing you do is you build an 167 00:12:49,912 --> 00:12:54,450 auxiliary matrix which is called the connectivity matrix. 168 00:12:54,450 --> 00:12:58,728 That's also end by end so in this case it's 3 by 3, and I'm just going to write 169 00:12:58,728 --> 00:13:04,510 one, two, three for the columns. And one, two, three for the rows, so 170 00:13:04,510 --> 00:13:08,140 we're sort of clear on that. And it's very simple. 171 00:13:08,140 --> 00:13:12,940 If a gate, i, has a two point wire to gate j, and the weight on that wire is w, 172 00:13:12,940 --> 00:13:18,160 then you go to the ith row in the jth column. 173 00:13:18,160 --> 00:13:21,752 And also the jth row in the ith column, and you put a one in it. 174 00:13:21,752 --> 00:13:26,980 it's as simple as that. Otherwise the matrix has a 0 in it. 175 00:13:26,980 --> 00:13:31,264 And so, for example the 4 on this wire from 2 to 3, okay, goes into the third 176 00:13:31,264 --> 00:13:37,939 row and the second column, and also the second row and the third column, right? 177 00:13:37,939 --> 00:13:42,227 And one of the things to note, right, which is a little bit strange, right, I'm 178 00:13:42,227 --> 00:13:46,314 going to put a kind of a question mark over here, is hey, shouldn't there be a 5 179 00:13:46,314 --> 00:13:50,602 in here somewhere, because this pad thing's got a great big heavily weighted 180 00:13:50,602 --> 00:13:57,610 wire, and the answer is, the C matrix ignores the pads. 181 00:13:57,610 --> 00:14:00,550 There's a special step that happens to sort of put the pads back into this 182 00:14:00,550 --> 00:14:03,400 problem. So this is the connectivity matrix. 183 00:14:03,400 --> 00:14:06,400 It just tells you what gates want to connect to, what other gates, and how 184 00:14:06,400 --> 00:14:11,206 much. It is a symmetric matrix as you can see, 185 00:14:11,206 --> 00:14:16,630 c[i,j] is c[j,i]. Now, how do you build the A matrix? 186 00:14:16,630 --> 00:14:18,582 This is a thing you actually have to solve. 187 00:14:18,582 --> 00:14:24,42 Two, sort of three-step recipe, so the first thing is elements a[i,j] that are 188 00:14:24,42 --> 00:14:28,574 not on the diagonal. All right, it would be a little clearer 189 00:14:28,574 --> 00:14:33,140 here, that, that's the diagonal. Elements that are not on the diagonal are 190 00:14:33,140 --> 00:14:38,700 just the negative of the c[i,j] value. So, concrete example. 191 00:14:38,700 --> 00:14:42,540 There is a 4 over here. 4 is not on the diagonal, so there is a 192 00:14:42,540 --> 00:14:46,190 negative 4 over here. Alright? 193 00:14:46,190 --> 00:14:49,250 So that's how you get all the stuff not on the diagonal. 194 00:14:49,250 --> 00:14:55,190 Elements on the diagonal are the formula shown here. 195 00:14:55,190 --> 00:15:02,45 a[i,j], okay, on the diagonal, right? is, what, which is actually, I guess, we 196 00:15:02,45 --> 00:15:05,817 could be a little clearer about that, a[i,i]. 197 00:15:05,817 --> 00:15:11,820 elements on the diagonal are the sum from j equals 1 to n of c[i,j] plus the weight 198 00:15:11,820 --> 00:15:16,642 of any pad wire. It's probably easier to say that in 199 00:15:16,642 --> 00:15:19,150 English. Add up the ith row of this connectivity 200 00:15:19,150 --> 00:15:22,350 matrix, and then, add in the weight of a pad. 201 00:15:22,350 --> 00:15:30,600 So, for example, why is this a 6, right, for a sub 1ne. 202 00:15:30,600 --> 00:15:35,388 And the answer is because when we look at gate 1, we see that there is a pad wire 203 00:15:35,388 --> 00:15:41,670 with a 5, and then we add up all of the other wires connected. 204 00:15:41,670 --> 00:15:46,824 We add up the row, right. The plus sign, right, when we add all 205 00:15:46,824 --> 00:15:53,910 that stuff up, we have a 5 plus the row is a 1, we get a 6. 206 00:15:53,910 --> 00:16:00,161 That's why there's a 6 there. And similarly, why is there a 5 for the 207 00:16:00,161 --> 00:16:04,847 second element, and the answer is, if you add up everything in this row, of 4 plus 208 00:16:04,847 --> 00:16:09,959 1, and there's no pad wire for either for gate number 2, because that's the row 209 00:16:09,959 --> 00:16:17,230 associated with gate number 2. There's no pad for that guy. 210 00:16:17,230 --> 00:16:20,464 You get a 4 plus 1, you get a 5, so that's why you get a 5. 211 00:16:20,464 --> 00:16:26,820 So, pretty simple recipe. Things not on the diagonal minus c[i,j]. 212 00:16:26,820 --> 00:16:30,789 Things on the diagonal, add up all the weights of the row, and then go ask does 213 00:16:30,789 --> 00:16:36,354 this gate, the one associated with this row is it connected to a pad? 214 00:16:36,354 --> 00:16:41,930 Yes, add that number in too. That's it. 215 00:16:41,930 --> 00:16:47,406 Now, how do I get the b vectors? Also very simple, so I've got a very 216 00:16:47,406 --> 00:16:52,924 simple cartoon here of a gate called i, connected to a pad at location xi, yi 217 00:16:52,924 --> 00:16:59,774 with a weight wi on the wire. And it's really very simple. 218 00:16:59,774 --> 00:17:05,299 for the bx vector, if gate i connects to a pad at xi, yi with a wire with weight 219 00:17:05,299 --> 00:17:09,889 wi, then set the ith element of the vector to the weight times the x 220 00:17:09,889 --> 00:17:16,607 coordinate. And similarly for the y vector, you set 221 00:17:16,607 --> 00:17:23,302 the ith element of the by vector to the weight times the y coordinate. 222 00:17:23,302 --> 00:17:27,110 So, it's really just the things I'm circling here. 223 00:17:27,110 --> 00:17:31,442 You want to know what the ith element of the b vector is for x? 224 00:17:31,442 --> 00:17:38,870 Ask if gate i connects to a pad, if so, multiply the weight by the x. 225 00:17:38,870 --> 00:17:42,640 want to know the ith element of the y vector? 226 00:17:42,640 --> 00:17:45,995 Ask if the i gate connects to a pad, if so, take the weight and multiply it by 227 00:17:45,995 --> 00:17:49,890 the y. It's as simple as that, that's it. 228 00:17:49,890 --> 00:17:57,750 So now, we have another question. are these difficult to do in practice? 229 00:17:57,750 --> 00:18:01,590 Because, you know, look, if I have 1 million gates to place, I can clearly 230 00:18:01,590 --> 00:18:06,16 write the [COUGH], you know, the quadratic expression. 231 00:18:06,16 --> 00:18:10,304 and, you know, I can sort of evaluate what the wirelength is without any great 232 00:18:10,304 --> 00:18:14,50 difficulty. And I can use the recipe to go from the 233 00:18:14,50 --> 00:18:18,905 net list of the 2 point wires. And remember, I take the net list and I 234 00:18:18,905 --> 00:18:24,8 turn it into a bunch of two point wires with appropriate weights. 235 00:18:24,8 --> 00:18:27,599 I can take the net list of wires and gates and pads, and I can build the A 236 00:18:27,599 --> 00:18:32,589 matrix and I can build the b vectors. And the A matrix is going to have a 237 00:18:32,589 --> 00:18:36,371 million by a million elements and a million b's, and b's for x, and a million 238 00:18:36,371 --> 00:18:40,920 b's for y. How do I solve that? 239 00:18:40,920 --> 00:18:43,975 And the thing that's really quite amazing is these are very easy to solve, even 240 00:18:43,975 --> 00:18:48,440 when they're very large. the A matrix has a special form. 241 00:18:48,440 --> 00:18:52,527 It's sparse, which is to say, it's almost entirely made out of 0s, because, if you 242 00:18:52,527 --> 00:18:58,446 ask a gate what else it's connected to, the answer is, you know, a couple things. 243 00:18:58,446 --> 00:19:02,667 So that row has a million elements in it, but that row which represents gate i, you 244 00:19:02,667 --> 00:19:08,658 know, there's only five or ten or 20 other things in that row that are not 0. 245 00:19:08,658 --> 00:19:12,62 So that's what sparse means. It's also symmetric. 246 00:19:12,62 --> 00:19:16,872 The element above the diagonal is the same as the element below the diagonal. 247 00:19:16,872 --> 00:19:20,904 It is diagonally dominant, which is to say, the element on the diagonal is at 248 00:19:20,904 --> 00:19:25,340 least as big as the sum of everything else in the row. 249 00:19:25,340 --> 00:19:30,155 Mathematically, there's a name for this. these matrices are called positive 250 00:19:30,155 --> 00:19:32,950 semidefinite and these are very simple to solve. 251 00:19:32,950 --> 00:19:35,574 And what's interesting is we don't use something you probably know, we don't 252 00:19:35,574 --> 00:19:39,460 use, like Gaussian elimination. We don't physically build the inverse for 253 00:19:39,460 --> 00:19:43,589 the matrix, so I'm just going to write A to the minus 1 over here. 254 00:19:46,10 --> 00:19:49,430 A to the minus 1, and then I'm going to put a big cross through it, because I 255 00:19:49,430 --> 00:19:56,840 don't even want you to think about that. We do not invert the matrix. 256 00:19:56,840 --> 00:19:59,570 Maybe I should draw it in a different way. 257 00:19:59,570 --> 00:20:02,890 A to the minus 1 with a big like slash through it. 258 00:20:02,890 --> 00:20:07,862 We don't invert the matrix. We use iterative, approximate solvers. 259 00:20:07,862 --> 00:20:11,650 This means the solver converges gradually to the right answer. 260 00:20:11,650 --> 00:20:14,450 It also means the answers can be a little bit off, right? 261 00:20:14,450 --> 00:20:17,170 So they can be just, just, you know, a little, teeny, tiny. 262 00:20:17,170 --> 00:20:19,930 You know, if you're expecting the answer to come out to be 7. 263 00:20:19,930 --> 00:20:27,47 You know, it might come about to be 6.99999999996 or 7.00000000002. 264 00:20:28,320 --> 00:20:33,886 This is the way it works. but it's possible to solve even these 265 00:20:33,886 --> 00:20:41,240 gigantic equations very efficiently, very reliably very robustly. 266 00:20:41,240 --> 00:20:43,210 So what is the real one of these examples look like? 267 00:20:43,210 --> 00:20:46,785 So, so here is a little example, it's got four pads and a little bigger five gate 268 00:20:46,785 --> 00:20:51,311 net list. So, there's a grid a chip image that 269 00:20:51,311 --> 00:20:56,120 again goes from 0, 0 to 1, 1. X on the horizontal axis. 270 00:20:56,120 --> 00:20:59,396 Y on the vertical axis. There are four pads at 0, 1, the top left 271 00:20:59,396 --> 00:21:02,690 corner. 1, 1, the top right corner. 272 00:21:02,690 --> 00:21:07,619 1, 0, the bottom right corner. And 0.50 the middle of the bottom. 273 00:21:08,630 --> 00:21:11,222 And there are five gates labeled 1, 2, 3, 4, 5. 274 00:21:11,222 --> 00:21:15,847 Gate 1 connects to the pad at the top left and to gates 2 and 3. 275 00:21:15,847 --> 00:21:21,858 Gate 2 connects to gate 1, gate 3, and gate 5, and gate 4. 276 00:21:21,858 --> 00:21:30,426 Gate 3 connects to gate 1, gate 2 gate 4, and also the pad at 1, 0. 277 00:21:30,426 --> 00:21:36,730 Gate 4 connects to the pad at 1, 1 and also gates 2, 3, and 5. 278 00:21:36,730 --> 00:21:43,700 And gate 5 connects to gates 2 and 4 and also the pad at 0.5, 0. 279 00:21:43,700 --> 00:21:47,600 All of the wire weights are 1, except the two that are highlighted by sort of fat 280 00:21:47,600 --> 00:21:51,667 lines in the picture. There's a weight of 10 on the wire from 281 00:21:51,667 --> 00:21:57,180 gate 1 to the top left pad, and a weight of 10 on the wire from gate 1 to gate 3. 282 00:21:57,180 --> 00:22:01,38 And that just makes it interesting. So, the first thing I do is I build the 283 00:22:01,38 --> 00:22:04,764 connectivity matrix. And the connectivity matrix is a matrix 284 00:22:04,764 --> 00:22:08,954 that has 5 rows and 5 columns. And it just says, what's the weight on 285 00:22:08,954 --> 00:22:13,252 the wire between gate i and gate j? And so, there's a lot of 0s in the 286 00:22:13,252 --> 00:22:15,265 matrix. Because, there's a lot of things that 287 00:22:15,265 --> 00:22:21,190 don't have wires connecting them. But the first row is 0 1 10 0 0. 288 00:22:21,190 --> 00:22:26,190 The second row is 1 0 1 1 1. The third row is 10 1 0 1 0. 289 00:22:26,190 --> 00:22:31,60 The fourth row, 0 1 1 0 1. The fifth row, 0 1 0 1 0. 290 00:22:31,60 --> 00:22:34,590 Okay? So that makes sense. 291 00:22:34,590 --> 00:22:37,500 There're some 10s in there. Why are there some 10s in there? 292 00:22:37,500 --> 00:22:42,393 There's some 10s in there, because gate 1 connected to gate 3 has a weight of 10. 293 00:22:42,393 --> 00:22:45,949 So, the 3, 1 element and the 1, 3 element in that matrix have 10s. 294 00:22:47,320 --> 00:22:51,490 This is the A matrix. So the A matrix is off the diagonal, the 295 00:22:51,490 --> 00:22:56,450 A matrix is just the negative of the c matrix. 296 00:22:56,450 --> 00:23:00,356 So if I circle the term here, in the top row, the 10, you can see that it appears 297 00:23:00,356 --> 00:23:05,118 negative here. But it also has a diagonal, which is the 298 00:23:05,118 --> 00:23:12,10 sum of everything on the row of the c matrix plus the weight of any pad. 299 00:23:12,10 --> 00:23:16,330 And so, I think an important thing to note is like, why is the 21 in that 300 00:23:16,330 --> 00:23:20,586 matrix? and the answer is that I'm adding 301 00:23:20,586 --> 00:23:25,706 together everything in the first row of the c matrix 0 plus 1 plus 10 plus 0 plus 302 00:23:25,706 --> 00:23:30,758 0. But then, I'm also adding the weight of 303 00:23:30,758 --> 00:23:35,38 the pad, of the wire that goes to the pad. 304 00:23:35,38 --> 00:23:41,7 Because, remember what you do, the thing on the ith, Aii element of the diagonal? 305 00:23:41,7 --> 00:23:44,250 You add up everything in the ith row of C. 306 00:23:44,250 --> 00:23:46,980 And then you ask, hey, does this gate connect to a pad? 307 00:23:46,980 --> 00:23:48,810 If so, what the weight? So, that's what you get. 308 00:23:48,810 --> 00:23:50,831 And the bx and by vectors are created just like I said. 309 00:23:50,831 --> 00:23:54,731 You ask if the gate in the ith position connects to a path in it, so for the x 310 00:23:54,731 --> 00:24:00,373 vector, you take the weight and you multiply it by the coordinate. 311 00:24:00,373 --> 00:24:08,328 And for the y vector, you take the weight and multiply by the coordinate. 312 00:24:08,328 --> 00:24:13,463 And so, among other things, you see that the first element of x is a 0 because 313 00:24:13,463 --> 00:24:20,110 gate 1 connects to a pad with an x of 0. And so, when you multiply 10 by 0, you 314 00:24:20,110 --> 00:24:24,326 get a 0, but the by vector has a 10, because the y coordinate of the pad is a 315 00:24:24,326 --> 00:24:28,330 one. 10 times one is 10. 316 00:24:28,330 --> 00:24:34,557 Very simple, very mechanical recipe. And so what happens if you solve it? 317 00:24:34,557 --> 00:24:37,712 This is what you get. So remember that I said, that the way to 318 00:24:37,712 --> 00:24:42,68 think about this is that the layer are springs and they're pulling like elastic 319 00:24:42,68 --> 00:24:48,434 bands, they're pulling the gates towards each other and toward the pads. 320 00:24:48,434 --> 00:24:53,333 this looks like something you would get with springs, so you know, where are the 321 00:24:53,333 --> 00:24:56,779 gates? Well, if you draw a straight line from 322 00:24:56,779 --> 00:25:00,496 the upper left corner to the bottom right corner, gate 1 is way up in the upper 323 00:25:00,496 --> 00:25:05,191 left corner, because it's got a wire with weight 10 on it. 324 00:25:05,191 --> 00:25:09,874 That spring is pulling really hard to get gate 1 in the upper left-hand corner. 325 00:25:09,874 --> 00:25:13,778 the wire between gate 1 and gate 3 also has a weight of 10, and so gate 3 is 326 00:25:13,778 --> 00:25:19,470 right up there right close to gate 1 on that straight line. 327 00:25:19,470 --> 00:25:22,683 Gate 2 is a little bit further down on that straight line from the left corner 328 00:25:22,683 --> 00:25:26,82 to the left top corner to the bottom right corner. 329 00:25:26,82 --> 00:25:29,184 Gate 4 is a little off. It's sort of more toward the center of 330 00:25:29,184 --> 00:25:31,904 the chip, but it's pulled toward the top right, because there's a pad wire pulling 331 00:25:31,904 --> 00:25:35,179 it to the top right. And gate 5 is pulled down a little bit, 332 00:25:35,179 --> 00:25:38,779 because there's a wire pulling it, pulling it down a little bit. 333 00:25:40,380 --> 00:25:44,458 It, it all just works out. if you like the physics of the problem, 334 00:25:44,458 --> 00:25:49,680 makes for a sort of an interesting sort of intuitive kind of a problem. 335 00:25:49,680 --> 00:25:52,914 The other thing that's kind of nice about this, that, that, that you might not 336 00:25:52,914 --> 00:25:56,99 think of, if you really think of the pads is being just these like fixed objects 337 00:25:56,99 --> 00:26:00,12 and you really think of the wires as springs. 338 00:26:00,12 --> 00:26:06,60 When you let the gates go, they're all going to be inside, in-between the pads. 339 00:26:06,60 --> 00:26:09,84 The gates as a result of this linear assault, they're never going to be 340 00:26:09,84 --> 00:26:12,540 outside the surface of the chip, because the springs are going to pull them to be 341 00:26:12,540 --> 00:26:16,480 in-between the pads. That's actually a very nice and very 342 00:26:16,480 --> 00:26:19,798 useful feature. So, this is what a quadratic placement 343 00:26:19,798 --> 00:26:24,110 looks like. And life would be great if we were done. 344 00:26:24,110 --> 00:26:27,740 If you could set set up this beautiful set of big matrix solves and just solve 345 00:26:27,740 --> 00:26:31,400 it and be done. Unfortunately, we're not. 346 00:26:31,400 --> 00:26:38,881 There's a new problem, and we're going to talk about that next. 347 00:26:38,881 --> 00:26:39,831 [SOUND].