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.
Multilevel Logic: Algebraic Model for Factoring
Loading...
En provenance du cours de University of Illinois at Urbana-Champaign
VLSI CAD Part I: Logic
94 notes
À partir de la leçon
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.
Rencontrer les enseignants
Rob A. RutenbarAdjunct Professor
Department of Computer Science
So, here in lecture 6.2, we're going to continue our exploration of multilevel
logic by introducing a new mathematical model of the logic that goes inside the
nodes in the Boolean network model. And that Mathematics has a name, it's
called the algebraic model. And what's actually rather interesting
about it is that it starts with its premise.
Let's take Boolean equations and let's throw away the parts that make them hard.
Let's actually throw away the parts that make them not look like polynomials over
real numbers. And in fact, if we through away those
difficult parts, we can do some really useful operations on these Boolean
equations in the algebraic model. And the really important thing we can do
is we can factor them. We can take big equations apart and pull
out common small pieces to make the networks smaller and less complex.
So, let's go take a look at what the algebraic model does.
So, before I start a little bit of context here.
Multilevel synthesis, just like 2-level synthesis, is a heuristic.
And more interestingly, it's a lot of heuristics.
And you've already seen in ESPRESSO, there are a lot of interesting heuristics that
were involved in the reduced expanding redundant loop.
Multilevel synthesis is just more complicated because there's a lot more
going on. And what turns out to be the case is that,
one actually writes scripts of basic operators.
One writes things that amount to little programs in a little programming language,
where there are many, many kinds of operators that each do a certain kind of
optimization iteratively over the surface of the Boolean logic network.
So, we'll do several different passes of different kinds of optimizations.
We'll do some cleanup kinds of steps to get rid of the too small nodes and remove
them. We'll look for certain kinds of easy
factors that are just sitting around in a logic network and we'll say, hey, are you
somebody's divisor? Can I sort of profitably reduce somebody's
the inside of somebody's Boolean network node by, you know, using you as a factor?
We'll look for hard factors where we take a bunch of big complicated nodes and we'll
do the difficult work too, and let me use the proper verb, extract them.
And try to keep the good factors and, you know, kind of plug them back in and we'll
do 2-level optimization on the insides of each logic network.
Now, their is a whole lot of art in the engineering of these scripts.
People get paid real money to write these kinds of scripts and different kinds of
logic, design, scenarios, have different kinds of scripts.
But the one big, big thing that you just don't know, that's the heart of most
Boolean multi the, the, at the heart of multilevel logic synthesis using a Boolean
logic network, is how to factor things. So let's talk about that.
I need another new model. I need a new mathmatical model.
So, how are we really going to do factoring?
This is actually a very cool idea. We're going to develop another model of
Boolean functions that's just specifically designed to let us do this factoring
thing. And the trade off, and this is may,
perhaps a surprise, is we're going to be willing to lose some expressivity.
Some aspects of Boolean behavior and some Boolean optimizations we're going to agree
we cannot do. They're just unavailable to us.
But what we gain is that we make it possible to do practical factoring in a,
in a, in a good way. You know, in a, in a, in a practical
useful way. So, not perfect.
There's somethings we, we agreed to give up, but we're going to get practical
factoring. The model's called, the Algebraic model
and the term Algebraic comes from pretending that the Boolean expressions
behave like polynomials of real numbers, not like Boolean algebra and we're going
to, end up with the new Boolean operator which is called Algebraic division because
it is using the Algebraic model. It's also called weak division because of
this loss of expressivity thing. Okay there's some things that we are just
unable to do. It's not fully you know, fully Boolean
kind of a model. Turns out that's a surprisingly good
trade-off. So, here's the basic idea of the Algebraic
model. We're going to keep just those rules or
technically those axioms that work for polynomials of reals and also for Boolean
algebra formulas, and we're going to dump the rest.
This is kind of surprising. So what I'm showing you here, on the left
hand side, I'm showing you some of the axioms for how operations work on real
numbers and on the right, I'm showing you how axioms of how things work on Boolean
algebra. And the things on the left ought to be
familiar for anybody whose done, you know, algebra for the last, you know, let's say
maybe 10 years. So there's somethings about real numbers a
times b equals b times a. A plus b equals b plus a.
That's commutativity. It doesn't matter what order you do things
in. A times b times c, equals a times b times
c. You can put the parentheses around the b,
c or the a, b. A plus parenthesis b plus c, equals
parentheses a plus b plus c. That is associativity, it doesn't matter
what order you do the times and the adds. A times b plus c is a times b plus a times
c, that's distributivity. A times one is a, a times zero is zero, a
plus zero is a, that's, that's the way identities work for you know real numbers
where you are actually adding and you are actually you know, multiplying.
Now, in Boolean algebra, those things that are listed in blue are also the same, a
and b, equals b and a, a or b equals b or a.
You know, as long as or is plus and, and is dot.
A and b and c in parenthesis is a and b and c.
A plus parenthesis b plus c, equals parenthesis a plus b plus c.
It doesn't matter the order in which you do ands and ors.
They associate. A and b plus c is a and b, plus a and c.
They distribute. A and 1 is a, a and 0 is 0, a or 0 is a.
Now, those are all the same. The problem is that Boolean algebra is not
the algebra of real numbers. And there's some other stuff, right?
So, for example, there are some rules for how things behave when you start doing
compliments. Right, a plus a bar is 1, a and a bar is
0. We don't really have compliments in real
numbers. That's just not there.
A and a is a, a plus a is a. That's a set of, of laws, those are called
the idempotent laws. A plus 1 is one.
That's another one of those rules for how identity works.
But you know, a plus 1 is not 1 for real numbers and, and then, there's another
distributive law which is the other one, a plus b times c is a plus b times a plus c,
and trust me, as somebody who's taught, you know, digital design for a really long
time, this is the rule that people mess up.
So, the idea is the stuff on the top of the diagram in blue, it just works for
both reals AND Boolean algebra. The stuff on the bottom of the diagram in
red does not work. And so, what we're going to do is we're
going to structure our Boolean equations in ways that literally let us ignore these
stuff in red by insuring that it never happens.
And it turns out there is actually a surprising simple way to do that.
So, if you only get to use algebra rules from real numbers.
One consequence that's very important and very immediate is that a variable and its
complement must be treated as unrelated, totally unrelated.
And this is really one of the principal losses of expressive power for Booleans in
the Algebraic model. And we just tolerate this.
So, if you have a Boolean expression like ab, F is ab, plus a bar x, plus b.
Y, b bar y, I need to get rid of those confluence.
I can't have as and a bars floating around in the same Boolean expression.
I can't have bs and b bars, so I'm going to let R equals a bar and S equals b bar.
And, when I rewrite this expression, it's going to be ab plus Rx plus Sy.
And then, suddenly, this looks more like, you know an equation that you could see
in, in just, you know, a polynomial form. And you know, again, the reason for this
is that we don't want to see any circumstances where we try to do something
like x times x bar or, you know, x plus x bar b, which one can simplify, or x plus x
bar, we just don't want any of those things to happen.
And so, by sort of removing the things with compliments and replacing them with
just different variable names, we're going to, basically, make, make sure that, that
doesn't happen. We're going to lose some expressive power.
But we're going to gain some very interesting factoring techniques.
So Boolean functions are manipulated just as SOP expressions just like polynomials,
each product term in such, in such an expression is just a set of variables, you
know, a, b, r, y. And the SOP expression itself is just a
list of those products that are list of those cubes.
So, very much like the URP stuff with, you know, positional cube notation kinds of
ideas. You know, it's just a list of cubes,
nothing more to it. Now, Algebraic Division, this is what
we're really trying to accomplish for Our Model of Factoring.
If I give you F and I give you a function D, okay then, what we want to do is take F
and divide it by D to create a quotient Q and a remainder R.
So, F equals D times Q plus R. And the remainder, well, if it's zero,
then, we say the divisor is technically called a factor, and if not, it's just
called a divisor. Now this should be very familiar if you
replace all these things with real numbers, like I show on the left hand side
of the slide. 15, F, is equal to 7 times 2 plus 1.
I took 15 and I divided it by 7. That's the divisor, D.
I got a quotient, 2 but it did not divide evenly, and so, I got a remainder, 1 of R.
I can do exactly the same thing with a Boolean sum of products form.
F, in this case, on the right hand side, is ac plus ad plus bc plus bd plus e.
And so, that's the same as saying, well, that's actually equal to a plus b, my
divisor D, times Q, the quotient, c plus d, and there's a remainder left over
because it's not a factor. It doesn't leave 0 left over.
And, you know, this is really, this sounds simple, but it's really almost as easy as
saying, look if I had a Boolean expression like abc, plus bcd and I wanted to divide
it by bc, if you didn't know that those were Boolean algebra quantities, you could
say, oh gosh, that's easy, I just cross bc out of the top and bottom and I get a plus
d. That's really the heart of the Algebraic
model. If we can keep things looking as simple as
this. Going to write the a plus d a little more
legibly. If we can keep things to be as simple as
this, wow not so bad. Let's go look at some other examples.
So, suppose I got I want to do some algebraic division.
And I've got F is ac plus ad plus bc plus bd plus e.
And I want F to be B times Q plus R. So let's just divide some Ds and see what
happens. So, we've got D and what we're really
going to do is we're going to do F divided by D and we're going to get a quotient Q.
And maybe we're going to get a remainder. And then, we'll ask the question as to
whether or not we actually got a factor. Okay, so, what happens if you just divide
D by F. Well, you get a you know, you get a
quotient of 1. If you divide something by itself you get
a quotient of 1. You shouldn't be surprised and you get a
remainder of 0 you should also not be surprised.
Is it a factor? Yeah, but it's a, it's a, it's a trivial
factor, you know, it's not very exciting. That's like saying 15 is equal to 15 times
1. Yes, it's true, but it's not very
interesting. If I divide F by a plus b, it turns out I
will get c plus d as a quotient and a remainder of e.
So, is it a factor? No.
But it's still useful. If I divide by c plus d, I get a plus b,
that's symmetric, no surprise there. I also get a remainder of e and it's still
not a factor, but it's a useful divisor. If I divide by a I get c plus d with a big
remainder of bc plus bd plus c, it's not a factor because it's got a remainder.
If I divide by b, I also get the same thing, c plus d is the quotient.
Ac plus ad plus e as the remainder. Not a factor, but still may be useful.
If I divide by c, I get a plus b as the quotient, ad plus bd plus e, no, it's not
a factor, it's got a great big remainder. If I divide by d, I also get a plus b,
with ac plus bc plus e as the remainder. Not a factor.
If I divide by e, it turns out I just get 1 because there's not very much I can do,
and the remainder is the entire F. Right, so the question is, you know, how
do we actually do this, right, because it looks like it works, it looks like it
sorts of does the right thing in terms of us, being able to pull out factors but you
know the next big question is, you know, how do we do this?
So, let's go explore that in the next lecture.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2019 Coursera Inc. Tous droits réservés.
