A modern VLSI chip has a zillion parts -- logic, control, memory, interconnect, etc. How do we design these complex chips? Answer: CAD software tools. Learn how to build thesA 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 first part of the course is on key Boolean logic representations that make it possible to synthesize, and to verify, the gate-level logic in these designs. This is the first step of the design chain, as we move from logic to layout. 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: Computational Boolean algebra, logic verification, and logic synthesis (2-level and multi-level). 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. Exposure to basic VLSI at an undergraduate level is nice -- but it’s not necessary. We will keep the course self-contained, but students with some VLSI will be able to skip some background material.e tools in this class.
2-Level Logic: The Reduce-Expand-Irredundant Optimization Loop
Loading...
From the course by University of Illinois at Urbana-Champaign
VLSI CAD Part I: Logic
77 ratings
From the lesson
2-Level Logic Synthesis, and Multi-Level Logic Synthesis via the Algebraic Model
In Week 3, we will move from "representing" things to "synthesizing" things. In this case, synthesis means "optimization", or maybe the word "minimization" is more familiar from hand work with Kmaps or Boolean algebra.
Meet the Instructors
Rob A. RutenbarAdjunct Professor
Department of Computer Science
So, here in lecture 5.2, we're going to continue looking at 2-level logic
synthesis. And I have to admit, this is probably one
of the most complex sounding talk titles I've got, The Reduced-Expand-Irredundant
Loop, which sounds very impressive, indeed.
And is the name of an extremely famous heuristic for doing 2-level synthesis,
2-level optimization, that uses the idea of reshaping a cover so that we get a
good, but not necessarily perfect, solution.
And so, what we're going to do in this lecture is, we're going to take a high
level tour through all of the key steps of this famous heuristic method for 2-level
logic optimization. So, let's go see how that works.
So, let's assume we are starting with a truth table.
But just to make this a little more realistic, let's note that we're going to
start with a truth table that can have input don't cares.
And what input don't cares means is that each row of the truth table can match many
rows of the full truth table and we do that by just allowing people to put an
asterisk which says, you can match either a 0 or a 1.
So, for example on the input truth table that I'm showing on the, on the bottom
right here there are one, two, three, four, five rows of the truth table, table
and they're going to each turn into some sort of a cube and they're called P, Q, R,
S and T, respectively. And I've got a Karnaugh map on the upper
right of the diagram four by four, a typical four by four grid ab on the top,
cd on the left. 1s in the top, left two by two squares,
bottom right, two by two squares, the entire bottom row is 1s, and the entire
second row of the Karnaugh map is 1s. And I've got a bunch of covers here, I'm
going to talk through them one at a time. So, let's talk about the, the row of the
truth table 0 star 0 star that's really just this 1 right here, the upper left two
by two. This is cubed P because obviously a is 0
for those 1s and c is 0 for those 1s, but b and d can be anything.
So, that's just a very simple way of specifying more than one row of the truth
table, more than one single one in the Karnaugh map.
0 star 10, which is cube Q will be this one here on the bottom.
That will be the bottom left two, bottom column left two 1's, that's cube Q.
Of course, if you'd like, it's always possible to specify individual 1s in, in
the Karnaugh map that, that's these guys right here.
So, this one in the Karnaugh map is S and this one in the Karnaugh map is R.
Second row of the Karnaugh map, right two squares.
And T is going to turn out to be the bottom right corner bottom right corner of
the Karnaugh map. That will be cube T.
So, this just makes it easy to specify a function with lots and lots of variables.
You know, you got a function with like 25 variables in it, you do not want to write
out a truth table with two to the 25 rows, believe me.
You just want to specify where the function is a one and that's probably a
whole lot less than two to the 25 rows. You can specify these with these input
don't cares. It makes a very, very tidy and very
convenient way of doing that. So, this truth table with its input don't
cares each row with its pattern match ability, specifies a product, a cube, it
might not be prime, that's important to know.
There's nothing that says this is a very good cover, but it surely is a cover of
all the 1s. So, if you will, it's a bad Karnaugh map.
Our goal is to start with this, and then, do some optimization.
Now, the first step is to expand each cube to be a prime.
So, expand is a heuristic and this is actually going to get done one cube at a
time. So, we're going to take each cube in some
appropriate heuristic order and we're going to make it as big as we can possibly
be and what that means is that we're going to make it prime.
Now, let's be clear. There might be different ways of doing
this for any specific cube. You know, you might be able to grow it in
one direction or a different direction. And we're not really talking yet about how
we do that. And so, we've got three cubes in our
current design that have been expanded. The S cube is no longer a single one in
the Karnaugh map. The S cube is now the entire second row of
the Karnaugh map. And the R cube is no longer a single one
in the Karnaugh map. The R cube is a two by two square of cubes
in the Karnaugh map, it's the middle two rows in the right two columns.
And the Q cube is no longer the left two 1s in the bottom row of the Karnaugh map,
the Q cube as it has been expanded is now the whole bottom row of the Karnaugh map.
So, the new solution is a prime cover. Every cube is as big as it can be.
But it's not the best we can necesarily do.
There's more work we might be able to do on this to improve it.
So, what's the next step we do? Well, the next step is we try to remove
redundant cubes. And the name of this heuristic is
irredundant. Okay.
The irredundant operation removes redundant cubes from the cover, and a cube
is redundant if I can remove it, and all of its 1s are still covered by other cubes
in the rest of the cover. And it's important to note that we can
clearly remove cube R. And I'm just going to put some little hash
marks across R here, so you can sort of see it.
Cube R is the right two columns intersected with the middle two rows.
Cube R is covered entirely by every, by, by some combination of the other cubes.
So, we can get rid of it and if we remove it, the new solution will still be a prime
cover and it is technically minimal and what minimal means is I cannot remover
another cube without breaking it, without uncovering some 1s.
This is one of these local minimum things like I showed on this conceptual graph a
couple of slides ago. However, we might not be done.
We might still be able to do better, so what do we do next.
This is a very interesting idea. We're going to reduce the prime cover.
Reduce is another heuristic. We're going to take each cube.
And we're going to shrink it as much as possible, but we are not allowed to
uncover any 1. So, we're not allowed to break the
function, but we're simply going to take the cubes that are covering the function
and shrink them, so that none of them overlap.
What's going to happen here is that we can shrink the S cube.
Which is suddenly going to become the right two 1s in the second column and
we're going to shrink the Q cube and so we're going to become the left two 1s in
the bottom most row. This is our reduced reshaped cover, this
is a really strange beast. This is, if it uses a Karnaugh map, I'd
failed you, right? I mean this is this is a bad solution.
But this is a really amazing essential step.
This new solution has a different shape and what's going to happen is that from
this seed, we are going to expand it again and perhaps when we expand it, we'll be
able to find yet another superior solution.
This is the critical step in this key chain of heuristics that we're showing
here. This is the idea that I said in the intro
talk. I need a way of, of you know, making a big
step from one solution to a different solution, from one local minimum to a
different local minimum. And the big trick is you reduce things to
the strange non-overlapping non-prime cover, and then, when you expand it again
you might get a different answer. You might get a better answer.
You might find some new cubes that are redundant that you can kill.
So, if we apply the same heuristic expand heuristic again you might get a different
answer because you started from a different starting point.
And again, when you run expand, part of the goal is going to be to see if you can
overlap some other cubes so that they can go away.
Oh, look, I've done that in this particular example.
I've expanded the S cube by basically growing it down and I've expanded the Q
cube, which is the bottom row, by growing it to the right.
And suddenly, if we will go take a look at the T cube, we see, oh, look, I can make
the T cube go away. Because I had a different solution after
reduction, because when I did expand I got a new solution, I found a new local
minimum. I can, I can work with this.
So now, we, again, run the irredundant heuristic, but it is starting from a
different cover so I can get a different answer.
We took each cube and we expanded it to make it prime, but we also tried to cover
the cubes to make them redundant. It's part of the heuristic.
So, in this example we can kill the T cube, and I'm just drawing that in.
So, the T cube is now the bottom right two by two square, right most 2 columns,
bottom most 2 rows of the Karnaugh map. That cube can go away.
Just going to circle that and sort of draw it.
That cube can go away as the result of, of redundant.
After this, the cover is again and prime and it's irredundant and I can't remove
anything to make it smaller. So, it's still some sort of a, of a local
optimum, we're just not sure how good a local optimum.
Now, look, in this particular example, I got lucky, I got the best answer.
Right, after that set of reduce expand irredundant heuristics, I got the best
answer. This will generally not happen, you know,
exclamation point, exclamation point, I cannot guarantee you that this is going to
happen, but what I can guarantee you and this is the big important takeaway, what I
can guarantee you is that this thing is prime.
I can't take any cube and make it bigger. This thing is minimal, can't remove
anything and irredundant, which is sort of the same thing.
This is a really good local minimum. This is a really good local solution.
And it turns out in practice that this iterative improvement by reshaping can
produce really excellent solutions and can do so really fast.
This entire sequence of ideas is really famous.
This is the rude expand irredundant loop which was the, basically, the name of the
title of this lecture. And so, you know, what do you start with.
Well, you start with some sort of a prime cover, right.
You could do that by taking, for example, your bad truth table cover, and then,
expanding it. Right, you could then run reduce on it
which gives you something that is not prime.
You could then run expand on that which will give you something that's prime and
different, but also may be redundant. You actually, you hope its redundant,
because you are trying to get rid of some cubes.
You can then run irredundant on that and you will get something that is prime and
irredundant. And then, you go back and you do it again.
What are you going to do next? You're going to reduce it, maybe you get
it something with a different shape, it's kind of a pivot.
Lets you see, well, maybe I can get out of this local minimum and get myself to a
better local minimum, and so, you keep running reduce expand irredundant, reduce
expand irredundant, and basically until it stops getting better.
This is a really famous idea. Maybe the most famous idea in the 2-level
synthesis universe. And there's also a famous tool called
ESPRESSO. So, ESPRESSO started at IBM and it
finished at Berkeley. There's a very famous book from 1984 by
Bob Brayton, Gary Hachtel, Curtis McMullen, and Alberto
Sangiovanni-Vincentelli, that's definitely kind of the key reference for this stuff.
Rick Rudell master's thesis from Berkeley in 1986 is also a pretty good source for,
for a lot of the deep structure. And [unknown] De Michelis textbook from
McGraw Hill in 1994 is also another really good place to look for the you know, a
kind of a textbook level presentation of this stuff.
So, this is the high level tour of 2-level synthesis.
Boy, there's just a lot of really interesting stuff in this universe.
I wish I had time to talk about a lot of it.
So, what I'm going to do in the next lecture is just give you one tour of one
step to try to give you some of the flavor of how this stuff actually works.
So, let's go take a look at that.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
