[SOUND].

So here in Lecture 11.7, we're going to continue our exploration of Maze Router.

And this is the second of three lectures in the sequence on the implementation

mechanics of the Maze Router. We left you in the end of the last

lecture with some pseudo code, so you know basically how it works.

You don't really know what the data structures are yet.

Now you, you certainly know that there's a routing grid.

But, but to date in all of our little illustrations the routing grid has been

sort of the only central actor In this process and honestly, the routing grid is

part of the process but it's not the whole thing.

You actually need something that just stores the cells in the routing grid that

are active, in the sense that they are about to be used to find one of their

neighbors to make the routing process sort of expand its search.

We need to talk about what those data structures really look like.

It turns out they're actually not very complicated.

But there's a really core set of ideas that we need to talk about there.

There's the first part of this lecture. The second part of this lecture is

going to talk about some constraints on what you can do with costs, in the inter

loop of the router. So we talked about, for example, that

via's may have a higher cost. We talked about the fact that you know,

we might seed areas of the routing grid with areas of higher costs.

So that, perhaps we liked putting nets there, or perhaps we disliked to put up

nets there. Are there some constraints to what I am

allowed to do with the cost? And the answer is yes.

And interestingly enough, they're are some very simple things that we might

like to do to the router that sort of break things in some surprisingly big

ways. and here's a really interesting one.

What if we decide we'd like to put a little bit of extra cost on a wire that

actually bends? What if we say we like wires that go

straight, but this, this is a little more expensive.

Something surprising happens. We break the cost functions in some

rather deep ways. These things have a name, they're called

the inconsistent cost functions. And it creates a surprising amount of

havoc in the core of the routing engine. And why am I telling you something about

havoc in the core of the routing engine? Because every industrial router in the

world does this stuff, because it's essential.

So I'm going to show you some interesting examples of things that real routers do

and how real routers deal with some of the interesting mess that these

inconsistent cost functions create. So we're going to first start with a

little bit about the core data structures and then we'll talk about critical

constraints on the cost structure of maze routers.

So here in the next lecture on implementation mechanics, the part two of

three, we're going to talk about data structures first.

And there's really two key data structures, the routing grid itself,

which is the routing surface which holds the costs of each cell.

Non-uniform perhaps, non-unit. And also you mark those cells to know

that what you've already reached. And you're also going to mark the

predecessor stuff. So there's basically three things going

on in the routing grid. What does it cost to use the cell.

Have you reached it yet in the expansion process, and the predecessor for the back

trace. We are not putting the path costs in

here. We can do this with not very many bits.

And the wavefront, which is this new thing from the previous lecture, which

holds the active cells to expand the edges of the cell expansion process.

The cells store pathcost information and predecessor information.

And also, you know, information, you know, just about, you know, if you will,

you know, the, the coordinates of the cell, obviously.

it's indexed on the pathcost. You always expand the cheapest cell next.

So for the data structures for the routing grid.

an obvious data structure is the right thing.

It's a two dimensional ray per layer. that's good, and it can even be an N

dimensional ray if you have N routing layers.

You index it by X and Y, and each grid cell C stores three things, the cost of

C, which is typically a small number. Um,you know people actually do these

things with, with, with bits. You know you might have 12 bits, or 11

bits, or ten bits. And you might put a ten bit number in

there or you might say, I have a ten bit Index.

And so I have a table with 2 to the 10 equals 1,024 cost values in it.

And so, I look up the index of the cost, and then I look up the cost, and that's

the pathcost. People do all kinds of tricks to save

bits. There's a predecessor tag for at least

the two level routing case north, south, east, west, up, down.

And reached a bullion that says, have I reached this cell yet, yes or no?

The wavefront, all right, I need something clever here.

I need fast insert delete and I need it to stay sorted for this cost based

indexing. What does every cell on the wavefront

actually involve? What does it store?

The coordinates in the grid of you know where the cell is.

You know, you have to tell me that the cell is there.

The layer, you know, that the cell is on in case there's a bunch of grids.

you know layer 1, 2, 3. the path cost which is the sum of all the

costs up to this cell and the predecessor tag,

We're just keeping them in both places to be a little conservative, This, you know,

this will work. You know, the nice thing about the wave

front idea is that it's not a gigantically large data structure.

So what do we use for the wave front? And the answer is, a famous data

structure, a heap. which is also called a priority queue,

consult your favorite data structures book.

most programming languages, most modern programming languages, you know, C++,

Java, things like that. they'll have a basically an object and a

method you know, built into the library to do this.

You can implement one yourself if you want, it's, it's, you know gosh, you know

a hurdred lines of code, 50 lines of code to do a simple heap.

but usually you don't have to you just use the one the language provides you.

This is a classical data structure designed for fast insertion and retrieval

of the lowest cost item. So all the operations, like add and

delete, have a login complexity for N objects.

So the thing that's cool about a heap is that the minimum cost item always stays

on the top. And when you insert a new item it, it, it

the word is often bubbles for something like a binary heap.

It bubbles the items and the heap around to ensure that the cheapest item stays on

top. So you don't know what else is going on

inside your heap other than the cheapest thing is always on top.

And when you add something it's not too expensive to rearrange the heap so that,

the cheapest thing is on top. And delete also does the right thing.

Key assumptions for our plain maze router.

I will always expand the cheapest cell next.

I will reach each cell just once. I will expand each cell just once and I'm

guaranteed to find the minimum cost path. Alright, so the cheapest cell next that's

easy. expand each reach each cell once, and

expand each cell once, that seems kind of obvious.

And the fact that I'm gaurenteed to find the minimum cost path, based on, you

know, the fact that this is, basically, an implementation of the Dijkstra

algorithm, that seems good. Here's a very strange question.

What constraints must be true in order for this simple search strategy to

actually get the best path, you know, to actually get the minimum cost path?

Well if I say this to you in a different way is there anything we can do wrong

that can break any of these nice assumptions?

Okay, and the thing that's really quite amazing answers is yes, there really is.

And if you choose to do the program that's associated with this assignment we

will ask you to break things because it's just easier than the implement the case

that doesn't break them. And your going to see it yourself in your

routing benchmarks. So, there is a name for what we're

talking about, for these constraints on the path cost and, and one of the names

is consistency. And what consistency means is that.

I want it to be true that the cost of adding a cell to a path, right, reaching

it, is independent of the path itself. So I don't care how you got to Cell C on

the routing surface. When you get to Cell C on the routing

surface, there's only one pathcost it can be.

And it doesn't depend on the shape of the path in the grid.

Alright, and it turns out that if you have a consistency cost function it

guarantees that you reach every cell once from the cheapest path and you expand

every cell once it will all work. And the thing that's big surprise, is

that its incredibly easy to create a cost scheme that is inconsistent which

violates all these nice properties and which makes good, physical, geometric

sense in a router. So, here it is.

I'm going to put a big star over it. So, I've got my diagram again from the

expanding reaching diagram. It's a little bit more to it.

So there's a pink cell C, I'm sorry, a pink cell B.

Which is on the wavefront and it's being expanded.

And its pathcost is 12, and its predecessor is north, so I, I was reached

from above B. And B is expanding to the east, to touch

C. Reach C expand reach C, and B is

expanding to the south to reach D. And C costs 3 and D costs 3.

So we're expanding B, we're reaching C and D.

Here's the new thing. I'm going to penalize paths with bends.

I'm just going to add another cost whenever you reach a cell that requires

you to turn. And that's actually really easy to tell.

So, I'm just going to draw this sort of the wire.

We know that cell B was reached from north because its predecessor is north.

So the wire that sort of Got to cell B is coming from the north.

If we keep expanding and we go into cell D, that wire is a straight line.

Okay? But if we, you know, expand from cell B,

and we turn and we go into cell C, that is bending.

That's a wire with a bend in it. All right?

And so we're going to penalize that. Now, technically, how do you check if

there's a bend? you look at the predecessor label you're

about to put in the re, in the new cell you're reaching.

And you look at the predecessor of the cell you're expanding.

And if they're different you made a bend. All right?

It's, it's as simple as that. You know, B is the north.

C is going to be a west. Those aren't the same.

And it must be a bend. B is a north.

D is going to be a north. No bend.

And so here we are. We're going to compute the path cost of C

and it's going to be 17. why is it 17.

Well you know B's path cost is a 12, C's sell cost is a 3 but there's another 2

because there is a bend. 12 plus 3 plus 2 gives 17 and where does

the bend penalty come from? We made it up.

So it's an artifact. We decided it's a parameter.

When we reach D and we put it on the way front.

Well, that's going to have a cost of 15 and the reason for that is that B has a

cost of 12, D has a cost of 3 and there is no bend.

No bend. So there's no 2 added.

And so, you know, we've got a problem here which is that it now depends on how

you reached C. It depends on the path that you got to C.

And it turns out that it's actually going to break some nice things about our

router. But it's a perfectly good thing, because

you know, bends are bad. We don't want to bend if we don't have

to. If you can route something in a straight

line, right, you know, do so. And, the particular thing that bend

penaties prevent, okay, just to be sort of clear about it.

Is that if I have two points that I'm routing, please do not show me this path

going to say bad. Please do not route that path.

Right? You know if you're going to route that

wire, you know route that wire either you know like that or or route that wire like

that. Don't route that wire with all those

little scare step things in it. You know you prevent that?

You put a bend penalty on your router. So let's try this tiny little example

with a bend penalty of 2. And I'm not going to mark the reach bit

in each grid, gre, sss, in each grid cell when you first touch it.

and so I'm going to allow the search to revisit previously reached cells.

So this grid is two grids high and three grids across.

And the top row is 1, 1, 3, and the bottom row is 2, 1 1.

The upper left corner is the source, and the bottom right corner is the target.

And you know, there's only three paths Here.

So one path goes south for two cells and then goes east for three cells, and it's

cost is 1 plus 2 plus 2 plus 1 plus 1, and that 2 in the middle of that path

cost that I'm putting n red, that's the been penalty.

So ti's 1 plus 2 plus 1 plus 1 for the material cost, plus 2 for the bend...

And the other way of doing it is, you could go east for three cells and then

south for two cells and the path cost is 1 plus 3 plus 2 plus 1 which is 8.

And the 2 that's in red is also a bend, and similarly you could take a path that

has 2 bends in it. I'm just going to highlight them.

Bends. 1 plus 1 plus 1 plus 2 plus two 2 plus 8.

So that's sort, that path goes to the east for a cell, and then it goes south

for a cell, and then it goes east for a cell.

So that's a cheap end path. Clearly, I'd like the path with a seven.

But, let's actually watch what happens when we do expansions.

So, here's the grid again, drawn real small.

And we expand the source cell, which costs 1.

And so we expand the east neighbor, and it costs 2.

And we expand the south neighbor, and it costs 3 because that cell's a little bit

more expensive. And then, because we are doing a Dijkstra

algorithm, we take the cheapest cell and that cheapest cell's a 2 and we expand

it. And one of the things we can do is we can

expand it to go to the self. Right?

And that will cost 5. Why will that cost 5?

Well, that costs 2 for the cell plus 1 for the cell plus 2 which is the bend.

and you can also expand to the east a little bit more.

That turns out I'm just not going to do it.

I'm just going to show a subset of the full expansion process.

It doesn't change anything. Okay.

now that next cheapest cell in the grid is the three.

Okay I'm circling that and so I'm going to expand that.

When i expand the three I'm going to expand it to the east and it costs 6.

Why does it cost 6? Well because its a 3, the cell costs 1,

which is 4 and its got a bend. Okay, so write it in here.

Bend exclamation point. Okay, so that's cell cost 6 because we

are a Dijkstra's kind of algorithm we expand the cheapest cell so we're going

to expand the 5. All right.

The 5 expands and it reaches the target with a cost of 8, because it's got

another bend in it. 5 plus 2 plus 1 is 8.

And so we've got the target, we hit it, you know, and we think well, are we done?

And the answer is no because you know one of the things we could do.

We could come back and we could expand the six cell, which is still in the heap

We could expand this cell. This excel expands to the east with a

cost of 1. This does not have a bend in it, and we

reach the target with a cost of 7 and that's actually the best path.

Now, this is very strange. Look what happened, I reached the same

cell. I reached it later.

I reached it at a higher cost, but it was ultimately the cheaper source to target

path if I ran the expansion process long enough.

So there are some, you know, kind of scary implications on this inconsistent

cost function stuff. You will reach cells multiple times at

different costs. You will have the same cell in the

wavefront multiple times at different costs.

You can still expand the cheapest sell first, but you cannot quit when you reach

the target. How do you know when you're done?

How do you how to terminate the search? Well you can't quit until every cell in

the way front has a cost so big that it's impossible to reach the target with

anything cheaper than the current cheapest path.

And so you may reach and expand a lot more cells with an inconsistent cost

function, but you can do a bunch of cool things.

Now you might be saying to yourself, Rob, this is terrifying.

Do people really do this in real routers? And I am here to tell you that the answer

is yes boys and girls, yes, they do. Every real router does something like

this. Really.

I'm really not kidding. Every real router does this, because

every real router has to have something like a bend penalty.

And there's some other things that do this as well.

And, as soon as you put a bend penalty in, the strange stuff happens.

So, how do people really know when to quit the search?

usually some heuristic, if you expanded M cells to hit the target, you pick a

number like, you know. 10% you know and you multiply M by 10%

point 1. And you say I'm going to do not more than

M prime additional expands and you take the best path you find.

You know you don't usually search until you get the best possible path its

usually too expensive. It adds a lot of complexity.

Well a, a moderate amount of complexity to the core implementation, but it really

does help with the quality. And for us it's good enough for you to

know that this can happen. And if anyone is actually, actually lots

of you are going to build the router. We don't expect you to implement any of

this. You can play with it if you like but you

don't have to. we're perfectly with the answers you get

with inconsistent cost functions.

[SOUND].

Implementation Mechanics: Data Structures & Constraints

VLSI CAD Part II: Layout

Conheça os instrutores