So here is the placement result if I actually just draw it for you.
So I'm showing you a picture of the unplaced layout again.
on the left, you know, padded 0, 0 and 1,0.5 two gates 1 and 2.
the 0, 0 pad goes to gate 1. Gate 1 goes to gate 2.
Gate 2 goes to the pad. Right?
And where does everything go? And the answer is, unsurprisingly, all
the gates go on a straight line between the 0, 0 pad on the left and the 1, 0.5
pad on the right. And I'm just showing you 1, 1, and so you
see the chip corner up at the top. They're all on a straight line, but,
they're not uniformly spaced. So it's not each sort of 1 3rd of that
wirelength. And the reasons are one, that it's well
the big reason is that they do not have uniform weights.
The weight on wire 2 was a 4. That's big.
Okay. The weight on the gate, the weight on the
wire from gate 2 to the pad is 4, and what happens is that makes the wire very
short. And the weight on the wire from gate 1 to
2 is a 2, the gate, the weight on the wire from gate 1 to the pad at 0, 0 is 1.
What actually happens is that you see this very significant shortening of the
wire with the big weight on it, that's actually pretty cool.
So the placement makes a visual sense. All the points are on a straight line
between the pads. And the analog of what's happening here
is that, is that in this model, each two point wire is like a spring, okay?
Or like a rubber band, or an elastic band or whatever you want to think of as a
stretchy thing that resists being stretched and pulls things in a straight
Y. And what this placement does is it
minimizes the lengths of all of the springs.
And so, if you think that there's a spring from the 0, 0 path to gate 1 to
spring from gate 1 to gate 2 and a spring from gate 2 to the pattern that the
spring that goes to the right path is four times as strong as the spring that
goes to the left path. You get this answer, it all makes sense.
So you put a bigger weight on a wire, you can get a shorter wire.
That gives us lots of control over the placement, that's actually a really
wonderful thing. And the other thing that's nice is that
you get the same matrix, but different right-hand side b vectors.
Why? Because the pads have different x and y
co-ordinates. So, you only get one matrix that you have
to deal with. You just get two different right-hand
side vectors. Now, it turns out that building the
matrix A, and building the bx and by vectors is actually really easy.
There's a really simple recipe. So let's start with a very simple net
list here. It's a new net list.
Okay and so, there are three placable gates 1, 2, 3 and a pad called P.
and there's a weight of 5 on the wire between the pad and gate 1, a weight of 1
on the wire between gate 1 and gate 2, and a weight of 4 on the wire between
gate 2 and gate 3. So the first thing you do is you build an
auxiliary matrix which is called the connectivity matrix.
That's also end by end so in this case it's 3 by 3, and I'm just going to write
one, two, three for the columns. And one, two, three for the rows, so
we're sort of clear on that. And it's very simple.
If a gate, i, has a two point wire to gate j, and the weight on that wire is w,
then you go to the ith row in the jth column.
And also the jth row in the ith column, and you put a one in it.
it's as simple as that. Otherwise the matrix has a 0 in it.
And so, for example the 4 on this wire from 2 to 3, okay, goes into the third
row and the second column, and also the second row and the third column, right?
And one of the things to note, right, which is a little bit strange, right, I'm
going to put a kind of a question mark over here, is hey, shouldn't there be a 5
in here somewhere, because this pad thing's got a great big heavily weighted
wire, and the answer is, the C matrix ignores the pads.
There's a special step that happens to sort of put the pads back into this
problem. So this is the connectivity matrix.
It just tells you what gates want to connect to, what other gates, and how
much. It is a symmetric matrix as you can see,
c[i,j] is c[j,i]. Now, how do you build the A matrix?
This is a thing you actually have to solve.
Two, sort of three-step recipe, so the first thing is elements a[i,j] that are
not on the diagonal. All right, it would be a little clearer
here, that, that's the diagonal. Elements that are not on the diagonal are
just the negative of the c[i,j] value. So, concrete example.
There is a 4 over here. 4 is not on the diagonal, so there is a
negative 4 over here. Alright?
So that's how you get all the stuff not on the diagonal.
Elements on the diagonal are the formula shown here.
a[i,j], okay, on the diagonal, right? is, what, which is actually, I guess, we
could be a little clearer about that, a[i,i].
elements on the diagonal are the sum from j equals 1 to n of c[i,j] plus the weight
of any pad wire. It's probably easier to say that in
English. Add up the ith row of this connectivity
matrix, and then, add in the weight of a pad.
So, for example, why is this a 6, right, for a sub 1ne.
And the answer is because when we look at gate 1, we see that there is a pad wire
with a 5, and then we add up all of the other wires connected.
We add up the row, right. The plus sign, right, when we add all
that stuff up, we have a 5 plus the row is a 1, we get a 6.
That's why there's a 6 there. And similarly, why is there a 5 for the
second element, and the answer is, if you add up everything in this row, of 4 plus
1, and there's no pad wire for either for gate number 2, because that's the row
associated with gate number 2. There's no pad for that guy.
You get a 4 plus 1, you get a 5, so that's why you get a 5.
So, pretty simple recipe. Things not on the diagonal minus c[i,j].
Things on the diagonal, add up all the weights of the row, and then go ask does
this gate, the one associated with this row is it connected to a pad?
Yes, add that number in too. That's it.
Now, how do I get the b vectors? Also very simple, so I've got a very
simple cartoon here of a gate called i, connected to a pad at location xi, yi
with a weight wi on the wire. And it's really very simple.
for the bx vector, if gate i connects to a pad at xi, yi with a wire with weight
wi, then set the ith element of the vector to the weight times the x
coordinate. And similarly for the y vector, you set
the ith element of the by vector to the weight times the y coordinate.
So, it's really just the things I'm circling here.
You want to know what the ith element of the b vector is for x?
Ask if gate i connects to a pad, if so, multiply the weight by the x.
want to know the ith element of the y vector?
Ask if the i gate connects to a pad, if so, take the weight and multiply it by
the y. It's as simple as that, that's it.
So now, we have another question. are these difficult to do in practice?
Because, you know, look, if I have 1 million gates to place, I can clearly
write the [COUGH], you know, the quadratic expression.
and, you know, I can sort of evaluate what the wirelength is without any great
difficulty. And I can use the recipe to go from the
net list of the 2 point wires. And remember, I take the net list and I
turn it into a bunch of two point wires with appropriate weights.
I can take the net list of wires and gates and pads, and I can build the A
matrix and I can build the b vectors. And the A matrix is going to have a
million by a million elements and a million b's, and b's for x, and a million
b's for y. How do I solve that?
And the thing that's really quite amazing is these are very easy to solve, even
when they're very large. the A matrix has a special form.
It's sparse, which is to say, it's almost entirely made out of 0s, because, if you
ask a gate what else it's connected to, the answer is, you know, a couple things.
So that row has a million elements in it, but that row which represents gate i, you
know, there's only five or ten or 20 other things in that row that are not 0.
So that's what sparse means. It's also symmetric.
The element above the diagonal is the same as the element below the diagonal.
It is diagonally dominant, which is to say, the element on the diagonal is at
least as big as the sum of everything else in the row.
Mathematically, there's a name for this. these matrices are called positive
semidefinite and these are very simple to solve.
And what's interesting is we don't use something you probably know, we don't
use, like Gaussian elimination. We don't physically build the inverse for
the matrix, so I'm just going to write A to the minus 1 over here.