0:00

[SOUND].

So, here in 11.2, we are going to show you the world's simplest router.

So, what's the world's simplest router? Everything lives on a simple grid.

All of the wires have exactly two pins, so they have a starting point and an

ending point which are traditionally called the source and the target.

All of the routing takes place on one physical layer of material so think of

that as one layer of metal available on an ASIC.

You can't change any layers. And your only goal is to connect the

first pin to the second pin. the mechanics of that are surprisingly

straight forward. It's a maze search process, and depending

on what computer science you've done in the past, you may have actually written

code to do something like find a path through a maze.

It's a famous classical problem, and interestingly enough, it's the basis for

essentially all routing that we know in the ASIC universe.

So, let's go look at the simple routing problem for 2 point next.

So let's start our discussion of the most basic kind of maze router with just a

little bit of history. I guess history, if you will, after

Moore's Mazes. So 1959, Moore publishes this basic idea.

A certain kind of a breadth first search through a grid, and it's really famous.

In 1961 just a couple of years later, it gets applied to electronics, and in this

case the wiring of print circuit boards, and so a person named Chester Lee at AT&T

Bell Labs publishes a famous paper. An algorithm for path connections and its

applications. And he basically says, you know, this

idea for more for how you find the path through a maze that's kind of like

routing things on print circuit boards with obstacles.

And he gets famous for sort of making these connections and for something like

a quarter of a century, all of the routers that are these kind of routers

are called Lee routers. When I was in graduate school, these

things were called Lee routers. In 1974, almost 15 years later, Frank

Ruben who was working at IBM makes another interesting connection.

He's reading some of the, early, early developments in artificial intelligence.

People doing certain kinds of search algorithms, and he say's oh, some of

these interesting ideas in AI can be applied to this particular search process

and you can make it go much faster. And so, interestingly he says, you know

the title of his paper is The Lee Path Connection Algorithm, which is again you

know, Lee, that guy Chester. and that's another core technique that

gets used in everybody's router today. And then in 1983 Dave Hightower, he's a

very interesting guy publishes another paper called the Lee router revisited.

And it turns out for something like a dozen or so years, people previously

people had said in the industry you know, this Lee router thing is really great.

But we just don't have enough memory in our computers to build the grids that

represent the things we want to route. And so we're going to do some other

interesting, clever kind of algorithms. And Dave Hightower got famous for another

kind of a router and called a high tower router.

and so it's a remarkable conversion when Dave publishes a paper that says, you

know, modern computers, you know, computers with astonishing 8 MB of

memory. And a virtual, memory, memory hierarchy.

So you have a disc that can store things that are bigger than 8 MB.

You know, if you have a modern computer, you can actually use a Lee router.

You can actually use a grid. You can actually use this really great

algorithm. It can route really big, really

complicated stuff. And you know, it's sort of from that

point thereafter, there's no looking back.

You know, most modern routers use this kind of idea.

So, a little really, really, really early history, if you care.

So, the maze routing strategy at a high level is that we're going to route one

net at a time. We're going to completely route the one

net, and then we're going to move onto the next net.

And we're going to optimize the path of the net.

we're going to find the best wiring path for each one.

And so there's some problems. early nets that are wired may block the

path of later nets that's actually easy to see in the little example.

You know, the optimal choice for any one net may not be good for a later net so,

you know, I route this, this pair of two points with this wire on one layer.

I route this pair of two points with a, with a, wire on one layer.

Then I'd like to route those two pair of red points there, and you know, what do I

see? I see that I can't do it.

So you know, now I've got these two elbows that go up and to the right that

are blocking basically the horizontal left to right accessibility in this

little rectangle. Then I've got another little elbow that

goes from below to above and those two blue wires are simply obstructing it and

I can't get around them. On one layer I can't get around them.

If I have multiple layers to route, I can get around them by going up to a

different physical wiring layer, so that's a non trivial problem.

We're going to have to figure out that. We'll talk about that later.

So blocked. That's the word.

It's blocked. So the basic maze router, the basic idea

is you're going to give me a grid, and each square cell represents where one

wire can cross. And we're going to start by connecting

two points, and the points are historically and traditionally called the

source and the target. You start from the source, and you route

to the target. And the problem is to find a shortest

path connecting the source cell and the target cell.

And, so when using the cells, a wire can, for example it can cross the cell, so you

can cross vertically. You can also cross horizontally, or you

can bend, you can go into the cell and you can sort of turn and go out sideways.

So you can do anything you want in a cell.

As you can just assume that all the geometry is correctly set up so that any

wire can cross any cell. So, that's how it works.

So, what's the big core idea of a maze router, you start with a source cell, you

know, just this single cell and then you find all the new cells that are reachable

at pathlength one. And so what that means is what are the

ends of all of the paths that start at the source that have exactly one unit of

total length. Which is to say, that are one cell long.

Mark them all. Well interestingly enough, it's just the

one cell, right? What are all the cells that are one cell

long that start at the source? And the answer is, the source.

That's it. Well, but then there's the more

interesting question, what are all the cell, the paths that are two cells long

that start at the source. And the answer is, those are all of the

cells that are adjacent in the north, south, east or west direction.

Right, so there's the cell that's adjacent on the north.

There's the cell that adjacent to the south.

There's the cell that's adjacent on the east.

There's the cell that's adjacent on the west.

and basically it's all the cells in the grid that are immediately adjacent to the

cell labelled 1. And so what you immediately see is this

little diamond pattern, right. There is a one in the middle and there

are a little sort of a diamond, 2 above, 2 below, 2 to the left and 2 to the

right. Or if you like 2 to the north, 2 to the

south, 2 to the west and 2 to the east. The big idea in Maze routing is you just

continue this process. That's the big great idea.

You find all of the paths that are three units in length, well those are the paths

that one unit of cells farther away from the twos.

You find all of the paths that are four units in length, those are all the cells

that are one unit away from the threes. And you just keep going until one of

those cells labels the target with a path cost, a pathlength and you found a path.

So, we are going to do this one by me writing then we will do these with

animation thereafter. But it is worth just sort of, you know,

doing it yourself if you like. So what do we do?

We start with the source cell. We say, what are all the paths of length

one? And the answer is, it's that one.

Okay, what are all the paths that have length two?

And the answer is, it is this diamond of cells north, south, east and west of the

source one cell. Okay, what're all the paths of length

three? And the answer is, it's this diamond of

cells right and when I say diamond I mean basically things that look like that.

It's this diamond of cells that are one unit away from the twos.

Okay, what are the paths that are of length four?

And the answer is, it is all of the cells that are one unit away in the north,

south, east or west direction from the threes.

Okay, so there's a little more of the diamond, and one of the things you see is

that I'm not getting the entire diamond because some of it, you know, I can't do

fours on the north and the left side, the north and the west side of this chip

because the source is up in the left corner.

All right, where are the paths that are five units of word in distance the answer

is they are one unit away from fours, so the time end is getting bigger.

Where the paths there are six paths in the length, oh, well those are the ones

that are one unit away from five. Where the paths there are seven units

away oh, look they are also one unit away from sixes.

Oh, look I have hit the target. I have labeled the target with a number,

and the number I have labeled the target with is a seven.

What does that mean? There's a path of length seven from the

source to the target. Sound simple, that's the deal, right?

there's a little bit of language we're going to revisit here.

Each of these expansion steps, you know going from the threes to the fours, going

from the fours to the fives, going from the fives to the sixes, creates a wave

front of paths. And the analogy is usually you know, if

you drop a rock in a pond, the waves, you know, sort of go out in a circle.

Well in this case the waves go out if I kind of draw it here the waves go out in

a diamond kind of a shape. So that's the core idea.

now what do you do? Well, you do a step called back tracing,

but before we do that, let's just do that previous step again.

But we're just going to do it with animation so you can see it with nicer

looking handwriting, right? So where are the cells on the paths of

length one? It's just the source cell.

What are the paths of length two, it's the diamond around the one.

What are the paths of length three, it's the diamond around the twos.

What are the paths of length four, one unit of cells away from the threes.

What are the paths of length five, one unit away form the fours.

Where are the paths of length six, one unit away from the fives.

Where are the paths of length seven, one unit away from the sixes, and what we

have discovered here is that I have labeled the target.

I've labeled it with a seven, okay. Now what do I do?

I do a next step called backtrace. Select the shortest path.

Any shortest path, there is a couple of, there is actually several shortest paths.

There is lots of paths between the source and the target, select one, mark the

cells, so they can not be used again. In particular, we are going to mark them

as obstacles, because this path once we embed it as a real wire and obstacle, the

next wires I route can not use this space.

And since there's many paths back, this optimization, optimization information

can be used to select the best one. this particular case it's really easy.

How do you do this? And the answer is just follow the path

lengths in the grids. You want to find a path from the target

to the source. The target is a seven.

Find a six. From the six, find a five.

From the five find a four, from the four find a three.

Right, so we can simply do that and what will happen is, I'm going to choose the

horizontal path seven to six to five to four on the slot of the second row of the

grid on the bottom. And then continuing, I'm going to choose

the vertical path four to three to two to one and so those pink cells are the back

trace result. Once the target is labeled with a number,

go look at the grid and follow the numbers backwards in decreasing order

until you find the source cell, that's your path.

Then what do you do? You do a step called clean-up, and

clean-up is just what it sounds, clean-up says, get rid of all the stuff you put in

the grid, so that the grid is in a state ready to route the next wire.

So if you just put some path length numbers in the grid please go erase them

all. And let's also just make sure that you

relabel the path you just found as an obstacle because the next wire can not

use any of those cells. So its got a big black l shaped thing

right in the you know kind of in the middle of this grid saying oh look I have

embedded a path. And now this grid is ready to route the

next net. With previous nets represented as

obstacles. Now the obstacles are, are, we sometimes

call them obstacles. We sometimes call them blockages.

Any cell you cannot use for a wire is an obstacle.

An obstacle or a blockage. There may be parts of the routing surface

you just cannot use, so before the problem even starts, we'll have labeled

those things. But the biggest thing is you'll label

each newly routed net as an obstacle and so future nets will route around.

So as a little example, I'm showing a new source and a new target here.

and if I was going to route this net I would be doing, you know, exactly the

same sort of a thing. I would I would say, oh, look, you know,

you put a one down, you find the paths of length two, they are one unit away.

You find the paths of length three, they are three units away.

And now you see, I've got an obstacle, I can't expand those threes any more.

You find the paths of length four. Those are the ones that are adjacent to

the threes. You find the paths of length five, and

you see this interesting phenomenon here. Oh, look, I'm sort of going around around

the obstacle. You find the paths of length six.

Oh, look, I'm going around the obstacle. You find the paths of length seven.

Oh, look, I'm going around the obstacle. You find the paths of length eight.

Oh, look, I'm going around the obstacle. You find the paths of length nine.

Oh, look, I found the target. Right?

If I backtrace things back, what I'm going to find is a wire that probably

looks something like that. And hey, I embedded the first wire.

I made it an obstacle, and the maze routing idea of expanding outward as of

length one, two, three, four, by just looking at the neighbor cells.

I'll actually respect the obstacle, I'll actually respect the desire to find a

shortest path. I can do very many interesting realistic

physical things with a pretty simple algorithm.

It's a beautiful thing, very famous, lovely, lovely result.

So that's the basic idea. Summarizing the three big steps, expand a

breadth first search to find all the paths from the source to target in path

length order. Why do we call it a breadth first search?

You find all the paths of length three before you find the paths of length four.

You find all the paths of length four before you find all the paths of length

five, and so on. Backtrace, walk a shortest path back to

the source. Back to the source.

And then mark the path cells as obstacles so that you can keep routing.

And then clean-up erases all the other stuff you put in the grid, returning it

to its original and pristine state, so that you can route the next net with the

previous nets represented as obstacles. So that's the basic idea.

It's pretty powerful. But to be honest, a little limited.

Because there's just a lot of physical stuff and a real routing problem we

haven't dealt with. How do I route something that has more

than two point nets? How do I handle more than one routing

layer? How do I deal with vias that physically

connect form one layer to the other? And I haven't really told you anything

yet about implementation, you know, do I really need a big grid, what information

do I have to put in every cell in the routing problem?

Do I really have to search the whole grid every time I do one of this?

You know, I mean, there's some tricks that make it go fast?

And, and the answers are, yeah, there's all kinds of tricks, there are things are

make it go fast. So, we're going to look at both kinds of

concerns. we're going to look at the applications

and features, components for the first couple of lectures in the, in the next

set to understand how you handle things that are really required in a router.

And then we'll move on to the interesting deep implementation stuff , the sort of

the more computer sciencey kind of stuff. Like what are the data structures look

like and what do the algorithms look like.

So let's get started on that. We're going to start adding some features

to our core router next.

[MUSIC].