[SOUND]. So, here in lecture 9.9, we're going to finish our discussion of placement, and we're going to do that by showing a kind of detailed example of what recursive partitioning does. For a very small little example of a placement done in the quadratic style. So, it doesn't have very many logic gates, and it's not very big, and it doesn't have very many pins. But it's very interesting, and I think useful to just show step by step. What does the initial quadratic placement look like? What does the assignment step look like? What does the containment step look like? What do the pin and gate propagation steps that link from a big problem to a sequence of smaller problems? So, to finish things up, we're going to talk about in detail, an analytical placement model, and then we'll just summarize the whole placer lecture. Let's go see how this works. So, I think the best way to show how the recursive partitioning idea really works is by just taking a very small little example and walking through the first couple of partitioning steps. So, you can see exactly what happens. So, I've got a little cartoon of a netlist here. And so, it's in a square chip image. There are three pads, a, b, and c. a is in the top left corner, b is in the middle of the right hand side, and c is on the bottom, about a third of the way from the left. There are five gates, labeled 1, 2, 3, 4, 5 in little circles. Gate 1 is connected to Pad a on the top left, and also Gates 2 and 5. Gate 2 is connected to Pad b on the right side, but also Gates 1, 5, and 3. Gate 3 is connected to Gates 2 and 4, but also Pad c on the bottom. Gate 4 is connected to Gates 3 and 5, and Gate 5 is connected to Gates 1, 2 and 4. And so, the first thing we do is we formulate the quadratic wire length minimization problem, and we solve it. And we get a placement that looks like all of the gates are connected by springs. And so, we get one of these sort of stretchy gates connected by elastic bands looking kind of, kind of placements. And the way I would, I would describe this is that most of the gates, Gates 1, 5, 4, and 3 are kind of on a line between Pad a on the top left and Pad c on the bottom. And Gate 2 sort of pulled off too far to the right is connected to Pad b. Now, this is all artificial, but this is set up in ways that are consistent with the way real quadratic placers can be tremendously, dramatically unbalanced. And this particular example creates all of the problems that you can really face. So, one of the things we notice immediately is that Gates 1, 5, 4 and 3 all seem to want to be on the left. But that's not going to be possible because let's assume that, you know, there's only space for about half of the gates. There are five gates. There's only space for, let's say, two or three gates on any side in half of this chip. I can't put four gates over there. Somebody is going to have to go on the right. So, what do we do? The assignment step says, let's sort the gates in the quadratic placement on their X value. And so, we sort them. And the gate order is 1, and then 5, and then 4, and then 3, and then 2. And what we say is, let's pick about half of them in the sort order. So, let's say that it's okay to put three of them on one side. And we find that Gates 1, 5 and 4 are going to go on the left, so I've colored them in light green. And Gate 3 and Gate 2 are going to go on the right, that means our new smaller quadratic placement problem, the containment problem we're about to solve, is going to only involve Gates 1 and 5 and 4. Gates 2 and 3 are outside the region we're about to place again. And so, I've got a new picture that has the chip image, and Pads a, b, and c, top left, middle right, bottom left. And it's got the three gates, 1, 5 and 4, in gray. And it's got the whole left half of the chip in gray which says, this is what I am about to replace. I'm about to replace Gates 1 and 5 and 4 to see where they want to go. Once we insist that they are contained on the left hand side, how do we make sure the gates stay there? We take everything that those gates are connected to and we represent it somewhere on the boundary of the left-hand side. That's this stuff called Propagation. So, we propagate Gate 2 to the boundary. We just push it to the left. And we propagate Gate 3 to the boundary, we just push it to the right. And one of the things that's very important to note about Gate 3 is that although the first quadratic placement put it on the inside, it's not going to stay there. It's not part of this new quadratic placement problem. I'm just going to draw a little circle around this stuff that is part of the new quadratic placement problem that we are about to solve, okay? Gate 2 gets pushed to the boundary. Gate 3 gets pushed to the boundary. I'll note also that Pad b does not get pushed to the boundary. Why not? Pad b is not connected to any wires that start in the left-hand side and leave and go to Pad b, so I don't have to worry about Pad b. And so, I get a new quadratic placement problem. It has the shape as shown. It's as tall as the original placement problem, but half as wide. It has gate, it has Pad a on the top left, and Pad c kind of in the middle of the bottom. And it's got two pseudo pads, Pad 2 and Pad 3, sort of on the middle bottom right, and it's got the wires that connect to 1, 5, and 4. But it's also got a wire from 5 to Pad 2, and 4 to Pad 3, which are now pseudo pads. I'm going to solve a new quadratic placement problem. It's got half as many gates, it's got three gates, not five gates. And so, I solve it. And I now have a new quadratically placed result. And so, what happened is that Gates 1 and 5 and 4, they all kind of went up a little bit in this little cartoon example. They all kind of, kind of went toward the top of the layout because there isn't anything pulling them down. There's nothing connecting to Pad c on the left-hand side so they all just go up a little bit. So now, we can return to the right-hand side. And this is still sort of a cartoon. The stuff on the left-hand side, Gates 1 and 5 and 4, are placed. So, that's why my little cartoon, which has Gates 1 and 5 and 4 on the left, it's white on the left, it says placed. We know where those guys want to go in the left-hand side. The right-hand side is now dark gray. That is about to be replaced. Gates 2 and 3 are still moving. What we know from the assignment step from sorting is that they're going to be on the right. But we don't know if they want to go on the right. And so, what we do is we make a representation of all the stuff to which they are connected that's not on the right. And so, what we do is we propagate the gates and the pads. So, Pad c slides over to the right and goes to the center line. Gate 4 slides over to the right and goes to the center line. Gate 5 slides over to the right and goes to the center line. Gate 1 slides over to the right. And so, what happens when we look down the center line, pseudo Pad 1, pseudo Pad 5, pseudo Pad 4, pseudo Pad c, I will note that Pad a didn't go anywhere. We didn't slide it over. Why not? Pad a has no wires that go to the right-hand side. It does not need to be represented in the containment problem on the right-hand side. So, what do we get? We get this new, smaller, right-hand side quadratic problem, has psuedo-pads 1, 5, 4, and, on the left, and real Pad c but slid to be a single pad on at the bottom. It had Gates 2 and 3 to be, to be determined in the middle, and it had a real Pad b on the left-hand side. We solve the new quadratic placement problem. And now, I'm making the box white, and I'm saying placed in little gray letters. And we see again a placement that looks like things connecting gates to pads with springs. It's got that sort of gates under tension kind of a look. And roughly speaking, the gates are on a line, kind of sort of drawn straight between b on the middle right, and c on the lower left. But they're a little distorted, they're pulled up toward Pads 1, 5 and 4, which are sort of located evenly spaced down the top of the left-hand side. And so, now we can take a step back and say, look, I have executed the containment operation. And I have Gates 1, 5, and 4 placed in good locations on the left, once they are required to be on the left. And I have Gates 2 and 3 placed on the right once they are known to be required to be on the right. But, I'm not done yet. I'm going to continue to partition this chip into smaller pieces because one of the things I notice is that I'm not exactly sure on the left where everything wants to go. Probably 1 and 5 want to go on the top, and 4 wants to go on the bottom. But look, on the right-hand side, 2 and 3 are already on the bottom half of the chip. And if I chop each of these regions apart again, it's not exactly clear whether Gate 2 and 3 want to both be on the bottom with no gates on the top. Or whether because of all those wires pulling Gate 2 up to Gates 1 and 5 on the left, does Gate 2 really want to go on the top. I need to solve new quadratic placement problems. And so, here we go again. On the left, I am going to say sort the gates on Y. And If I sort the gates on Y, I get Gates 1, 5, 4 in order from the top to the bottom, and I'm going to decide that Gates 1 and 5 go on the top, and Gate 4 goes on the bottom. And so, I'm going to formulate a new containment problem. I've just solved the assignment problem. I know what gates are going to go there. 1 and 5 are going to go on the top. The new containment problem is to figure out all of the gates and pads outside that this thing is connected to and to push them some place on the boundary of this new region. Now, the thing that's going to happen now is that I'm going to get pseudo pads on more than just one side. So, here's what happens. Gate 4 is on the bottom, it's going to propagate up to the bottom of this region. Gate 2 is way far away from this thing. The closest point I could propagate it to and the easiest point is to just put it on the corner. But nothing else actually needs to move. Pad b does not need to propagate neither does Gate 3, that's this one over here. they don't have any wires that connect directly to Gates 1 and 5. Gate 2 propagates to the corner of this region, that's sort of the closest point on the region, and Gate 4 just propagates up to the bottom of the new region. And now, I have the new quadratic placement problem. I know what I have to solve, it's one quarter the size of the original problem. It's got real pads and pseudo pads all the way around it and it's got two gates in it. I can write the equations again and solve them and they will be contained in that upper left white square. So, what do I do? I keep recursively partitioning. What I'm probably going to get is Gates 1 and 5 on the left top, Gate 4 on the bottom left, Gate 2 on the top right, Gate 3 on the bottom right, probably based on the way I was developing this artificial example. Usually, you continue until you have a small number of gates in each region typically between say, 10 and 100. But if, you know, you're placing something with like a million gates, you don't go down to one gate in every region. You, you know, you go down just like a nice small number, 10 to 100. And what you're going to get is a good global placement, but you're still not going to get what we call a final placement. You're going to get something that looks like this placement on the right-hand side here. A lot of little squares with a lot of little blobs of gates in them. it turns out, we're still not quite done. We still need to force the gates into the precise rows of standard cells. And, you know, the quadratic placement methods, for all of their beauty, they cannot force the gates into lined, lined up standard cell rows without overlaps. So, there's one final solution step that I don't really have time to talk about in great detail, which is called Legalization. Legalization is the process of taking the final, in this case, analytical placement where the gates are points. And, snapping them into rows in some intelligent way, and there's many different algorithms. there's some things we can do in the assignment step and the containment step that will help us a little bit. We didn't have time to talk about them. there's some other interesting analytical methods that we can do that that try to do the legalization. it's a rich source of interesting combinatorial optimization problems. One surprisingly easy way to do this is with annealing. you know, formulate the wire length, minimum wire length problem. Maybe even formulate a part of the cost function as being, I would like to move the gates from where they start as little as possible. Maybe have that be part of the cost function. Do swaps and you know, kind of movements of the gates. Little movements of the gates in the rows. And the big trick is you you don't set the initial T equals HOT to be a hot number. You set it to be a very small cold number. So, you set the initial hot temperature to be a cool number. So, instead of randomizing things very aggressively, you just sort of gently simmer them. I know that sounds crazy, but but people really do that. You set the initial hot temperature of the annealer to a very cold number, so you just allow it to sort of bubble around a little bit to go from not being in the rows. You snap them into the rows, and you let them sort of jiggle around a while until they come out in sort of reasonable places. Like I said, it sounds crazy. It works really well. People really do that. So, here we are finally at the end of this very long and interesting and, and you know, kind of content-rich lecture. what can I tell you about placers? Here's what I think you know. Early placers were based on iterative improvement, random iterative improvement, and simulated annealing is a very good and famous example. Annealing stuff is used widely in VLSI CAD . And we showed you how to make a simple annealing-based placer. But it's not really the way big placers are done today, it's just too inefficient. But it's important to know from the history of VLSI CAD, and for all the other kinds of things that use annealing. Modern placers are all analytical. You write some kind of a big equation, and you minimize it directly with numerical methods. and all of these things are really based on what model of the wire length you can, you can work out. And turns out there's lots of different ways of doing that. Many modern placers can do some legalization at the same time as the wire length. The Quadratic Placement is a very famous important example. We took the quadratic placement and we did an interesting recursive partitioning, kind of a scheme, to get it to be a real, almost real final placement. And then, one of the things I suggested was do a little annealing with the temperature cool at the end to sort of jiggle things together and snap them into rows. So, it's interesting about how real placers are actually sequences of different kinds of placement sort of glued together to make, make the real problem. Placement is a wonderful, interesting, big, active subject area. But at the end of this week, you actually know a lot. A lot about the history of placement, the mathematical foundations of placement and something about how real modern analytical placers are done as well.