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).
Technology Mapping Basics
Loading...
Do curso por University of Illinois at Urbana-Champaign
VLSI CAD Part II: Layout
20 ratings
Na lição
Technology Mapping
Technology Mapping! We omitted one critical step between logic and layout, the process of translating the output of synthesis -- which is NOT real gates in your technology library -- into real logic gates. The Tech Mapper performs this important step, and it is a surprisingly elegant algorithm involving recursive covering of a tree. Another place where knowing some practical computer science comes to the rescue in VLSI CAD.
Conheça os instrutores
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[SOUND].
So here we are in lecture ten. This is actually sort of the link between
the logic part of this course, and the layout part of this course.
So the course is called VLSI Cad Logic to Layout And the logic stuff.
We've done lots of bouillon algebra, computational bouillon algebra.
Representation, optimization, synthesis, lots of interesting stuff.
And on the layout side, we're going to be placing things.
We're going to be routing things. We're going to be figuring out how their
timing works. There's kind of a link and the link is
interesting. The link is actually a step called
technology mapping and you might think after all that interesting two level and
multilevel optimization that we did that what comes out is logic gates.
And the answer is no, what comes out of multilevel logic synthesis is a Boolean
logic network. Each of whose nodes is a sum of products
form, it's not gates and even worse it's not gates in the actual library of pieces
of gate technology that you get to put on the surface of the chip those are things
called standard cells. So, to start things off, we're just
going to talk about what actually happens at the end of logic synthesis.
And what you actually need to do to get started with layout.
I'm going to talk about the pieces of the optimization problem.
And what the problem is. So let's go talk about technology
mapping. So we are still in, sort of, in the
middle of our transition from logic to layout and one of the things I mentioned
in the last lecture is that there's really a missing step.
And because of our desire to actually start doing some interesting projects
with layout technology, we sort of inverted the order.
So, so we're going to go back to this now.
So, just to review what, what you know from the first half of the class is
computational Boolean algebra. A lot of really interesting
representations, some verification's, some synthesis technology.
This is the so called front end of the ASIC design process.
The back end is the layout the geometry end, and there's a big missing step which
is how do you actually go from the results of multilevel synthesis into real
gates for the layout and perhaps it's a bit of a surprise that you don't actually
get real gates as the result of multilevel synthesis and that's the topic
of this lecture. This stuff goes by a lot of different
names it's most formally called Technology Mapping, it's very frequently
called tech mapping just because it's shorter to say.
It's often just called mapping. depending on the application, sometimes
it's called fitting, sometimes it's called binding, but most commonly, the
stuff is called tech mapping or just mapping.
A nice reference for this stuff is sort of a broad reference of of a variety of
technologies for this stuff is the Nadia McKelly book, Synthesis and Optimization
of Digital Circuits. This is chapter 10 in that book.
So, let's talk about tech mapping, what is the problem?
The problem is that the multi-level model is still a little bit abstract.
So, you know, what happened in the multi-level synthesis technology that we
talked about. We figured out the structure of the
boolean logic network. And so in my, my little example here,
which has input's a, b, c, d. Three nodes in the network, X equals b
plus c, Y equals aX, Z equals Xd. We figured out the right high level
structure of the network. You know, what the nodes are and how
they're connected. And we also did ESPRESSO-style 2-level
simplification on the inside of each of these nodes, the yellow nodes in there,
or so, we optimized them well, but this is not really gates.
And the, the thing to just be, be clear about is that.
This diagram below, those are not logic gates, those are nodes in a graph that
has a particular kind of a structure. The boolean logic network there could be
thousands of those bubbles in a real version of this as the result of
multi-level logic synthesis. What if everyone of those nodes has a
half a dozen or 10 or 15 literals in its sum of products form?
It's not real gates, and the question is how do you get it to be real gates?
So, suppose that you actually have a particular technology library.
And suppose that this is that technology library.
Now, frequently, when we talk about the technology library.
The library of discrete standard cells that we are allowed to use as our basic
logic elements. It's very frequently just called the
technology. So suppose this is the technology that I
get to use. I get to use a 2 input and gate.
AND2 input or gate and a slightly strange looking thing called an OA21.
Its a two input OR gate feeding one of the inputs of an and gate.
And the other one is just a standard input to the and gate.
It's a little bit complicated. So this is the so called complex gate in
our library. The big question that we need to figure
out how to correctly answer, is if I give the output of multilevel optimization, in
this case, my little bouillion logic network with the x-node, the y-node, and
the z-node. How do we build the two Functions, in
this case the y function and the z function.
Functions of a, b, c, and d, specified in this[UNKNOWN] logic network using only
these gates from our library. Now, just drawing this picture again here
in my new slide. So this is a simple example.
So I'm drawing the library as a two input and A2 input or.
And this 0A21 To input or feeding one of the inputs of an and gate.
I'm drawing it with big curly set brackets just to emphasize the fact that
its an important object that we get to, work with and manipulate and play with.
In order to effect our technology mapping.
And I'm coloring this in in yellow, just to highlight it.
What we need to do is look at our Boolean logic network and say, if I only get to
use this and gate, this or gate and this strange OA21 thing, how do I actually
Take the logic function specified in the bouillon logic network.
And turn it into real logic gates. And look, this is just a really simple
example. It's set up to be a simple example.
One of the ways I could do this is I could do this example here.
I'm calling this the obvious mapping because look, you look at the logic
network, the x node is an or gate. The Y note is an end gate.
The Z note is an end gate, maybe we should just make the X note an orgate
with inputs B and C. And connect the output of the orgates to
2 and end gates. And the top end gate has an input A.
And the bottom end gate has an input D. And one of them makes Y and one of them
makes Z. And that's really just pretty obvious.
Now where this stuff gets interesting is that there are.
Less than obvious mappings and I am calling this an un-obvious, may be a non
obvious mapping and in this mapping I use two of these OA21 gates.
So, to implement the Y function I actually do this as 1 OA21 with inputs a,
b, and c. A goes under the AND gate, b and c go
into the OR gate and for output z I go d into the AND gate and b and c go into
the OR gate and you are thinking. Well this is a little bit strange, and
I'm, I'm just putting a little kind of a question mark here on top of the two OR
gates I'll even write two question marks. it would appear that I've duplicated the
Or gate, why why would I do that? You know, why would I choose the
un-obvious mapping? And let me give you an answer.
Why would you choose the non-obvious mapping?
the answer perhaps is cost. Perhaps it is the case that the
un-obvious mapping is superior in some dimension that I can associate with a
number. So imagine that every gate in my
library[UNKNOWN] has a cost associated with it.
May be it's the amount of silicon area in the, in the standard cell gate, may be it
has something to do with the power. That means there are all kinds of ways of
creating matrix for this but you know low cost is better and so I am just putting
cost numbers. The AND2 has a cost of 2, the OR2 has a
cost of 3 and the OA21 has a cost of 4. These are entirely arbitrary and now
somebody has to figure out what the right costs are but now I have got a picture of
the obvious mapping on the left at the bottom, one or two ends.
And then I've got a picture of the un-obvious mapping 2OA21's at the right
and what we can see immediately is if I put the cost values on the cost mapping
the or costs three. Each of the ands cost three.
This entire mapping cost three plus three plus three that's nine, but what if I put
the cost values on the un-obvious mapping?
Well each of these OA21 gates costs four, and so, putting two of those together
costs eight, eight is better than nine, this is a better mapping now (no period)
This is a quite synthetic examThis is a quite simplified example.
But in the real world, where you have large[UNKNOWN] logic networks.
And you have things that have, you know, hundreds or thousands or tens of
thousands of gates in them. What the right answer is is not at all
obvious. You need some kind of metric to guide you
for what the. What the best answer is associate cost
with all of the gates. Map so that you choose the lowest cost
covering. The lowest cost mapping of the Boolean
logic network on to the library that's going to get you an answer that makes
sense. So, the other way of saying why you
choose a non-obvious mapping, the sort of the second answer is that you know the
non-obvious mapping has better complexity.
And really this is just sort of cost in a, in a different way.
So for example, your library might have a bunch of complicated gates, so-called
complex gates. The are really hard to map to by eye, it
is pretty easy to figure out where you can put in 2, put AND gate or to input OR
gate or input invert but I am showing you to realistic gate cells.
On the left I am showing you OR, AND and Invert structure, this is a so-called
OAI22. So, it's a layer of OR gates connected to
an AND gate with an inverter at the output that's why it's called OAI and the
an answer to the question. How many and gates, sorry, how many or
gates are there and what are their structure?
The reason it's called a two two, is that there are two such gates.
That's why there's two digits there. And each of those gates has two inputs.
So you see a two input or gate. And another two input or gate.
So, that's why this is a two two, and let's say that that costs 6.
And next to that, on the right, is an and or invert structure, a different one and
AOI221. Again, an input bank of and gates, then
an or gate, and then a invert, a bubble. In this case, how many or gates are
there? Well, there's kind of three.
Alright the first 1 has 2 inputs the second 1 has 2 inputs and the third 1 has
1 input and, and you know, kind of the obvious way to think about why I'm just
drawing a wire going into this Or structure this Or Invert structure is
that this is really sort of an AND gate with exactly 1 input going into it and
what's an AND gate with 1 input going into it it's a wire.
So this is an AOI-221. Imagine that the AOI-22 cost 6 and the
AOI-221 cost 7. An interesting thing to note, it seem the
OAI and the AOI gate structures are often very efficient at the transistor level.
A bit more efficient than actually discretely using some ends and[UNKNOWN]
and inverts. And you know, for small versions of these
complex gates. These things are actually a sometimes a
better cost match and its much, much more difficult to match where these things go.
To technology map where these things go which is why we need an algorithim so,
It's helpful to introduce what I'm just referring to as a mental model, a kind of
a conceptual way of thinking about what multilevel synthesis does.
This is what multilevel synthesis does. It structures the multiple vertex Boolean
logic network well. What does well mean?
It means that the number of bubbles the structure of the bubbles, the number of
layers of, of you know, bubbles between the input and the output.
The complexity of the logic inside each of the bubbles, you know, pretty good.
And so, you know, following up on that as it minimizes or as it optimizes the
macroscopic structure of the logic network it minimizes the sum of product
contents inside each vertex so that the two level form that each vertex wants to
implement is also well structured in terms of the number of literals in the
sort of the macroscopic. Graph structure is also good.
The big, important thing to note is that optimizing the macroscopic graph
structure of the logic network, and optimizing the sum of products contents
of all of those bubbles is not logic gates.
And in particular, it's not logic gates in the technology library you are
permitted To use, alright? So this result actually has an
interesting name, a new name. actually a couple of names that you may
or may not have heard of. This is often called uncommitted logic.
Which is to say, I have not committed this to a particular set of gates from my
technology library. It is also called technology independent,
because we often call the library that we get to use, the technology.
And when the stuff that pops out of multi-level synthesis is not mapped yet
to the technology. We say that it's technology independent.
And so I've just got a little picture down here, there's an X node, a W node, a
V node, the X and the W nodes go into the Y node.
The Y node is an output, the W and the V node go into the Z node, The Z node Is an
output. Just to sort of highlight this, what
multilevel synthesis does is it gives a good global structure to the nodes, the
X, the Y, the Z, the W and the V in this diagram.
And it gives a good local structure to the insides, the sum of products forms
the sum of products inside the nodes like Z.
But this is not logic gates. So what does technology mapping do?
Technology mapping does something sort of interesting in an interesting way.
The first thing we do typically, is we transform this into uncommitted logic
that is made up of only very simple gates, but real gates, alright.
So a very common way of doing this is to transform every sum of products
expression inside each node, into something very simple, like NAND and NOT
gates, and nothing else. So, I've got a little picture of my
network from the previous page, you know, X, Y, Z, W and V nodes.
And I've got the X node and the Y node highlighted.
We know that those are sum of products 2-level forms.
What do we do? We turn the X node into.
NOT gates, inverters, and NAND gates. Now, one of the things to remember from
way back when in Boolean algebra, is that if you have a sum of products form, you
know, with AND gates for each product term in a big OR gate connecting it, you
can replace every AND gate and the OR gate itself with a NAND gate, and it will
all work properly. It's sort of an interesting side effect
of the De Morgan laws for how compliments work.
And so we're going to take all of the AND gates in the products and replace them
with NAND gates, and we're going to take the output OR and replace it with a NAND
gate. And then we'll just put inverters
wherever we need the literals to be in the complimented form, and we're going to
build, X the node, as real gates, but real simple gates.
So we're going to build it all out of NOTs and NANDs.
And then similarly we're going to take the Y node and then we're going to build
that, out of NANDs and NOTs. And so, it's got, probably a different
number of products, so it's got a different number of the input NANDs.
It's got, maybe a different. You know number of products and so the
size of the output end is different. Its got complements on different places
on the literals and so then the inverter gates are in different places.
But again, I can build the contents of the individual node, which is a sum of
products form, simple two-level form, as nothing but inverters and NAND gates.
We're going to do that for every single node in this network and then we're
going to connect things so, the X node connects as an input to the Y node.
And I'm just making kind of an arbitrary assumption that it connects to one input
on one gate, it could connect to a whole (no period) Bunch of different places
going in to the y node. But the big important idea is that we
need to take a step away from the abstract form of the Boolean logic
network to something that's real. Gates and our first step is an
interesting simple step. We go from the sum of products forms to
nans and nots and we do that for every node in the Boolean logic network.
And so what we're going to get as a consequence of that is this.
Sort of complicated looking diagram here. Where the X node, the W node, the Y node,
the Z node, the V node. Each one of those things is replaced by
some combination of NAND gates for the product terms.
NOT gates for the literals that appear in complimented form in a big NAND gate at
the output to implement the two level form.
A two level not NAND form for every sum of products form, and then the sum of
products forms themselves are connected properly.
So, what I get here is one big, flat and I'm referring to that in a very
particular way, okay? One big flat network of NANDs and NOTs.
This is what you map, what flat means in this context is that the boundaries,
between the X node, the Y node, the W node, the Z node.
All of those things go away. So one of the really important things to
note is that it's not as though I'm restricted to take the gates in my
technology library. And map them against them against the
insides of every yellow bubble on this diagram.
No, I take the logic function specified by every node in the diagram.
I flatten it out into 2 level NAND, NAND not structure.
I connect up everything appropriately and I throw the bouillon logic network away.
This big messy looking logic network with all of these NAND gates and inverters,
this is what we map, this is what happens next.
So, this is our strange and complicated looking starting point multilevel
synthesis produces well the first thing it produced was a bullion logic network
model with well structured microscopic form and well structured sum of product
form and what we did was we in a sort of a dumb brute force simple minded way.
We push that immediately into real gates, but very simple gates, NANDs and NOTs.
This big network, that I'm again highlighting on the, on the pager here,
this is what we start with, this is what we're going to map.
And the big and interesting question for us is algorithmically, how do I transform
this big network of NAND gates and inverters, how do I map this thing onto
the standard cells in our library in some optimal way?
So, this is a pretty algorithm as it turns out, a very nice application of the
ideas from the computer science universe to a really interesting hard problem, in
the[INAUDIBLE] universe, so let's go see how that works next.
[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.
