[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.