0:08

So here in 11.3 we're going to advance to the next step in our exploration of

routing. In the previous lecture we showed you how

to route nets that have exactly too points.

But as we learned in the placer problem, not all nets actually have two points.

Nets can have lots of points, they can have lots of points, pins, because there

are fan outs, right? You have a logic gate that's driving a

whole bunch of other input gates. So you can have wires, nets that actually

have lots of pins on them. How do you route a multipoint net?

Roughly speaking, you route the first pair of pins and then you take the entire

wire and you expand it to reach the next nearest pin and you repeat to go until

you find all of the paths. It looks very much like the two point

problem and one of the things that's really cool about the maze routing

methodology is that the foundational method is very straightforward but it's

incredibly flexible and adaptable. We can keep adding piece functionality

features or, you know, interesting stuff. And so the first thing we're going to add

is how do you do multi-point nets so let's go take a look.

1:14

>> So our first feature addition to the maze routing core is multipoint nets.

I've got one source and if you like many targets.

And look, you're going to get this in any net that represents fanout.

So I have let's say a gate here and I have a net and the net connects to, you

know, an inverter over here. And a nine gate over here And an

exclusive NOR gate over here. And whatever else, I'm, I'm going to have

fanout. That has to be able to deal with

arbitrary numbers of pins on my net. And there's a surprisingly simple

strategy that works okay. we'll talk through it in English.

And then we'll, we'll show you a, an illustration.

You pick one point as the source. And you label all the others as targets.

So this is the first new thing, several targets.

And they use the maze-routing algorithm to find a path from the source to

something, the nearest target. You don't know which one it is.

You're going to route until you find a target, alright?

Then you relabel all the cells on the found path as sources.

And then you rerun the maze router using all of the sources simultaneously.

That requires a picture to illustrate. And you just repeat this for every

unconnected target point until you connect all the targets.

2:26

So, here's my problem. I've got a grid my friendly little six by

six grid, and I've got a source in the upper left, I've got two targets sort of

on the bottom left, and kind of the middle on the right.

and I want to find a short path connecting the source to all of the

targets; I want one wire. That does that, okay?

And so, the first segment of the path, I'm just going to run the maze router to

find the closest target. So I'm going to start at the source,

which is in the upper-left, and I'm just going to go until I find the target.

So here we just animate that in. So, let us label all of the path, all of

the cells that are on the end of a path that's one unit long, and that's the

source, so the source cell gets a 1. Let us find all the paths that are two

units long. Okay, those are the north, south, east,

and west neighbors of the 1, the little diamond shape.

Let's find all the paths that are three units long, so those are the 3s that are

one unit away, north, south, east, and west from the 2.

So the diamond is sort of expanding to the kind of lower left, lower right side

of the, of the grid. Let's find all the cells that are on

paths four units in length, well the diamond is getting a little bigger and

continuing to sort of expand toward the bottom right corner.

Let's find all of the paths that are five units in length, so the diamond continues

to get a little bigger, the wave front continues to grow and oh, look.

I have hit the target with a five, what is it that I know?

What I know is that there is a path of length five that will do the job.

I know that there is a path of length five from the source to the target and I

can just continue to run my algorithm. Now look, remember, I didn't know which

target I was going to hit when I started. because you know, this, this layout could

be filled with obstacles. So even the fact that the target is

close, doesn't mean I know which one I'm going to hit.

So, this is the target I hit. I hit the one on the bottom left.

4:15

Now what? I backtrace, and the backtrace is, you

know the process by which I figure out the physical cells in the path and so I'm

going to walk backwards from the label five.

From the five I'm going to find a four, from the four a three, a three and two

and so on, right, so we'll just animate that in.

So I'm going to find a five. The four I choose to find is the four to

the west, so I'm doing the horizontal thing first, and then I safe that to

continue to decrease the numbers, i have to go north.

And some that I call north and so there's my path so the path is 1, 2, 3, 4 cells

verticals and 1, 2 cells horizontal it's kind of an L shaped path from the source

in the upper left to the target in the bottom left.

Now there's something new and interesting.

I am not done. I am not going to label this as an

obstacle. This thing that I've just traced, this

path that I've just traced, becomes the source for the next phase of the

algorithm. I'm going to label everything in here as

a source, all of these cells are going to become the source, and I am going to

continue the algorithm. Okay, so what happens?

I put an S on every one of those cells, and then I'm just a little bit careful

when I do the maze routing step, you know?

I'm not going to try to take an S and expand it from a 1 to a 2 by labeling

another S, right? I'm only going to look at the empty

cells. So going forward this is the scenario.

That L shapes wire that was in the left part of the grid, all of those things are

sources now. We're going to expand this entire set of

source cells to find the next segment, so it doesn't need to be the case that the

source is just the cell. The source can be a bunch of cells.

And all we have to do is have you know an appropriate semantics for how we label

the adjacent neighbors. And the answer is we start by labeling

all of the cells that are one unit in length.

Right? And that's going to be just what you

think, it's going to be all the source cells.

They're one unit in length, which is to say, what are all the paths that are one

unit away from a source? And the answer is those are the source

cells. Right.

Now we're going to find all the paths that are two units away.

Alright, and the rule is you're allowed to label an empty square.

You're not allowed to empty a square that's got a number in it already.

So we're not going to try to take a one and overwrite it with a two.

So what are all the cells that are two units in length on a path from a source?

And the answer is it's sort of a little halo around the source cells.

And I'm just going to kind of draw that in a little bit, you know just because

it's kind of interesting. Okay.

It's this little halo. if the source is a cell, a single cell,

the halo is kind of a diamond. If the source is a complicated shape, the

halo is kind of a diamond that got kind of smeared over all of the source cells.

Right, so those are all of the cells on a path two units in length that starts from

any source, and you just keep going. What are all the cells that are three

units in length? Well there they are, it's another sort of

a halo around all of the twos, and what we can see is that the halo is kind of

marching across to the right. What are all the cells on paths of length

four from any source? Well the halo continues to march across

to the right. And it's kind of vertically going all the

way from the top of the grid to the bottom of the grid.

What are all the cells on paths of length five form any source cell.

And, you know, it continues to march, and in fact the grid is almost completely

filled up at this point. And Oh look, we have hit the target, or

we've, we've hit a target, in this case we've hit the single remaining target.

And next, we're going to do just what we did before.

We're going to take the five that we just labeled the target with.

And we're going to find a four, and then a three, and then a two, and then a one,

and we know that when we hit a one, we have found a source cell.

What's interesting is we don't know which source cell, we're going to find the most

appropriate source cell. In this case the closest source cell,

which when expanded will find a path of length five to hit the target.

So, I'm drawing it just like I did before, we started with a 5, 4, 3, 2, 1.

The pink thing, which is sort of almost the entire horizontal width of the six by

six grid, sort of in the top third, connects the target on the far right to

the source on the top left, and there we go.

That's the next segment on the path. And like I said, we didn't know which

part of the source we were going to start with, that's the right part.

10:08

it's called a Steiner tree. Alright.

how hard is it to get a Steiner tree. Exponentially hard.

almost everything that's, that's, that's really valuable in the CAD business is,

is just really hard. So just another example of why CAD is

full of touch and interesting problems to solve.

just a quick example. Suppose I have these four points to

connect. So I've got a little yellow box with four

pins in it. The points are, you know, kind of in the,

you know, the upper left, the upper right, the kind of the middle left and

the lower right. There are four pins to connect.

And the optimum connection is called the Steiner tree, so it's in this case it's a

graph. Or it's a, it's a set of paths whose

wires are only horizontal and vertical, that has the absolute minimum length, in

this case red wires, red lines, the minimum length.

and what's hard about this problem is that as you can see here, the wire just

like the wire we routed with our little maze routing algorithm.

It's not going to be the case that all of the wire segments start on one of the

black pins and end on one of the black pins.

Some of the wire segments are going to start in the middle of other wire

segments. Those points at which the wire segment

connect have a special name. They're called Steiner points and one of

the things we did in our little heuristic for multi-point wiring was we found a

Steiner point. When we did the final trace back of the

second target. We connected in the middle of the first

wire segment, the point we connected at was a Steiner point.

You know, why this is hard in general is you don't know at the start where the

right Steiner points are. And, depending on the order in which you

pick the first point, and the order in which the expansions happen, and you know

some other stuff you know the heuristic is.

going to give you a pretty good answer, the heuristics is absolutely not

guaranteed to give you the best answer, and that's just the way it works.

So simply heuristics worked okay but there's no guarantee that you're going to

get the best possible Steiner point. Nevertheless, the heuristic that we

showed you It's perfectly good, and you can use it to route multi-point nets.

So, let's continue adding functionality to the router.

[SOUND]