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.

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.

BDD Ordering

VLSI CAD Part I: Logic

Rencontrer les enseignants