0:00

So here, we are at Lecture 3.3. We're continuing our exploration of

Computational Boolean Algebrea and Binary Decision Diagrams.

Up til now, we've shown you how you make. A BDD for a Boolean function.

But honestly, in the real world who wants, to manipulate one Boolean output?

Right? You know a block of logic on a real chip

has lots and lots of inputs and lots and lots of outputs.

We need to be able to manipulate lots of Boolean equations at the same time.

It turns out that BDDs naturally support that.

In fact, we can share nodes in BDDs so that many different functions can be using

the same ecosystem of nodes in the BDD. And it turns out that one actually gets

more efficient BDDs. So in this lecture, we're going to show

you some examples of how sharing actually enables us to represent complicated sets

of functions with one set of BDD nodes. So now that we know how you build a

reduced order BDD by starting with a decision diagram.

At least conceptually, requiring a total variable ordering from the root to a leaf,

and then reducing the BDD so that there are no redundancy so that you get the

smallest, tightest possible BDD. Let's just talk a little bit about the

interesting things you can do. So, the first thing is that you can

represent any function. And any Boolean function of anything is a

reduced ordered BDD. And you can do so in a canonical way.

So some lovely things happen. What if I told you, that my function of

variables x1 through xn is a 0? Right?

How might we represent that as a reduced ordered BDD?

Well, really, there is only one option. There's exactly one option, and it is

that. If this function is equal to 0, for all

possible inputs, then it has to just be a pointer to the 0 node.

What if the Boolean function is a 1? All right, well, then the same thing is

going to happen. If the Boolean function is a 1, then it

has to be a pointer to just the 1 node. And I'm going to go off to the side with

this little text box here and, box here and say let's, let's just remember

something. In a Reduced Ordered BDD, a Boolean

function is really just a pointer to the root node of a canonical graph data

structure. So you point to the top node of the BDD.

And then you descend the BDD and that's how you determine the values of the

function for the variables of interest. If f is a 0, it's a pointer to the 0 node.

Period. There's no other way of, of that

happening. And if the function is a 1, it's a pointer

to the 1 node. There's no other way of doing it, because

reduced ordered BDD's are canonical. There is one and only one way to represent

every function. So that's just a very nice simple thing.

What if in contrast, the function is of a, of variables x1, x2, dot, dot, dot, xn.

And we just pick one of those variables, we just call it x.

And we say that the, that function is just x and we ignore all the other variables.

That well, then, we're going to get a variable node.

And the low child is going to point to a 0.

And the high child is going to point to a 1.

And the function itself is going to point to that x node.

So it's really a very nice, simple kind of a thing.

What if we have a more interesting function, you know, a function that's got

a little bit of complexity to it. Let us assume that we have a function and

that it's a function of four variables, x1, x2, x3, and x4.

And that the ordering is in fact x1, x2, x3 and x4 in that order.

So here's just a simple function on the left.

X1 plus x2 and x4. What we'll notice is that interestingly

enough, there is no vertex labelled x3, would be, in here somewhere if it existed.

Because it has to be after x2 and before x4.

But this particular function does not depend on x3 and so there are no x3's.

And lots of graphs are shared, we're going to, we're going to talk about that more

extensively in this talk. And you know, this particular you know,

function is really just again a point or two the top node on this BDD.

Because a BDD is really just a pointer to the, to the, to the variable that defines

the top of the BDD graph data structure. And you can see, if you just think about

this for a little bit, that this, that this BDD actually makes sense for, you

know. For example you know this thing is really

x1, x4 plus x2 x4. And so what I expect is the only two ways

to make this function a 1. Okay?

Are I need to make the first term a 1. Or I need to make the second term a 1,

right? And the way to make the first term a 1 is

to go down this path, which says x1 has to be a 1 and x4 has to be a 1.

And the way to make the second path a one is to go down this path which insists that

x2 is a 1 and x4 is a 1. So it actually works.

Odd parity is a more interesting, kind of a denser, if you will, a more compact

function. Odd parity is x1 exclusive or x2 exclusive

or x3 exclusive or x4. And its odd parity which means that it

makes a 1 if and only if there is an odd number of 1's among the inputs.

So, for example, if we just think about lets say, x1, x2, x3, x4.

Imagine we have 1, 1, 1 0. Let's see if this works.

Okay. Here's a x1 is a 1.

Here's is x2 is a 1. Here's x3 is a 1.

Here's is x4 is a 0. Yeah, makes a 1.

All right. So this is this sort of zigzag sort of

path back and forth. This is very dense way of capturing the

fact that I only care about when an odd number of the representative variables

take the value 1. That's the only way I can get to a 1.

Any path with an even number of zigzags takes me to a 0.

It's a very tight representation. It's a very, kind of elegant and compact

representation. And it is also illustrating another very

important technical point. And that's sort of the, the substantial

part point of this particular lecture. Every BDD node, not just the root, but

every BDD node represents some Boolean function in a canonical way.

Now, you might create the BDD on the left because you chose to want to manipulate x1

plus x2 and x4, and that's great. But every node inside the BDD is the root

of some subgraph. And every single one of those represent

some other function. Even of you didn't want it, even of you

didn't try to create it, it just happens. Right?

So for example this, right, is f. And this is f, right, x1 plus x2 plus x

times x4. That's great, What if I tell you that,

that function is a g? What is that?

Right? And the answer is, if you kind of stare at

it for a little bit. That g is equal to x2 x4.

And that makes you know really good sense. The only way be able to get to the 1 node

from starting from g, is x2 is 1 and x4 is 1.

So g is x2 x4. That's just you know that's just an end

gate with x2 and x4 as its inputs. If we look at the, the BDD on the right,

okay? And, and we say all right now, this is f,

all right? So f is equal to x1 exclusive or x2

exclusive or x3 exclusive or x4. And now I start pointing at intermediate

nodes like that node. You know, what do I get?

Well, if you stare at that one that node is actually the root of the function x3

exclusive or x4. Right?

The only way you can get to the 1 node is if x3 disagrees with x4, if they have

different values. And conversely, the 1 on this side, right,

the 1 on the right hand side of the B, of the exclusive word BDD is x3 exclusive nor

x4. And just by way of a reminder, that's just

an exclusive or gate with a inverter bubble on the output of it.

And that's actually the even parity function for two inputs.

And similarly, the one on the right-hand side here the x4 node, that's actually

just the root of the function x4 bar, right?

And you stare at it, you'll say, yeah, if x4 is 0, I get a 1.

And if x4 is a 1, I get a 0. Okay.

That must be not x4. Now, we can take this idea that every node

inside a BDD represents a function. And we can take this to sort of the, the

next logical step, which is that we can do something useful with this fact.

So, here's a more interesting, rather more realistic example.

So let us consider a 4-bit adder. And so the yellow box that I'm showing you

on the left hand side is a four bit adder. It has two sets of 4 bit numbers as its

input. It has a3, a2, a1, a0, that's a 4 bit

number. And it has b3, b2, b1, b0, it's another 4

bit number. It adds those numbers together.

It produces a sum, s3, s2, s1, s0. But I don't care about anything other than

the most significant bit, the high order bit of the sum.

That's s3. And it's gotta carry out.

And I will note here, just for completeness, that there is no carry in,

in this example. Alright, so there's only a carry out.

And there's a high order sum bit. If I were to build the BDD for the sum

bit, S3, that is the BDD shown on the left, it's got a lot of exclusive or kind

of structure, because, you know, things on the inside of adders are, you know, lots

of exclusive or kinds of things. And it's got a positive logic carry chain

that tells you when, you know, the carry wants to be a 1.

And it's got a negative logic carry chain that tells you when the carry into the

high order bit wants to be a 0. And then you can decide, you know, based

on those two things. With a little bit of x or computation at

the top, you know. Whether the sum3 bit is a 1 or a 0.

If you then go look on the right hand side at the other BDD for the carry out, you

see it's got really quite a lot of the same structure.

In fact, the big gray box, which is what I am highlighting.

So I'm just going to sort of outline it here.

There's this big gray BDD over here. And there's this big gray BDD over here.

Those things are basically the same shared function, sub function.

And I, I , I can say that even more, even more strongly, those things are identical

graphs. There is nothing different, those things

are exactly the same. And so we get an interesting question.

Which is you know, in any realistic kind of a digital design scenario, you don't

build a BDD for one function. You build a BDD for a whole lotta

functions. I mean, you know, maybe hundreds and

hundreds of functions. So, you know, it's not at all unreasonable

that I'd like to build the BDD for the sum3 bit.

And I'd like to build a BDD for the carry out bit.

Do I actually have to build all the stuff in gray twice?

If I physically build a BDD package, and I physically build the data structures for

the sum3 bit and the carry out bit, do I have to physically build two copies of

those gray nodes? Gosh, I hope not.

That would be very, very inefficient. And it turns out that there is really good

news. One doesn't have to represent it twice.

One can have the BDD have multiple entry points or multiple roots.

Right? One can simply share that subgraph.

And so, as I'm showing it here again in gray.

All right. The carry out function gets to use it.

I'm going to circle the, the parts of the carry out function that use it.

And, in addition, the sum3 function gets to use it.

And, you know, the way it gets to use it, right, is that there's this shared BDD sub

function and the carry out gets to send some edges pointing to it to use it.

And the sum3 gets descend some edges into it getting to use it and you just share

it. Right?

And so these things are called multi-rooted, which just means that

there's more than one pointer pointing to the node.

There's a single node up there at the top that defines the entry point of the BDD.

So these things are called multi-rooted BDDs.

And again, every node in a BDD represents some Boolean function.

So this multi-rooting idea is just explicitly exploiting all of this to

better share stuff. So it turns out it's sort of an

engineering idea, but it's a wonderful and simple idea, it actually makes things very

efficient. You ask, how efficient?

Oh, it makes things wonderfully, magnificently efficient.

And so here's a, a, a lovely example from, from Randal Bryant again.

Why stop at two roots, right? You know, why not have as many roots as

you want, right? So if I have a, you know, sort of a, a

shared subfunction here. You know, I can have all kinds of people

wanting to use that thing. As, as, as, as many as I like.

So these are big savings for sets of functions.

You can minimize the size over several separate BDDs by maximizing this sharing.

So the thing that I'm actually showing you on the right is, the full 4-bit adder.

Right? So this is the full, 4-bit adder.

Right? And so what you're seeing are the four sum

bits, okay, and also the carry outs. So, four things, um,eight things go in.

Four As and four Bs, as you can see here. A0 through 3 and B0 through 3, and four

things come out for sum bits and one carry out comes out.

Now, how much savings do you actually get when you do stuff like this?

Well, if you were to build the BDD separately for each of the bits of the sum

and the carry out. If you had a 4-bit adder, it would be 51

nodes. And it would be almost well, 12,500 nodes

for the 64-bit adder. But if you shared them, and so 31 nodes

for the 4-bit adder and 571 nodes for the 64-bit adder.

Now, look. The difference between 51 nodes and 31

nodes is no big deal. The difference between 12,000 nodes and

600 nodes is a factor of, of what, 20? That's a gigantic savings and it just gets

bigger as things get bigger. So the multi-rooted idea, the sharing

idea, the fact that we can exploit the fact that every node in a BDD is a Boolean

function. And if somebody else needs to use it, they

can just point to it. That's a wonderful thing.

That's just a really great, great thing about binary decision diagrams.

And so, this lecture has been all about the fact that BDDs are shared data

structures that we can build lots of Boolean functions in the same data

structure. That every node in a BDD represents a

Boolean function and that we kind of reuse those things in appropriate ways with

multi-rooted graphs to do really significant amounts of, of, of engineering

savings. So, next, what we want to talk with a

little about is how people actually implement these things.