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).
Simple Iterative Improvement Placement
Loading...
Do curso por University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
30 classificações
Na lição
ASIC Placement
In this second part of our course, we will talk about geometry. We will begin with an overview of the ASIC layout process, and discuss the role of technology libraries, tech mapping (a topic we delay until the following week, to let those who want to do the Placer programming assignment have more time), and placement and routing. In this set of lectures, we focus on the placement process itself: you have a million gates from the result of synthesis and map, so, where do they go? This process is called “placement”, and we describe an iterative method, and a mathematical optimization method, that can each do very large placement tasks.
Conheça os instrutores
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND].
So, here in lecture 9.3, we're actually going to build a very simple placer.
So what you know is that, to first order, what a placer does is arrange the gates
on the surface of the chip. And try to optimize an estimate of the
wirelength, and one of the estimators we now know how to do is the half-perimeter
wirelength, or the bounding box wirelength.
How do actually arrange the gates to make this number small?
And an interesting idea is that we use randomness.
We randomly place the gates We randomly pick a couple of the gates.
We randomly exchange the gates. And we see if things got better, right?
And then we just continue that process and go forward.
It sound really simple minded. It actually works.
And it is the basis for some real interesting commercial sorts of placement
engines. So we're going to start by building a
simple Randomized iterative improvement placer.
So let's go see how that works. So the easiest way to show how a placer
is put together is to build one. And so we're just going to build the
world's simplest placer, because it illustrates a lot of the really core
ideas. And after we go from this very simple
foundation We'll add some sophistication. We'll add some, some more interesting and
useful ideas. So to start, how are we going to start
our placer? Well, there are really two big ideas and
this is an iterative improvement placer and so there's a, two important ideas.
The first is you start with a random placement.
You just randomly assign each gate to a grid location.
Only one gate per grid please. And if you're thinking to yourself, wow,
that has got to be just a terrible, terrible placement, because if I take all
of the gates and I just throw them at the surface of the chip and they land where
they may. And I take a step back and use my
Wirelength estimation techniques as I can estimate the half perimeter wirelength
for all of those nets and I can add that number up and I can get a measure of the
quality of this placement. This is probably a terrible placement and
the answer is, yes, it is. But it's a real placement, and it is a
complete placement. And that is essential because what we're
actually going to do Is iteratively improve it.
So the idea is as follows, I don't know how to just get, in one step, a good
placement. But I know how to get any placement.
It's a random placement. It's a bad placement.
And it's not that hard to improve a placement a little bit.
And the idea is that you pick a random pair of gates in the grid, And you
exchange their locations, that's really the key step.
You exchange their locations, and then you evaluate whether things got better.
So, what do you compute? You compute the change in the wire
length, you compute the new total half perimeter wire length, subtract the old
half perimeter wire length delta L. And delta L is an indication as to
whether the exchange of those 2 gates, the swap of those 2 gates.
Made the placement better, or made the placement work.
If delta L is less than 0, the new total wire length got smaller.
That's good. That's an improvement.
You just made the placement better. Keep it.
If delta L is bigger than zero, the new total wire length is bigger.
That's bad. You just made the placement worse.
Undo it. You just keep doing this for many many
random swaps. Literally millions and millions and
millions, maybe more, random swaps. How long do you do this?
Well, you can do this until the Quality of the placement stops improving until L
stops getting smaller, or if you have a CPU time limit, you know, you can do this
for an hour or you can do this for a day or you can do this for a weekend or you
can do this for a week. You can do this as long as you like.
But at some point, L is going to stop improving, the placement is done and you
look and you see how good it is. That sounds tremendously simple, and it
is, but it actually works. So, here's a high level Pseudo-code for
an, a random iterative improvement placement.
And it's just got a couple of parts, alright?
So, the first part, up at the top, says, random initial placement for each gate G
in the netlist place Gi in a random location in the grid, alright?
So that's just this, this initial placement.
You gotta get the random initial placement before you can improve it.
And then the next thing you have to do, is you have to calculate the initial wire
length. So L equals zero for each net N.
And the net list L equals L plus the HPWL, the half perimeter wire length
estimator for that net. You just gotta add up all the lengths of
the nets. And then there is an improvement loop.
Right, and the improvement loop just says, while the overall wire length L is
improving, pick a random gate GI, and random gate GJ, swap the gates, evaluate
the change in the wire length delta L. And then, there's just the two key parts
here. If delta L is less than 0, oh, I have
just improved the quality of my placement, because I swapped two gates
and the wire length got better, please keep that.
And so what you see here is it says if delta L is less than 0, L equals L plus
delta L. I update the wire length to res, to res,
to remember the fact that I, I improve things.
Else if delta L is greater than 0, I just made a worse placement, right?
And in that case, what you do is you undo the swap.
And you just keep doing this until the wire length is falling.
That sounds incredibly simple, but you know that works.
SO this is an Iterative Improvement Placer where we in a very long sequence
of very small steps, iteratively improve the placement.
And how do we do that iteration? Random.
Random gate swaps. Now, one thing that I have to mention is
that it is imperative that you try to calculate the delta L efficiently.
And what that means is that you have to calculate it incrementally.
And what that means is if you are taking two gates and exchanging them, it is
extremely inefficient and extremely stupid to go measure again the
half-perimeter wire length for all 10 million wires in your layout.
Look, you have two gates, and you exchange them.
They're probably connected to five other wires, ten other wires; y'know, depends
on what they are, 20 other wires, whatever.
Trust me; they're not connected to 10 million other wires.
Do not go back and reevaluate the half-perimeter wire length for all the
nets in the layout. Just evaluate the change on the nets that
could themselves change. That is said to be an incremental
evaluation. And so on the left I've got a little
picture. Again, my four by my five by six grid, x
goes from 0 to 4, y goes from 0 to 5. There's a gate in (1,4) There's a gate in
2,1. There's a gate in 3,3.
And there is a gate in 4,5. The top two gates, or the top two rows,
are black. The bottom two gates are red.
There's a net called Net I that connects the top three gates, two blacks and a
red. There's a blue net.
There's a net that's kind of purple called Net K that connects the topmost
gate and the bottommost gate. and then there is a Net J, that's orange,
that connects the bottommost gates. And the gate at three three is called
one, and the gate at two one is called two.
And what I want to do is Exchange them. I'm going to swap Gates 1 and 2.
And so, I'm going to swap the two red gates.
And when I swap them, now Gate 2 is on the top and Gate 1 is on the bottom.
So, there are still gates in 2 1 in the grid and 3 3 in the grid, but they're
different gates. And what we see is now Net i is now
longer. The blue net, the net that takes the top
two gates and now connects to the bottommost gate.
Net j, which connected the two red gates, has not changed, because it was just
connecting the gates that were swapped, and so there's still gates in the same
place. Its half-perimeter wire length isn't
changed. Net k appears to be much shorter, because
it used to connect the topmost gate and the bottommost gate.
And we swap the bottom-most gate to be somewhere in the middle of the layout.
Did the overall wire length go up as a result of this, or did it go down as a
result of this? I don't know, right.
I, I, you know, I don't, I don't know. I actually have to go calculate this.
Right, and I calculate this incrementally, and so incrementally means
that Delta l is the sum of the half perimeter wire lengths for nets I, J and
K after the swap. I add those things together and then I
subtract from that the sum of the half perimeter wire lengths of I, J and K
before the swap. And so you just have to arrange your data
structures, and you know, your, your internal organization of your code so
that you can do this easily. So you have 10,000,000 gates that you're
trying to work with, a 1,000,000 gates you're trying to work with, a 100,000
gates that you're trying to work with you take 2 of those gates and you swap their
locations. Do not go reevaluate the half perimeter
wire length estimator for another million or ten million nets, just evaluate it for
the ones that could have changed their length.
Which ones are those? Those are the ones connected to the
things that you've moved. It sounds simple but it's a really
important concept. So, how does that work?
It works okay... And if I sound less than enthusiastic,
it's because okay is the best thing I can say.
This is not a good placement. And I'm going to show you techniques that
give you dramatically better placements. But this is the right Starting point.
This is sort of the historical origins of placement.
You want to talk about how people were doing placement in the 1970's?
This is how. So, this is a small benchmark.
It's about 2500 gates and 5000 pins. It's being placed in a 50 by 50 grid.
The graph shows progress. So the horizontal axis goes from zero to
ten e6, which means ten million swaps. And it's labeled zero, two million, four
million, six million, and eight million. The vertical axis is the sum of the half
perimeter wire lengths. Right?
So that's actually the thing we're optimizing.
And there's a, basically a blue curve that's has a nice sort of exponential
kind of fall-off. It starts up around oh, call it 42,000,
and it falls off to something that looks to be maybe 26,000 or 27,000 in the total
wire length. So you know, that's a pretty significant
improvement. And you can just see that it sort of, you
know, it falls really fast at the start because you started with a bad random
placement. And everything you do is useful.
And then, you know, once you start to go out there, honestly, most of the swaps
you try are unsuccessful because they make the placement worse.
So it takes longer and longer to find something that actually improves things,
and the rate at which the improvement happens is falling off pretty
dramatically. So this particular swap particular design
actually ran you know, something like you know, about eight million swaps to
actually get this result, and this is okay.
This is not great, trust me, this is not great, but this is okay.
So what can I say about random iterative improvement placement?
Well the first is that it's easy to understand and it's easy to implement.
and you know, that code that I actually showed.
that example is actually a place where I wrote, gosh, 25 years ago.
and that one of my enterprising TA's tweaked a little bit to to get this
graph. So, big idea, you start with a random
placement, you randomly improve it. You can optimize what we care about,
which is the total estimated wire-length. The sum over all the nets of the
half-perimeter wire length. Please remember to do this incrementally,
don't be stupid. the wire length will improve, it will
sometimes improve a lot. But the still, the overall result is just
not very good. Compared to what we know how to do today,
not very good. We can do better.
We can do really a lot better. So let's go talk about adding some
Interesting sophistication to this, to get a much better answer for a
placement[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.
