0:00

[SOUND].

So, here in lecture 9.3, we're actually going to build a very simple placer.

So what you know is that, to first order, what a placer does is arrange the gates

on the surface of the chip. And try to optimize an estimate of the

wirelength, and one of the estimators we now know how to do is the half-perimeter

wirelength, or the bounding box wirelength.

How do actually arrange the gates to make this number small?

And an interesting idea is that we use randomness.

We randomly place the gates We randomly pick a couple of the gates.

We randomly exchange the gates. And we see if things got better, right?

And then we just continue that process and go forward.

It sound really simple minded. It actually works.

And it is the basis for some real interesting commercial sorts of placement

engines. So we're going to start by building a

simple Randomized iterative improvement placer.

So let's go see how that works. So the easiest way to show how a placer

is put together is to build one. And so we're just going to build the

world's simplest placer, because it illustrates a lot of the really core

ideas. And after we go from this very simple

foundation We'll add some sophistication. We'll add some, some more interesting and

useful ideas. So to start, how are we going to start

our placer? Well, there are really two big ideas and

this is an iterative improvement placer and so there's a, two important ideas.

The first is you start with a random placement.

You just randomly assign each gate to a grid location.

Only one gate per grid please. And if you're thinking to yourself, wow,

that has got to be just a terrible, terrible placement, because if I take all

of the gates and I just throw them at the surface of the chip and they land where

they may. And I take a step back and use my

Wirelength estimation techniques as I can estimate the half perimeter wirelength

for all of those nets and I can add that number up and I can get a measure of the

quality of this placement. This is probably a terrible placement and

the answer is, yes, it is. But it's a real placement, and it is a

complete placement. And that is essential because what we're

actually going to do Is iteratively improve it.

So the idea is as follows, I don't know how to just get, in one step, a good

placement. But I know how to get any placement.

It's a random placement. It's a bad placement.

And it's not that hard to improve a placement a little bit.

And the idea is that you pick a random pair of gates in the grid, And you

exchange their locations, that's really the key step.

You exchange their locations, and then you evaluate whether things got better.

So, what do you compute? You compute the change in the wire

length, you compute the new total half perimeter wire length, subtract the old

half perimeter wire length delta L. And delta L is an indication as to

whether the exchange of those 2 gates, the swap of those 2 gates.

Made the placement better, or made the placement work.

If delta L is less than 0, the new total wire length got smaller.

That's good. That's an improvement.

You just made the placement better. Keep it.

3:15

If delta L is bigger than zero, the new total wire length is bigger.

That's bad. You just made the placement worse.

Undo it. You just keep doing this for many many

random swaps. Literally millions and millions and

millions, maybe more, random swaps. How long do you do this?

Well, you can do this until the Quality of the placement stops improving until L

stops getting smaller, or if you have a CPU time limit, you know, you can do this

for an hour or you can do this for a day or you can do this for a weekend or you

can do this for a week. You can do this as long as you like.

But at some point, L is going to stop improving, the placement is done and you

look and you see how good it is. That sounds tremendously simple, and it

is, but it actually works. So, here's a high level Pseudo-code for

an, a random iterative improvement placement.

And it's just got a couple of parts, alright?

So, the first part, up at the top, says, random initial placement for each gate G

in the netlist place Gi in a random location in the grid, alright?

So that's just this, this initial placement.

You gotta get the random initial placement before you can improve it.

And then the next thing you have to do, is you have to calculate the initial wire

length. So L equals zero for each net N.

And the net list L equals L plus the HPWL, the half perimeter wire length

estimator for that net. You just gotta add up all the lengths of

the nets. And then there is an improvement loop.

Right, and the improvement loop just says, while the overall wire length L is

improving, pick a random gate GI, and random gate GJ, swap the gates, evaluate

the change in the wire length delta L. And then, there's just the two key parts

here. If delta L is less than 0, oh, I have

just improved the quality of my placement, because I swapped two gates

and the wire length got better, please keep that.

And so what you see here is it says if delta L is less than 0, L equals L plus

delta L. I update the wire length to res, to res,

to remember the fact that I, I improve things.

Else if delta L is greater than 0, I just made a worse placement, right?

And in that case, what you do is you undo the swap.

And you just keep doing this until the wire length is falling.

That sounds incredibly simple, but you know that works.

SO this is an Iterative Improvement Placer where we in a very long sequence

of very small steps, iteratively improve the placement.

And how do we do that iteration? Random.

Random gate swaps. Now, one thing that I have to mention is

that it is imperative that you try to calculate the delta L efficiently.

And what that means is that you have to calculate it incrementally.

And what that means is if you are taking two gates and exchanging them, it is

extremely inefficient and extremely stupid to go measure again the

half-perimeter wire length for all 10 million wires in your layout.

Look, you have two gates, and you exchange them.

They're probably connected to five other wires, ten other wires; y'know, depends

on what they are, 20 other wires, whatever.

Trust me; they're not connected to 10 million other wires.

Do not go back and reevaluate the half-perimeter wire length for all the

nets in the layout. Just evaluate the change on the nets that

could themselves change. That is said to be an incremental

evaluation. And so on the left I've got a little

picture. Again, my four by my five by six grid, x

goes from 0 to 4, y goes from 0 to 5. There's a gate in (1,4) There's a gate in

2,1. There's a gate in 3,3.

And there is a gate in 4,5. The top two gates, or the top two rows,

are black. The bottom two gates are red.

There's a net called Net I that connects the top three gates, two blacks and a

red. There's a blue net.

There's a net that's kind of purple called Net K that connects the topmost

gate and the bottommost gate. and then there is a Net J, that's orange,

that connects the bottommost gates. And the gate at three three is called

one, and the gate at two one is called two.

And what I want to do is Exchange them. I'm going to swap Gates 1 and 2.

And so, I'm going to swap the two red gates.

And when I swap them, now Gate 2 is on the top and Gate 1 is on the bottom.

So, there are still gates in 2 1 in the grid and 3 3 in the grid, but they're

different gates. And what we see is now Net i is now

longer. The blue net, the net that takes the top

two gates and now connects to the bottommost gate.

Net j, which connected the two red gates, has not changed, because it was just

connecting the gates that were swapped, and so there's still gates in the same

place. Its half-perimeter wire length isn't

changed. Net k appears to be much shorter, because

it used to connect the topmost gate and the bottommost gate.

And we swap the bottom-most gate to be somewhere in the middle of the layout.

Did the overall wire length go up as a result of this, or did it go down as a

result of this? I don't know, right.

I, I, you know, I don't, I don't know. I actually have to go calculate this.

8:30

Right, and I calculate this incrementally, and so incrementally means

that Delta l is the sum of the half perimeter wire lengths for nets I, J and

K after the swap. I add those things together and then I

subtract from that the sum of the half perimeter wire lengths of I, J and K

before the swap. And so you just have to arrange your data

structures, and you know, your, your internal organization of your code so

that you can do this easily. So you have 10,000,000 gates that you're

trying to work with, a 1,000,000 gates you're trying to work with, a 100,000

gates that you're trying to work with you take 2 of those gates and you swap their

locations. Do not go reevaluate the half perimeter

wire length estimator for another million or ten million nets, just evaluate it for

the ones that could have changed their length.

Which ones are those? Those are the ones connected to the

things that you've moved. It sounds simple but it's a really

important concept. So, how does that work?

It works okay... And if I sound less than enthusiastic,

it's because okay is the best thing I can say.

This is not a good placement. And I'm going to show you techniques that

give you dramatically better placements. But this is the right Starting point.

This is sort of the historical origins of placement.

You want to talk about how people were doing placement in the 1970's?

This is how. So, this is a small benchmark.

It's about 2500 gates and 5000 pins. It's being placed in a 50 by 50 grid.

The graph shows progress. So the horizontal axis goes from zero to

ten e6, which means ten million swaps. And it's labeled zero, two million, four

million, six million, and eight million. The vertical axis is the sum of the half

perimeter wire lengths. Right?

So that's actually the thing we're optimizing.

And there's a, basically a blue curve that's has a nice sort of exponential

kind of fall-off. It starts up around oh, call it 42,000,

and it falls off to something that looks to be maybe 26,000 or 27,000 in the total

wire length. So you know, that's a pretty significant

improvement. And you can just see that it sort of, you

know, it falls really fast at the start because you started with a bad random

placement. And everything you do is useful.

And then, you know, once you start to go out there, honestly, most of the swaps

you try are unsuccessful because they make the placement worse.

So it takes longer and longer to find something that actually improves things,

and the rate at which the improvement happens is falling off pretty

dramatically. So this particular swap particular design

actually ran you know, something like you know, about eight million swaps to

actually get this result, and this is okay.

This is not great, trust me, this is not great, but this is okay.

11:17

So what can I say about random iterative improvement placement?

Well the first is that it's easy to understand and it's easy to implement.

and you know, that code that I actually showed.

that example is actually a place where I wrote, gosh, 25 years ago.

and that one of my enterprising TA's tweaked a little bit to to get this

graph. So, big idea, you start with a random

placement, you randomly improve it. You can optimize what we care about,

which is the total estimated wire-length. The sum over all the nets of the

half-perimeter wire length. Please remember to do this incrementally,

don't be stupid. the wire length will improve, it will

sometimes improve a lot. But the still, the overall result is just

not very good. Compared to what we know how to do today,

not very good. We can do better.

We can do really a lot better. So let's go talk about adding some

Interesting sophistication to this, to get a much better answer for a

placement[SOUND].