0:01

So, here in lecture 6.5, we're going to complete our exploration of Multilevel

Logic. What we know from the previous lecture is

that all of the aciton, all of the interesting factoring possibilities

happened in the kernels and the co-kernels of the Boolean equations expressed in the

Algebraic model. What we don't know yet is how do you

actually find kernels of Boolean equations expressed in this model?

Well, the answer is, you kernel them. And so, there is a lovely recursive

algorithm to extract the kernels of a Boolean equation in this model.

So, let's complete our study of Multilevel Logic by figuring out how to go find the

kernels. So, kernels are very, very useful, but

now, we have to figure out how to find them.

So, how do you find them, it's another recursive algorithm.

You should not be surprised as I've said multiple times in the VLSI cad business.

It's often the case that recursion is the one, one of the most powerful techniques

we used to find these things. But there's another couple of properties

that we need of kernels to, to be able to sort of put all the pieces on the table,

so that we can actually create a not very complicated algorithm.

So, here's the first thing I want to explore.

Suppose I start with a function F and it has a kernel, k1, in the kernels of F.

And so, one of the things I know is that I can write the Boolean expression of F in

this manner. I can say F is cube1 times k1.

Right, and k1 is the kernel, plus some remainder.

So, now I can ask a new and interesting question.

What's true about the kernels of k1? Because, you know, k1 is just a perfectly

nice Boolean expression. It's in the algebraic model.

It's clearly something that I can apply a kernel operator to.

It's got its own kernels. Do the kernels that live inside k1 have

anything interesting to say about F? Which is what I started with.

I, I took F, I did a kerneling operation on it, I got k1.

I now want to take the kerneling operation and do it on k1 itself.

Now, what happens? So, this is a kind of an informal kind of

uh,, kind of a derivation. We know this.

We know that F is cube1 times k1 plus remainder1 because k1 is a kernal.

Now, suppose k2 is a kernal inside k1. Then, I now know that I can write k1 as a

cube times k2, which is a kernal, plus remainder2.

Okay why don't I substitute that expression back into the original

equation, the one I started with. And then, just kind of expand it all out.

Well, if I, if I do that, then I'm going to find that f is cube1 times cube2 times

k2 plus remainder2 plus remainder1. Ok.

Now, let's just do a little bit of very simple Boolean algebra here.

Let's remember that, you know, cube1, ANDed with cube2, that's just a single

cube. You know, cube1 is something like a, b, c

and cube2 is something like x, y, z, and a, b, c, x, y, z, that's still another

cube. Right, so I can actually take those two

cubes and sort of pull them out. And if I just do little bit of algebra,

I'm going to get that f is cube1 and cube2, ANDed with k2, the kernel of k1,

plus a bunch of other junk. And so, the important thing to be able to

say is that F is equal to a cube, ANDed with a cube-free quotient, plus other

stuff. And the, the cube in that we're talking

about is cube 1 and cube 2, and the cube-free quotient is k2.

And so, what have I just said? I've said that F is equal to a cube times

k2 plus junk. Which means, if I take F and divide it by

a cube, I get k2 and k2 is cube-free. K2 is also a kernel of F with a different

co-kernel. That's a, a, a remarkable, beautiful,

practical result. Okay?

I took F, I did a kerneling operation, I got k1.

I take k1, I do a kerneling operation, I get k2.

What can I say about k2? It is also a kernel of F.

4:46

So, kernels have a hierarchical structure. They live inside of each other in this

sort of tree, right? And so, the terminology is that a kernel K

and F is a level-0 kernel if it contains no kernels inside of it except itself.

What that means is that if you were to apply a kerneling operation to it, you

wouldn't find anything new. Just kind of get yourself back with a

co-kernel of 1. And a level n kernel is level n if it

contains at least one level n minus 1 kernel, and no other level n kernels

except itself. So, level-1 kernels can have level-0

kernels inside them. Level-2 kernels can have level-1 kernels,

and also level-0 kernels. Right.

And you can start with F, and it turns out you can extract all of these kernels in

this very simple hierarchical manner. So, that turns out to be a really useful

insight. Now, that's my first result.

Here's my second result. Another result from Brayton in France.

Co-kernels of a billion expression in sum of products form correspond to

intersections of two of the more cubes in the constituent SOP form.

So, intersections here, means, specifically that we regarded cube is a

set of literals. And we look at common subsets, right?

So, this is not like ANDing for products, this is just simple common sub-expression.

So, if I had a function here, ace plus bce plus de plus g, if you intersect ace and

bce, you just get ce. If you intersect ace into bce and de, you

just get e. And what that means is that, that's a

potential co-kernel. Right.

So, you want to know where the co-kernels come from?

Intersect the cubes in the Boolean expression in algebraic form.

You want to have some sense of how the kernels arrange themselves.

There is a hierarchy of them inside the function.

That turns out to give us everything we need for a surprisingly straightforward

algorithm. So, how do you use those two results?

We're going to find their kernels recursively.

Again, you should not be surprised. This is just such a big, important

concept. And whenever we find one, we will call our

FindKernels algorithm on it to see if there's any lower level kernels inside.

And we're going to use algebraic division to divide the function by potential

co-kernels to drive the recursion. But we're going to be smart.

And so, we're just going to organize the computation to look only, only at the

intersections of the cubes. And if there's at least 2 cubes, we'll

look at the intersections of those cubes and we'll use that intersected result as

our potential co-kernel. And one technical point is that, you know,

we're supposed to start this with a cube-free function F to make things work

out nice. If it's not cube-free, you should just go

find the biggest common cube in the function and cross it out, and then, then

start. So, here's the algorithm.

And just as previously, I'm going to walk through the pseudocode of this algorithm,

but then, I am also going to show you a little kind of diagrammatic form how the

algorithm works, which I hope will clear things up.

So, find kernels is our algorithm, and it's recursive.

So, you start with a cube-free expression for F.

And the first thing you say is, alright, look.

I don't know anything, so the set k of kernels is empty.

And then, for every variable in x, I say, are there at least 2 cubes in F that have

that variable? If so, then, that's a potential co-kernel.

And what we know is that the way you get a kernel is by dividing F by a co-kernel and

what Brayton just told us is that you want to find a co-kernel?

Those are intersections of the cube. So, this is what I'm doing.

But I'm doing this, driving this process one variable at a time.

So, if there's at least 2 cubes in F that have this variable, let big S be the cubes

that have that variable in them. Let co be the cube that results from

intersecting all those cubes. That's a potential co-kernel.

Then, what we're going to do is take F and algebraically divide it by co, and that's

going to be a kernel, we think. And that'll be returned at the end.

But what we're going to do is recursively take F, divide it by that co-kernel, take

that new kernel and say, hey, let's go look and see if there's anything inside

that. And when we're done, sort of exploring

down the kernel hierarchy, as we come back up from the recursion.

The last thing that we'll do is actually return that kernel that we found.

Stick it on the set. Return it back up.

So, the algorithm may seem a little bit complicated, but it's actually pretty

straight forward if you just sort of build this little tree-like representation to

see how things work. So, let's just do this.

We have an example F equals ace plus bce plus de plus g.

And we're basically going to divide F by each of its variables and use that to

start the recursion. So, think of this as we're looking for

co-kernels that start with this one variable in them, and then, by sort of

recursing down, we'll be able to find everything.

So, we take F and the first thing we say is, alright, let's go look for all the

cubes that have an a in them. And the answer is there's only one cube

with an A in it and what we know from you know, the theory that we've got right now

is that if there's not at least two cubes There's nothing worth doing, and so

there's no work to do, and so we stop there.

What about cubes that have a b in them? Well, there's only one of those.

What about cubes that have a c in them? There's 2 cubes that have a c in them.

Those cubes are in fact ace and bce. So, you know, since we know that

co-kernels are intersections of cubes and we have at least 2 cubes, we have

something we can intersect. And so, we can see what's going on.

If we intersect them, we get ce and that is a co-kernel candidate.

So, we're going to divide F by our co-kernel candidate to get a plus b.

Well, that turns out to be cube-free and, you know, that's good.

That's actually a kernel. And the way this is going to work is we're

going to recurse further on that. Right, we're going to call the function on

this a plus b and we're going to reduce the same thing.

We're going to say, so, is there any as in it, any bs, any cs?

And we're going to do it. And we'll actually get a plus b on the way

back from that recursion. Next, you know, we got to the d variable.

Are there more than 1 cube with ds in it? No, alright, well then, we can stop that.

How about e? Are they any cubes with es in it?

Yes, actually, there are 3 cubes with e's in it.

And if you look, there are ace, bce and de, if we intersect them, we get a

co-kernel candidate e. F divided by the co-kernel candidate e is

ac + bc+ d that's cube-free. So that, that's actually, that's a kernel,

and again, well recursed by doing the same thing.

Call the function on itself on ac + bd + e and check every single variable and see

what we can find. So, when that returns, we'll go back,

we'll check the last variable g, there's only 1 cube with a g, so there's no work.

So, this is what happens at the first layer of the recursive calls, let's go

look on the next slide and see what happens when each of those boxes that

suggests there's more recursion actually recurses.

So, what's happening at the next level of the hierarchy?

Well, you know, here we found a plus b is a good kernel.

And then, we recursed down further, and so, we would actually call the recursion

with a plus b on it, and we would discover there's no work to be done on any

variable. And so, what would happen is we'd return a

plus b with a co-kernel ce. And that's how that branch would finish

itself. On the other hand, over here when we did

ac plus bd, bc plus d and we did the recursion there is actually some work.

When we looked at a, there's no work to be done, there's only one cube with an a,

only one cube with a b, and similarly only one cube with a de, and a g.

But there are a couple of cubes, there are two cubes, with this a c in them, ac and

bc, we intersect them to get a co-kernel candidate, c.

We take F and algebraically divide it by co, we get a plus b, it turns out we get a

plus b again. Right, again, we find this same kernel

with a co-kernel ce, only what's interesting is that when we found it

previously, we found it by immediately finding the co-kernel ce and this time we

found it by first finding the co-kernel e, and then second, finding the co-kernel c.

Okay, that's a little awkward, but it's not wrong, it gets the right answer.

So, we'll recurse on a plus b, we'll discover there's no more work and a plus b

will come back, saying, hey no more kernels living inside of it, we're done

with that path of the recursion or will return everything up the tree.

So, we get ac plus bc plus d and we get a plus b.

So, with this algorithm, you can find all the kernels and the co kernels too.

And you get the kernels by ANDing the divisor co cubes up the recursion tree.

There's one tiny problem, you're going to visit the same kernel multiple times.

And the solution is just, you have to remember which variables you've already

tried as you go down the paths of the recursion tree.

So the problem is the kernel you get for co-kernel abc is the kernel, the same

kernel you get for kernel cba. The kernel algorithm doesn't know this.

It's going to find it multiple times. There's a little extra bookkeeping to

solve this, but I'm just not going to worry about it.

Now, this is a fabulous result because it turns out that the kernels and the

co-kernels are exactly the right component pieces for doing what we see here on this

diagram. If I want to extract a single cube divisor

from multiple expressions, I'd like to know where to go look.

If I'd like to extract a multiple cube divisor from multiple expressions, I'd

like to know where to look. So, if I have F and G as nodes in a

Boolean network logic model, I would like to pull out divisors which are either a

single-cube or multiple-cube. So, a single-cube is like abc.

A multiple-cube is like abc plus def. And use those extracted divisors to

simplify the internal structure of the F and the G node.

And when we started this lecture, you had no ideal about the, the, the Boolean

network model, you had no idea about the algebraic model, you had know idea about

algebraic division, you had no ideal about factoring, you didn't know how toe extract

them. And now, you know a remarkable amount, you

know that it turns out that the only place to look for multiple cube divisors in

intersections of the kernels. And the good place to look for single-cube

divisors is in the co-kernels. And you know that kernels live in a

hierarchy inside this Boolean expression. So, you want to go find a single-cube

divisor, go look at the co-kernels, you want to find a good multiple-cube divisor,

go look at the kernels. And algorithmically, we know how to do

that in a simple deterministic manner. There's only one thing you really don't

know how to do yet and that's how do you deal with something that's got, like a

thousand Boolean network nodes in it. Well, alright, that's, that's what we're

actually going to go do in the next sequence of lectures.

So what's our overall summary for Multilevel Synthesis Models?

The Boolean network model, it's like a gate network, but each node is in, in the

network is a sum of products formed. It supports many operations to add, reduce

or simplify nodes in the network. The algebraic model and algebraic division

are big new ideas. They simplify Boolean functions to behave

like polynomials of a real numbers. We can one boolean function by another.

F equals D times Q plus R. Kernels and Co-kernels of a function F in

the algebraic form, the kernel is a cube-free quotient obtained by dividing by

a single cube which is called a co-kernel. Intersections of the F and G kernels are

all multiple-cube common divisors. There are, is only one place to look for

good divisors, and that's looking in the intersections of the kernels.

That's an amazing big, practical result of engineering consequence.

We're going to talk about how to use that. The problem, the big thing you don't know,

is that you don't know what are the best common divisors to get?

You know that, that the algebraic model and the kerneling operation kind of tell

you what the right pieces are. But you don't really know how to deal with

something with like a large Boolean network model with lots of lots of nodes.

And that's what we're going to talk about next.

I'll just say, also by, as an aside, the algebraic model and algebraic division are

not the only options in Multilevel Logic. There are some Boolean division models and

algorithms. And there are also some things that are

sort of more expressive than the algebraic model, but less expressive than a full,

complete Boolean model but these things are more complex.

There's a really interesting and rich universe of models and methods here.

There's a couple of good references to read about these things.

The paper by Bob Brayton, Rick Rudell and Alberto Sangiovanni-Vincentelli and Albert

Wang MIS: A Multiple-Level Logic Optimization System from 1987.

That's a really good primary source for the sort of the early historical evolution

of these things. And also, Giovanni De Micheli's Synthesis

and Optimization book from McGraw-Hill, that's another really good place to look.