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