0:00

[SOUND].

So, here in Lecture 11.8, we're going to continue our exploration of

Implementation Mechanics for the Maze Router.

This is the third of our three lecture sequence on Implementation Mechanics.

One of the things that's been true so far is that whenever we did this expansion

process from one source cell. You know we expand outwards searching in

the grid to some other target in the grid.

We basically have this search process sort of omnidirectional, you know I mean

we search north, south, east, west equally.

It just sort of, you know it goes out sort of like dropping a rock in a pond.

But, but, you know, that seems a little inefficient.

I mean, if I have, a, a point over here and I'm attempting to connect a path to a

point over here, why am I expanding in the wrong direction?

Well, it turns out you don't actually have to expand in the wrong direction.

You can actually add some more interesting mechanism.

To the maze router, you can add a predictor to actually predict of how

expensive it's going to be to actually get you to the target.

You can change the structure of the cost function again in a very cleaver way.

You can do something called debt first search which preferentially biases the

search wave front. In the router process sort a, kind a,

sort of in the direction of the target. And just like our previous discussion of

consistent and inconsistent cost functions, there are ways you can do this

that don't mess things up and there are ways you can do this that do mess things

up. And people in the industrial world do it

both ways. Which is very interesting.

So, what we're going to look at in this lecture, the last of our implementation

mechanics lectures, is depth-first search, the purpose of which is to make

the basic maze router core run faster. So, in this, the third of our three

lectures on the implementation mechanics for maze routers.

I want to talk about one specific enhancement to the expansion process.

So, so here's just a true cat, a true fact.

You expand lots of cells to find one path to the target, and the CPU time is

proportional to the number of cells you expand.

And so if you have a great big grid, and you have a source and a target that are

really kind of far apart, well you know, you're going to expand a lot of cells.

In the maze routing method, until you actually go, you know, find that, find

that target. And there's really not any attempt to

search in the direction of the target first or preferentially.

So there's a question, which is can you bias the expansion so you just sort of

head toward the target? as opposed to searching you know, read

first manner. Or away from the target.

Just assuming that maybe that's a little more efficient.

And you know, kind of a side question. Based on all of our discussion of

consistency and inconsistency. Can you do this in a way, that keeps any

of the guarantee's of reaching the target with a minimum cost path.

Now ignore the inconsistent cost function thing.

Just assume it's a concistent cost function.

can I do this at all? Can I do this in a way that doesn't mess

up any of the nice properties of, you know, this sort of minimum cost search

stuff? the answer is yes, which is interesting.

So I'm, I'm just showing you a, an example here of a, again, the six by six

grid, source sort of in the middle, target bottom right.

And I'm showing you the path cost labels in the grid, again for simplicity, and so

there’s a, a diamond of 2's around the source.

And then an outward going diamond threes around the source and then a diamond of

4's around the source and then so on. And the point of the diagram is that all

of this stuff that's going to the west and to the north would appear to be

expanding away from the target and maybe that's a waste of time.

And we might be a little precise about defining what toward the target is I'm

just going to shade the box. Which is the smallest box.

The bounding box just like in placement. The bounding box of the source and target

pin. This is often called the source-target

box. And I'm going to say you know I just as

soon like to search in the yellow box before I search outside the yellow box.

Okay. That's a perfectly good definition of

what it means to be searching toward the target.

Is it possible to do that without messing up any of the other guarantees of how the

minimum cost search algorithm works, and it turns out the answer is yes.

so there's two parts to the idea we're going to add a predictor function to the

cost to direct the search to the target. So instead of just having the basic path

cost, the additional second part is the predictor.

So in a plain maze router, you add a cell c to a wave front with a cost that

measures what? It measures the cost of the partial path

that goes from the source to the cell c. In a smart maze router we're going to add

a cell c to the wavefront with a cost that estimates the entire

source-to-target cost of the path through cell c.

And the trick is that we're going to estimate this as the path cost from the

source-to-cell c. We know that plus a predictor.

And I'm circling the predictor. The predictor's an estimate.

And i'm just going to write estimate here.

The predictor is an estimate. And today we recognize this.

This is actually something famous. It's the difference between a smart depth

first search with a predictor versus a classical breadth first search, and in

fact this is a very famous application of a very famous idea.

If you've done any artificial intelligence kinds of coursework this is

A* search. This is exactly what this is but applied

in the context of a maze router. So, let's look at Plain maze routing.

And we know how this works. We expand from the source.

We get to a cell. We expand it.

We put it on the wayfront. We pull it off the wayfront, and we

expand that cell, so that cell is Gray here, and there's a big, sort of squiggly

blue line that says we got here somehow. We're expanding the gray box, we're

reaching the yellow box located underneath it.

What does it cost to reach that cell? And the answer is the path cost of the

source to the cell being expanded and the cost of the newly reached cell.

And that's how it goes on the wave front. Path cost plus cell cost.

There's a different way you could do it. We could add one more term, we could add

an estimate of the path cost from the newly reached cell to the target.

And so roughly speaking, this says that Instead of putting things in the

wavefront indexed by how much it costs to get there.

We're going to put things in wavefront indexed on how much we think the whole

route that touches the target and completes the wire costs.

Well, we haven't touched the target and we haven't completed the wires, so what

do we do? Right?

We have something that we know, the path cost and the cost.

And we have something that we estimate. What is an estimator?

Well, a typical estimator would be, you compute the distance to the target.

And that's just like you, you compute something like, a bounding box in a half

perimeter wire length router. You know, delta x plus delta y in the

grid. That's the distance to the target.

That's the length of the shortest wire that will get you from the cell to the

target. Multiply by the smallest cell cost

because, you know, what's a simple model of the rest of the wire?

And the answer is, it's the shortest possible wire.

Made up of the cheapest possible cells. So that's the distance to the target

multiplied by the smallest cell class. People do actually much fancier things

with this. for example, if you know you have to

change layers, you will include the cost of the simplest, cheapest vias that will

get you onto the layer that you need. If you know that you need to make a band

to get to the. the target.

You will calculate the bend. If you know there's three or four

different ways you could get to the target, you'll calculate the three or

four different ways and take the best cost.

Alright, people really do fancy things in real routers here, but the simple thing

is how far away is the target? How cheap is the cheapest cell?

Multiply those 2. That works.

And, there's some technical results. As long as the predictor is a lower bound

on, which is to say it is less than, the extra pathcost you will add to reach the

target. we guarantee you will still get the

minimum cost path. That's a wonderful thing.

That's the basic, the technical foundation of A-Star search, a very

famous result. What does this actually to, in a real

router. It alters the order in which you expand

the cells. So you won't get a different answer

necessarily, you'll touch the cells in a different order.

It prefers to expand the cells that are closer to the target first.

So let's go look at that. So here's my 6 by 6 grid again with a

source in the middle and a target at the bottom.

And there's the source to target box which is a three by three set of cells in

the middle is highlighted in yellow. And the source cost is one.

And we're just going to you know, run a little bit of the search process with

this predictor thing. And well, then turn to the observations

on the right. So, you know, what actually happens when

we actually do this. Well let's let's expand the cells to the

East and to the South. Right, well the pathcost is a 2, for

those cells, because it's 1 plus 1. And then there's a distance to target.

And the distance to target, which is in this case is our estimate of the

predictor, right? Is just basically that that, that wire

costs one unit, two units, three units. Right, that's the predictor for both of

those two. And that predictor has a cost of three,

we're just using the distance of, you know.

the predictor here is the distance to the target times 1 in this particular grid.

So, that's what the predictor is. so they cost 5.

what if we actually expand in the other direction, oh.

Well those cost 7. Why do they cost 7, because the estimate

for the wire to get to the target 1, 2, 3, 4, 5.

That predictor is 5. And so those sell the pathcost is 2,

right? and the predictor is a 5, as opposed to

the other case where the predictor was a 3.

So what happens is, they both get searched, they both get reached, both

kinds of cells get reached. They both get a cost associated with

them, they both go in the wavefront. If we need to use the cells that are

outside the source to target box, we will.

we'll just expand them later. Now an interesting thing is that the,

turns out that all the cells of the source of the target box, now cost the

same thing. Which is to say all the cells in the

yellow region cost the same thing because the pathcost, the source to target, the

source to sell. Plus the pathcost from the cell to the

target and that's the, basically, the predictor, okay, as constant.

And in this particular case, you know our predictor was just defined to be the same

as the distance to the target. So that's just in this simple case with

units cost and grinds that's what happens.

When you have complicated cost and the girds and other things going on it's not

so, not so clear. But in this most simple of examples where

it's unit cost and the predictor is just the distance to the target, it wants to

expand everything in the yellow box first.

That's kind of what you wanted except there's some classical cases when it's

not what you want. So here again, is my 6 by 6 grid, the

source is now in the upper left, the target is kind of in the lower right.

And there's a big black obstacle around the target.

And one of the problems is that this very simple expansion scheme wants to expand

all the cells in the source to target box before it will go outside the box to find

the path. And it turns out you cannot route this

source to target inside the source to target box, you have to go out.

And so that makes this particular case a little inefficient.