[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].
