You should complete the VLSI CAD Part I: Logic course before beginning this course. A modern VLSI chip is a remarkably complex beast: billions of transistors, millions of logic gates deployed for computation and control, big blocks of memory, embedded blocks of pre-designed functions designed by third parties (called “intellectual property” or IP blocks). How do people manage to design these complicated chips? Answer: a sequence of computer aided design (CAD) tools takes an abstract description of the chip, and refines it step-wise to a final design. This class focuses on the major design tools used in the creation of an Application Specific Integrated Circuit (ASIC) or System on Chip (SoC) design. Our focus in this part of the course is on the key logical and geometric representations that make it possible to map from logic to layout, and in particular, to place, route, and evaluate the timing of large logic networks. Our goal is for students to understand how the tools themselves work, at the level of their fundamental algorithms and data structures. Topics covered will include: technology mapping, timing analysis, and ASIC placement and routing. Recommended Background: Programming experience (C, C++, Java, Python, etc.) and basic knowledge of data structures and algorithms (especially recursive algorithms). An understanding of basic digital design: Boolean algebra, Kmaps, gates and flip flops, finite state machine design. Linear algebra and calculus at the level of a junior or senior in engineering. Elementary knowledge of RC linear circuits (at the level of an introductory physics class).
Maze Routing: Multi-Point Nets
Loading...
From the course by University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
34 ratings
From the lesson
ASIC Routing
Routing! You put a few million gates on the surface of the chip in some sensible way. What's next? Create the wires to connect them. We focus on Maze Routing, which is a classical and powerful technique with the virtue that one can "add" much sophisticated functionality on top of a rather simple core algorithm. This is also the topic for final (optional) programming assignment. Yes, if you choose, you get to route pieces of the industrial benchmarks we had you place in the placer software assignment.
Meet the Instructors
Rob A. RutenbarAdjunct Professor
Department of Computer Science
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.
>> 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.
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.
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.
So what we do next, we do the final cleanup phase, which is we take the
paths, we, the path we found. When we're all done finally with all of
the expansions to all of the targets. We label all of the segments that we
found as an obstacle because this entire thing is a wire.
So this entire multi point, in this case 3 point net, is a wire, all of the
subpaths we have found are in obstacle and it all just works.
So what have we done? We've just embedded a multipoint net and
we've rendered it an obstacle for future nets.
So, just a quick aside. does this method give us a guaranteed
shortest multi-point net? I mean, is this optimal in any sense?
And the answer is no. And that might be really surprising
because that looks like a, just a spectacularly clever and good heuristic
for doing the multi-point nets. So I'll give you just a little
terminology. The optimal path has a name.
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]
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
