[SOUND]. So here in lecture 9.8, we're going to continue our exploration of Analytical Placement. The really amazing thing about the quadratic wire length model is that I can write a giant equation for where the logic gates go. And I can solve it using some calculus and some linear algebra, and actually get as the solution to this equation, done numerically, a placement. That's pretty amazing. The problem is that because we made some key assumptions, and one of those assumptions is that the gates are dimensionless points, we don't actually get a legal placement. So, unlike the intricate methods where we had a grid and every gate was located in one and only one cell on the grid, when we're done with a quadratic style analytical placement, the gates can be in one big blob in on little corner of the chip. We're going to have to do something, a different kind of an optimization step to kind of spread them out. And interestingly enough, we're going to do something that's kind of recursive. We're going to chop the chip up into pieces. We're going to figure out which piece the gates need to go in. And we're going to formulate an increasing series of smaller quadratic placement problems, each of which is going to, sort of in a finer, and finer, and finer way. Put the gates in the right place. So, this is recursive partitioning using a quadratic style analytical placer model. Let's go see how that works. We just introduced the full, sort of mathematical model and solution technique for representing wire length as quadratic clique wire-length model. pretending all the gates are dimensionless points, optimizing the quadratic wire-length, which turns into a set of matrix solutions. An a matrix and a bx vector, an a matrix and a by vector, and we solve that and we get x-coordinates and y-coordinates. What does it look like? It looks like this. This is a small IBM ASIC a reasonably famous public benchmark with a few thousand gates. And you immediately see the problem. This doesn't look like a placement at all. this is this big smear of gates right in the middle of the chip, and this little sprinkling of gates in other places. this is a big problem, a new problem an interesting problem, maybe an unexpected problem. The quadratic wire-length model minimizes the wire-length for netlists in a numerical way, but it totally ignores the fact that the gates have a physical size and they can't be on top of each other. There is, and this is the beautiful thing about the quadratic wire-length model. There is one solution that minimizes the sum of the quadratic wire-lengths. And when you solve it, you get what you get. And you don't necessarily get the gates lining up in rows not on top of each other. I've got to fix this. And it turns out there's a lovely strategy for doing this which we can call Recursive Partitioning. Lots and lots of recursive stuff in this class. The recursion is a little more conceptual, it's not like the Shannon co-factoring stuff, but you'll get the idea when we show you some pictures of the geometry. This is a bigger industrial example. I'm showing you this for a couple of reasons. One, just because it looks cool. This is something that was done by one of my students, Joan Shue. This benchmark is also from IBM. This has about 211,000 gates, they are in blue, and about 543 fixed blocks. Those are the red things. You imagine some designer has simply put them down in the right places where they want to go. And the image shows where the gates want to go if we modeled the blocks like big pads, if you think that. and this is a quadratic placement where we model all of the wires as two-point quadratic connections with appropriate fractional weights. And we solve the placement problem so there are pads around the outside, I'm just going to circle some pads. Those are all pads, all those little skinny boxes around the outside are pads. all of the 500 red boxes are either SRAMS or pads. That's all the stuff in red. and the blue smear is the result of the 2 ax equals bx, ay equals by solved. So, why am I showing you this? this is an example of how badly imbalanced the quadratic placement can be. It can be terribly, terribly unphysical. So look, almost all the gates want to go up in the top left. That just says there's a lot of pads up there, and there's a lot of big dense wiring groups that go from the SRAMS and the top left to all of the gates that want to be there, but they can't go there. So, we're going to have to do something really smart to make the gates go into more physical, reasonable, realizable places. So, the big idea is this recursive partitioning. So, you do a first quadratic place, and I'm going to start calling quadratic places QPs, because it takes less space on my slides. And I'm going to write QP a lot. You do the first quadratic place and you get some weird blob of gates that minimizes the quadratic wire-length. Then, what you do is you partition the chip right in half. And so, I'm just going to draw a big line over here. You partition the chip in half, and you make a decision. Some of the gates are going to go on the left, some of the gates are going to go on the right. You formulate two new smaller quadratic placement problems where you say, the gates on the left must stay on the left and the gates on the right must stay on the right. And so, I'll solve two new quadratic placement problems that are each about half the size of the first one. And then, why this is recursive? I will repeat. I will again partition things. But I will partition the region on the left by drawing a line to the left and the right. And I will partition the region on the right. Similarly, by drawing a slice to the left and the right, and I will say that the gates on the top on the left have to go on the top, and the gates on the bottom on the left have to go on the bottom. And so, I now get four regions, each with about 1 4th of the total gates.. I will solve four new smaller quadratic placement problems, and I'll see where they go. And I will just continue to do this until I get a placement that looks a little bit more like a real physical placement. So, the one on the right I'm showing you here, and this is a real one, by the way. This is the result after 16 QP solves. And you can just keep going until the number of gates in each of these little cells, these little grid squares, is something manageable. So, here's a high level recipe for how recursive partitioning is going to work. These are the big steps. There's the partitioning step itself. How do you divide the chip into new smaller placement tasks on which we can run a smaller quadratic placement? The assignment task says, which gates should go into each new smaller region? So, we run quadratic placement on a region, then we partition the region into two smaller parts, and we assign gates to each of the two parts. Which gates go where? And there's the containment problem. How do you actually formulate the new quadratic placement matrix solve so the gates stay inside the new regions, but inside the new regions they go in good places. Because one of the problems is that, there are gates inside the region. The new region, the smaller region, that are connected to wires that go outside the region. How do we, how do we model that sort of connection from the inside of a smaller problem to the outside? That's the containment problem. And I'm going to talk about one early strategy from a classical paper. So, this is a paper from Ren Song Tsay, Ernie Kuh and Chi Ping Hsu called PROUD: A Sea-Of-Gates Placement Algorithm way back from December 1988. This is one of the first generation of analytical sort of placers, one of the first generation of quadratic placers. By modern standards, this is a very, very simple kind of a placer. Modern, modern placers are very much more complicated. The thing I like about the PROUD Algorithm, it's really easy to explain how it works. If you know how to do the basic quadratic placement mathematics it's not too hard to explain the partition step, the assignment step, and the containment step. They're all sort of fairly simple geometrically. It's a quite elegant solution, it's something you can actually, I think, get your head around. So, so let's talk about this. How does this recursive partitioning stuff work? Well, the, the first problem is, how do we actually do the partitioning? And the solution is that, after the first quadratic placement, we're going to divide the chip area exactly in half. And for us, we're just going to pick vertically as the way to divide it. Now note, this is completely arbitrary. You could divide it horizontally. But for us, it doesn't matter. We're just going to do a vertical division, and we want half of the gates on each side, right? So, we're going to slice it and we want half of the gates to be on the left-hand, and we want half of the gates to be on the right-hand side. And the question is, how do we make that happen? And why that could be a challenge is, and I'm showing you a little tiny picture of the IBM ASIC again. What if the quadratic placement does not spread the gates evenly between the halves? And so, I'm showing you my little cartoon of a chip that's a square with some pads around the edges, and there's, you know, about a dozen gates here. And they're all kind of smeared in the blob on the left. How do we know which gates to put on the left versus which gates to put on the right if this thing that I'm showing you is the initial quadratic placement, or set differently the quadratic placement is telling you they all want to go on the left? What the heck am I going to do? Well, that's just not acceptable, right? I have to do something that puts the gates in a sensible set of locations. So, what I'm going to do again[SOUND] is I'm going to partition the region that I'm placing exactly in the center. And I'm going to reformulate a new quadratic placement for the gates on each side. So my new problem is, how do I pick which are the right gates? This is the assignment problem. And the answer is actually lovely and simple. I've sort the gates. So, I sort the place gates first on their x-coordinate and then on their y-coordinate in the event that they are any ties. And honestly, if these things are based on floating point x's and floating point y's, you're probably not going to have too many ties. But you're going to do this anyway. First on x, and then if goes a tie, then on y. And so, the answer is that even if all of the gates are smeared in a clump way over on the left, when you sort it on x and then on y, you take the first N/2 gates in the sorted list, those are the ones that go on the left. All right, so that's those guys. Those guys go on the left, and all of the others go on the right. And you have now taken the initial quadratic placement and use the results of that placement, the x and y-coordinates, to do the assignment problem. Which gates go on the left? Answer, the half of them that are the most on the left. It sounds simple but, you know, it's what works. The leftmost half of the gates go on the left, the rightmost half of the gates go on the right. Now, we've got this thing that I'm, I'm calling the containment problem. So, you've now decided which gates go on the left. And so, I'm, I'm drawing the left part of the chip as a grey box. And I'm saying, let's focus on the gates inside this shaded region, R, on the left-hand side of the cut. I need to formulate a new quadratic placement problem to properly locate those gates in a region that's now the same height as the original QP problem, but half the width. And the new problem is, I want to solve a quadratic placement problem and I want all the gates to stay there on the left hand side. And I've really got two things that I've got to worry about. The first is, how do I keep the gates on the left-hand side on the left-hand side? How do I keep them in the gray box? And the second part is, how do I model the wires that connect from those gates on the left-hand side to the gates and pads on the right-hand side because, you know, I cannot ignore those things? You know, the reason that the quadratic placement problem is you know, is so attractive and why people like this method is that it optimizes the lengths of all the wires. If in the partitioning problem we ignore the fact that there are, say a whole bunch of wires that connect the gates that are not on the left-hand side, we're going to put those gates in the wrong place. You know, the gates that are heavily connected to the gates on the right-hand side, they probably be want to be on the right-hand side of the grey box. I can't just take all those wires and make them vanish, I have to do something with those. So again, there's a geometrically very attractive solution, and it's got a funny name. we're going to do something called Pseudo-pads. These are also called Pseudo-pins, sometimes. The basic idea is that every gate and pad not inside region R is modeled as a pad on the boundary of R. And the word that we use is propagate. We propagate these outside gates, or outside pads, using their current xy location to the nearest point on R, which is the grey box. And so, for this simple first cut we just take the y-coordinate and we put the pad on the center line, so that's the, that's the center line. So, you know, what actually happens here, right? Is that anything that the gate was connected to in R, that's connected on the right-hand side. So, imagine that there are a couple of gates which are the red circles, and a pad which is the red square. We take those things and we just slide them leftward and we pretend that they really live on the cut line, on the star. And so, we are not ignoring them. We're sort of doing the right thing. We are putting them in the right position on the boundary of region R so that when we replace all of these gates, right? When we do a new quadratic placement, there is some effect. You know, the gate on the top right is being pulled to a pad on the top right because that's where the real pad is. And the gates in the middle are being pulled to the rightward boundary because there are pads there that pretend to be like the gates that they are connected to only those pads aren't moving. So, this is what you get the resulting new quadratic placement problem for the gates in the left-hand region. And one of the reasons why this works so incredibly well is, remember the model of the wires as being like springs. If all of the pads are on the boundary of this new region, the gray region, and all of the wires are like springs, when we solve for the new gate locations, they're all going to stay inside the gray box. Because the springs between the wires between the gates pull the gates closer to each other, and the springs to the paths pull the gates close to the paths. But there is nothing that's going to pull the gate outside the box, right? So, by propagating the gates and paths outside the region to the boundary of the region, we get a quadratic placement problem that has the property that when we solve it, the gates will stay inside. And they will still respect the fact that the system stuff outside that's connecting to them and kind of pulling them to one part or another in the grey box. So, this is kind of the summary slide here. Why containment and propagation are so critical. On the left-hand side, the first point is you cannot ignore the gates outside the region that you're replacing. You want the gates inside the gray box on the left to feel some pull from the wires to the gates and pads outside the region. The pseudo-pads do this for us. So, there's all these blue wires, okay? there's all these blue wires here that are connected to things outside the gray region. The pseudo-pads pretend to be the gates ,and the paths that are not available to us to place anymore. So, the gates inside, they, they sort of go in the right place. And on the right-hand side, the pseudo-pads also guarantee containment, right? They guarantee that the gates locate inside the region. if you think of the pads as fixed things that the springs are connected to when the springs pull the gates toward the pads, they're never going to pull the gates outside the grey region. So, the pin propagation, pad propagation stuff does the right thing in terms of keeping a good global solution quality. It means you don't ignore the gates that are connected outside the gray region that you're replacing, and it means that containment is achieved. The gates stay inside the boxes as the boxes get smaller and smaller. So, this sounds maybe a little bit complicated. So obviously, the next thing is to do a little tiny example in a lot of detail. So, let's go do that next.