K, in this particular case, is 4. So, I again have the grid, x goes from 0

to 4, y goes from 0 to 5. And there are four gates, gate 1 is at

1,4, gate 2 is at 3,1, gate 3 is at 3,3, and gate 4 is at 4,5.

And I've got a wire drawn here that's kind of the way a physical wire might get

routed. But it's not at all clear what quadratic

wirelength means here. And so, here's the recipe.

The first thing you do is you replace the one real net with k times k minus 1 over

2, 2-point nets. And the way to think of that is I'm just

going to add a new net between every pair of points, and that's how many points,

pairs of points there are. Right.

So this has a name that's called a fully-connected clique model.

this is pronounced cleeek clique model. And so, the way this one would work is,

I'm showing again the, the grid without any wires in it on the right here.

Gates at 1,4, 3,1, 3,3, and 4,5. And what I'm just showing is that.

If k is equal to 4, then 4 times 4 minus 1 over 2 is 6.

So what's going to happen is there's one 2-point wire, two 2-point wires, three

2-points wires, four 2-point wires, five 2-point wires, six 2-point wires.

I'm just drawing every wire in k times k minus 1 over 2 for k is 4, 4 times 3 over

2. There's six 2-point nets that we're going

to connect. So that's what you do.

You take the one multi point net when k is greater than 2, and you turn it into k

times k minus 1 over 2, 2-point nets. It has a name.

Sometimes it's called fully connected because obviously ever pair of gates has

a wire connecting it. More commonly it's called a clique.

So, here's that same example. I'm showing the clique model again the

grid, x goes from 0 to 4, y goes from 0 to 5, gates at 1,4, 3,1, 3,3, and 4,5,

and I'm showing all six 2-point nets. The other thing you gotta do is that you

have to wait, which is to say, multiply the length of each of these quadratic

wirelengths by a number. So let's just think about it.

You know, I used to have one physical net.

And I replace this one physical net with six nets.

And I'm going to measure the quadratic wirelength of each of those six nets.

It makes some sense that I need to multiply by some small number.

So that I don't dramatically over estimate how much wire this physical net

needs. And so the, there are lots of ways that

people do this, but the traditional weighting factor is 1 divided by k minus

1. So, in this particular example.

If we were to estimate the wire length. There would be six quadratic wirelengths,

which are squares of differences of coordinates.

And each one of them is multiplied, in this case, by 1 over 4 minus 1, which is

1 3rd. So this is 1 3rd times 4 minus 1 squared

plus 5 minus 4 squared. Plus 1 3rd times 4 minus 3 squared plus 5

minus 1 squared. 1 3rd 3 minus 1 squared plus 4 minus 1

squared. 1 3rd 3 minus 1 squared plus 4 minus 3

squared. 1 3rd 4 minus 3 squared plus 5 minus 3

squared. 1 3rd 3 minus 3 squared plus 3 minus 1

squared. Six 2-point quadratic wirelengths, each

multiplied by this weighting, that sort of reduces their estimated length.

Now the other thing I'll notice here is that when k equals 2, this weight is just

1 divided by 2 minus 1, which is 1, so there's no special treatment for the two

point case, right? So it all works out.

You always multiply by the weighting factor 1 over k minus 1 and when it's a

2-point net, nothing special happens. You just multiply it by 1.

So, there's one more big idea here, kind of an interesting idea.

To make the math work out easily, we're going to ignore the physical size of all

the gates. we're going to pretend the gates are

dimensionless points. Now previously in the iterative

improvement placer we also sort of ignored their size.

We pretended they were all the same size. But it's not like we actually said that

they had no size at all. We just assumed they were as big as the

square on the grid. We are now going to honestly pretend that

they don't have any size at all. They're dimensionless.

And the big thing is we're going to ignore the fact that the gates can't go

on top of each other. And as we shall shortly see the technique

we're about to develop puts lots of gates on top of each other.

It's going to be the second part of our algorithm is how we fix that.

This sounds strange but it allows us to write a very simple, very elegant

equation for the placement, and then to solve it quickly and effectively.

So why do we do these interesting mathematical tricks?

Why do we model the wirelength as a bunch of fractionally weighted 2-point

quadratic forms? And the answer is, because the math makes

it possible for us to solve. So the easiest way to see this is with a

little example. So I've got a little example here.

So I'm modeling the chip as box. X goes from 0 to 1, and y goes from 0 to

1. This is totally arbitrary, by the way.

this could go 0 to 1. It could go from 0 to 100.

It could be in microns. Doesn't matter.

The, the, the math will work out. And there are two gate points, they have

indexes 1 and 2, they are the green circles with one and two next to them.

And there are three nets, they're each two points to just keep things small and

simple and they have weights 1, 2 and 4 respectively, and there are two pads.