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).
Wirelength Estimation
Loading...
Do curso por University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
36 classificações
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
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.2, we're going to start talking about the real technical
part of ASIC placement. And to first order any placer for logic
gates optimizes things. And what it optimizes is an estimate of
the amount of wire it's going to take to connect all those gates.
That estimate is usually called the Wirelength, right?
And the reason we estimate it is because the actual physical act of connecting
those wires, which is called routing those wires, is computationally pretty
complicated. So, we actually have to build some
appropriate mathematical estimators that our optimization algorithms can use.
So, to start things off, talking about the technology of ASIC placers, we're
going to start with some classical forms of wirelength estimation.
So, let's go see how that works. The easiest way to talk about how a
placer works is to build, so let's build a very simple basic placer to start.
And so, we need to start with a simple model of the chip surface itself, and so
the simplest thing is to just use a grid. So, think of this as like a chessboard.
there is a set of slots, or cells that we can use.
And the gates, which are the cells from our standard-cell libraries can go in the
grid slots. And any gate can go in any slot.
You're allowed to put exactly one gate in each one of those slots, and it's okay if
the slots are empty. This is a very simple model of the gates
because it assumes that the gates are all exactly the same size.
And that is extremely unrealistic. But it dramatically simplifies things.
And so, we're just going to go with that in order to get started on, on looking
how we, how we deal with a real placer. So, a grid.
Every slot can hold exactly one gate or exactly zero gates.
It's not okay to put more than one gate in a slot.
All of the gates are the same size. So, we know what the representation is.
What are we trying to do? What does a placer do?
A placer optimizes the ability of the router to connect all the nets.
That's the first thing a placer does. But, the router, which is the tool that
actually puts the wires down and finds paths to make all the wires, you know,
possible. Routers are computationally expensive
things. You can't run one inside the placer.
I need a simplifying approximation. And so, what every real placer does, and
this is no exaggeration, what every real placer does is it minimizes an
appropriate mathematical model of the expected wirelength.
And, to be more precise about that, for each wire in the design, there is an
estimate, an approximation of the expected length of the routed wire.
And we add all of those expected lengths together, those estimated lengths
together for every single wire. So, we sum over all of the wires in the
design, the estimated length of the wire, we add them up and we minimize that.
That is what a placer does. A placer optimizes the estimated lengths
of the wires and solves for locations for the gates that minimize that estimated
wirelength. That's what a placer does.
And, you know, to first order, you could actually categorize the very many
different kinds of placers that there are by the mathematical model they choose to
use for the wirelength. Now, we need a little terminology so that
we can all talk about these things the way people who really do ASIC layout talk
about them. So, the first common term is that the
term for a wire in a layout is a net. So, we call them nets.
And the whole set of gates and wires together is called the netlist.
So, the thing that comes out of multi-level logic synthesis, and then
followed with technology mapping is a netlist.
The thing that goes into your placer is a netlist.
And nets are actually categorized by how many things it connects, and we tend to
call these points. So, I've got a nice simple little example
on the left. I've got a grid that goes from 0 to 4,
it's got five columns on the x direction and the y vertical direction, it goes
from 0 to 5. It's got, you've got six rows and I've
got a two-point net, so I've got a gate at x,y, 1,4, and I've got a gate at 3,1,
and I've got a little blue wire connecting them.
And so, it's really clear that this is a two-point net because there's two gates
that it's connecting. and if everything in every netlist looked
like this, we probably wouldn't be talking about this and we wouldn't be
giving it special terminology. But the problem is they don't look like
this. They also look like this.
So, on the right-hand side, I'm showing you a four-point net.
And so, again, the x grid goes from 0 to 4.
The y grid goes from 0 to 5. There's a gate at 1,4, there's also two
gates at 3,1 and 3,3, and another gate at 4,5.
This is a four-point net because there is a wire connecting four separate points.
This is, in some sense, why we don't just call it a wire.
Because there's a lot of wires that are going to get created to actually route
this thing and connect this thing all together.
And in answer to the first maybe obvious question, which is how is it the case
that there are actually things like wires that have more than two things that they
connect? the obvious answer is, there's fanout.
And I've even got it drawn with the gates sort of showing their directions as
though. There's a little AND gate at each one of
these grid cells, and the inputs appear to be coming from the left.
And the output appears to be going to the right.
And so, there's a gate in the 1,4 location in this grid that appears to be
driving the inputs to three other gates. The ones at 3,1, 3,3, and 4,5.
So, how is it possible to have things with more than two pins, two points?
The answer is fanout. And in modern[UNKNOWN] there are lots of
things that happen to connect to many things at the same time.
So some, some elements of scan chains and the testability components of logic you
know, there are things in the clocks that actually synchronize all the flip-flops.
There's some very, very high fanout nets. In fact, there are often special kinds of
routing technologies to connect those things.
So, it's not just like you can have K.net where K is 4 or 5, you can have K be
hundreds. So, about the wirelength estimation,
there are many, many different kinds of estimators.
And in fact different placers depend for their foundational methods to a large
degree on the kind of wirelength estimator that you pick.
So, why is it hard to estimate the length of wire that's going to be used to
connect the nets? And the answer is that multi-point nets
can be routed in many different paths. And in a dense layout, nets do not all
get routed in their shortest path. I mean, the inside of an ASIC and the
inside of a 20 million or 50 million gate ASIC, it's a very crowded place.
Even with lots of physical layers for wiring, it's a very crowded place.
Nets just don't get to go in at their minimum possible length.
So, a concrete example here. I've got the same diagram that I had on
the previous slide. a grid.
x goes from 0 to 4 on the bottom. y goes from 0 to 5 on the top.
There's a gate at 1,4. Gates at 3,1, 3,3, and 4,5.
And there's a very straight little wire connecting them.
You know, this is basically about the best I can do to wire this, this
particular design. I can't really probably do better than
this than this, this little example here. But in the middle, I'm showing something
that you know, it's a kind of a different looking wire.
Now does this have a little more wire? Yeah, this is, this is just a slightly
longer than the, you know, than the previous wire is just because of the way
things escape from the, from the topmost gate.
But, you know, this is still okay. I, I would even say maybe this is good.
You know, this is a particular, this is a good path.
You know, it's just a little bit worse than the previous path.
But now on the right-hand side, I'm showing an appallingly bad gate
wirelength. it's again, the same example you know, x
is you know, 0 to 4, and y is 0 to 5. but the, the wires are snarled all over
the place. They seem to go way out of their way to
connect things. And, and there's nothing else to say
other than, you know, this is pretty bad. And the reason this is pretty bad is
probably there's 20 million other wires that are trying to get routed, and this
one just didn't get able to be routed short.
And in real designs, that just happens. So, estimating what the length of the
wire is, is actually quite challenging. We have to estimate something that is a
reasonable model of what the wire might actually be.
And so, what we tend to do is, is estimate a best wirelength.
We tend to estimate the best and then we, we do some other techniques to sort of
deal with the fact that they're not always going to come out this good.
So, the most famous estimation for a wire is called the Half-Perimeter Wirelength,
and sometimes abbreviated HPWL. But it's also called the Bounding Box
Wirelength, usually BBOX, BBOX. And you'll see us using them
interchangeably in this lecture. The idea is pretty simple.
I'm going to describe it in words first. You put the smallest bounding box you can
around all the gates. So, let's assume in the little grid
things that I'm showing you. The gate lives in the center of the grid
slot. And the coordinates that are labeling x
equals 0, 1, 2, 3, 4 in the example I'm showing on the bottom left, y equals 0,
1, 2, 3, 4, 5. Let's assume the xy coordinates are the
center of the cell, the grid. And that the gate lives on that, that
coordinate. And so, what we do is we put the smallest
possible box around all of the gates. And then, we measure the width of the
box, delta x, and the height of the box, delta y, and we add them together, and
that's our wirelength estimate. So, for this little example where there's
a gate at 1,4 and a gate at 3,1, the first thing we do is we put a bounding
box. And so, the box goes from x equals 1 to 3
and y equals 1 to 4. And then, we simply we do the math.
Delta x is 3 minus 1, that's 2. Delta y is 4 minus 1, that's 3.
We add them together, 3 plus 2 is 5. The half-perimeter wirelength is 5.
And one of the great things about the half-perimeter wirelength is that it's
easy to do a multi-point net. So, here's a four-point net again on the
x equals 0 to 4, y equals 0 to 5 grid gates at 1,4, 3,3 3,1, 3,3, and 4,5.
We again put the smallest bounding box, and that goes from x equals 1 to 4 and y
equals 1 to 5. And then, we again, we can do the math.
Delta x is 4 minus 1, that's 3. Delta y is 5 minus 1, that's 4.
The half-perimeter wirelength estimate for this gate is 3 plus 4, is 7.
So, the great thing about the half-perimeter wirelength, it's easy and
it works for multi-point nets. So, more generally, the half-perimeter
wirelength, the general formula that I'm showing here is, you look at all of the
x-coordinates of all your gates, you take the max.
You look at all the x-coordinates of your gates and you take the min and you take
the max minus the min. Then, you look at all the y-coordinates
for your gates, you take the max. You look at all the y-coordinates for
gates, you take the min. You take the max minus the min, and
that's what you add together. The maximum, the x-coordinates for the
gates minus the min of the x-coordinates for the gates plus the max of the
y-coordinates for the gates minus the min of the y-coordinates for the gates,
that's the half-perimeter wirelength. One of the important things to note is
that this is always a lower bound on the real wirelength.
Which is to say, it is always less than or equal to the real wirelength no matter
how complex the final routed path is. You need at least this much wire.
And look, this just makes sense. You need to go from the gate on the far
left to the gate on the far right. That's delta x amount of wire from the
previous diagram. And you need to go from the bottom most
gate to the top most gate, and that's delta y amount of wire.
And no matter how you route this path, you need delta x plus delta y amount of
wire. So an important aside to note is that,
all of the wiring on big chips and most of the wiring on big printed circuit
boards is strictly horizontal and vertical.
There's no arbitrary angles for manufacturing reasons.
That's rigidly true for integrated circuits these days, big modern digital
SOC designs. there is some funny all angle wiring to,
to do things like get out of complicated pin arrangements underneath the big
chips. But once you escape from the pins near
the chip then you know, it already actually go across the board strictly
horizontal and strictly vertical. So that's just another reason the HPWL is
a good estimator because it just does a nice job of estimating the lower bound on
the amount of wire. No matter how many points you have, no
matter how many pins you have, no matter how many gates you have on your net.
this is just interesting, this is what the actual half-perimeter wirelength
estimation distribution looks like for a little design.
So this is old data. So this is 165,000 gate ASIC from the
late 1990s from Jens Vygen's group at Bond/g.
this is 181,000 net. So you know, call it about 200,000 nets.
I'm showing you this because it's just sort of an, an interesting piece of data.
the horizontal axis here shows a histogram buckets for the wirelength.
So, 0 to 0.5, 0.5 to 1, 1 to 1.5, 1.5 to 2, 2 to 2.5, 2.5 to 3, 3 to 3.5, etc., up
to 4, 4.5, 5, 6, 7, 8, 9, 10. And then, note at the end the buckets get
bigger, 10 to 15, 15 to 20. this is actually in millimeters, this is
a really old chip. So, it's one of the things to be aware of
is that this is a really old chip. so don't think about this as being
anything other than a a normalized number.
And note that the vertical scale is a log scale, right?
So, the vertical scale is a log scale. The vertical scale says, how many nets
have this length? So, you know, question.
How many nets are the shortest possible length between 0 and 0.5 in whatever
units are appropriate? And the answer is 100,000 of almost
200,000 nets. How many nets are between 0.5 and 1?
and the answer is, as far as I can tell, probably about 30 or 40,000.
Remember, this is a log scale, maybe 20,000.
the idea is that most nets are short, most nets are very short.
But unfortunately, there's a really long tail, and there are nets out here that
are you know, 40 times longer than the shortest net, and those nets are not zero
in number. So, real routers deal with the fact that
most of the nets are short but there's a non-trivial number of nets that are long.
And so, is just an interesting data that shows you that in a concrete way.
[MUSIC]
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.
© 2019 Coursera Inc. Todos os direitos reservados.
