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.
Computational Boolean Algebra: Application to Logic Network Repair
Loading...
來自 University of Illinois at Urbana-Champaign 的課程
VLSI CAD Part I: Logic
77 個評分
從本節課中
Computational Boolean Algebra
In this module, we will introduce advanced Boolean algebra math concepts that make it possible to take a "computational" approach to Boolean algebra.
與講師見面
Rob A. RutenbarAdjunct Professor
Department of Computer Science
[music] So here, in Lecture 2.4, we're going to continue working on Computational
Boolean Algebra. And now that we've done some interesting
things with cofactors, and we've put them together in some interesting ways, let's,
let's do an interesting application. Let's actually do a realistic application.
This is a network repair application. So, suppose I, I, I gave you a
specification for a Boolean function, let's say something complicated with a lot
of logic gates in it and suppose you got, you got that wrong and, and suppose you're
pretty sure that one of those gates in your thousand or 5,000 or 10,000 gates is
incorrect and you'd like to figure out how to change it that seems to be an
incredibly complicated kind of a problem. It turns out that by using some clever
cofactor-based computational techniques, we can pose the problem, we can write an
equation like Physics, that expresses the problem when we can solve the equation
like Physics. And the solution of the problem will not
only tell us that the gate is wrong, the solution to the problem will actually tell
us what gate we should use to repair it. That's a pretty amazing amount of stuff
that you can do just by manipulating Boolean Algebra with a computational kind
of a mindset. So, let's go see how that works.
This is Lecture 2.4, . We're continuing our development of
Computational Boolean Algebra. We've just done a lot of interesting
things with cofactors. Let's actually do a, a realistic sort of
application, something called logic network repair.
So, suppose that I gave you a logic block to implement, and let's say, I specified
it as Boolean Algebra and this is how I specified it.
Now, I will admit right away that this is very silly because if you just do a little
Boolean Algebra on this what you will discover is that this is a plus B bar.
So, I'm just going to say, please ignore this.
I need this to be simple so that the example works out in a nice way.
So, I give you the specification, right, and then I ask you to implement it.
And you know, maybe you're having a bad day and it's, you know, just kind of not
working. And, you know, some of this stuff you got
right so there's an inversion, right, you got the inverter right and that's an and
gate and you got the and gate right and that is an or gate and, oh, gosh, I have
no idea what you did, you don't know what you did but you didn't do the right thing
and this function g, wow, it's just not doing the right thing.
It's, it's not implementing f. Here's what I'd like to ask as an
Engineering problem. Can I deduce precisely how to change this
gate to restore the correct function? And the answer is yes.
And what's amazing is that I'm going treat this like a Physics problem.
And in a Physics problem, you know, you get some physics.
You have a cannon, you know, you shoot a cannonball up in the air, you ask how high
it goes, and at what time it gets there and you write an equation and you solve
it. But, in order to do this network repair,
I'm going to do exactly the same thing. I'm going to write an equation in the
Boolean domain, I'm going to solve it, and the solution is going to tell me if this
gate can be repaired and if so, what gate to replace it with to repair it, which is
pretty amazing. So, we are going to use this trivial test
case so that you can see how the mechanics all work, right?
So, the first thing is that there is a trick and the trick is that we're going to
replace our suspect gate with a 4 to 1 multiplexer.
And remember that a 4 to 1 multiplexer has two select lines and it selects from one
of four values, in this case, d0 through d3 shown down here.
And by putting some constant values on the d's, we can pretend to be, or fake any
gate, right? So those two inputs right to the gates,
are now the select lines. By putting constant values on the d's, we
can make the gate anything we want. So, the big question we are trying to
figure out is what are the right values of the d so g is repaired, so that g is
actually the same thing? Now, it's just a, a little reminder, you
can do any function of two variables with one four input multiplexer, right?
So, in this particular example, I have zeros in all, on all of the inputs, except
when both s1 and s0 are one. And so this thing is actually pretending
to be an and gate. And similarly, over here the only times I
have ones are when the s1 and s0 are different.
And so, this guy here is pretending to be an exclusive or gate, that's great.
What we know is that, if I can solve for the constants that go into the
multiplexers and make that, the logic networks correct, right, if I can make the
network with the multiplexer do the same thing as the specification network, then I
can repair things. So, here's the next interesting trick.
I'm going to make this new function Z, and Z is a function of the original variables,
alright, so there's the original variables.
Z has got them, but the Z is also a function of all of these multiplexeor
inputs. And note what I'm doing here, this is
required, this is a known good version of the logic, or at least just some Boolean
equation that does the right thing, even if I don't have it implemented in
engineering practical gates. I just gotta have it written down
somewhere. And I'm comparing the, the function up
here, okay, the G function with the funny multiplexer with the known good version,
and I'm doing over here an exclusive nor gate.
And just a little, a little reminder, okay, alright?
An exclusive nor gate looks, looks like, looks like that.
People I like to write this as an exclusive or sign with a bar over it, x
exclusive nor y. And this is xy plus x bar y bar, and this
thing is equal to 1 if and only if x is the same thing as y, alright?
This is an equality gate. So, we're going to take this equality
gate, and we're going to compare G and we're going to compare f, right?
And we're going to call this whole thing Z, and Z is the thing that we're going to
try to figure out. So, what do I want?
You just think real hard about, about what I want.
This is what I want from an engineering point of view.
I want the values of these constants, d0, d1, d2, d3, that make this interesting new
function, that make this thing Z exactly equal to 1.
And look what I'm writing. I'm being very careful.
For all possible values of the original inputs a and b I know how to do that.
If you give me the Z function, what I will do is I will universally quantify away a
and b out of the Z function, that's a new function.
And that functions depends only on d0, d1, d2 and d3, it doesn't have any a's and b's
in it. And then I will ask the question, can I
make this thing a 1, can I find some values of the d's that make it a 1?
And so, just like the bullet says, hey, this is something I know how to do.
Universal quantification of Z with respect to the variables a and b will do the
trick. Any pattern of the d's that makes this new
universally quantified function of one solves my problem.
That's petty amazing. And aside, you know where the a and b
went? They went away because they got consumed
in the co-factors when we set a and b to all four possible values of the a and b,
00 01 10 11. Let's go do it, okay?
Let's convince ourselves we can do it. So, the first thing I'm doing on the top
is I'm just writing the equation for the multiplexer, alright?
So, for example, you know, when s1 is a 0 and s0 is a 0, d0 is the value you, you
send on out, right? So, that's just the mux.
Alright. So, what's the, what's the G function,
right? The G function is if we just take the, the
function shown on the top and replace it with basically this logic, alright, what I
get is I get d0 ab bar, b bar, bar, two bars, plus d1 ab bar, b with a bar, plus
d2 ab, b with two bars, plus d3 ab b bar. Well, okay, that one just goes right away.
And then if I simplify this a little bit I will get d0 a bar b plus d1 b bar plus d2
ab. So, that's the G function.
That's the thing with the multiplexer pretending to be a gate, whose function is
determined by the d's. I'm going to put that into an exclusive
nor inequality gate, okay? I'm also going to put that in, that's the,
that's the f function, and the result of that is going to be my Z.
So, Z is G exclusive nor f which is Gf plus G bar f bar and what I want is to go
calculate this thing with the star, for all abZ, right, which is going to be the
ab cofactor ended with the a bar b cofactor ended with the a, b bar cofactor
ended with the a bar b bar cofactor. Now one could take a frontal assault on
this and just go pound out all of these all of these exclusive nors and one would
be badly advised if one did that. That would, golly that would hurt.
I really don't advise you to do that. I advise you to be smart and use some of
the tricks that we just showed you a couple of lectures ago, alright?
So, here it is again, all written out nice.
Z is equal to the G exclusive nored with the f.
And I've just got a little reminder over here, if you don't play with exclusive
nors too often. If you exclusive nor something with a
zero, you complement it. And if you exclusive nor something with a
1, you return it unchanged. Let's use the nice property that we showed
a couple of lectures ago. The cofactor of an exnor is the exnor of
the cofactors. So, in other words, I don't have to do
this terrible exnor and make this, this terrible big expression and then go
cofactor it. I can go cofactor it first.
If I cofactor it first, life is ever so much easier.
Then, all I have to do is in the, the G function, and in the f function, I have to
set the a's and the b's to all four possible constant values.
So, if I set the a to 0, and the b to 0, right okay it turns out that what I will
get is just d1, right? The first term goes away because b is a 0
and the third term goes away because b is a 0, right, but the second term stays
because b is a 0, alright? And then that's going to be exclusive
nored with a 1, and that's going to give me d1, right?
And if I take a as a 0 and b as a 1, it turns out I get a d0, and it turns out I
am exclusive noring it with a 0, so that turns out to be d0 bar.
If I take a as a 1, and b as a 0, it turns out I get d1 exclusive nored with a 1.
I get d1 back again and in this last one, I get d2 exclusive nored with a 1, a 1, I
get d2. And the thing to remember is that the
thing I'm trying to calculate, the universal quantification of Z, right,
which is a function of d0, d1, d2, d3, right?
It's just the end of all of these cofactors and so that's just d0 bar, d1,
d2. And that's not so horrible, alright?
Trust me. If you had exclusive nored those things
out and made this really horrible big Boolean expression, and then cofactored
it, and then tried to and them all together, it would be very painful.
This is a much smarter way of doing it. Sorry, draw it in the right place there.
So what did we get? What we got was that the, the
quantification that got rid of the a's and the b's in the matter that we needed is
just d0 bar, d1, d2. And we know that our goal is to solve
this, aright and make it a 1. So you know, what do you have to do to
make this thing a 1? And the answer is you have to make d0 a 0,
you have to make d1 a 1, you have to make d2 a 1 and d3 is I don't really care,
don't care. Anything you want, it doesn't matter,
which is interesting. And it's going to be surprising, it's
going to be actually of relevance. Those values will repair this network,
alright? So remember what I said.
If you take d0 is a 0, d1 is a 1, d2 is a 1, and d3 is a don't care, it repairs this
network, alright? Well, look, one of these values makes
eminently good sense, right? If you do this as 0110, that's an or gate,
right? That makes a 1, I'm sorry 0111, okay?
That is an or gate, right? And look, that's what we expected,
alright? We expected that if this Boolean thing
worked, it would produce an or gate, because we knew that produced the right
answer. But what's interesting is that if you take
the other value, 0110, it specifies an exclusive or gate, and that will also
repair it. That's very cool, alright?
Because in the real world, you don't have a tiny example like this one is, you have
a big network. It has a hundred inputs, it has 50,000
gates. It's big and complicated, and you can
localize the problem to some blob of gates, right?
And you can point at the gate and say, gosh, I wonder what that gate is supposed
to be? And perhaps you have a specification that
you can actually work with for what is, what the golden correct version of the
logic is. But it alone is quite complicated.
The fact that you can do this as a Boolean equation, that you can do this like
physics, you can write an equation and solve the equation.
And if you solve the equation, the Boolean expression equals 1, it repairs the
network. That's a completely amazing kind of a
result. That's why we're focusing on this
Computational Boolean Algebra business. You've never really done Boolean Algebra
like Physics, where you write equations and expect solutions.
So, what have I just done? I've given you a mechanical procedure to
answer, can I change one gate and repair it?
Now, what you really haven't seen yet are a lot of computational strategies.
In this particular case, what I needed was to find inputs, okay, that make this
particular value of this function a one. That is the most famous computational
problem in all of Boolean Algebra. That's called Boolean satisfiability.
Give me a Boolean expression, tell me if there is a way to make it a 1, or tell me
that there is no possible way to make it a 1.
That's called the SAT problem. And the ability to do Boolean SAT
efficiently is a big goal for this. We're going to, we're going to see how to
do this in some, in some later lectures, but for now, what we're going to do next,
is give you some more computational infrastructure for Boolean Algebra.
[music]
