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).
Analytical Placement: Quadratic Wirelength Model
Loading...
From the course by University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
20 оценки
From the lesson
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.
Meet the Instructors
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND].
So here were are in lecture 9.6. We're going to talk about a very
different kind of placement algorithm. We're going to talk about analytical
methods. So, all of the placement techniques that
we've talked about up 'til now in this lecture, have been based on some form of.
Random improvement, random exchange, random perturbation with some interesting
control parameters like for example simulated annealing.
Those are really good and powerful techniques but they really run out of
steam. They are not very efficient when you get
to let's say a half a million gates. And since people are really placing
things with a few million gates, you know, 10 million gates these days as a
kind of an atomic placement task maybe even more.
the annealing like methods don't really work very efficiently.
The analytical methods are based on a very different kind of an idea.
We're actually going to write an equation.
a mathematical equation and we're actually going to use calculus on it and
some interesting linear algebra and we're going to solve that equation,
numerically. And the solution of that equation is
going to be the placement of the gates. And if you're thinking wow, if I have a
million gates. Am I going to have an equation with,
like, 1 million x's and one million y's in it?
And you're telling me that I'm going to do calculus on it, and I'm going to solve
it? I'm going to tell you yes, that's
actually how modern placers really work. So let's start by talking about the sort
of the introductory background to analytical placement.
We're going to write an equation whose minimum is the placement.
Now you understand something about this because roughly speaking what the
iterative improvement simulated annealing style placers did was iteratively
minimize a wirelength function. Whose value is determined by the
locations of all the gates. But now we're going to write something
that looks more like a physics equation, a continuous valued equation, an
analytical equation, an equation that I can actually write down.
And we're going to solve for its minimum. So if you have a million gates you need a
million x y values. As a result one for each of your million
gates. We're going to formulate an appropriate
cost function for all of the gate level x y coordinates.
That function is going to be a function of ten, of 1 million x's and 1 million
y's, and then we're going to solve it analytically which means we're actually
going to do math on it. And we're going to get 10 mill 1 million
x's and 1 million y's. And that will be the minimum of this
function. And the resulting set of values give you
the placement of all million gates. And I recognize that this sounds kind of
crazy. but it works great.
And there's a trick. The trick is that you have to figure out
a way to write the wirelength in a mathematically friendly form that you can
optimize. And what's interesting is that this is
actually quite possible, and in fact there's several different ways of doing
it. All modern placers for big ASICs and big
Systems On Chip are analytical in this style.
So the big idea behind the class of analytical placers that we're going to
study in this lecture is something called the quadratic wirelength model.
And the idea is that it turns out that by optimizing this thing called the
quadratic wirelength instead of the half perimeter wirelength, it has the nice
friendly mathematical properties we need to be able to derive a solution.
So said differently, why do we pick the quadratic wirelength?
Because the mathematics works out in a way that we can solve.
So for a 2-point net, this is actually very simple.
This is the squared length of the distance between the points.
So I've got a little grid here, the same grid I have been showing previously.
X goes from 0 to 4, so there's five columns, Y goes from 0 to 5 so there's
six rows. Let's assume that the coordinates refer
to the center of the grid elements. So there's a gate at 1,4 labeled 1, and a
gate at 3,1 labelled 2. And this is a 2-point net as we know.
What is the length of this net? It's just the length of this hypotenuse
of this triangle, so I'm just going to sort of draw this kind of like a
triangle. it's just the length of the straight
line, the blue straight line between gate 1 and gate 2.
And that's nothing more than x1 minus x2 squared plus y1 minus y2 squared.
So that's actually, pretty straight forward.
And if we were to, you know, actually calculate that that's going to be 3 minus
1 squared plus 4 minus 1 squared, do that math and the length of this wire is 13.
So, this is straight forward. Note that there's no square roots here,
okay? This is the squared, I'm going to write
this as squared, squared length here, okay?
It's the squared length between those two gates.
So, It's not as mathematically friendly if
you take the square root. but perhaps more interestingly, is,
What happens if your net has more than two points in it?
That's not at all straightforward. So, here is now, a k-point net.
K, in this particular case, is 4. So, I again have the grid, x goes from 0
to 4, y goes from 0 to 5. And there are four gates, gate 1 is at
1,4, gate 2 is at 3,1, gate 3 is at 3,3, and gate 4 is at 4,5.
And I've got a wire drawn here that's kind of the way a physical wire might get
routed. But it's not at all clear what quadratic
wirelength means here. And so, here's the recipe.
The first thing you do is you replace the one real net with k times k minus 1 over
2, 2-point nets. And the way to think of that is I'm just
going to add a new net between every pair of points, and that's how many points,
pairs of points there are. Right.
So this has a name that's called a fully-connected clique model.
this is pronounced cleeek clique model. And so, the way this one would work is,
I'm showing again the, the grid without any wires in it on the right here.
Gates at 1,4, 3,1, 3,3, and 4,5. And what I'm just showing is that.
If k is equal to 4, then 4 times 4 minus 1 over 2 is 6.
So what's going to happen is there's one 2-point wire, two 2-point wires, three
2-points wires, four 2-point wires, five 2-point wires, six 2-point wires.
I'm just drawing every wire in k times k minus 1 over 2 for k is 4, 4 times 3 over
2. There's six 2-point nets that we're going
to connect. So that's what you do.
You take the one multi point net when k is greater than 2, and you turn it into k
times k minus 1 over 2, 2-point nets. It has a name.
Sometimes it's called fully connected because obviously ever pair of gates has
a wire connecting it. More commonly it's called a clique.
So, here's that same example. I'm showing the clique model again the
grid, x goes from 0 to 4, y goes from 0 to 5, gates at 1,4, 3,1, 3,3, and 4,5,
and I'm showing all six 2-point nets. The other thing you gotta do is that you
have to wait, which is to say, multiply the length of each of these quadratic
wirelengths by a number. So let's just think about it.
You know, I used to have one physical net.
And I replace this one physical net with six nets.
And I'm going to measure the quadratic wirelength of each of those six nets.
It makes some sense that I need to multiply by some small number.
So that I don't dramatically over estimate how much wire this physical net
needs. And so the, there are lots of ways that
people do this, but the traditional weighting factor is 1 divided by k minus
1. So, in this particular example.
If we were to estimate the wire length. There would be six quadratic wirelengths,
which are squares of differences of coordinates.
And each one of them is multiplied, in this case, by 1 over 4 minus 1, which is
1 3rd. So this is 1 3rd times 4 minus 1 squared
plus 5 minus 4 squared. Plus 1 3rd times 4 minus 3 squared plus 5
minus 1 squared. 1 3rd 3 minus 1 squared plus 4 minus 1
squared. 1 3rd 3 minus 1 squared plus 4 minus 3
squared. 1 3rd 4 minus 3 squared plus 5 minus 3
squared. 1 3rd 3 minus 3 squared plus 3 minus 1
squared. Six 2-point quadratic wirelengths, each
multiplied by this weighting, that sort of reduces their estimated length.
Now the other thing I'll notice here is that when k equals 2, this weight is just
1 divided by 2 minus 1, which is 1, so there's no special treatment for the two
point case, right? So it all works out.
You always multiply by the weighting factor 1 over k minus 1 and when it's a
2-point net, nothing special happens. You just multiply it by 1.
So, there's one more big idea here, kind of an interesting idea.
To make the math work out easily, we're going to ignore the physical size of all
the gates. we're going to pretend the gates are
dimensionless points. Now previously in the iterative
improvement placer we also sort of ignored their size.
We pretended they were all the same size. But it's not like we actually said that
they had no size at all. We just assumed they were as big as the
square on the grid. We are now going to honestly pretend that
they don't have any size at all. They're dimensionless.
And the big thing is we're going to ignore the fact that the gates can't go
on top of each other. And as we shall shortly see the technique
we're about to develop puts lots of gates on top of each other.
It's going to be the second part of our algorithm is how we fix that.
This sounds strange but it allows us to write a very simple, very elegant
equation for the placement, and then to solve it quickly and effectively.
So why do we do these interesting mathematical tricks?
Why do we model the wirelength as a bunch of fractionally weighted 2-point
quadratic forms? And the answer is, because the math makes
it possible for us to solve. So the easiest way to see this is with a
little example. So I've got a little example here.
So I'm modeling the chip as box. X goes from 0 to 1, and y goes from 0 to
1. This is totally arbitrary, by the way.
this could go 0 to 1. It could go from 0 to 100.
It could be in microns. Doesn't matter.
The, the, the math will work out. And there are two gate points, they have
indexes 1 and 2, they are the green circles with one and two next to them.
And there are three nets, they're each two points to just keep things small and
simple and they have weights 1, 2 and 4 respectively, and there are two pads.
And I'm just putting a little arrow to the pads.
There are two pads. There's a pad at 0,0.
It's the red square. And a pad at 1,0.5.
The pads are fixed pins. Those are the things, if you will, around
the edges of the chip. That are the IOs, the input outputs.
And so there are three wires. There's a wire from the pad at 0,0 to
gate 1, with weight 1. A wire from gate 1 to 2, with weights 2.
And a wire from gate 2 to pad 1, 0.5 with weight 4.
And I'm just making the weights up, so you can see what happens when we do the
math. And the math all turns out nice.
So, it's very easy to write the quadratic wirelength.
And that fact's one of the reasons we do it like this.
So, if we just look at the problem, the first thing we see is.
I'm going to look at the wirelength from gate 2 to the pad at 1, 0.5.
That's 4. The length of the weight on the wire
times x2 minus x1 squared plus Plus 4 times y 2 minus 0.5 squared.
Where are those constant? Well, the pad is fixed at 1,0.5 so you
know, we subtract 1 from x and square it. We subtract 1 0.5 from y and squared it.
And the fractional multiplier or in this case the weight multiplier, it's not a
fraction is a 4. The other wire that connects gates 1 and
2 has a weight too so you get 2 x2 minus x1 squared plus 2 y2 minus y1 squared.
The final wire has weight 1, and it connects to a pad, 1 times x1 minus 0
squared plus 1 times y1 minus 0 squared. That's the components of the quadratic
wire length. You add these all together, and that's
it. So it's really as simple as that.
Now there's one other thing I'll have you notice, and this turns out to be very
important. If you look at these terms, there are no
terms where there's an x variable multiplied by a y variable.
In each one of these cases we get terms that look like xi squared, and xi times
xj, or yi squared, yi times yj. Right?
So if you look at the middle equation, right?
You're going to get an x2 squared, an x2 x1 and an x1 squared, you're going to get
a y2 squared, a y2 y1, and a y1 squared with some constants
And also for the wires that connect to pads, you're just going to get linear
terms, x2s and x2 squareds, y2s and y2 squareds, for example, on the first one,
but you're never going to see an x multiplying by a y.
This turns out to be extremely important because it means I can separate the x
terms and the y terms, and, as we shall see, I can actually optimize them
separately. So the next great question is, how do I
optimize this? So let's go look.
[SOUND]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
