0:00

[SOUND].

So here in lecture 9.8, we're going to continue our exploration of Analytical

Placement. The really amazing thing about the

quadratic wire length model is that I can write a giant equation for where the

logic gates go. And I can solve it using some calculus

and some linear algebra, and actually get as the solution to this equation, done

numerically, a placement. That's pretty amazing.

The problem is that because we made some key assumptions, and one of those

assumptions is that the gates are dimensionless points, we don't actually

get a legal placement. So, unlike the intricate methods where we

had a grid and every gate was located in one and only one cell on the grid, when

we're done with a quadratic style analytical placement, the gates can be in

one big blob in on little corner of the chip.

We're going to have to do something, a different kind of an optimization step to

kind of spread them out. And interestingly enough, we're going to

do something that's kind of recursive. We're going to chop the chip up into

pieces. We're going to figure out which piece the

gates need to go in. And we're going to formulate an

increasing series of smaller quadratic placement problems, each of which is

going to, sort of in a finer, and finer, and finer way.

Put the gates in the right place. So, this is recursive partitioning using

a quadratic style analytical placer model.

Let's go see how that works. We just introduced the full, sort of

mathematical model and solution technique for representing wire length as quadratic

clique wire-length model. pretending all the gates are

dimensionless points, optimizing the quadratic wire-length, which turns into a

set of matrix solutions. An a matrix and a bx vector, an a matrix

and a by vector, and we solve that and we get x-coordinates and y-coordinates.

What does it look like? It looks like this.

This is a small IBM ASIC a reasonably famous public benchmark with a few

thousand gates. And you immediately see the problem.

This doesn't look like a placement at all.

this is this big smear of gates right in the middle of the chip, and this little

sprinkling of gates in other places. this is a big problem, a new problem an

interesting problem, maybe an unexpected problem.

The quadratic wire-length model minimizes the wire-length for netlists in a

numerical way, but it totally ignores the fact that the gates have a physical size

and they can't be on top of each other. There is, and this is the beautiful thing

about the quadratic wire-length model. There is one solution that minimizes the

sum of the quadratic wire-lengths. And when you solve it, you get what you

get. And you don't necessarily get the gates

lining up in rows not on top of each other.

I've got to fix this. And it turns out there's a lovely

strategy for doing this which we can call Recursive Partitioning.

Lots and lots of recursive stuff in this class.

The recursion is a little more conceptual, it's not like the Shannon

co-factoring stuff, but you'll get the idea when we show you some pictures of

the geometry. This is a bigger industrial example.

I'm showing you this for a couple of reasons.

One, just because it looks cool. This is something that was done by one of

my students, Joan Shue. This benchmark is also from IBM.

This has about 211,000 gates, they are in blue, and about 543 fixed blocks.

Those are the red things. You imagine some designer has simply put

them down in the right places where they want to go.

And the image shows where the gates want to go if we modeled the blocks like big

pads, if you think that. and this is a quadratic placement where

we model all of the wires as two-point quadratic connections with appropriate

fractional weights. And we solve the placement problem so

there are pads around the outside, I'm just going to circle some pads.

Those are all pads, all those little skinny boxes around the outside are pads.

all of the 500 red boxes are either SRAMS or pads.

That's all the stuff in red. and the blue smear is the result of the 2

ax equals bx, ay equals by solved. So, why am I showing you this?

this is an example of how badly imbalanced the quadratic placement can

be. It can be terribly, terribly unphysical.

So look, almost all the gates want to go up in the top left.

That just says there's a lot of pads up there, and there's a lot of big dense

wiring groups that go from the SRAMS and the top left to all of the gates that

want to be there, but they can't go there.

So, we're going to have to do something really smart to make the gates go into

more physical, reasonable, realizable places.

So, the big idea is this recursive partitioning.

So, you do a first quadratic place, and I'm going to start calling quadratic

places QPs, because it takes less space on my slides.

And I'm going to write QP a lot. You do the first quadratic place and you

get some weird blob of gates that minimizes the quadratic wire-length.

Then, what you do is you partition the chip right in half.

And so, I'm just going to draw a big line over here.

You partition the chip in half, and you make a decision.

Some of the gates are going to go on the left, some of the gates are going to go

on the right. You formulate two new smaller quadratic

placement problems where you say, the gates on the left must stay on the left

and the gates on the right must stay on the right.

And so, I'll solve two new quadratic placement problems that are each about

half the size of the first one. And then, why this is recursive?

I will repeat. I will again partition things.

But I will partition the region on the left by drawing a line to the left and

the right. And I will partition the region on the

right. Similarly, by drawing a slice to the left

and the right, and I will say that the gates on the top on the left have to go

on the top, and the gates on the bottom on the left have to go on the bottom.

And so, I now get four regions, each with about 1 4th of the total gates..

I will solve four new smaller quadratic placement problems, and I'll see where

they go. And I will just continue to do this until

I get a placement that looks a little bit more like a real physical placement.

So, the one on the right I'm showing you here, and this is a real one, by the way.

This is the result after 16 QP solves. And you can just keep going until the

number of gates in each of these little cells, these little grid squares, is

something manageable. So, here's a high level recipe for how

recursive partitioning is going to work. These are the big steps.

There's the partitioning step itself. How do you divide the chip into new

smaller placement tasks on which we can run a smaller quadratic placement?

7:13

The assignment task says, which gates should go into each new smaller region?

So, we run quadratic placement on a region, then we partition the region into

two smaller parts, and we assign gates to each of the two parts.

Which gates go where? And there's the containment problem.

How do you actually formulate the new quadratic placement matrix solve so the

gates stay inside the new regions, but inside the new regions they go in good

places. Because one of the problems is that,

there are gates inside the region. The new region, the smaller region, that

are connected to wires that go outside the region.

How do we, how do we model that sort of connection from the inside of a smaller

problem to the outside? That's the containment problem.

And I'm going to talk about one early strategy from a classical paper.

So, this is a paper from Ren Song Tsay, Ernie Kuh and Chi Ping Hsu called PROUD:

A Sea-Of-Gates Placement Algorithm way back from December 1988.

This is one of the first generation of analytical sort of placers, one of the

first generation of quadratic placers. By modern standards, this is a very, very

simple kind of a placer. Modern, modern placers are very much more

complicated. The thing I like about the PROUD

Algorithm, it's really easy to explain how it works.

If you know how to do the basic quadratic placement mathematics it's not too hard

to explain the partition step, the assignment step, and the containment

step. They're all sort of fairly simple

geometrically. It's a quite elegant solution, it's

something you can actually, I think, get your head around.

So, so let's talk about this. How does this recursive partitioning

stuff work? Well, the, the first problem is, how do

we actually do the partitioning? And the solution is that, after the first

quadratic placement, we're going to divide the chip area exactly in half.

And for us, we're just going to pick vertically as the way to divide it.

Now note, this is completely arbitrary. You could divide it horizontally.

But for us, it doesn't matter. We're just going to do a vertical

division, and we want half of the gates on each side, right?

So, we're going to slice it and we want half of the gates to be on the left-hand,

and we want half of the gates to be on the right-hand side.

And the question is, how do we make that happen?

And why that could be a challenge is, and I'm showing you a little tiny picture of

the IBM ASIC again. What if the quadratic placement does not

spread the gates evenly between the halves?

And so, I'm showing you my little cartoon of a chip that's a square with some pads

around the edges, and there's, you know, about a dozen gates here.

And they're all kind of smeared in the blob on the left.

How do we know which gates to put on the left versus which gates to put on the

right if this thing that I'm showing you is the initial quadratic placement, or

set differently the quadratic placement is telling you they all want to go on the

left? What the heck am I going to do?

Well, that's just not acceptable, right? I have to do something that puts the

gates in a sensible set of locations. So, what I'm going to do again[SOUND] is

I'm going to partition the region that I'm placing exactly in the center.

And I'm going to reformulate a new quadratic placement for the gates on each

side. So my new problem is, how do I pick which

are the right gates? This is the assignment problem.

10:57

And so, the answer is that even if all of the gates are smeared in a clump way over

on the left, when you sort it on x and then on y, you take the first N/2 gates

in the sorted list, those are the ones that go on the left.

All right, so that's those guys. Those guys go on the left, and all of the

others go on the right. And you have now taken the initial

quadratic placement and use the results of that placement, the x and

y-coordinates, to do the assignment problem.

Which gates go on the left? Answer, the half of them that are the

most on the left. It sounds simple but, you know, it's what

works. The leftmost half of the gates go on the

left, the rightmost half of the gates go on the right.

Now, we've got this thing that I'm, I'm calling the containment problem.

So, you've now decided which gates go on the left.

And so, I'm, I'm drawing the left part of the chip as a grey box.

And I'm saying, let's focus on the gates inside this shaded region, R, on the

left-hand side of the cut. I need to formulate a new quadratic

placement problem to properly locate those gates in a region that's now the

same height as the original QP problem, but half the width.

12:17

And the new problem is, I want to solve a quadratic placement problem and I want

all the gates to stay there on the left hand side.

And I've really got two things that I've got to worry about.

The first is, how do I keep the gates on the left-hand side on the left-hand side?

How do I keep them in the gray box? And the second part is, how do I model

the wires that connect from those gates on the left-hand side to the gates and

pads on the right-hand side because, you know, I cannot ignore those things?

You know, the reason that the quadratic placement problem is you know, is so

attractive and why people like this method is that it optimizes the lengths

of all the wires. If in the partitioning problem we ignore

the fact that there are, say a whole bunch of wires that connect the gates

that are not on the left-hand side, we're going to put those gates in the wrong

place. You know, the gates that are heavily

connected to the gates on the right-hand side, they probably be want to be on the

right-hand side of the grey box. I can't just take all those wires and

make them vanish, I have to do something with those.

So again, there's a geometrically very attractive solution, and it's got a funny

name. we're going to do something called

Pseudo-pads. These are also called Pseudo-pins,

sometimes. The basic idea is that every gate and pad

not inside region R is modeled as a pad on the boundary of R.

And the word that we use is propagate. We propagate these outside gates, or

outside pads, using their current xy location to the nearest point on R, which

is the grey box. And so, for this simple first cut we just

take the y-coordinate and we put the pad on the center line, so that's the, that's

the center line. So, you know, what actually happens here,

right? Is that anything that the gate was

connected to in R, that's connected on the right-hand side.

So, imagine that there are a couple of gates which are the red circles, and a

pad which is the red square. We take those things and we just slide

them leftward and we pretend that they really live on the cut line, on the star.

And so, we are not ignoring them. We're sort of doing the right thing.

We are putting them in the right position on the boundary of region R so that when

we replace all of these gates, right? When we do a new quadratic placement,

there is some effect. You know, the gate on the top right is

being pulled to a pad on the top right because that's where the real pad is.

And the gates in the middle are being pulled to the rightward boundary because

there are pads there that pretend to be like the gates that they are connected to

only those pads aren't moving. So, this is what you get the resulting

new quadratic placement problem for the gates in the left-hand region.

And one of the reasons why this works so incredibly well is, remember the model of

the wires as being like springs. If all of the pads are on the boundary of

this new region, the gray region, and all of the wires are like springs, when we

solve for the new gate locations, they're all going to stay inside the gray box.

Because the springs between the wires between the gates pull the gates closer

to each other, and the springs to the paths pull the gates close to the paths.

But there is nothing that's going to pull the gate outside the box, right?

So, by propagating the gates and paths outside the region to the boundary of the

region, we get a quadratic placement problem that has the property that when

we solve it, the gates will stay inside. And they will still respect the fact that

the system stuff outside that's connecting to them and kind of pulling

them to one part or another in the grey box.

So, this is kind of the summary slide here.

Why containment and propagation are so critical.

On the left-hand side, the first point is you cannot ignore the gates outside the

region that you're replacing. You want the gates inside the gray box on

the left to feel some pull from the wires to the gates and pads outside the region.

The pseudo-pads do this for us. So, there's all these blue wires, okay?

there's all these blue wires here that are connected to things outside the gray

region. The pseudo-pads pretend to be the gates

,and the paths that are not available to us to place anymore.

So, the gates inside, they, they sort of go in the right place.

And on the right-hand side, the pseudo-pads also guarantee containment,

right? They guarantee that the gates locate

inside the region. if you think of the pads as fixed things

that the springs are connected to when the springs pull the gates toward the

pads, they're never going to pull the gates outside the grey region.

So, the pin propagation, pad propagation stuff does the right thing in terms of

keeping a good global solution quality. It means you don't ignore the gates that

are connected outside the gray region that you're replacing, and it means that

containment is achieved. The gates stay inside the boxes as the

boxes get smaller and smaller. So, this sounds maybe a little bit

complicated. So obviously, the next thing is to do a

little tiny example in a lot of detail. So, let's go do that next.