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: Recursive Partitioning
Loading...
来自 University of Illinois at Urbana-Champaign 的课程
VLSI CAD Part II: Layout
25 个评分
从本节课中
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.
与讲师见面
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND].
So here in lecture 9.8, we're going to continue our exploration of Analytical
Placement. The really amazing thing about the
quadratic wire length model is that I can write a giant equation for where the
logic gates go. And I can solve it using some calculus
and some linear algebra, and actually get as the solution to this equation, done
numerically, a placement. That's pretty amazing.
The problem is that because we made some key assumptions, and one of those
assumptions is that the gates are dimensionless points, we don't actually
get a legal placement. So, unlike the intricate methods where we
had a grid and every gate was located in one and only one cell on the grid, when
we're done with a quadratic style analytical placement, the gates can be in
one big blob in on little corner of the chip.
We're going to have to do something, a different kind of an optimization step to
kind of spread them out. And interestingly enough, we're going to
do something that's kind of recursive. We're going to chop the chip up into
pieces. We're going to figure out which piece the
gates need to go in. And we're going to formulate an
increasing series of smaller quadratic placement problems, each of which is
going to, sort of in a finer, and finer, and finer way.
Put the gates in the right place. So, this is recursive partitioning using
a quadratic style analytical placer model.
Let's go see how that works. We just introduced the full, sort of
mathematical model and solution technique for representing wire length as quadratic
clique wire-length model. pretending all the gates are
dimensionless points, optimizing the quadratic wire-length, which turns into a
set of matrix solutions. An a matrix and a bx vector, an a matrix
and a by vector, and we solve that and we get x-coordinates and y-coordinates.
What does it look like? It looks like this.
This is a small IBM ASIC a reasonably famous public benchmark with a few
thousand gates. And you immediately see the problem.
This doesn't look like a placement at all.
this is this big smear of gates right in the middle of the chip, and this little
sprinkling of gates in other places. this is a big problem, a new problem an
interesting problem, maybe an unexpected problem.
The quadratic wire-length model minimizes the wire-length for netlists in a
numerical way, but it totally ignores the fact that the gates have a physical size
and they can't be on top of each other. There is, and this is the beautiful thing
about the quadratic wire-length model. There is one solution that minimizes the
sum of the quadratic wire-lengths. And when you solve it, you get what you
get. And you don't necessarily get the gates
lining up in rows not on top of each other.
I've got to fix this. And it turns out there's a lovely
strategy for doing this which we can call Recursive Partitioning.
Lots and lots of recursive stuff in this class.
The recursion is a little more conceptual, it's not like the Shannon
co-factoring stuff, but you'll get the idea when we show you some pictures of
the geometry. This is a bigger industrial example.
I'm showing you this for a couple of reasons.
One, just because it looks cool. This is something that was done by one of
my students, Joan Shue. This benchmark is also from IBM.
This has about 211,000 gates, they are in blue, and about 543 fixed blocks.
Those are the red things. You imagine some designer has simply put
them down in the right places where they want to go.
And the image shows where the gates want to go if we modeled the blocks like big
pads, if you think that. and this is a quadratic placement where
we model all of the wires as two-point quadratic connections with appropriate
fractional weights. And we solve the placement problem so
there are pads around the outside, I'm just going to circle some pads.
Those are all pads, all those little skinny boxes around the outside are pads.
all of the 500 red boxes are either SRAMS or pads.
That's all the stuff in red. and the blue smear is the result of the 2
ax equals bx, ay equals by solved. So, why am I showing you this?
this is an example of how badly imbalanced the quadratic placement can
be. It can be terribly, terribly unphysical.
So look, almost all the gates want to go up in the top left.
That just says there's a lot of pads up there, and there's a lot of big dense
wiring groups that go from the SRAMS and the top left to all of the gates that
want to be there, but they can't go there.
So, we're going to have to do something really smart to make the gates go into
more physical, reasonable, realizable places.
So, the big idea is this recursive partitioning.
So, you do a first quadratic place, and I'm going to start calling quadratic
places QPs, because it takes less space on my slides.
And I'm going to write QP a lot. You do the first quadratic place and you
get some weird blob of gates that minimizes the quadratic wire-length.
Then, what you do is you partition the chip right in half.
And so, I'm just going to draw a big line over here.
You partition the chip in half, and you make a decision.
Some of the gates are going to go on the left, some of the gates are going to go
on the right. You formulate two new smaller quadratic
placement problems where you say, the gates on the left must stay on the left
and the gates on the right must stay on the right.
And so, I'll solve two new quadratic placement problems that are each about
half the size of the first one. And then, why this is recursive?
I will repeat. I will again partition things.
But I will partition the region on the left by drawing a line to the left and
the right. And I will partition the region on the
right. Similarly, by drawing a slice to the left
and the right, and I will say that the gates on the top on the left have to go
on the top, and the gates on the bottom on the left have to go on the bottom.
And so, I now get four regions, each with about 1 4th of the total gates..
I will solve four new smaller quadratic placement problems, and I'll see where
they go. And I will just continue to do this until
I get a placement that looks a little bit more like a real physical placement.
So, the one on the right I'm showing you here, and this is a real one, by the way.
This is the result after 16 QP solves. And you can just keep going until the
number of gates in each of these little cells, these little grid squares, is
something manageable. So, here's a high level recipe for how
recursive partitioning is going to work. These are the big steps.
There's the partitioning step itself. How do you divide the chip into new
smaller placement tasks on which we can run a smaller quadratic placement?
The assignment task says, which gates should go into each new smaller region?
So, we run quadratic placement on a region, then we partition the region into
two smaller parts, and we assign gates to each of the two parts.
Which gates go where? And there's the containment problem.
How do you actually formulate the new quadratic placement matrix solve so the
gates stay inside the new regions, but inside the new regions they go in good
places. Because one of the problems is that,
there are gates inside the region. The new region, the smaller region, that
are connected to wires that go outside the region.
How do we, how do we model that sort of connection from the inside of a smaller
problem to the outside? That's the containment problem.
And I'm going to talk about one early strategy from a classical paper.
So, this is a paper from Ren Song Tsay, Ernie Kuh and Chi Ping Hsu called PROUD:
A Sea-Of-Gates Placement Algorithm way back from December 1988.
This is one of the first generation of analytical sort of placers, one of the
first generation of quadratic placers. By modern standards, this is a very, very
simple kind of a placer. Modern, modern placers are very much more
complicated. The thing I like about the PROUD
Algorithm, it's really easy to explain how it works.
If you know how to do the basic quadratic placement mathematics it's not too hard
to explain the partition step, the assignment step, and the containment
step. They're all sort of fairly simple
geometrically. It's a quite elegant solution, it's
something you can actually, I think, get your head around.
So, so let's talk about this. How does this recursive partitioning
stuff work? Well, the, the first problem is, how do
we actually do the partitioning? And the solution is that, after the first
quadratic placement, we're going to divide the chip area exactly in half.
And for us, we're just going to pick vertically as the way to divide it.
Now note, this is completely arbitrary. You could divide it horizontally.
But for us, it doesn't matter. We're just going to do a vertical
division, and we want half of the gates on each side, right?
So, we're going to slice it and we want half of the gates to be on the left-hand,
and we want half of the gates to be on the right-hand side.
And the question is, how do we make that happen?
And why that could be a challenge is, and I'm showing you a little tiny picture of
the IBM ASIC again. What if the quadratic placement does not
spread the gates evenly between the halves?
And so, I'm showing you my little cartoon of a chip that's a square with some pads
around the edges, and there's, you know, about a dozen gates here.
And they're all kind of smeared in the blob on the left.
How do we know which gates to put on the left versus which gates to put on the
right if this thing that I'm showing you is the initial quadratic placement, or
set differently the quadratic placement is telling you they all want to go on the
left? What the heck am I going to do?
Well, that's just not acceptable, right? I have to do something that puts the
gates in a sensible set of locations. So, what I'm going to do again[SOUND] is
I'm going to partition the region that I'm placing exactly in the center.
And I'm going to reformulate a new quadratic placement for the gates on each
side. So my new problem is, how do I pick which
are the right gates? This is the assignment problem.
And the answer is actually lovely and simple.
I've sort the gates. So, I sort the place gates first on their
x-coordinate and then on their y-coordinate in the event that they are
any ties. And honestly, if these things are based
on floating point x's and floating point y's, you're probably not going to have
too many ties. But you're going to do this anyway.
First on x, and then if goes a tie, then on y.
And so, the answer is that even if all of the gates are smeared in a clump way over
on the left, when you sort it on x and then on y, you take the first N/2 gates
in the sorted list, those are the ones that go on the left.
All right, so that's those guys. Those guys go on the left, and all of the
others go on the right. And you have now taken the initial
quadratic placement and use the results of that placement, the x and
y-coordinates, to do the assignment problem.
Which gates go on the left? Answer, the half of them that are the
most on the left. It sounds simple but, you know, it's what
works. The leftmost half of the gates go on the
left, the rightmost half of the gates go on the right.
Now, we've got this thing that I'm, I'm calling the containment problem.
So, you've now decided which gates go on the left.
And so, I'm, I'm drawing the left part of the chip as a grey box.
And I'm saying, let's focus on the gates inside this shaded region, R, on the
left-hand side of the cut. I need to formulate a new quadratic
placement problem to properly locate those gates in a region that's now the
same height as the original QP problem, but half the width.
And the new problem is, I want to solve a quadratic placement problem and I want
all the gates to stay there on the left hand side.
And I've really got two things that I've got to worry about.
The first is, how do I keep the gates on the left-hand side on the left-hand side?
How do I keep them in the gray box? And the second part is, how do I model
the wires that connect from those gates on the left-hand side to the gates and
pads on the right-hand side because, you know, I cannot ignore those things?
You know, the reason that the quadratic placement problem is you know, is so
attractive and why people like this method is that it optimizes the lengths
of all the wires. If in the partitioning problem we ignore
the fact that there are, say a whole bunch of wires that connect the gates
that are not on the left-hand side, we're going to put those gates in the wrong
place. You know, the gates that are heavily
connected to the gates on the right-hand side, they probably be want to be on the
right-hand side of the grey box. I can't just take all those wires and
make them vanish, I have to do something with those.
So again, there's a geometrically very attractive solution, and it's got a funny
name. we're going to do something called
Pseudo-pads. These are also called Pseudo-pins,
sometimes. The basic idea is that every gate and pad
not inside region R is modeled as a pad on the boundary of R.
And the word that we use is propagate. We propagate these outside gates, or
outside pads, using their current xy location to the nearest point on R, which
is the grey box. And so, for this simple first cut we just
take the y-coordinate and we put the pad on the center line, so that's the, that's
the center line. So, you know, what actually happens here,
right? Is that anything that the gate was
connected to in R, that's connected on the right-hand side.
So, imagine that there are a couple of gates which are the red circles, and a
pad which is the red square. We take those things and we just slide
them leftward and we pretend that they really live on the cut line, on the star.
And so, we are not ignoring them. We're sort of doing the right thing.
We are putting them in the right position on the boundary of region R so that when
we replace all of these gates, right? When we do a new quadratic placement,
there is some effect. You know, the gate on the top right is
being pulled to a pad on the top right because that's where the real pad is.
And the gates in the middle are being pulled to the rightward boundary because
there are pads there that pretend to be like the gates that they are connected to
only those pads aren't moving. So, this is what you get the resulting
new quadratic placement problem for the gates in the left-hand region.
And one of the reasons why this works so incredibly well is, remember the model of
the wires as being like springs. If all of the pads are on the boundary of
this new region, the gray region, and all of the wires are like springs, when we
solve for the new gate locations, they're all going to stay inside the gray box.
Because the springs between the wires between the gates pull the gates closer
to each other, and the springs to the paths pull the gates close to the paths.
But there is nothing that's going to pull the gate outside the box, right?
So, by propagating the gates and paths outside the region to the boundary of the
region, we get a quadratic placement problem that has the property that when
we solve it, the gates will stay inside. And they will still respect the fact that
the system stuff outside that's connecting to them and kind of pulling
them to one part or another in the grey box.
So, this is kind of the summary slide here.
Why containment and propagation are so critical.
On the left-hand side, the first point is you cannot ignore the gates outside the
region that you're replacing. You want the gates inside the gray box on
the left to feel some pull from the wires to the gates and pads outside the region.
The pseudo-pads do this for us. So, there's all these blue wires, okay?
there's all these blue wires here that are connected to things outside the gray
region. The pseudo-pads pretend to be the gates
,and the paths that are not available to us to place anymore.
So, the gates inside, they, they sort of go in the right place.
And on the right-hand side, the pseudo-pads also guarantee containment,
right? They guarantee that the gates locate
inside the region. if you think of the pads as fixed things
that the springs are connected to when the springs pull the gates toward the
pads, they're never going to pull the gates outside the grey region.
So, the pin propagation, pad propagation stuff does the right thing in terms of
keeping a good global solution quality. It means you don't ignore the gates that
are connected outside the gray region that you're replacing, and it means that
containment is achieved. The gates stay inside the boxes as the
boxes get smaller and smaller. So, this sounds maybe a little bit
complicated. So obviously, the next thing is to do a
little tiny example in a lot of detail. So, let's go do that next.
