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.