[SOUND]. So here were are in lecture 9.6. We're going to talk about a very different kind of placement algorithm. We're going to talk about analytical methods. So, all of the placement techniques that we've talked about up 'til now in this lecture, have been based on some form of. Random improvement, random exchange, random perturbation with some interesting control parameters like for example simulated annealing. Those are really good and powerful techniques but they really run out of steam. They are not very efficient when you get to let's say a half a million gates. And since people are really placing things with a few million gates, you know, 10 million gates these days as a kind of an atomic placement task maybe even more. the annealing like methods don't really work very efficiently. The analytical methods are based on a very different kind of an idea. We're actually going to write an equation. a mathematical equation and we're actually going to use calculus on it and some interesting linear algebra and we're going to solve that equation, numerically. And the solution of that equation is going to be the placement of the gates. And if you're thinking wow, if I have a million gates. Am I going to have an equation with, like, 1 million x's and one million y's in it? And you're telling me that I'm going to do calculus on it, and I'm going to solve it? I'm going to tell you yes, that's actually how modern placers really work. So let's start by talking about the sort of the introductory background to analytical placement. We're going to write an equation whose minimum is the placement. Now you understand something about this because roughly speaking what the iterative improvement simulated annealing style placers did was iteratively minimize a wirelength function. Whose value is determined by the locations of all the gates. But now we're going to write something that looks more like a physics equation, a continuous valued equation, an analytical equation, an equation that I can actually write down. And we're going to solve for its minimum. So if you have a million gates you need a million x y values. As a result one for each of your million gates. We're going to formulate an appropriate cost function for all of the gate level x y coordinates. That function is going to be a function of ten, of 1 million x's and 1 million y's, and then we're going to solve it analytically which means we're actually going to do math on it. And we're going to get 10 mill 1 million x's and 1 million y's. And that will be the minimum of this function. And the resulting set of values give you the placement of all million gates. And I recognize that this sounds kind of crazy. but it works great. And there's a trick. The trick is that you have to figure out a way to write the wirelength in a mathematically friendly form that you can optimize. And what's interesting is that this is actually quite possible, and in fact there's several different ways of doing it. All modern placers for big ASICs and big Systems On Chip are analytical in this style. So the big idea behind the class of analytical placers that we're going to study in this lecture is something called the quadratic wirelength model. And the idea is that it turns out that by optimizing this thing called the quadratic wirelength instead of the half perimeter wirelength, it has the nice friendly mathematical properties we need to be able to derive a solution. So said differently, why do we pick the quadratic wirelength? Because the mathematics works out in a way that we can solve. So for a 2-point net, this is actually very simple. This is the squared length of the distance between the points. So I've got a little grid here, the same grid I have been showing previously. X goes from 0 to 4, so there's five columns, Y goes from 0 to 5 so there's six rows. Let's assume that the coordinates refer to the center of the grid elements. So there's a gate at 1,4 labeled 1, and a gate at 3,1 labelled 2. And this is a 2-point net as we know. What is the length of this net? It's just the length of this hypotenuse of this triangle, so I'm just going to sort of draw this kind of like a triangle. it's just the length of the straight line, the blue straight line between gate 1 and gate 2. And that's nothing more than x1 minus x2 squared plus y1 minus y2 squared. So that's actually, pretty straight forward. And if we were to, you know, actually calculate that that's going to be 3 minus 1 squared plus 4 minus 1 squared, do that math and the length of this wire is 13. So, this is straight forward. Note that there's no square roots here, okay? This is the squared, I'm going to write this as squared, squared length here, okay? It's the squared length between those two gates. So, It's not as mathematically friendly if you take the square root. but perhaps more interestingly, is, What happens if your net has more than two points in it? That's not at all straightforward. So, here is now, a k-point net. K, in this particular case, is 4. So, I again have the grid, x goes from 0 to 4, y goes from 0 to 5. And there are four gates, gate 1 is at 1,4, gate 2 is at 3,1, gate 3 is at 3,3, and gate 4 is at 4,5. And I've got a wire drawn here that's kind of the way a physical wire might get routed. But it's not at all clear what quadratic wirelength means here. And so, here's the recipe. The first thing you do is you replace the one real net with k times k minus 1 over 2, 2-point nets. And the way to think of that is I'm just going to add a new net between every pair of points, and that's how many points, pairs of points there are. Right. So this has a name that's called a fully-connected clique model. this is pronounced cleeek clique model. And so, the way this one would work is, I'm showing again the, the grid without any wires in it on the right here. Gates at 1,4, 3,1, 3,3, and 4,5. And what I'm just showing is that. If k is equal to 4, then 4 times 4 minus 1 over 2 is 6. So what's going to happen is there's one 2-point wire, two 2-point wires, three 2-points wires, four 2-point wires, five 2-point wires, six 2-point wires. I'm just drawing every wire in k times k minus 1 over 2 for k is 4, 4 times 3 over 2. There's six 2-point nets that we're going to connect. So that's what you do. You take the one multi point net when k is greater than 2, and you turn it into k times k minus 1 over 2, 2-point nets. It has a name. Sometimes it's called fully connected because obviously ever pair of gates has a wire connecting it. More commonly it's called a clique. So, here's that same example. I'm showing the clique model again the grid, x goes from 0 to 4, y goes from 0 to 5, gates at 1,4, 3,1, 3,3, and 4,5, and I'm showing all six 2-point nets. The other thing you gotta do is that you have to wait, which is to say, multiply the length of each of these quadratic wirelengths by a number. So let's just think about it. You know, I used to have one physical net. And I replace this one physical net with six nets. And I'm going to measure the quadratic wirelength of each of those six nets. It makes some sense that I need to multiply by some small number. So that I don't dramatically over estimate how much wire this physical net needs. And so the, there are lots of ways that people do this, but the traditional weighting factor is 1 divided by k minus 1. So, in this particular example. If we were to estimate the wire length. There would be six quadratic wirelengths, which are squares of differences of coordinates. And each one of them is multiplied, in this case, by 1 over 4 minus 1, which is 1 3rd. So this is 1 3rd times 4 minus 1 squared plus 5 minus 4 squared. Plus 1 3rd times 4 minus 3 squared plus 5 minus 1 squared. 1 3rd 3 minus 1 squared plus 4 minus 1 squared. 1 3rd 3 minus 1 squared plus 4 minus 3 squared. 1 3rd 4 minus 3 squared plus 5 minus 3 squared. 1 3rd 3 minus 3 squared plus 3 minus 1 squared. Six 2-point quadratic wirelengths, each multiplied by this weighting, that sort of reduces their estimated length. Now the other thing I'll notice here is that when k equals 2, this weight is just 1 divided by 2 minus 1, which is 1, so there's no special treatment for the two point case, right? So it all works out. You always multiply by the weighting factor 1 over k minus 1 and when it's a 2-point net, nothing special happens. You just multiply it by 1. So, there's one more big idea here, kind of an interesting idea. To make the math work out easily, we're going to ignore the physical size of all the gates. we're going to pretend the gates are dimensionless points. Now previously in the iterative improvement placer we also sort of ignored their size. We pretended they were all the same size. But it's not like we actually said that they had no size at all. We just assumed they were as big as the square on the grid. We are now going to honestly pretend that they don't have any size at all. They're dimensionless. And the big thing is we're going to ignore the fact that the gates can't go on top of each other. And as we shall shortly see the technique we're about to develop puts lots of gates on top of each other. It's going to be the second part of our algorithm is how we fix that. This sounds strange but it allows us to write a very simple, very elegant equation for the placement, and then to solve it quickly and effectively. So why do we do these interesting mathematical tricks? Why do we model the wirelength as a bunch of fractionally weighted 2-point quadratic forms? And the answer is, because the math makes it possible for us to solve. So the easiest way to see this is with a little example. So I've got a little example here. So I'm modeling the chip as box. X goes from 0 to 1, and y goes from 0 to 1. This is totally arbitrary, by the way. this could go 0 to 1. It could go from 0 to 100. It could be in microns. Doesn't matter. The, the, the math will work out. And there are two gate points, they have indexes 1 and 2, they are the green circles with one and two next to them. And there are three nets, they're each two points to just keep things small and simple and they have weights 1, 2 and 4 respectively, and there are two pads. And I'm just putting a little arrow to the pads. There are two pads. There's a pad at 0,0. It's the red square. And a pad at 1,0.5. The pads are fixed pins. Those are the things, if you will, around the edges of the chip. That are the IOs, the input outputs. And so there are three wires. There's a wire from the pad at 0,0 to gate 1, with weight 1. A wire from gate 1 to 2, with weights 2. And a wire from gate 2 to pad 1, 0.5 with weight 4. And I'm just making the weights up, so you can see what happens when we do the math. And the math all turns out nice. So, it's very easy to write the quadratic wirelength. And that fact's one of the reasons we do it like this. So, if we just look at the problem, the first thing we see is. I'm going to look at the wirelength from gate 2 to the pad at 1, 0.5. That's 4. The length of the weight on the wire times x2 minus x1 squared plus Plus 4 times y 2 minus 0.5 squared. Where are those constant? Well, the pad is fixed at 1,0.5 so you know, we subtract 1 from x and square it. We subtract 1 0.5 from y and squared it. And the fractional multiplier or in this case the weight multiplier, it's not a fraction is a 4. The other wire that connects gates 1 and 2 has a weight too so you get 2 x2 minus x1 squared plus 2 y2 minus y1 squared. The final wire has weight 1, and it connects to a pad, 1 times x1 minus 0 squared plus 1 times y1 minus 0 squared. That's the components of the quadratic wire length. You add these all together, and that's it. So it's really as simple as that. Now there's one other thing I'll have you notice, and this turns out to be very important. If you look at these terms, there are no terms where there's an x variable multiplied by a y variable. In each one of these cases we get terms that look like xi squared, and xi times xj, or yi squared, yi times yj. Right? So if you look at the middle equation, right? You're going to get an x2 squared, an x2 x1 and an x1 squared, you're going to get a y2 squared, a y2 y1, and a y1 squared with some constants And also for the wires that connect to pads, you're just going to get linear terms, x2s and x2 squareds, y2s and y2 squareds, for example, on the first one, but you're never going to see an x multiplying by a y. This turns out to be extremely important because it means I can separate the x terms and the y terms, and, as we shall see, I can actually optimize them separately. So the next great question is, how do I optimize this? So let's go look. [SOUND]