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).
From Detailed Routing to Global Routing
Loading...
來自 University of Illinois at Urbana-Champaign 的課程
VLSI CAD Part II: Layout
29 個評分
從本節課中
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.
與講師見面
Rob A. RutenbarAdjunct Professor
Department of Computer Science
So here in lecture 11.9 were going to complete our exploration of maze routing,
and were actually going to look at a, just a slightly different topic.
but again something based on the core maze routing methods.
So again, over and over, one of the things we've been emphasizing is that one
of the things that's just great about the maze routing idea is that it is so
flexible and so adaptable. All of the routers that we have been
talking about so far in this lecture series are what are called, detailed
routers. And what a detailed router is is a router
that actually embeds a wire in a physical way that could make a physical path.
There's another kind of a routing process and these are called global routers.
A global router does not put the physical wire down in the physical final path.
The Global Router tells you, roughly speaking the wire wants to go, kind of,
sort of, over here. Think of this as a hierarchical
decomposition of routing. Instead of decomposing the chip surface
into a gigantic grid of tiny little cells, each of which can fit one wire.
We decompose the chip surfacing to a coarse grid of cells, each of which could
hold, say, a couple of hundred wires. And on this coarse grid, we route.
What does it mean to have a cost in this coarse grid?
What does it mean to traverse a cell in this coarse grid.
What does it mean to be an obstacle in a course grid that's the size of, you know,
200 wires on this dimension and 200 wires on this dimension.
there's an entire parallel ecosystem of ideas in global routing that lets us
coarsely. And efficiently plan the macroscopic
paths of the 25 or so million nets on a really big ASIC.
In an efficient way, so that when we finally invoke the detailed routing, we
don't actually run the maze router on the full surface of the chip.
We run it in little sort of boxes where we know the net already wants to go.
An the beautiful thing is, it's just another maze router.
It's just another expansion process. It's just another interesting set of cost
functions. An it is really, really the way, big
things get routed. So, let's finish our exploration of
routing for ASICs and the maze routing method in particular, by talking about
global routing. We're going to finish our discussion of
maze routing by kind of popping up a level to sort of talk about the, the, the
big picture problem again. And, as a starting point let's, we're
going to do a little bit of a reality check.
so you know here's, here's just my great big giant chip that I showed at the
beginning of this lecture this is an industrial actually a, a processor chip.
let's say that something like this is maybe one centimeter on the side, 20 to
50 million nets in a modern integrated circuit technology.
The grid as we taught you about the wiring grid, probably has the picture of
the wires which means the centre of one wire to the center of the closest
adjacent wire. Which we can think of, its the size of a
grid cell, maybe about a 100 nanometers. So if you have 1 centimeter, and you have
a 100 nanometer grid, you have 100000 grids on each.
on the X axis and the Y axis. And then if you multiply that by 10
different routing layers, you get about 100 billion grid cells.
So, this is one of the reasons I said we care about how big the grid cells are,
and we'd like to have as few bits as possible.
But, but do w-, we really just do it like this?
And the answer is not, not really. there's some more interesting stuff that
happens. So the first fact just as an aside is
that in, in real industrial ASIC routers we have like ten layers of wiring.
Every other layer of metal wiring has a preferred direction.
So let's say, for example, metals 3, 5, 7 and 9 are vertical Metals 4, 6, 8, and 10
are horizontal and this is how strong this preference is.
Is just a function of the, the router and the preference of the user but I'm just
going to show you an example where it's strictly enforced.
so suppose I've got a chip and I've got a pen on layer three.
as I've shown over here I've got a pin on layer six, how do I route it.
you know, I mean the typical way I'd route something like this is I'd route it
vertically on layer three. And then I'd pop a via in and then I'd go
horizontally on layer four, then I'd pop a via in, and then I'd go vertically on
layer six and I'd pop a via up to. Layer set.
So I'd, vertically on layer five, and I'd pop a via up and I'd drop that connection
in on layer six. And so the idea is that if you need to
bend, use a via. Or, and people will play games with the
bend penalty, you're allowed to bend, but boy very, very little.
and the whole idea is that the wires on these layers look like mostly straight
lines. Right, which makes it much much much
easier to route a lot of things that are just going in straight lines.
It is harder, harder to block stuff. Okay?
And when you need to go around, you go to another layer that is mostly straight
lines. So that is one of the ways you deal with
the complexity. but there is another interesting way,
which is the divide and conquer scheme. So how do you deal with a huge, the huge
scale of chips? The first kind of routing is called
global routing. and global routing is again a grid based,
maze routing, kind of a thing. and so we have a grid on which we run a
certain kind of a maze router. But the thing that's different is that
the grid is not a one wire per cell grid. The grid is now very coarse.
So the grid might be a set of boxes on the surface of the chip that are maybe
200 wires by 200 wires in size. So, the grid is extremely coarse.
And the big idea is that you run the maze router on your wire.
Just through these great big coarse regions.
So I've got a, you know, a little yellow wire here, going from a pin in the upper
left to a pin in the lower right. Now, why am I doing this?
So here's the basic idea. I'm going to chop the chip up into these
coarse regions. Later on in the flow, I'm going to use a
real router to put the real wires in. All the routing that we've actually
talked about so far has a name. It's called detailed routing.
And why it's called detailed routing is that it plans the exact final path of the
wire. Now, in this kind of routing, we are not
planning the exact final path of the wire.
We're just telling you roughly where the wire wants to go.
And what roughly means is through this set of big course grids.
Those things have a name, they're often called GBOXs.
Okay, so, that's a GBOX. a GBOX is a grid in a global router whose
size is perhaps one hundred wires by one hundred wires.
Two hundred wires by two hundred wires, could even be bigger.
and the idea is we're just going to do a sort of a large scale plan for where the
wires want to go. So, what global writing does is it makes
sure that the overall wiring congestion is reasonable.
And the way you can think of that is that it balances the supply of how much space
is available, versus the demand of how many paths want to go here.
And so, the other way to think about it is that global routing generates regions
of confinement, a coarse path for a wire. So I route the wire in the G box grid.
And what it tells me after I have routed the wire is that when I am ready to embed
the wire in detail I should put the wire in the yellow box.
The yellow serpentine path, the thing with the star in it.
And you know what? That's going to be tremendously helpful
to the efficiency of the router. Because if I don't have to expand the
route across the entire surface of the chip.
If the region on which I run my detailed router is just the smaller yellow box,
it's going to be dramatically faster. So what detailed routing does, what the
kind of routing we've been teaching up until this point does, is it embeds the
exact paths in these regions. And the simplest model is a grid.
Right? you require the wires and the pins to use
the tracks on this grid. So the global router in the picture on
the left tells us to search for detailed paths just in the highlighted yellow set.
Of G boxes and I am showing you the sort of the individual routing grids on the
inside. Okay, to just give you some sense of you
know, the fact that there is a detailed routing problem yet to happen.
The detailed router on the right tells us the exact final path in this region by
routing the wire on the grids inside. This means that you can balance the
demand for wiring across the surface of the chip by roughly planning where the
wires go first. It also makes the detailed embedding of
the wire with your router much faster because you just don't have to search so
much space. So what's really different about a global
router other than that it is a very coarse kind of a routing grid.
And the big answer is the cost function. Right?
So in a detailed router, the grid cells are either blocked, which means they have
a cost that's effectively infinite. You're not allowed to use them.
Or they have a cost proportional to how much you want to avoid them.
In a global router the cells have a dynamic cost.
The way to think about it is that in a global router the cells have memory.
They remember how many wires went through them previously.
And so in a global router the cells have a cost proportional to how many
previously routed wires use this cell. An how many more can fit in later?
So suppose in my little example shown at the right of a little GBOX, the GBOX is
ten tracks. And we're just talking about, we're
pretending there's just one layer to be very simpleminded here.
So what does the GBOX cost look like? Well the horizontal access says, how many
wires have been routed here? Okay and the way a G box a very simple G
box might have a cost is that you know out to maybe you know five wires going
through the G box. you know the cost is low.
It, you know it's, whatever the version of one is in this router.
But as soon as you start putting more wires through it starts to get more
expensive. And the idea is I don't want to allow the
router to try to put more wires in here than Can fit in here.
An one of the things that's going to happen is, that, you know, by the time
you actually have ten routers in here. what's going to happen is that you
actually have something like, infinite cost.
Or, or you have, if, if it's not infinite It's actually big, and you're going to
highly discourage future pads from using this cell because it's all used up.
You know, you've had enough layers going into it that there's just no more space.
And as you can probably imagine, you could be very, very sophisticated in your
mechanisms for figuring out the cost of a GBOX.
You know, for example, you could look at the sort of logic gates that are on the
bottom in the GBOX and say, well, do they already have a lot of wiring inside of
them? And you could look at things like other
blockages you could look at things like, how many layers of routing is htere?
You could look at things like does the wire that goes in, bend?
And does it put a Via in becuase if you put a Via in you might actually need a
little extra space depending on the nanometer rules.
there are entire groups of people in real companies that spend their lives figuring
out the cost for the GBoxes in global routers.
So that you do a good job of balancing. The demand for wiring with the supply of
wiring. And if you do global routing well, it
makes the detailed routing so much faster.
And so much more efficient and so much more likely to succeed in routing all the
nets. So, an it's, cool for us, because it's
just another maze router with, a cost function that has memory in it.
That remembers, how many wires have already used a piece of the space on the
chips surface. So, very cool.
And so, we come to the end of a very long but, I hope, interesting lecture.
This Maze Routing idea has been around a long, long time.
When people were doing, you know, mazes you know, routing through mazes in the
50s. The first, you know, routers were printed
circuit boards in the very, very early 1960s.
It's a very flexible cost based search. And, and it can be recast to attack many
different problems. That's one of the reasons people like it.
And really, it really does dominate most modern routers.
there's some big chip level routers that use fancy dynamic grids, because the
nanometer's rules are complicated. There also are some rather sophisticated
grid-less representations of space. but you still end up with something that
has a best cost [UNKNOWN] like minimum cost path algorithm.
You just get a much more sophoistiacted representation of space.
Where for example, if you want to sort of expand the path in a particular direciton
you sort of dynamically build a model of what's out there.
And then you search on it and you throw it away.
There are lots of ancillary problems and solutions, you know, you still route nets
one at a time. Early nets block later nets.
There are all kinds of tricks for that. There are a lot of iterative improvement
strategies. you often route the nets multiple times.
an interesting strategy is that you route every net as though all the other nets
didn't matter. You just route them.
Okay, and then you use the places where there are lots and lots of nets.
Too many nets. An unphysical amount of nets.
And you use that to change the cost of the grid to make nets not want to use
that space. You use the basically a demand driven.
A demand routing. to create a demand map and then you use
that to sort of put cost down and then you can use that to sort of route things
later. There are negotiation schemes where net
sort of route each other and rip each other up.
One of the things that you can do is you can route a net and in the consequence of
routing a net. You can decide to remove a piece of
another net and ask the other net to re route itself.
This very interesting stuff there is alot more hierarcy and abstraction going on in
real working. You absolutely do global routing for a
big chip, you absolutely do detailed routing for a big chip.
Probably with something like a grid or some fancy dynamic data structure.
There are a whole bunch of steps in real routing where you go in and you look at
the actual rectangles on the paths. And you have to go in and fix all of
these horrible nano meter scales physic rules.
That's the sort of thing that's keeping everyone awake at night today.
a lot, a lot, a lot of interesting computational geometry in those
algorithms. But if you're going to know one thing
about maze, about routing, know about maze routing an all the interesting
things surrounding it. An so, that is our, exploration of
routing.
[SOUND][MUSIC].
