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).
Implementation Mechanics: Data Structures & Constraints
Loading...
Do curso por University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
17 ratings
Na lição
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.
Conheça os instrutores
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND].
So here in Lecture 11.7, we're going to continue our exploration of Maze Router.
And this is the second of three lectures in the sequence on the implementation
mechanics of the Maze Router. We left you in the end of the last
lecture with some pseudo code, so you know basically how it works.
You don't really know what the data structures are yet.
Now you, you certainly know that there's a routing grid.
But, but to date in all of our little illustrations the routing grid has been
sort of the only central actor In this process and honestly, the routing grid is
part of the process but it's not the whole thing.
You actually need something that just stores the cells in the routing grid that
are active, in the sense that they are about to be used to find one of their
neighbors to make the routing process sort of expand its search.
We need to talk about what those data structures really look like.
It turns out they're actually not very complicated.
But there's a really core set of ideas that we need to talk about there.
There's the first part of this lecture. The second part of this lecture is
going to talk about some constraints on what you can do with costs, in the inter
loop of the router. So we talked about, for example, that
via's may have a higher cost. We talked about the fact that you know,
we might seed areas of the routing grid with areas of higher costs.
So that, perhaps we liked putting nets there, or perhaps we disliked to put up
nets there. Are there some constraints to what I am
allowed to do with the cost? And the answer is yes.
And interestingly enough, they're are some very simple things that we might
like to do to the router that sort of break things in some surprisingly big
ways. and here's a really interesting one.
What if we decide we'd like to put a little bit of extra cost on a wire that
actually bends? What if we say we like wires that go
straight, but this, this is a little more expensive.
Something surprising happens. We break the cost functions in some
rather deep ways. These things have a name, they're called
the inconsistent cost functions. And it creates a surprising amount of
havoc in the core of the routing engine. And why am I telling you something about
havoc in the core of the routing engine? Because every industrial router in the
world does this stuff, because it's essential.
So I'm going to show you some interesting examples of things that real routers do
and how real routers deal with some of the interesting mess that these
inconsistent cost functions create. So we're going to first start with a
little bit about the core data structures and then we'll talk about critical
constraints on the cost structure of maze routers.
So here in the next lecture on implementation mechanics, the part two of
three, we're going to talk about data structures first.
And there's really two key data structures, the routing grid itself,
which is the routing surface which holds the costs of each cell.
Non-uniform perhaps, non-unit. And also you mark those cells to know
that what you've already reached. And you're also going to mark the
predecessor stuff. So there's basically three things going
on in the routing grid. What does it cost to use the cell.
Have you reached it yet in the expansion process, and the predecessor for the back
trace. We are not putting the path costs in
here. We can do this with not very many bits.
And the wavefront, which is this new thing from the previous lecture, which
holds the active cells to expand the edges of the cell expansion process.
The cells store pathcost information and predecessor information.
And also, you know, information, you know, just about, you know, if you will,
you know, the, the coordinates of the cell, obviously.
it's indexed on the pathcost. You always expand the cheapest cell next.
So for the data structures for the routing grid.
an obvious data structure is the right thing.
It's a two dimensional ray per layer. that's good, and it can even be an N
dimensional ray if you have N routing layers.
You index it by X and Y, and each grid cell C stores three things, the cost of
C, which is typically a small number. Um,you know people actually do these
things with, with, with bits. You know you might have 12 bits, or 11
bits, or ten bits. And you might put a ten bit number in
there or you might say, I have a ten bit Index.
And so I have a table with 2 to the 10 equals 1,024 cost values in it.
And so, I look up the index of the cost, and then I look up the cost, and that's
the pathcost. People do all kinds of tricks to save
bits. There's a predecessor tag for at least
the two level routing case north, south, east, west, up, down.
And reached a bullion that says, have I reached this cell yet, yes or no?
The wavefront, all right, I need something clever here.
I need fast insert delete and I need it to stay sorted for this cost based
indexing. What does every cell on the wavefront
actually involve? What does it store?
The coordinates in the grid of you know where the cell is.
You know, you have to tell me that the cell is there.
The layer, you know, that the cell is on in case there's a bunch of grids.
you know layer 1, 2, 3. the path cost which is the sum of all the
costs up to this cell and the predecessor tag,
We're just keeping them in both places to be a little conservative, This, you know,
this will work. You know, the nice thing about the wave
front idea is that it's not a gigantically large data structure.
So what do we use for the wave front? And the answer is, a famous data
structure, a heap. which is also called a priority queue,
consult your favorite data structures book.
most programming languages, most modern programming languages, you know, C++,
Java, things like that. they'll have a basically an object and a
method you know, built into the library to do this.
You can implement one yourself if you want, it's, it's, you know gosh, you know
a hurdred lines of code, 50 lines of code to do a simple heap.
but usually you don't have to you just use the one the language provides you.
This is a classical data structure designed for fast insertion and retrieval
of the lowest cost item. So all the operations, like add and
delete, have a login complexity for N objects.
So the thing that's cool about a heap is that the minimum cost item always stays
on the top. And when you insert a new item it, it, it
the word is often bubbles for something like a binary heap.
It bubbles the items and the heap around to ensure that the cheapest item stays on
top. So you don't know what else is going on
inside your heap other than the cheapest thing is always on top.
And when you add something it's not too expensive to rearrange the heap so that,
the cheapest thing is on top. And delete also does the right thing.
Key assumptions for our plain maze router.
I will always expand the cheapest cell next.
I will reach each cell just once. I will expand each cell just once and I'm
guaranteed to find the minimum cost path. Alright, so the cheapest cell next that's
easy. expand each reach each cell once, and
expand each cell once, that seems kind of obvious.
And the fact that I'm gaurenteed to find the minimum cost path, based on, you
know, the fact that this is, basically, an implementation of the Dijkstra
algorithm, that seems good. Here's a very strange question.
What constraints must be true in order for this simple search strategy to
actually get the best path, you know, to actually get the minimum cost path?
Well if I say this to you in a different way is there anything we can do wrong
that can break any of these nice assumptions?
Okay, and the thing that's really quite amazing answers is yes, there really is.
And if you choose to do the program that's associated with this assignment we
will ask you to break things because it's just easier than the implement the case
that doesn't break them. And your going to see it yourself in your
routing benchmarks. So, there is a name for what we're
talking about, for these constraints on the path cost and, and one of the names
is consistency. And what consistency means is that.
I want it to be true that the cost of adding a cell to a path, right, reaching
it, is independent of the path itself. So I don't care how you got to Cell C on
the routing surface. When you get to Cell C on the routing
surface, there's only one pathcost it can be.
And it doesn't depend on the shape of the path in the grid.
Alright, and it turns out that if you have a consistency cost function it
guarantees that you reach every cell once from the cheapest path and you expand
every cell once it will all work. And the thing that's big surprise, is
that its incredibly easy to create a cost scheme that is inconsistent which
violates all these nice properties and which makes good, physical, geometric
sense in a router. So, here it is.
I'm going to put a big star over it. So, I've got my diagram again from the
expanding reaching diagram. It's a little bit more to it.
So there's a pink cell C, I'm sorry, a pink cell B.
Which is on the wavefront and it's being expanded.
And its pathcost is 12, and its predecessor is north, so I, I was reached
from above B. And B is expanding to the east, to touch
C. Reach C expand reach C, and B is
expanding to the south to reach D. And C costs 3 and D costs 3.
So we're expanding B, we're reaching C and D.
Here's the new thing. I'm going to penalize paths with bends.
I'm just going to add another cost whenever you reach a cell that requires
you to turn. And that's actually really easy to tell.
So, I'm just going to draw this sort of the wire.
We know that cell B was reached from north because its predecessor is north.
So the wire that sort of Got to cell B is coming from the north.
If we keep expanding and we go into cell D, that wire is a straight line.
Okay? But if we, you know, expand from cell B,
and we turn and we go into cell C, that is bending.
That's a wire with a bend in it. All right?
And so we're going to penalize that. Now, technically, how do you check if
there's a bend? you look at the predecessor label you're
about to put in the re, in the new cell you're reaching.
And you look at the predecessor of the cell you're expanding.
And if they're different you made a bend. All right?
It's, it's as simple as that. You know, B is the north.
C is going to be a west. Those aren't the same.
And it must be a bend. B is a north.
D is going to be a north. No bend.
And so here we are. We're going to compute the path cost of C
and it's going to be 17. why is it 17.
Well you know B's path cost is a 12, C's sell cost is a 3 but there's another 2
because there is a bend. 12 plus 3 plus 2 gives 17 and where does
the bend penalty come from? We made it up.
So it's an artifact. We decided it's a parameter.
When we reach D and we put it on the way front.
Well, that's going to have a cost of 15 and the reason for that is that B has a
cost of 12, D has a cost of 3 and there is no bend.
No bend. So there's no 2 added.
And so, you know, we've got a problem here which is that it now depends on how
you reached C. It depends on the path that you got to C.
And it turns out that it's actually going to break some nice things about our
router. But it's a perfectly good thing, because
you know, bends are bad. We don't want to bend if we don't have
to. If you can route something in a straight
line, right, you know, do so. And, the particular thing that bend
penaties prevent, okay, just to be sort of clear about it.
Is that if I have two points that I'm routing, please do not show me this path
going to say bad. Please do not route that path.
Right? You know if you're going to route that
wire, you know route that wire either you know like that or or route that wire like
that. Don't route that wire with all those
little scare step things in it. You know you prevent that?
You put a bend penalty on your router. So let's try this tiny little example
with a bend penalty of 2. And I'm not going to mark the reach bit
in each grid, gre, sss, in each grid cell when you first touch it.
and so I'm going to allow the search to revisit previously reached cells.
So this grid is two grids high and three grids across.
And the top row is 1, 1, 3, and the bottom row is 2, 1 1.
The upper left corner is the source, and the bottom right corner is the target.
And you know, there's only three paths Here.
So one path goes south for two cells and then goes east for three cells, and it's
cost is 1 plus 2 plus 2 plus 1 plus 1, and that 2 in the middle of that path
cost that I'm putting n red, that's the been penalty.
So ti's 1 plus 2 plus 1 plus 1 for the material cost, plus 2 for the bend...
And the other way of doing it is, you could go east for three cells and then
south for two cells and the path cost is 1 plus 3 plus 2 plus 1 which is 8.
And the 2 that's in red is also a bend, and similarly you could take a path that
has 2 bends in it. I'm just going to highlight them.
Bends. 1 plus 1 plus 1 plus 2 plus two 2 plus 8.
So that's sort, that path goes to the east for a cell, and then it goes south
for a cell, and then it goes east for a cell.
So that's a cheap end path. Clearly, I'd like the path with a seven.
But, let's actually watch what happens when we do expansions.
So, here's the grid again, drawn real small.
And we expand the source cell, which costs 1.
And so we expand the east neighbor, and it costs 2.
And we expand the south neighbor, and it costs 3 because that cell's a little bit
more expensive. And then, because we are doing a Dijkstra
algorithm, we take the cheapest cell and that cheapest cell's a 2 and we expand
it. And one of the things we can do is we can
expand it to go to the self. Right?
And that will cost 5. Why will that cost 5?
Well, that costs 2 for the cell plus 1 for the cell plus 2 which is the bend.
and you can also expand to the east a little bit more.
That turns out I'm just not going to do it.
I'm just going to show a subset of the full expansion process.
It doesn't change anything. Okay.
now that next cheapest cell in the grid is the three.
Okay I'm circling that and so I'm going to expand that.
When i expand the three I'm going to expand it to the east and it costs 6.
Why does it cost 6? Well because its a 3, the cell costs 1,
which is 4 and its got a bend. Okay, so write it in here.
Bend exclamation point. Okay, so that's cell cost 6 because we
are a Dijkstra's kind of algorithm we expand the cheapest cell so we're going
to expand the 5. All right.
The 5 expands and it reaches the target with a cost of 8, because it's got
another bend in it. 5 plus 2 plus 1 is 8.
And so we've got the target, we hit it, you know, and we think well, are we done?
And the answer is no because you know one of the things we could do.
We could come back and we could expand the six cell, which is still in the heap
We could expand this cell. This excel expands to the east with a
cost of 1. This does not have a bend in it, and we
reach the target with a cost of 7 and that's actually the best path.
Now, this is very strange. Look what happened, I reached the same
cell. I reached it later.
I reached it at a higher cost, but it was ultimately the cheaper source to target
path if I ran the expansion process long enough.
So there are some, you know, kind of scary implications on this inconsistent
cost function stuff. You will reach cells multiple times at
different costs. You will have the same cell in the
wavefront multiple times at different costs.
You can still expand the cheapest sell first, but you cannot quit when you reach
the target. How do you know when you're done?
How do you how to terminate the search? Well you can't quit until every cell in
the way front has a cost so big that it's impossible to reach the target with
anything cheaper than the current cheapest path.
And so you may reach and expand a lot more cells with an inconsistent cost
function, but you can do a bunch of cool things.
Now you might be saying to yourself, Rob, this is terrifying.
Do people really do this in real routers? And I am here to tell you that the answer
is yes boys and girls, yes, they do. Every real router does something like
this. Really.
I'm really not kidding. Every real router does this, because
every real router has to have something like a bend penalty.
And there's some other things that do this as well.
And, as soon as you put a bend penalty in, the strange stuff happens.
So, how do people really know when to quit the search?
usually some heuristic, if you expanded M cells to hit the target, you pick a
number like, you know. 10% you know and you multiply M by 10%
point 1. And you say I'm going to do not more than
M prime additional expands and you take the best path you find.
You know you don't usually search until you get the best possible path its
usually too expensive. It adds a lot of complexity.
Well a, a moderate amount of complexity to the core implementation, but it really
does help with the quality. And for us it's good enough for you to
know that this can happen. And if anyone is actually, actually lots
of you are going to build the router. We don't expect you to implement any of
this. You can play with it if you like but you
don't have to. we're perfectly with the answers you get
with inconsistent cost functions.
[SOUND].
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
