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.