0:00

[SOUND].

So, here in Lecture 9.2, we're going to start talking about the real technical

part of ASIC placement. And to first order any placer for logic

gates optimizes things. And what it optimizes is an estimate of

the amount of wire it's going to take to connect all those gates.

That estimate is usually called the Wirelength, right?

And the reason we estimate it is because the actual physical act of connecting

those wires, which is called routing those wires, is computationally pretty

complicated. So, we actually have to build some

appropriate mathematical estimators that our optimization algorithms can use.

So, to start things off, talking about the technology of ASIC placers, we're

going to start with some classical forms of wirelength estimation.

So, let's go see how that works. The easiest way to talk about how a

placer works is to build, so let's build a very simple basic placer to start.

And so, we need to start with a simple model of the chip surface itself, and so

the simplest thing is to just use a grid. So, think of this as like a chessboard.

there is a set of slots, or cells that we can use.

And the gates, which are the cells from our standard-cell libraries can go in the

grid slots. And any gate can go in any slot.

You're allowed to put exactly one gate in each one of those slots, and it's okay if

the slots are empty. This is a very simple model of the gates

because it assumes that the gates are all exactly the same size.

And that is extremely unrealistic. But it dramatically simplifies things.

And so, we're just going to go with that in order to get started on, on looking

how we, how we deal with a real placer. So, a grid.

Every slot can hold exactly one gate or exactly zero gates.

It's not okay to put more than one gate in a slot.

All of the gates are the same size. So, we know what the representation is.

What are we trying to do? What does a placer do?

A placer optimizes the ability of the router to connect all the nets.

That's the first thing a placer does. But, the router, which is the tool that

actually puts the wires down and finds paths to make all the wires, you know,

possible. Routers are computationally expensive

things. You can't run one inside the placer.

I need a simplifying approximation. And so, what every real placer does, and

this is no exaggeration, what every real placer does is it minimizes an

appropriate mathematical model of the expected wirelength.

And, to be more precise about that, for each wire in the design, there is an

estimate, an approximation of the expected length of the routed wire.

And we add all of those expected lengths together, those estimated lengths

together for every single wire. So, we sum over all of the wires in the

design, the estimated length of the wire, we add them up and we minimize that.

That is what a placer does. A placer optimizes the estimated lengths

of the wires and solves for locations for the gates that minimize that estimated

wirelength. That's what a placer does.

And, you know, to first order, you could actually categorize the very many

different kinds of placers that there are by the mathematical model they choose to

use for the wirelength. Now, we need a little terminology so that

we can all talk about these things the way people who really do ASIC layout talk

about them. So, the first common term is that the

term for a wire in a layout is a net. So, we call them nets.

And the whole set of gates and wires together is called the netlist.

So, the thing that comes out of multi-level logic synthesis, and then

followed with technology mapping is a netlist.

The thing that goes into your placer is a netlist.

And nets are actually categorized by how many things it connects, and we tend to

call these points. So, I've got a nice simple little example

on the left. I've got a grid that goes from 0 to 4,

it's got five columns on the x direction and the y vertical direction, it goes

from 0 to 5. It's got, you've got six rows and I've

got a two-point net, so I've got a gate at x,y, 1,4, and I've got a gate at 3,1,

and I've got a little blue wire connecting them.

And so, it's really clear that this is a two-point net because there's two gates

that it's connecting. and if everything in every netlist looked

like this, we probably wouldn't be talking about this and we wouldn't be

giving it special terminology. But the problem is they don't look like

this. They also look like this.

So, on the right-hand side, I'm showing you a four-point net.

And so, again, the x grid goes from 0 to 4.

The y grid goes from 0 to 5. There's a gate at 1,4, there's also two

gates at 3,1 and 3,3, and another gate at 4,5.

This is a four-point net because there is a wire connecting four separate points.

This is, in some sense, why we don't just call it a wire.

Because there's a lot of wires that are going to get created to actually route

this thing and connect this thing all together.

And in answer to the first maybe obvious question, which is how is it the case

that there are actually things like wires that have more than two things that they

connect? the obvious answer is, there's fanout.

And I've even got it drawn with the gates sort of showing their directions as

though. There's a little AND gate at each one of

these grid cells, and the inputs appear to be coming from the left.

And the output appears to be going to the right.

And so, there's a gate in the 1,4 location in this grid that appears to be

driving the inputs to three other gates. The ones at 3,1, 3,3, and 4,5.

So, how is it possible to have things with more than two pins, two points?

The answer is fanout. And in modern[UNKNOWN] there are lots of

things that happen to connect to many things at the same time.

So some, some elements of scan chains and the testability components of logic you

know, there are things in the clocks that actually synchronize all the flip-flops.

There's some very, very high fanout nets. In fact, there are often special kinds of

routing technologies to connect those things.

So, it's not just like you can have K.net where K is 4 or 5, you can have K be

hundreds. So, about the wirelength estimation,

there are many, many different kinds of estimators.

And in fact different placers depend for their foundational methods to a large

degree on the kind of wirelength estimator that you pick.

So, why is it hard to estimate the length of wire that's going to be used to

connect the nets? And the answer is that multi-point nets

can be routed in many different paths. And in a dense layout, nets do not all

get routed in their shortest path. I mean, the inside of an ASIC and the

inside of a 20 million or 50 million gate ASIC, it's a very crowded place.

Even with lots of physical layers for wiring, it's a very crowded place.

Nets just don't get to go in at their minimum possible length.

So, a concrete example here. I've got the same diagram that I had on

the previous slide. a grid.

x goes from 0 to 4 on the bottom. y goes from 0 to 5 on the top.

There's a gate at 1,4. Gates at 3,1, 3,3, and 4,5.

And there's a very straight little wire connecting them.

You know, this is basically about the best I can do to wire this, this

particular design. I can't really probably do better than

this than this, this little example here. But in the middle, I'm showing something

that you know, it's a kind of a different looking wire.

Now does this have a little more wire? Yeah, this is, this is just a slightly

longer than the, you know, than the previous wire is just because of the way

things escape from the, from the topmost gate.

But, you know, this is still okay. I, I would even say maybe this is good.

You know, this is a particular, this is a good path.

You know, it's just a little bit worse than the previous path.

But now on the right-hand side, I'm showing an appallingly bad gate

wirelength. it's again, the same example you know, x

is you know, 0 to 4, and y is 0 to 5. but the, the wires are snarled all over

the place. They seem to go way out of their way to

connect things. And, and there's nothing else to say

other than, you know, this is pretty bad. And the reason this is pretty bad is

probably there's 20 million other wires that are trying to get routed, and this

one just didn't get able to be routed short.

And in real designs, that just happens. So, estimating what the length of the

wire is, is actually quite challenging. We have to estimate something that is a

reasonable model of what the wire might actually be.

And so, what we tend to do is, is estimate a best wirelength.

We tend to estimate the best and then we, we do some other techniques to sort of

deal with the fact that they're not always going to come out this good.

So, the most famous estimation for a wire is called the Half-Perimeter Wirelength,

and sometimes abbreviated HPWL. But it's also called the Bounding Box

Wirelength, usually BBOX, BBOX. And you'll see us using them

interchangeably in this lecture. The idea is pretty simple.

I'm going to describe it in words first. You put the smallest bounding box you can

around all the gates. So, let's assume in the little grid

things that I'm showing you. The gate lives in the center of the grid

slot. And the coordinates that are labeling x

equals 0, 1, 2, 3, 4 in the example I'm showing on the bottom left, y equals 0,

1, 2, 3, 4, 5. Let's assume the xy coordinates are the

center of the cell, the grid. And that the gate lives on that, that

coordinate. And so, what we do is we put the smallest

possible box around all of the gates. And then, we measure the width of the

box, delta x, and the height of the box, delta y, and we add them together, and

that's our wirelength estimate. So, for this little example where there's

a gate at 1,4 and a gate at 3,1, the first thing we do is we put a bounding

box. And so, the box goes from x equals 1 to 3

and y equals 1 to 4. And then, we simply we do the math.

Delta x is 3 minus 1, that's 2. Delta y is 4 minus 1, that's 3.

We add them together, 3 plus 2 is 5. The half-perimeter wirelength is 5.

And one of the great things about the half-perimeter wirelength is that it's

easy to do a multi-point net. So, here's a four-point net again on the

x equals 0 to 4, y equals 0 to 5 grid gates at 1,4, 3,3 3,1, 3,3, and 4,5.

We again put the smallest bounding box, and that goes from x equals 1 to 4 and y

equals 1 to 5. And then, we again, we can do the math.

Delta x is 4 minus 1, that's 3. Delta y is 5 minus 1, that's 4.

The half-perimeter wirelength estimate for this gate is 3 plus 4, is 7.

So, the great thing about the half-perimeter wirelength, it's easy and

it works for multi-point nets. So, more generally, the half-perimeter

wirelength, the general formula that I'm showing here is, you look at all of the

x-coordinates of all your gates, you take the max.

You look at all the x-coordinates of your gates and you take the min and you take

the max minus the min. Then, you look at all the y-coordinates

for your gates, you take the max. You look at all the y-coordinates for

gates, you take the min. You take the max minus the min, and

that's what you add together. The maximum, the x-coordinates for the

gates minus the min of the x-coordinates for the gates plus the max of the

y-coordinates for the gates minus the min of the y-coordinates for the gates,

that's the half-perimeter wirelength. One of the important things to note is

that this is always a lower bound on the real wirelength.

Which is to say, it is always less than or equal to the real wirelength no matter

how complex the final routed path is. You need at least this much wire.

And look, this just makes sense. You need to go from the gate on the far

left to the gate on the far right. That's delta x amount of wire from the

previous diagram. And you need to go from the bottom most

gate to the top most gate, and that's delta y amount of wire.

And no matter how you route this path, you need delta x plus delta y amount of

wire. So an important aside to note is that,

all of the wiring on big chips and most of the wiring on big printed circuit

boards is strictly horizontal and vertical.

There's no arbitrary angles for manufacturing reasons.

That's rigidly true for integrated circuits these days, big modern digital

SOC designs. there is some funny all angle wiring to,

to do things like get out of complicated pin arrangements underneath the big

chips. But once you escape from the pins near

the chip then you know, it already actually go across the board strictly

horizontal and strictly vertical. So that's just another reason the HPWL is

a good estimator because it just does a nice job of estimating the lower bound on

the amount of wire. No matter how many points you have, no

matter how many pins you have, no matter how many gates you have on your net.

this is just interesting, this is what the actual half-perimeter wirelength

estimation distribution looks like for a little design.

So this is old data. So this is 165,000 gate ASIC from the

late 1990s from Jens Vygen's group at Bond/g.

this is 181,000 net. So you know, call it about 200,000 nets.

I'm showing you this because it's just sort of an, an interesting piece of data.

the horizontal axis here shows a histogram buckets for the wirelength.

So, 0 to 0.5, 0.5 to 1, 1 to 1.5, 1.5 to 2, 2 to 2.5, 2.5 to 3, 3 to 3.5, etc., up

to 4, 4.5, 5, 6, 7, 8, 9, 10. And then, note at the end the buckets get

bigger, 10 to 15, 15 to 20. this is actually in millimeters, this is

a really old chip. So, it's one of the things to be aware of

is that this is a really old chip. so don't think about this as being

anything other than a a normalized number.

And note that the vertical scale is a log scale, right?

So, the vertical scale is a log scale. The vertical scale says, how many nets

have this length? So, you know, question.

How many nets are the shortest possible length between 0 and 0.5 in whatever

units are appropriate? And the answer is 100,000 of almost

200,000 nets. How many nets are between 0.5 and 1?

and the answer is, as far as I can tell, probably about 30 or 40,000.

Remember, this is a log scale, maybe 20,000.

the idea is that most nets are short, most nets are very short.

But unfortunately, there's a really long tail, and there are nets out here that

are you know, 40 times longer than the shortest net, and those nets are not zero

in number. So, real routers deal with the fact that

most of the nets are short but there's a non-trivial number of nets that are long.

And so, is just an interesting data that shows you that in a concrete way.

[MUSIC]