0:07

So here in lecture 11.5, we're going to look at non uniform grid costs.

So, this is another feature addition to the basic maze router method, but maybe a

little subtle one. one of the things that's been true in all

of the grids that I've shown you so far, is that the cost of traversing one single

cell was always 1. is that a requirement, is that a, a, a

critical foundational part of the major router method?

No, I'm free to put any cost value in any cell I like why would I do that?

And what's interesting is that I can actually see that the routing edge with

costs and drive the shapes, the geometry of the nets to do things that I like.

I could put high cost values in a region of the grid representing some part of the

trip that I would prefer the nets. As they are routed, avoid.

I could put low-cost values in other parts of the grid representing the chip's

surface, and preferentially sort of drive the nets to use those low-cost regions.

It is an amazingly flexible method, it is actually the way all real industrial

routers do their business. And it's a surprisingly simple feature

add to the basic maze router methodology. So let's go look at what cool things we

can do with non-uniform costs in our maze routing grids.

1:26

So the next feature that we're going to add to our basic maze routing core is to

allow the individual squares in the grid to cost something other than one.

To use as a part of a path. So in the original way we specified this

problem, each cell in the grid cost the same to cross it.

So more or less, that means everything costs one, we say that this is the unit

cost grid case, or uniform. Unit cost grid case.

is this necessary? No.

now give a source and a target and again, I've got my six by six grid shown here

with a source in the upper left and a target in the lower right, I'm going to

allow you to have different costs for each cell.

So it will It will no longer be the case that when we do the expansion process to

you know, sort of search for a path when I say find all the cells that are paths

of length 6. Find all the cells that are paths of

length 7. Length is not really what we're going to

be looking at anymore. We're going to say, oh let's find the

cells that are the cheapest to expand next and we'll figure out what they cost

and what they cost will be based on the cost of the path to find them and the

cost of the grid. That is used.

So we need to find some different language for describing how this

expansion process works. The process is going to be basically the

same. The sort of the way we describe it is

going to get a little bit different. What we're going to move toward is

finding the minimum cost path. That connects the source to the target.

So, what are we going to do? We're going to put some new cost items in

the grid. So in my grid a great big set of orange

squares has appeared. two cells high, three, four cells wide

and they all have threes in them. So, it does not cost one, to add this

cell to your path, it now costs three to add this cell to your path.

So, you can think of this as being something that's expensive and we'd sort

of like the path not to use it if it doesn't have to.

Alright that's what you do with the cost. And so just to be clear, the shaded

cells, the orange cells, cost three and the unshaded cells, the white cells, cost

one. It's just easier not to put all the ones

in the grid, it just makes it visually, sort of cluttered.

So a white cell cost one, something that doesn't cost one I'm going to label it

for you in some special way. So we needed to find a new metric for the

quality of our paths, and that's just the path cost.

And that's just the sum over all the cells in the path of the cost of each

cell. It's really quite simple.

Take all the cells you use in your path, add up the costs.

So here on the left I've got my six by six grid again, with a 2 by 4 element of

3's, the high cost things in it. And I've got a sort of a straight simple

path from the source in the upper left to the target in the lower right.

It's just an L shape. Four cells in the vertical arm north to

south, four cells in the horizontal arm west to east.

What does this path cost, this bright red path cost?

And the answer is, well, the source cell costs 1.

The next cell costs a three, the next cell costs a three, the corner cell costs

a one, and then the other cells that get you to the target cost a one.

1 plus 3 plus 3 plus 1 plus 1 plus 1 plus 1, that's 11.

This path costs 11. So the short straight path costs 11.

What's another path you might consider? Well, how about this path?

This path avoids the high cost region. This path first goes to the west by one

cell, then goes south four cells, then goes east five cells to make a connection

to the target. It doesn't use any of the cells that cost

three. What does this path cost?

The answer is, well every cell on it costs 1.

The source costs 1. The corner at the top left costs 1.

The path down costs 1. The corner at the bottom left costs 1 and

then all the cells on the path to the target cost 1.

You add them up, there's eleven of them. I'm sorry, there's nine of them.

This path costs nine. Oh, look, something interesting happened.

The path on the left is short, but the path on the left is expensive.

5:45

Why is it expensive? Because it used this high cost region and

maybe we don't like that. The path on the right is long, the path

on the right is cheap. Perhaps, we prefer the path on the right

unless the wire Is in trouble. You know, it's got blockages all over the

place. And the wire really urgently needs to use

that piece of space. then okay, I'll put the wire there, even

though I'll make it more expensive. But if you can, please find a path that

doesn't use those, those high cost cells. This is an incredible important way.

That you can change the, the, the fabric of the routing grid in ways that will

encourage nets to take paths that you like.

This is a big deal. This is very important.

This is a really vital feature of all real routers.

You use costs to encourage wires to take shapes that you prefer.

So you can make the router avoid a congested area.

Suppose you can do some analysis that says some regions of the chip are going

to have way more wires that want to put their paths there.

Then there is space to put paths there. You might put some big cost values in the

grid so that the early wires you route don't just go there, and you leave enough

space for the later wires to get through when you need it.

You can make different layers have different costs to use.

You can make different via's have different expense to use.

You can make different directions of expansion more expensive.

You know, you might decide that some layer you want mostly vertical wires, or

some layer you want mostly horizontal wires, we'll talk about that later too.

but it does have some some profound impacts on the search process of

expanding out. So it's no longer the case that we're

going to say, find all the paths that are find all the cells that are on paths of

length six. And find all the cells that are on paths

of length seven. Then find all the cells that are on paths

of length 8. No, that's the way you started but now

what we're going to say is, find the cells that are labeled, whose neighbors

are not labeled. Figure out what it costs to reach the

cells that are not labeled. When you do that then, find the new cells

that are not labeld who have neighbors that are, find the new cells that are

labeled with the cost that have neighbors that are not labelled with a cost.

You get the same expansion of way fronts with costs but you're not really just

searching all the paths of link k and then all the links of path of link k plus

1. and we get some, some technical

questions. You know, what does it cost to reach one

of the non-unit cells? What does it cost to put a v on a

non-unit cell? So let's just go look at the mechanics.

Here's our friend, the grid, 6 by 6 source in the upper left target in the

lower right, 2 by 4 region of high cost cells that cost 3 in the middle.

we can still start with the same language, right, you know.

The source is going to cost 1, and we're going to find all the cells that are sort

of you know 1 unit away, in distance. We're going to find all the neighbors of

the source. But then we're going to have to find some

different language for, for labeling things for the way this sort of works.

So, you know when we start the source gets a cost of 1.

That makes sense. And then we're going to look at the

neighbors of the source that are not labelled with a cost value and say what

does it cost to get there? And those are all the cells that are just

next to it, you know, one cell away. So to go to the west, that costs two, one

plus one. To go to the north, that costs two, one

plus one. To go the the east, that costs two, one

plus one. But to go to the south, that costs four.

Right, that costs four because that's one plus three.

I'm just going to put an arrow that says, that cell costs four because You expanded

the source, which cost one, using the cell, which cost three.

Right, so, so far this is all good. And, you know, there's nothing

interesting here. And you wonder why I'm belaboring this

point. But now, let's look at the cell that's to

the south and the east of the source cell.

We have not seen this situation before. In all of the previous examples that we

did. Both of the neighbors of this red

highlighted cell would have had the same number on them, they don't.

The cell to the north costs 2, that's the minimum cost path to find it.

And I could expand to the south to reach the cell.

10:11

So, just to put this in words, what is the cell's pathcost to be reached?

The highlighted red cell, that is the south and the east of the source cell,

that is orange, that costs three. Is it 2 plus 3 equals 5, because I'm

coming from the north? Or is it 4 plus 3 equals 7, because I'm

coming from the west? And the answer is it costs 5.

And it's important that you always, always want to label cells with the

minimum pathcost to reach that cell because otherwise this whole idea doesn't

work. I want to be able to search the grid to

find paths of minimum pathcost, what that just means when you add up all the costs

of the cells on the physical path I get the path with the smallest number for the

pathcost. So the right answer is though cheapest

way to get the cell. the red, highlighted cell is five.

It's to go east through cell because it cost two, and then it goes south with the

cell that costs five. We're going to have to get teh mechanics

of this algorithm right so that it always does the right thing.

11:14

Next, what if I have a via scenario? So, I've got basically the same scenario

from the previous slide, where the source expanded.

And, you know, there were some twos to the west and the north and the east.

And a four to the south. And then there were some threes in a

diamond around that, but there's five to the south and the east of the source.

And suppose that five, the big red square, wants to expand to layer two.

So I've got another six by six grid on the right side here.

And its got a great big area of high cost that's two cells wide and four cells

high. Sort of on the left of this is all those

cells are real expensive, they cost six. And one of the things that's true is that

cell that's red on the left on lalyer on that wants to but a via to go to layer to

that's part of a high cost region. If you put a via in and you go to layer

two, that cell costs six. So I have a question here.

What does it cost to get to that cell? Okay.

What does It cost to get to the same cell three rows down from the top, three

columns over from left in layer two, if we expand from the cell that costs five

in layer one? And the answer is I need to know what the

via costs so I've got it highlighted here the via cost 20 so what does it cost to

get to that cell labeled 6 because the cost of that cell is 6 in the layer 2

grid. And the answer is it costs 31.

Why? The cell you started with cost a five.

That was the pathcost to get to that cell on layer one.

It cost 20 to put the via there. Why?

Because I told you that it cost 20 and vias are expensive.

The via gets you to layer two. What does it cost to use the cell that

you land on in layer two? Answer, six.

Why? Because I said so.

That cell is expensive for some appropriate reason.

What does it cost to get to that cell on layer two?

5 plus 20 plus 6, 11 plus 20, 31. It costs 31 to use that cell.

Alright. So, what do we do?

We're going to show you some mechanics to search these grids, parallel grids with

complicated costs and complicated via costs, to find the minimum cost path.

It's going to turn out, to be a surprisingly simple an elegant algorithm.

So, here's a kind of a midpoint summary. What do we know?

We know about this grid based expansion, one net at a time thing for maze routing.

And that we can use costs in the grid to get different effects.

And we know we can deal with complicated physical scenarios like multiple wiring

layers and multi-point nets. But there's a bunch of stuff we don't

know, and we just started to get to the point where not knowing it was a problem.

Problem. I don't know real implementation

strategies. I don't really know how I build this

thing. I don't know what the real data

structures are. I don't know how cells get touched during

the search, that's the big thing. how do I expand cells, how do I reach

cells? You know, it was good and easy when I

said, find all the paths of length seven. Good.

Find all the paths of length eight. They are one cell away.

When these cost values start happening you know you gotta be a little more

careful. And there are some subtle interactions

between the cost strategy and the search strategy.

And surprisingly enough, there are some cost mechanics we can put in that

actually break the way the search works. And even though they break it, we do it

anyway because it's actually really important to the physical stuff we're

trying to accomplish with the router . So we've done sort of a discussion of the

features that we want in routing from the point of view of the user, you know

somebody trying to wire nets. Next, I got to look at the real

implication mechanics. And so were going to put our Computer

Science hats on and were going to say, hey algorithms, data structures, how do

we actually make this stuff work? Let's go look at that next.

[SOUND].