0:00
[SOUND].
So here we are in lecture nine and as you know the title of the course is VLSI Cad
Logic to Layout. So we had to get to layout eventually and
here we are. So we've done lots of work in the boolean
algebra logic hardware universe. We've done representation, we've done
optimization, we've done synthesis. We sort of know how to make the gates.
Right, what we have to do next is we have to figure out geometrically where they go
and how we connect them. And so, we're going to move into the part
of the course where we get to talk about layout.
And we're going to start by talking about ASIC placement And so this is the
question of, now that I have a million gates, where do they go on the surface of
the chip? And so, what we're going to start with is
a sort of an overview of just what's the terminology?
What does the technology landscape look like?
What do we have as the basic placeable elements?
What's the technology components of this problem.
And then we can start actually talking about some interesting new geometric
algorithms. So, let's go look at the basics to get us
started with ASIC placement. So, this is a little bit of review here.
What do you know? I think you know a lot about
computational boolean algebra at this point, I think you know a lot about
representation You know a little bit of verification.
You know a lot of things about synthesis and optimization for two-level and
multilevel logic. This has a name.
This is called the front end of the ASIC design process.
So if you, you want to think of this at a very high level.
Give a high level description. You know, something that comes in, in say
VHDL or Verilog. There's some compiler like things that
happen that, that turn that into a form that, to which we can actually apply, all
of the synthesis and verification technologies that you now know.
And what comes out of that is a connected set of gates and wires in the Technology
associated with your chip, that has a name that's called a netlist, we'll,
we'll revisit that in a minute. What you don't know is the next part of
the ASIC design process, which is called the back end problem.
Turning these IC's into masks to build real chips this is called layout.
it's also called physical design, which is a named that is kind of a hold over
from a very early[INAUDIBLE] . Days of the the electronic business when
people were putting little you know, little packages on big boards in order to
build any kind of electronic system. We're going to start with something
called the placement problem, which is how do you locate those gates on the
surface of a Of a piece of silicon. But, but to do that,
I need to back up just a little bit. So, in honest fact, there's 1 missing key
step. So, what comes out of multi level
synthesis is not actually gates. it's a Boolean network model.
It's a, it's a graph of nodes. Each of which is a, a 2 level sum of
products form. as I'm showing here I'm actually picking
one of the pictures from one of the assignments for this class and and just
showing it here. What comes out of multi-level synthesis
is actually not logic gates. We have to do something to turn it into
logic gates. And there's a key step.
And that step is called Technology Mapping.
That transforms the abstract form of the above network.
The result of multi-level logic synthesis into real logic gates and wires.
I'm going to cover this next week and not this week because.
We're actually going to do a programming assignment in this mook, that's a placer.
And I need to just get you the, the methods and models and mathematics and
algorithms of placement in order to let you do that.
So we're doing this a little bit out of order, and I just want to explain why
we're doing that. So, placement for ASICs.
We're going to focus on the most common tasks in, in layout, and what we're
going to focus on are layout tasks associated with row based standard cells.
So, synthesis and mapping is going to give us a net list of gates and wires.
Our job is to place them optimally in rows on regions of the chip and to route
the wires that connect everything. So this is a chip I showed way back when
at the very early, lecture. introduction to the class.
And I'm just highlighting. Two two regions on this chip that are
actually rows of standard cell logic. that's the job that we're going to do
when we start looking at the layout problem.
Now, what do you start with? You start with something called a
standard cell library. And this is a slightly confusing name.
So, just to very clear about this. This is a library.
And the things that are in this library are themselves called standard cells.
And a standard cell is a basic logic gate or a small logic element, that you get to
use to create the substance of your design.
So, the way to think of this is, this is the set of allowed logic elements you get
to use to build your chip, so you get, for example, you know, inverters, and you
get NAND gates with, let's say, you know, a couple of different numbers of inputs,
and you get NOR gates, and you get some little tiny Useful things that are, are
used all over the place like one bit ADDERs and two to one multiplexers, and
so on. And you also get sequential elements
things like d flip flops and registers. Why do we restrict ourselves to operating
with these, if you will, predefined elements?
And the answer is that there's lots of complicated electricity stuff going on at
the transistor level. Each of these cells in our standard cell
library hides all of this difficult electrical detail and presents a simple
geometric abstraction that we can use for our geometry design algorithms to work
with. So, an interesting question, how big is a
standard cell library? how many cells are there in a cell
library? And the interesting answer is they're
often pretty big. you have to have all of the logic
functions that you need. You have to have all of the input and
output variants, in terms of how many pins.
There are often several timing variants things that are fast but have higher
power or slow and have lower power. Different sorts of electrical drive
strengths, and so on. At a very high level the way to think
about this is that there's a lot of different logic functions.
So, you know, and and nand, or and nor, xor and xnor.
Things like that. And a bunch of different kinds of flip
flops. There's a lot of fan in and fan out
variants, so you probably want NAND gates that have two inputs and three inputs and
four inputs for example. Ditto for all the other kinds of basic
logic gates. There's a lot of different timing
variations. There's a lot of different kinds of flip
flops. there are a lot of, if you understand
anything about how Testability is done on a modern chip with scan chains.
There are a lot of different scan variations on flip flops.
And if you don't know what that means, don't worry about it.
I'm just sort of mentioning it as to one of the things that adds variation to a
cell library. And there's a lot of different electrical
variants, let's say drive strength kinds of variants.
You multiply all those things together, it's easy to have a library with 1,000 or
more. Standard cells.
How should we think about what's inside a standard cell?
think of a standard cell as a, as a, as a geometric container for the circuits, the
electrical circuits, the transistor-level circuits that you need to make the logic
functions. So inside the cell, there's complex
devices, you know, transistors and wires and things, complex geometric mask things
happening right down at the, sort of the nanoscale surface of the, of the
integrated circuit. Complicated electrical issues, but
outside the standard cell, it's a box with pins.
And that sounds you know, a little simple minded, but really in order for the
geometry things that we need to be able to do to optimize at the level of
millions and millions of standard cells and wires, we need a simple abstraction.
And the abstraction that it's a box with pins is going to work for us.
7:47
let's look at a few real standard cells. This is in an older technology.
This is 130 nanometers CMOS. You know, where we are today you know,
lots of things are at the 32 nanometer node.
There are some things, you know, popping out at the 22 nanometer node now things
at sort of 15 nanometer node are in, are in, are in research.
So this is an, an older technology. these are some pictures of some things
from a website, www.vlsitetechnology.org, that has a bunch of open-source cells, so
if you want to actually look at Transistor level designs.
And, and, you know? Geometry designs.
It's just an interesting place to go. 2 things that I want you to take away
from this. The first is, here's a first fact.
They all have the same height. And the reason is that we want to be able
to arrange them in rows. And when we arrange them in rows, we can
snap them together, if you will. We can.
Put the power grids down so that the, the vdd and the vss power connect, we can
make all of this stuff work. The second geometric fact to be aware of
is they have very different widths as I'm, I'm showing you here.
So, the cell on the left hand side is a NAND2, that's a, that's just a two input
NAND gate, and the cell on the right is and Edge-triggered, D Flip Flop, so it's,
it's going to have, a D input, it's going to have a queue and a queue bar
going out, it's going to have a clock. Right, going in the D Flip Flop is much,
much bigger than the NAND. And the reason it's got a lot more
transistors in it to be able to do what it does.
So standard cells, they all have the same height.
We snap them together in rows. And they have different widths because
they have different circuit complexity. In a realistic context, what we are
talking about is placing the insides of one block on a, on a big system on chip
kind of design. So here's an actually a real SOC design
courtesy of my My friend and colleague Larry Pileggi at Carnegie Mellon
University, Big, system on chip designs, big SOCs are
often designed hierarchically, which means you figure out how, what each of
the blocks is supposed to be, and then you may have, you know, hundreds of
blocks that get put together in an appropriate way.
To make a big SOC, and what's being shown in this particular picture of an SOC
that's in the middle of being designed is there's a lot of pins around the edges
and those are all the little slice things with the little colors.
And then there's a bunch of blocks inside the SOC and some of them have a colored
boarder, but they're gray. Those things are actually big memories,
and you don't get to play with their insides.
They get generated by some other kinds of CAD tools.
But the things that have blobs of primary color, those are actually blocks that are
being placed. And the reason that there are sort of
funny shapes of the colors is that we are actually tagging and color coding where
the blocks came from in the original source.
let's say the verilog or the VHDL, and we're seeing sort of where did the gates
actually go when we're doing the layout task.
For our purposes, you can pick one of those rectangles and say, how am I going
to place the however many hundred thousand or you know, half a million or a
million gates Associated with the insides of one of those blocks.
How am I going to arrange them in rows in some optimal fashion?
How am I going to place them in rows, and how am I going to route them?
That's actually what we're going to look at.
So, let's just talk for a little bit about the size distribution on standard
cells. The big thing to note is that small cells
dominate but there's lots of wide cells, too.
So this is an old example, but a published example.
It's about 206,000 gates from an IBM ASIC.
It's actually part of an IBM processor, way back when, in the late 1990's.
It's done by Jens Vygen Of the University of Bonne.
And this would be, sort of, 1 small block today on a, on a big SOC.
You know, a big SOC may be, you know, 20 million gates, 50 million gates, 100
million gates, a really, really big one. And what I'm showing on this graph is
that on the horizontal axis, we are showing, basically, the width of the
cells. Right, and you can think of the width as
being how many pins wide is the cell, as I showed on the previous example.
And on the vertical axis we're showing the number of cells, and so there's about
200,000 cells, 200,000 gates in this design.
And what you're seeing is something is one cell wide, that's just some sort of a
filler, but you know, you know how many cells are two pins wide, oh something
like, you know, 27,000, three pins wide, maybe 27,000 Four, five, six pins wide, a
few more than 20,000, seven pins wide, only 10,000, eight pins wide, again
25,000, that's a nice round number, nine, ten, 11, 12, 13, 14 pins wide, you know,
just a couple thousand, but then an interesting bump out around 17 and 18
pins wide, you know, more than 10,000 cells, and then you know, down in the
noise. The way you can sort of think of this is
that most of the small gates dominate, you know, the things with the two, three,
four inputs, that's mostly what the net list is made out of.
and just as a concrete example you know, what is this bar over here with 27 or
28,000 things that are two pins wide? and the answer is that you know, that's
an inverter, right, because as a standard cell that's got one pin for the input and
one pin for the output. And what's this peak out here with things
that are 17 or 18 standard cell widths wide.
Probably, that's a mix of things, like little registers with, maybe, 4 bits,
maybe 8 bits depending on how it was how it was implemented.
But that's also probably things like flip flops, you know, with a D input and a Q
output in a clock. So, mostly small cells dominate.
Very small cells, things like two input NANDs, two input NORs, one input, one
output inverters, but there's also a lot of things like flip flops in a modern
design. there's an interesting, sort of an aside
that I just wanted to share with everybody.
it's, it's sort of the way people use language to talk about chip size.
So this is a strange question. How bit is a 100 million gate ASIC?
And surprisingly, it is almost not 100 million gates.
the numbers are usually referred to in one of two ways, and the most common is,
let's say, equivalent small gates. So the idea is that because there are
lots of things on the surface of the chip, little gates, big gates,
Adders, flip flops, all kinds of other stuff,we sort of transform them into an
equivalent number of let's say 2 input NAND gates.
So if we, as I'm showing you in the middle of this picture so here's a two
input NAND gate, so how big is that? Well that's like one input.
And here's something called a AOI22, so its 22 input and, a two input OR and an
inverter, that's an atomic gate in a lot of cmoss libraries.
That's maybe four gates in size. And then I've got a picture of a one gate
adder, how big is that? maybe six gates.
And then I got a picture of a D flip flop, how big is that?
maybe ten gates, maybe more. the idea is you take all of your real
logic elements, the ones you get to use in your technology library.
And you sort of replace them with an equivalent number of gates.
And when someone says, how big is your design, you add up those numbers of
2-input NANDs and you use that. So, there's two things that people might
tell you when they tell you how many millions of gates in their ASIC.
One of them is gates. This is usually an equivalent little NAND
gates, so this is usually a big number. The other is a term you might not have
heard before called instances. This is the number of things you really
used in your library. This is the number of things you really
placed, you know, the number of things you actually had to find space for and
put wires to connect to on the surface of your chip.
And the basic rule today is that the instances is basically the gates divided
by 4 or 5. So, you know big round numbers, if
someone tells you they have a hundred million gate ASIC, how many instances are
there? Probably 20 million.
Five is probably the best number to use today, and honestly, they might not even
all be gates. people might be taking their very large
static RAM, SRAM memories and other blocks and converting those into, an
approximate equivalent number of gates in terms of their silicon area, so If
someone tells you they have a 100 million gate ASIC, they probably don't actually
have 100 million logic gates. They probably have a maximum of 20
million, might be less. So, what's our first problem as we
actually talk about layout in in our MOOC?
Our first problem is placement, and I've got a nice little diagram here.
Up at the top, there's a picture of a netlist.
The netlist goes through a box that says placement.
And that turns into a bunch of rows of little gates and standard cells.
That goes into a box that's called routing.
And suddenly, little wires appear that connect all the gates.
What does a placer do? A placer starts with a netlist of gates
and wires and the output is the exact location of each gate.
You know, where does it go? And the goal of the placer is to be.
Creating a placement that allows us to route, which is to say to connect all of
the wires. That is the most fundamental plask...uh,
the most fundamental task of the placer. Is this hard?
Oh yes, very, very, hard. A bad placement could lead to an enormous
amount of extra wire, and if you have more wire, your chip may need to be
bigger in order to be able to fit those wires.
And it's going to be slower because there's delay to get your signal through
those wires, and there's going to be more power because taking voltages up and down
on all those wires is actually you know, consuming energy.
It's very bad. And if the placement is extremely bad,
the next tool in the flow, which is called the router, might actually be
unable to connect all the wires or to meet the timing requirements of your
chip. So, placement is an extremely important
task. Very critical task.
Very critical for us to get right and so, it's the first task we're going to focus
on. So, let's go talk about how we really do
placement.
[MUSIC]