0:00

[SOUND].

So here were are in lecture 9.6. We're going to talk about a very

different kind of placement algorithm. We're going to talk about analytical

methods. So, all of the placement techniques that

we've talked about up 'til now in this lecture, have been based on some form of.

Random improvement, random exchange, random perturbation with some interesting

control parameters like for example simulated annealing.

Those are really good and powerful techniques but they really run out of

steam. They are not very efficient when you get

to let's say a half a million gates. And since people are really placing

things with a few million gates, you know, 10 million gates these days as a

kind of an atomic placement task maybe even more.

the annealing like methods don't really work very efficiently.

The analytical methods are based on a very different kind of an idea.

We're actually going to write an equation.

a mathematical equation and we're actually going to use calculus on it and

some interesting linear algebra and we're going to solve that equation,

numerically. And the solution of that equation is

going to be the placement of the gates. And if you're thinking wow, if I have a

million gates. Am I going to have an equation with,

like, 1 million x's and one million y's in it?

And you're telling me that I'm going to do calculus on it, and I'm going to solve

it? I'm going to tell you yes, that's

actually how modern placers really work. So let's start by talking about the sort

of the introductory background to analytical placement.

1:36

We're going to write an equation whose minimum is the placement.

Now you understand something about this because roughly speaking what the

iterative improvement simulated annealing style placers did was iteratively

minimize a wirelength function. Whose value is determined by the

locations of all the gates. But now we're going to write something

that looks more like a physics equation, a continuous valued equation, an

analytical equation, an equation that I can actually write down.

And we're going to solve for its minimum. So if you have a million gates you need a

million x y values. As a result one for each of your million

gates. We're going to formulate an appropriate

cost function for all of the gate level x y coordinates.

That function is going to be a function of ten, of 1 million x's and 1 million

y's, and then we're going to solve it analytically which means we're actually

going to do math on it. And we're going to get 10 mill 1 million

x's and 1 million y's. And that will be the minimum of this

function. And the resulting set of values give you

the placement of all million gates. And I recognize that this sounds kind of

crazy. but it works great.

And there's a trick. The trick is that you have to figure out

a way to write the wirelength in a mathematically friendly form that you can

optimize. And what's interesting is that this is

actually quite possible, and in fact there's several different ways of doing

it. All modern placers for big ASICs and big

Systems On Chip are analytical in this style.

So the big idea behind the class of analytical placers that we're going to

study in this lecture is something called the quadratic wirelength model.

And the idea is that it turns out that by optimizing this thing called the

quadratic wirelength instead of the half perimeter wirelength, it has the nice

friendly mathematical properties we need to be able to derive a solution.

So said differently, why do we pick the quadratic wirelength?

Because the mathematics works out in a way that we can solve.

So for a 2-point net, this is actually very simple.

3:47

This is the squared length of the distance between the points.

So I've got a little grid here, the same grid I have been showing previously.

X goes from 0 to 4, so there's five columns, Y goes from 0 to 5 so there's

six rows. Let's assume that the coordinates refer

to the center of the grid elements. So there's a gate at 1,4 labeled 1, and a

gate at 3,1 labelled 2. And this is a 2-point net as we know.

What is the length of this net? It's just the length of this hypotenuse

of this triangle, so I'm just going to sort of draw this kind of like a

triangle. it's just the length of the straight

line, the blue straight line between gate 1 and gate 2.

And that's nothing more than x1 minus x2 squared plus y1 minus y2 squared.

So that's actually, pretty straight forward.

And if we were to, you know, actually calculate that that's going to be 3 minus

1 squared plus 4 minus 1 squared, do that math and the length of this wire is 13.

So, this is straight forward. Note that there's no square roots here,

okay? This is the squared, I'm going to write

this as squared, squared length here, okay?

It's the squared length between those two gates.

So, It's not as mathematically friendly if

you take the square root. but perhaps more interestingly, is,

What happens if your net has more than two points in it?

That's not at all straightforward. So, here is now, a k-point net.

5:35

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.

11:35

And I'm just putting a little arrow to the pads.

There are two pads. There's a pad at 0,0.

It's the red square. And a pad at 1,0.5.

The pads are fixed pins. Those are the things, if you will, around

the edges of the chip. That are the IOs, the input outputs.

And so there are three wires. There's a wire from the pad at 0,0 to

gate 1, with weight 1. A wire from gate 1 to 2, with weights 2.

And a wire from gate 2 to pad 1, 0.5 with weight 4.

And I'm just making the weights up, so you can see what happens when we do the

math. And the math all turns out nice.

So, it's very easy to write the quadratic wirelength.

And that fact's one of the reasons we do it like this.

So, if we just look at the problem, the first thing we see is.

I'm going to look at the wirelength from gate 2 to the pad at 1, 0.5.

That's 4. The length of the weight on the wire

times x2 minus x1 squared plus Plus 4 times y 2 minus 0.5 squared.

Where are those constant? Well, the pad is fixed at 1,0.5 so you

know, we subtract 1 from x and square it. We subtract 1 0.5 from y and squared it.

And the fractional multiplier or in this case the weight multiplier, it's not a

fraction is a 4. The other wire that connects gates 1 and

2 has a weight too so you get 2 x2 minus x1 squared plus 2 y2 minus y1 squared.

The final wire has weight 1, and it connects to a pad, 1 times x1 minus 0

squared plus 1 times y1 minus 0 squared. That's the components of the quadratic

wire length. You add these all together, and that's

it. So it's really as simple as that.

Now there's one other thing I'll have you notice, and this turns out to be very

important. If you look at these terms, there are no

terms where there's an x variable multiplied by a y variable.