0:02
So, here we are in lecture 3.4. We're going to complete our exploration of
binary decision diagrams as a, a really powerful and important data structure for
doing Computational Boolean Algebra. And up to this point, we showed how we
could represent complicated sets of Boolean functions using a shared set of
BDD nodes. And life just sounded really, really good.
And as we're going to show in this lecture, you can answer some very
complicated questions, like whether two complicated pieces of, of digital logic
are the same. How they're different.
Can you find an input that can make a complicated Boolean function equal to 1?
We're going to see some really wonderful and, and seemingly simple ways to answer
those questions. And so, in anything that's wonderful,
there's got to be a catch, right? And the problem is that, the ordering of
the variables has a profound effect on our ability to actually make the BDD.
Not every BD, not every Boolean function can turn into a manageably sized BBD.
And for some orderings of the variables, the BDDs are small and friendly.
And for some orderings of the BDD variables, the BDDs are exponential and
horrible. And sometimes we can fix that, and
sometimes we can't. It's just the way life works here.
And so, let's go look at how ordering affects life in BDDs.
So let's talk a bit now about how BDDs are really implemented.
And one of the things I said when we were beginning the development of BDDs is that
I cannot honestly implement them the way I, I sort of conceptually introduced them.
Which is to say, I cannot build the entire decision diagram flat out to like 2 to the
100 in leaf nodes at the bottom for a function of a 100 variables, and then
apply reductions. There's got to be a better way, and there
is a better way. And we're going to talk just in a very
high level about that better way in this, in this bit of our lecture.
How BDDs are really implemented are recursive methods.
And it's, it's going to be a kind of a recurring theme in this class.
You know, if you ask me, well, that's a really complicated CAD problem there, Rob.
How do you think we're going to solve it? The answer's going to be, I don't know.
Could we break it up into two pieces? Solve them recursively and then glue the
answer back together, and the answer maybe 9 times out of 10 is going to be yes.
So, even for BDDs, the trick is there's, there's some Shannon co-factor divide and
conquer kinds of things. And the big idea here is that a BBD
package is, is actually functionally implemented as a set of operators, we call
them ops, on the BDDs. So, you get all the things that you would
imagine from, say, gates, you know, you get an And, you get an Or.
Not exclusive or exclusive nor. You get the Shannon kinds of operations,
you know, co-factor or variable, or variables out.
Because you have co-factors and Ands and Ors, you can do things like universal
quantification. Where you co-factor things out, and, And
them together. You can do existential quantification.
You co-factor them out, and Or them. You can do satisfiability, which is to say
you can tell me what makes the function a one by tracing a path to the one node down
at the bottom. All of these things are implemented on top
of the basic BDD data structure. And the basic idea is that we're going to
operate on the universe of Boolean data as input and output, so we're going to have
constants 0 and 1 are sum of our data objects.
We're going to have variables, and we're going to have Boolean functions
represented as shared BDD graphs. So, the big trick, the really big trick is
that we're going to implement each operator so that if the inputs to the
operator are shared, reduced, ordered BDDs, then the outputs of the operator
reduced ordered BBDs. So, the other way to say this is that we
never build an unreduced, badly ordered version of the BDD.
We always start with things that are reduced and ordered and shared, and we
maintain them. And roughly speaking, we use recursive
methods to sort of take the function apart down to the bottom.
And then, we sort of put it back together from the bottom up, just like URP, and we
sort of, by putting them up back together in this sort of bottom up manner every
time the recursion comes back up, we make sure the variables are in the right order
and that we're doing whatever the appropriate reductions are.
So that, you know, the way to sort of think about this thing, I've got a little,
just a little example here, I'll put a little star by it.
H equals BDD, and I've kind of writing this in a C-like style, you know, casting
this as a, as a BDD up, a data object. You know, operator is some kind of a
subroutine that takes an F bdd and a G bdd and produces and H bdd.
And you want to think about that is well, here's F, right?
F is the pointer to the top of some graph, here in the big cloud of BDD nodes.
And G is a pointer to another graph in this cloud of BDD nodes.
And perhaps, F and G overlap, maybe. Right?
And then, when we call whatever op is, it's some kind of operation on BDDs F and
BDDs G, we get a new BDD. And maybe BDD H is over here somewhere,
and perhaps it also overlaps some. Or, you know, might be over here
somewhere. Maybe that's BDD H, or kind of draw it
with the dotted lines here. Maybe, maybe BDD H is some really big
complicated messy thing, and F and G are mostly buried down inside of H, I don't
really know. It depends on F, depends on G, depends on
the operator as to what H is. But you start with shared reduced ordered
binary decision diagrams. And you build the operators that you need
to do real engineering. So that they return to you shared reduced
order BDDs, and everything works beautifully.
So, how do you actually build the BDD for something complicated?
And the most standard example would be, that I give you something like a logic
network, like a big logic network, a logic network with 10,000 logic gates in it and,
you know, 50 inputs and 20 outputs. And the answer is, you can build back up
by basically walking the gate-level network in a, in an incremental fashion.
So, each input is a BDD. Each gate becomes an operator that
produces a new output BDD. And we build the BDD for out, which is
the, the value that we're looking for here.
Basically is a script of calls to basic BDD operations.
So, I've got the basic BDD operators script shown here on the right.
It's kind of a very high level. It's kind of a pseudo code kind of thing.
You know, step one says A equals create variable A.
And that's just a kind of a shorthand for this, you know, this step over here that
says, oh, okay. I'm, I'm going to create a variable A.
And it is a, a function and it is a Boolean function.
And it's pointing to you know, the 0 to the, to this variable node here.
And the, the second one is a B which is creating a variable, you know, B and B is
a function pointing to it. And the third one is a variable C, which
is creating a function pointing to that. And each of those are the single node
BDDs, you know, one, one vertex pointing to constant zero in one children, low
child high child respectively. And then, it gets interesting.
T1, as we see over here, T1 is the And of A and B.
Going to put little check marks over here because I did one, two and three.
T1 is the And of the A function and the B function so I'm going to assume that I
have And implemented as an operator in my BDD package.
And as a consequence, like in call, it would BDDs A and BDDs B, and I will get
back BDD T1, which points at this particular little BDD as the result of
step 4. And if you just stare at this for a while,
you can see, yeah, that's actually the BDD for And because the only way I can get a
one node is if a variable, variable A and variable B are both 1.
Like okay, you know, that works. What happens next?
Well, T2 is the And of quantities B and C. All right, well, T2 is going to be that.
And T2 is going to be the result of step 5, and that is going to be a little BDD
for B and C. And we can see again, it's sort of the
trivial B BDD. The only way to get a 1 in this small,
trivial BDD is to have B and C each be 1. All other paths lead to the 0 node.
And then, we'll do the next step. Obviously, out is equal to T1 and T2.
T1 is a BDD, T2 is a BDD. Or is an operator that our BDD package
will provide for us. And so, we call the Or on T1 and T2, and
this is what I'll get. I'll get out is equal to this, and this is
going to be A,B plus B,C. And again, if we stare at this for a
while, we can see, oh yeah, this makes sense.
You know, the ways to get a 1 are A and B is 1, or B and C is 1, and everything else
gives you a 0. So, how do you do something really
complicated? What if I gave you 50,000 logic gates?
I could, I could actually do that now. If I gave you a BDD scripting package,
which I'm actually going to do. And if I gave you a whole bunch of logic
gates, you could interrogate the graph that represents the logic network.
You could even determine an appropriate order for building these BDDs representing
each of the internal nodes in an appropriate order.
And you could build them up one by one by just making simple calls to And, Or Not,
Nand, Nor, Xor, Xnor and so forth. Until you had BDDs for every single one of
your gate level outputs even for a very complicated network.
And the only decision that you have to make is what are you going to do with the
variable ordering? Now, you also get some other wonderful
capabilities from any real well-implemented BDD package.
And that's for comparing things. So, one of the most important engineering
application for something like a BDD package is asking, are these two Boolean
functions, F and G, the same? Very often, because they are representing
different pieces of logic that are supposed to be the same, and you actually
want to know it they're actually really the same.
And so, the way you do that is you build the BDD for F and you build the BDD for G,
and then you just compare the pointers. And let's remember that reduced order BDDs
are canonical. If F and G are in fact the same Boolean
function, they are the same graph. But because we are building shared,
emphasize that, shared BDDs, not only are they the same graph, they're the exact
same graph. The pointers point to the same place.
So, you know, the way this is going to work is you build the BDD for F.
Okay, there it is. And then, you build the BDD for G, and
what you get is a pointer to exactly the same thing.
You don't get another copy of it. This is very important.
You don't get another copy of it. You don't get another version of it that
happens to have the same nodes in the same places.
You get the same graph, okay? And so, if you build BDD for F and you
build the BDD for G, and if they are the same function, then the pointers are the
same. Literally, this turns something that
sounds extraordinarily complex, are these two 50,000 gate logic networks the same,
into you know, two integer address comparisons on the F pointer and the G
pointer, are they both pointing to the same node in computer memory that
represents the top variable? That's a pretty amazing kind of a powerful
result. So, are two Boolean functions the same?
You build F, you build G, if the pointers are the same, they are.
But what if they are not the same? Well then, we've got another interesting
thing we can do. After we get over our you know, our
unhappiness that perhaps F and G are not the same, the question we might want to
ask is can you find me an input that makes them different?
And, you know, the way you would think about doing that is that here's F and it's
got, you know, a bunch of inputs. And here's G and, you know, it's got the
same inputs, call it, call it x. What I would do is I would build myself an
exclusive Or gate for that output. So, I would build a new function, let's
call it H, right? And that new function H makes a 1 only
when F disagrees with G. It makes a 1 only if F makes a different
output than G for the same input, okay? So, I'm going to build the BDD for F.
There it is. I'm going to build the BDD for g.
There it is. I'm going to assume they share something
because they're supposed to be the same function, right?
Then, I'm going to build the BDD for H, right?
I don't really know how to draw that, but let's just assume that it's something
really big and complicated, and sort of subsumes them both.
And then, I'm going to ask if H is satisfiable, which means I'm going to ask
if there's a path from the top of H to the one node.
And if that's the case, every such path that goes from the top of H to the 1 node
specifies the values of variables that makes H equal to 1.
Those are the values that make F and G as pieces of hardware, have different
outputs, a 0,1, or a 1, 0. Those are inputs that make F disagree with
G. You know, maybe you can use those things
to figure out why F is not equal to G. When you think F is supposed to be equal
to G, or perhaps F is not suppose to be equal to G.
And you just want to know what makes them different.
Here's the way you do it. And again, you build F, you build G, you,
you know, invoke the operation of built into the BDD package of exclusive Or-ing
two Boolean functions. And wham, you've actually got the result
again. So very, very powerful things, BDDs.
You can do some, you know, amazing, amazing you know, operational stuff in an
engineering kind of a context, more useful BDD applications.
Well, you can do tautology checking. We already kind of, kind of mentioned
this. I spent a whole lecture showing you how to
do Unate Recursive Paradigm cube list tautology because it was a really nice
warm up. But you'd never actually do that.
Well, mostly you're not going to do that. Because probably, you just build a BDD.
Because look, with a BDD, it's trivial. If a function is equal to one, then that
is the only way it can happen because we are canonical.
There's only one representation. And we are shared.
If we have multiple functions that all are supposed to be the same truth table, they
all point to the same node. So, if that's just supposed to be a 1, it
just points to the 1 node. So, wow, that's a heck of a lot less work.
What about satisfiability? And it gets satisfiability's when, when
you solve a Boolean equation. You say, what value makes it equal to one?
Well, I have no idea how to do that with cubelist.
But here, you know, as long as you can find a path from the root to the leaf with
the one node, you can do it. So, one way to satisfy this function, for
example, X1 is a 1, X2, I don't care about what the value is.
X3, I don't care what the value is. X4 is 1.
So, for this little BDD, you know, it just works.
And similarly, that's another pattern that'll do it.
So, X1 is a 0, X2 is 1, X3 we don't care about, and X4 is 1, that'll also do it.
So, as long as you build the BDD, so basically you can go backwards from the
one node, you can have pointers going both ways this is all very easy to do.
So, this is just another I'm just going to write this here.
16:44
This is just another operator implemented in your BDD package.
You can ask the question, is it satisfiable?
And you can ask for some values that satisfy.
So all of this seems just too good to be true.
So, at this point, if you're thinking sort of hard, you ought to be a little
suspicious. And one of the, the reasons you ought to
be a little suspicious is that, boy, it looks like I can take just about any
profoundly theoretically exponentially difficult, you know, computer science
problem. And if I can, you know, build a BDD, you
know, like, wow. It looks like I can solve it.
How come we all still have jobs? You know, how come there are any problems
left to solve? And there's a problem.
There's a, actually, a really big problem. And the problem is that the variable
ordering that you used to build the BDD matters.
And what does it mean that it matters? And the answer is that, if you can find a
good ordering, you could build the BDD in a reasonable amount of space.
So, here's a BDD for a, a very simple function.
A1 and a1 plus a2 and b2 plus a3 and b3. So, I'm going to say that n equals 3 here
because you can make this thing you know n as big as you like.
The BDD on the left has a good ordering. That ordering is a1, b1, a2, b2, a3, b3.
It's this nice tight little linear chain. It shows linear growth, which N, which is
to say that it's size looks to be sort of ordering as N, you know, kind of some
constant times N, right? But the ordering on the right, in which
you do all of the a's first and then you do all of the b's makes an exponentially
sized BDD. Which is to say that the size of this BDD
is ordered 2 to the N, and that is a very unhappy circumstance.
And so, the problem, you know, which makes this really, just very interesting is that
there are lots of problems that have very efficient solutions.
If, and I'm emphasizing this, if you can build the BDD.
And the problem is, you can't always build the BDD.
So I'm just sort of writing this down here you know, it's a really interesting
problem. Some problems that are known to be
exponentially hard are very easy on a BDD so that's, that's pretty amazing.
The problem is that you can't solve every instance of those problems.
The trouble is they're easy only if the size of the BDD for the problem is
reasonable. Some problems make nice small BDDs, others
make pathological large BDDs. And there's no universal solution.
I'm just going to emphasize that. There's no universal solution, or we could
always solve exponentially hard problems easily and we'd all be out of a job.
How do people handle this thing? Well, there are, there's a lot of work on
variable ordering heuristics. How do you figure out an ordering to make
a nice BDD for a reasonable problem. There a lot of work on that.
There's characterization, you know, you should just know which problems never make
nice BDDs, so just don't try. I'll give you some examples.
Multipliers are one of those things. Adders are great, multipliers are
terrible. There's also dynamic ordering techniques.
A dynamic ordering technique lets the BDD software package pick the order by itself
and adjust it dynamically as your script executes to try to you know, make the best
ordering. That's actually pretty interesting.
We don't have time to talk about that, but that's actually one of the things that
people do in practice today. Let me give you a little bit of intuition
about BDD ordering. Here's some rules of thumb.
So, I'm showing the same function again, a1, b1 plus a2, b2 plus a3, b3.
And so, here's the linearly ordered BDD, the linearly-sized BDD on the left and
exponentially-sized one on the right. What's going on here?
So, let's just read my rules of thumb. Related input should be near each other in
the order. Groups of inputs that determine the
function all by themselves should be one, close to each other, and two, near the top
of the BDD. This is a, a heuristic, this is not you
know, a perfect solution. But let's just observe on the left that,
you know, the a1, ai bi pairs are all next to each other in the order.
Because, you know, in this function that I'm showing over here ai and bi, right?
Can together determine the value of the function.
So, by having the ai, bi pairs close to each other every time you get an ai, bi
pair, you know, you, you, you choose an ai, let's say an a2 value, and then you
choose a b2 value. Well, you actually know whether you can,
you know, make a1 if the a2 and the b2 are 0.
And if not, you don't need to know anything more about the a and the b.
You can sort of, you know, not show a bunch more of them in the order and you
can just move on. You know, look at the one on the right
hand side. This is honestly, basically, this is
basically the worst order you can do. This is just terrible.
And if you sort of stare at this for a while, you get this, this, this sort of
interesting little house picture here. This one has all the a's first, and then
all the b's. That's terrible.
And the reason is that you need a ai, bi pair to be able to determine the value of
the function. Which means that if you give me all the
ai's first, I have to remember them all. And so, the first level of the diagram has
an a1, and I can't tell you anything about the value of the function.
So, the next level of the diagram has two a2's, and I have to remember them all.
Because I can't tell you anything about the value of the function.
And the thrid level of the BDD has four a3's because I can't tell you anything
about the value of the function. If I had 40 a's and 40 b's, I would have 2
to the 40 things at this rank. Because I have no b's yet, I can't tell
you the value of the function. And it's not until I introduce some b's
into the BDD that I can actually make a decision and tell you the value of the
function. So, groups of inputs that can determine
the function by themselves need to be close to each other, not widely separated.
Because if you make them widely separated, then the BDD just gets big.
It just gets wide. It gets fat in the middle because you have
to remember all the possible values of that BDD.
And the way a BDD remembers all of its possible values is by having a lot of
nodes and a lot of edges. And that makes everybody unhappy, right?
So related input should be near each other.
Groups of inputs that can determine the function by themselves should be close to
each other. And as far as you can, you can shove them
up toward the top of the BDD. Can't always do it, but that's the basic
heuristics. It's worth knowing just like, you know,
what works for BDDs and what doesn't work for BDDs.
So arithmetic currents are really important, you know, people build data
paths all the time. How are their BDDs?
Circuits that have their based-on carry chains have linear-sized reduced order
BDDs, so adders, subtractors, comparitors, you know, things that decide whether a is
greater than b in priority encoders. Those, those have you know, at their
heart, they have carry chains, those have linear-sized BDDs.
And the rule is that you always alternate the variables in BBD order for carry chain
circuits. So, if you're going to remember anything
about ordering, remember this, right? A0, b0, a1, b1, a2, b2.
There's usually an obvious order for, you know, kind of whatever the low order bid
is whatever the one you can compute with the least work that goes first in the
order. And always, always, always alternate.
Never, never, never do all the a's and do all the b's.
So, it would be wonderful if all arithmetic circuits were easy and they all
made friendly BDDs, but that is unfortunately false.
Addition, the best order is linear. That makes us happy.
The worst order is exponential. So that's good, that's bad.
Linear ordering, alternate the a's and b's.
Exponential ordering, don't. Multiplication, oh, that's very
unfortunate. Multiply two things together.
It's always an exponential BBD. It's just really bad.
Turns out you need a different data structure, and they actually exist.
They're other kinds of decision diagrams that have other kinds of canonical forms
to represent things like multipliers. We don't have time to talk about them, but
they actually exist. So, the general experience with binary
decision diagrams is that many tasks have reasonable ordered BDD-sized,
reduced-order BDD sizes. The algorithms are practical to like, you
know, 100 million nodes which is a, you know a really big amount of memory.
And, you know, people spend a lot of effort finding orderings that work.
That's the only downside for BDDs. So here we are.
We're at the end of our, our, our lecture on, you know, the first really practical
and important data structure for us, Reduced, Ordered, Binary Decision
Diagrams, ROBDDs, or what everybody just calls them BDDs these days.
They're a canonical form. They're a data structure for Boolean
functions. Two Boolean functions are the same if and
only if they have an identical BDD. A Boolean function is just a pointer to
the root node of the BDD graph. Every node in a shared BDD represents some
function, and we can use that sharing very intelligently.
Within a shared BDD, you can test if a function F is equal to a function G just
by checking their pointers for equality. Do the actually point to the root node?
That's really cool. The basis for much of today's general
manipulation of, of Boolean stuff. Bdds are very, very, very widely used in,
in the CAD industry, and actually in a lot of other applications.
The problem is that variable ordering matters, and, and it matters a lot.
It can be the difference between needing, you know, a 1 million nodes of BDD and,
you know, 2 to the 100 nodes of BDD, and sometimes the BDD is just too big and you
just can't build it. Which leads us to whole other class of
representations and algorithms. Because, you know, it's surprising.
But sometimes, you just want to know something that's called SAT.
Sometimes you just want to build the Boolean function and ask what appears to
be a simpler question, is there a way to satisfy this Boolean function and make it
a 1? If so, can you please give me a value of
the variable that does that? And if it's not possible to satisfy this
Boolean function, please prove it for me. And just return that information.
No, I cannot satisfy this Boolean function.
It's quite surprising how many practical things can be cast in that different form,
which will lead us to our next series of lectures about representation schemes and
solvers for Boolean satisfiability.