0:00

So here in 9.7 we're going to continue our discussion of analytical placement.

In the previous lecture, we talked about a different model, a different wirelength

model, the quadratic model where we take the wires and break them apart into what

amounts to two point springs. Characterized by their quadratic

Euclidean length, and we add up all those lengths and we can write an equation to

actually minimize it. So, in this lecture, we're going to show

how the quadratic wirelength model makes it possible to actually build an

analytical model of placement that we are actually going to be able to solve.

So let's talk about how we go from the quadratic wirelength model, an analytical

model of this problem, so a quadratic placer that creates a giant equation that

we can actually solve to create a kind of a placement that's going to create some

new kinds of problems that we're going to have to solve in the rest of this

lecture. So, let's go look at how this works.

So this is the same example that I showed at the end of the previous lecture.

An example in detail of the quadratic wirelength model.

So again two pads at 0,0 and 1,0.5. Two gates labeled 1 and 2.

A wire from the 0,0 pad to gate 1. A wire from gate 1 to gate 2.

A wire from gate 2 to pad 1,0.5, and the weights on those three wires, 1, 2 and 4

respectively going left to right, bottom to top in this little example.

And there are three quadratic wirelength terms.

4 x2 minus x1 squared plus 4 y2 minus 0.5 squared, 2 x2 minus x1 squared plus 2 y2

minus y1 squared, 1 x1 minus 0 squared plus 1 y1 minus 0 squared.

We add those things together and we get a quadratic wirelength, and again,

highlighting effect, there are no terms with an x multiplied by a y.

This is a very, and maybe, surprisingly important.

So what do I want to do? Okay?

After I add this thing together, I want to minimize it.

How do I do that? A very surprising answer.

Calculus, basic calculus. Remember, in basic calculus, we said what

is true about the extreme values of functions, the maximum of, of a function

or the minimum of a function, and the answer was it was where the derivative

was a 0. And if you took a first derivative and

set it to 0, you could find a max or a min, and if you look at the second

derivative, you could figure out if it was a max or a min.

It turns out for these wirelength things, when you solve for the derivative and

when you set it to 0, it's always a minimum.

There's no maximum and so it just does the right thing.

However, one of the things that may be a little bit complicated for you is that

there are multiple variables. This isn't just a function of one thing

like in x. Even more, perhaps frighteningly.

This is a function of maybe a million x's and a million y's.

So what do you do? You do partial derivatives, right?

You differentiate the wirelength with respect to each individual x and each

individual y. And you set the entire set of equations

to 0. And it turns out that when all of those

equations are 0 at the same time, that is a quadratic wirelength minimum.

Now, one of the things that's very important that I showed you on the

previous slide was that there are no terms that have x's and y's in them at

the same time. And so, it is perfectly okay to pull out

the x part of the wirelength and to the y part of the wirelength and deal with them

separately. And so I'm doing that here.

I have a curve line calling Q of X, which is the X part of the quadratic

wirelength, 4 times x2 minus 1 squared plus 2 times x2 minus x1 squared plus 1

times x1 minus 0 squared. And I've got a term that looks similar

called Q of Y, which is the Y part, 4 times y2 minus 0.5 squared plus 2 times

y2 minus 1 squared plus 1 times y1 minus 0 squared.

Structurally, those equations are almost exactly the same.

But the constants, okay? The things inside the parentheses are

different because the pads, the fixed pads around the edges of the chip, they

have different X and Y coordinates. So what do you do?

You differentiate. So let's take the x part of the

wirelength and differentiate with respect to x1.

So, let's look, 4 times x2 minus x1 squared, okay?

there's no x1's in that, so that's just a 0.

2 times x2 minus x1 squared, well, that's 2 times, 2 times the thing inside, times

the thing inside to the power of 1, times the derivative of the thing inside.

Remember, how do you differentiate, you know, u of x, with respect to dx?

It's, you know, you differentiate u and then you differentiate x, right?

So, it's 2 times x2 minus x1 times 2, because the 2 exponent comes down to the

power 1, and then the derivative of what's inside, which is as far as x1 is

concerned, a constant minus x1. So, 4 times x2 minus x1 minus 1.

Similarly, the 1 x1 minus 0 squared becomes 2 x1.

You get a linear equation 6 x1 minus 4 x2 is 0.

Similarly, if you different, differentiate with respect to x2, the 4

x2 minus 1 squared term becomes 8 x2 minus 1.

The 2 x2 minus x1 squared term becomes 4 x2 minus x1.

And the derivative of what's inside is 1. And the 1 x1 minus 0 squared term, well,

that's x1, it's a wrong variable, it's constant as far as x2 is concerned, you

get a 0. you get another linear equation, 4 minus

4 x1 plus 12 x2 minus 8 equals 0. And if you do it on the y side, same

thing. The, the derivative with respect to y1 is

0 plus 4 y2 minus y1 times negative 1 plus 2 y1.

Another linear equation, 6 y1 minus 4 y2 is zero.

Differentiate the y wirelength with respect to y2.

Well, the first term turns into 8 y2 minus 0.5.

The second one turns into 4 y2 minus y1. And the third term, it only has y1's in

it, it goes away, you get a 0. Another linear equation, negative 4 y1

plus 12 y2 minus 4 equals 0. So, hey, this is actually pretty

impressive. I started with something that seemed very

complicated, this quadratic wirelength thing, and I wrote a quadratic

wirelength. And I said, well, I'd like to minimize

it. And by minimizing it, I, I did calculus.

I set all the partial derivatives to 0 and I got linear equations.

That's gotta be good, and it is. Those are linear equations.

We know how to solve linear equations, we are very good at solving linear

equations. So again, this is just the Q of X

wirelength and the Q of Y wirelength. Restated, 4 x2 minus 1 squared 2 x2 minus

x1 squared 1 x1 minus 0 squared. For the Y term, 4 y2 minus 0.05 squared 2

y2 minus y1 squared 1 y1 minus 0 squared. What did we do?

We minimized them. We did calculus on them.

We took the partial derivatives with respect to every x for the term on the

left and every y in the term on the right and we got linear equations.

And if we were to write that in a form that you should be familiar with matrix

notation. What I get is a matrix times a vector

equals a constant. And so I get a 2 by 2 matrix, because

there's only two gates that are moving, and the matrix is 6, minus 4 in the first

row and minus 4, 12 in the second row times a vector x1, x2 equals a vector 0,

8 for the x side. And for the y side, 6, minus 4, minus 4,

12 for the matrix. The same matrix times a vector y1, y2

equals 0, 4, a different vector. You can solve that.

x1 is 0.571, x is 0.857. You can solve the y.

y is, y1 is 0.286, y2 is 0.429. And so, to summarize, what do you get?

You get two matrix equations. Ax equals bx, AY equals BY.

If you have N gates, the matrix is N by N.

So, yes, you do get a 1 million by 1 million system of linear equations.

If you have 1 million gates, the same matrix for the x and y solves, and

interestingly, you solve for the x's in one solve and independently you solve for

the y's, but you get different b vectors. So you solve Ax equals one thing to get

the xs, ay equals a different thing to get the ys.

The x, B, and y vectors all have N elements in them, so they are vectors

with a million things in them. This is very interesting.

9:30

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.

22:47

This is the A matrix. So the A matrix is off the diagonal, the

A matrix is just the negative of the c matrix.

So if I circle the term here, in the top row, the 10, you can see that it appears

negative here. But it also has a diagonal, which is the

sum of everything on the row of the c matrix plus the weight of any pad.

And so, I think an important thing to note is like, why is the 21 in that

matrix? and the answer is that I'm adding

together everything in the first row of the c matrix 0 plus 1 plus 10 plus 0 plus

0. But then, I'm also adding the weight of

the pad, of the wire that goes to the pad.

Because, remember what you do, the thing on the ith, Aii element of the diagonal?

You add up everything in the ith row of C.

And then you ask, hey, does this gate connect to a pad?

If so, what the weight? So, that's what you get.

And the bx and by vectors are created just like I said.

You ask if the gate in the ith position connects to a path in it, so for the x

vector, you take the weight and you multiply it by the coordinate.

And for the y vector, you take the weight and multiply by the coordinate.

And so, among other things, you see that the first element of x is a 0 because

gate 1 connects to a pad with an x of 0. And so, when you multiply 10 by 0, you

get a 0, but the by vector has a 10, because the y coordinate of the pad is a

one. 10 times one is 10.

Very simple, very mechanical recipe. And so what happens if you solve it?

This is what you get. So remember that I said, that the way to

think about this is that the layer are springs and they're pulling like elastic

bands, they're pulling the gates towards each other and toward the pads.

this looks like something you would get with springs, so you know, where are the

gates? Well, if you draw a straight line from

the upper left corner to the bottom right corner, gate 1 is way up in the upper

left corner, because it's got a wire with weight 10 on it.

That spring is pulling really hard to get gate 1 in the upper left-hand corner.

the wire between gate 1 and gate 3 also has a weight of 10, and so gate 3 is

right up there right close to gate 1 on that straight line.

Gate 2 is a little bit further down on that straight line from the left corner

to the left top corner to the bottom right corner.

Gate 4 is a little off. It's sort of more toward the center of

the chip, but it's pulled toward the top right, because there's a pad wire pulling

it to the top right. And gate 5 is pulled down a little bit,

because there's a wire pulling it, pulling it down a little bit.