0:08

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

5:25

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.