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