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. 
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. 
A to the minus 1, and then I'm going to 
put a big cross through it, because I 
don't even want you to think about that. 
We do not invert the matrix. 
Maybe I should draw it in a different 
way. 
A to the minus 1 with a big like slash 
through it. 
We don't invert the matrix. 
We use iterative, approximate solvers. 
This means the solver converges gradually 
to the right answer. 
It also means the answers can be a little 
bit off, right? 
So they can be just, just, you know, a 
little, teeny, tiny. 
You know, if you're expecting the answer 
to come out to be 7. 
You know, it might come about to be 
6.99999999996 or 7.00000000002. 
This is the way it works. 
but it's possible to solve even these 
gigantic equations very efficiently, very 
reliably very robustly. 
So what is the real one of these examples 
look like? 
So, so here is a little example, it's got 
four pads and a little bigger five gate 
net list. 
So, there's a grid a chip image that 
again goes from 0, 0 to 1, 1. 
X on the horizontal axis. 
Y on the vertical axis. 
There are four pads at 0, 1, the top left 
corner. 
1, 1, the top right corner. 
1, 0, the bottom right corner. 
And 0.50 the middle of the bottom. 
And there are five gates labeled 1, 2, 3, 
4, 5. 
Gate 1 connects to the pad at the top 
left and to gates 2 and 3. 
Gate 2 connects to gate 1, gate 3, and 
gate 5, and gate 4. 
Gate 3 connects to gate 1, gate 2 gate 4, 
and also the pad at 1, 0. 
Gate 4 connects to the pad at 1, 1 and 
also gates 2, 3, and 5. 
And gate 5 connects to gates 2 and 4 and 
also the pad at 0.5, 0. 
All of the wire weights are 1, except the 
two that are highlighted by sort of fat 
lines in the picture. 
There's a weight of 10 on the wire from 
gate 1 to the top left pad, and a weight 
of 10 on the wire from gate 1 to gate 3. 
And that just makes it interesting. 
So, the first thing I do is I build the 
connectivity matrix. 
And the connectivity matrix is a matrix 
that has 5 rows and 5 columns. 
And it just says, what's the weight on 
the wire between gate i and gate j? 
And so, there's a lot of 0s in the 
matrix. 
Because, there's a lot of things that 
don't have wires connecting them. 
But the first row is 0 1 10 0 0. 
The second row is 1 0 1 1 1. 
The third row is 10 1 0 1 0. 
The fourth row, 0 1 1 0 1. 
The fifth row, 0 1 0 1 0. 
Okay? 
So that makes sense. 
There're some 10s in there. 
Why are there some 10s in there? 
There's some 10s in there, because gate 1 
connected to gate 3 has a weight of 10. 
So, the 3, 1 element and the 1, 3 element 
in that matrix have 10s. 
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. 
It, it all just works out. 
if you like the physics of the problem, 
makes for a sort of an interesting sort 
of intuitive kind of a problem. 
The other thing that's kind of nice about 
this, that, that, that you might not 
think of, if you really think of the pads 
is being just these like fixed objects 
and you really think of the wires as 
springs. 
When you let the gates go, they're all 
going to be inside, in-between the pads. 
The gates as a result of this linear 
assault, they're never going to be 
outside the surface of the chip, because 
the springs are going to pull them to be 
in-between the pads. 
That's actually a very nice and very 
useful feature. 
So, this is what a quadratic placement 
looks like. 
And life would be great if we were done. 
If you could set set up this beautiful 
set of big matrix solves and just solve 
it and be done. 
Unfortunately, we're not. 
There's a new problem, and we're going to 
talk about that next. 
[SOUND].