So, it turns out we need a more sophisticated model and the model that we

need has a name, it's called the Boolean Logic Network.

And it's surprisingly simple idea, so the way to illustrate that is, let's take an

ordinary gate level logic network with which you're very familiar and I, I'll

draw that on the left. And so there are two gates here.

The first gate is an and gate, it has the ab as an input, and the x as an output.

And the second gate is an or gate. It has x, the output of the and gate as an

input, and c, an input, and the or gate makes y as an output.

And let's transform that into this different thing called a Boolean Logic

Network. So, we still have inputs called a, b, and

c but we'll draw a little box around them now and we're going to be a little, you

know, more technical. We're going to call them primary inputs

because they're inputs that go to the entirety of the model.

And we still got x and ys outputs now drawing in little boxes on the right-hand

side, those are primary outputs, they are produced by the entire Boolean Logic

Network. And, now instead of two gates, there's two

bubbles, right? And so, there is a first bubble, which has

in it, the equation x equals ab. And it connects to the primary inputs a

and b, and the output x. And then, there is a second bubble and

that says y equals b plus c. And that consumes an output from bubble x

and a primary input c, and it connects to primary output y.

Now, these are the same representations of the same logic.

And so, what's really different here? And the answer is that, like the logic

network, the Boolean Logic Network is just bubbles, if you will, things that I can

draw that look like logic connected to inputs and outputs.

But unlike the ordinary gate level logic, which restricts things to be simple gates,

and, or, nand , not, such like that, in a Boolean Network model, any two level

Boolean function in a sum of products form is permitted in any of the bubbles.

So, x equals ab is a perfectly nice sum of products form, it's just got one product.

Y equals b plus c, perfectly nice sum of products form, got two products, each of

the products is pretty simple. But in general, the contents of each of

our nodes in a Boolean Logic Network can be arbitrarily complex, they just have to

be 2-level Boolean functions in sum of products form.

This turns out to be a remarkably useful way of representing complicated multilevel

logic. So, if I represent it like this, what do I

want to optimize? Well, it turns out that there's a

simplistic but surprisingly useful answer, which is the total literal count.

And technically, that would be that we're going to count every appearance of every

variable on the right-hand side of an equal sign on every single node.

So, yeah, logic delays matter, too but, but this is really a focus on complexity,

and what this is really counting is something that will really turn into gate

inputs. So, I've got a logic network down here in

a Boolean Logic Network form. It's got a, b, c, and d as primary inputs

on the left and Q as a primary output on the right.

There's a Y equals b plus c bubble that consumes b and c and creates Y.

There's a Z equals bc bubble that consumes b and c and creates Z.

There's an X equals yd plus z bubble that consumes Y and Z and primary input d, and

there's a Q equals aX bubble that consumes a, a primary input, and X an internal

node. And if we were to count literals, very

simply, look at every bubble, count everything on the right-hand side.

1, 2 in the Y node, 3, 4 in the Z node, 5, 6, 7 in the X node, 8, 9 in the Q node.

The number of literals in this design is 9.

And one of the things that I will also remind you of is that if we look at the X

node X is an output, now it's an internal output.

Okay. And so I guess, I should write, that it is

an internal output because it's created inside the Boolean logic network.

But it is consumed over here in the Q node and over here in the Q node X is an

internal input. Because it becomes an input, it's going

to, to be an input to somebody's gate somewhere, and so we may as well count

that thing. And that's why counting the literals

counting the appearance of a variable in a true or complemented form on the

right-hand side of an equal sign is a pretty surprisingly good model of the

complexity of one of these logic networks. So this thing is a data structure.

And what we know from our, you know, previous exploration of things like binary

decision diagrams, we are now expecting to have some operators that work on this data

structure. So, there are really 3 kinds of operators.

One, you actually know about. So, there are operators that simplify

network nodes. So, that means they simplify the insides

of a network node. They don't change the number of nodes in

the logic, Boolean logic network, they just optimize the insides.

You actually already know this. This is just 2-level synthesis.

This is 2-level optimization. This is in the, you know, the, the tools

we're going to use in this class. This is literally ESPRESSO running on the

insides of the node. So, good, you already know how to do that.

Another optimization, another operator that we need on this data structure is to

remove network nodes, and what one typically does is take nodes that we deem

to be too small And substitute them back into the fanouts.

And I'm going to show you an example on the next slide to make that more clear.

This is really not too hard. This is mostly just manipulating the graph

and some simple edits to sum of products form.

The big one, the, the, the exciting one, if you will, Is to add new network nodes.

This is factoring this is where you take some big nodes in the Boolean network

model and you extract some common divisors, some common some expressions,

you pull them out you create them as a separate node and you feed them back in to

reduce the overall complexity. This is a big deal.

This is new, this is really what we need to teach you.

This is sort of the heart and the soul of multilevel synthesis.

So, let's look at those examples of things that I just showed are just mentioned in

text on the previous slide. Simplifying a node.

I've got an example here where it says X equals a plus ab plus bc is a Boolean

logic network node. And I'm showing you that I could run

ESPRESSO on this node, and it would hopefully come back and tell me, well, X

is actually a plus bc. Why I do things like this is that as

structural changes happen macroscopically across the network, it's often the case

that the insides of the nodes can get, if you will, messed up.

And every so often, one would like to take a step back and just do a nice, powerful

optimization of the insides of every node and that's what simplifying a node lets us

do. Removing a node, here's my example of a

typical case, is where we have a small factor.

And the small factor we have here is Z equals ab and let's just be clear Z equals

ab is an and gate with two inputs, that's a very small factor and it is feeding to a

node X equals qZ plus stuff and a node Y equals cdZ plus stuff.

And let's decide that its just not worth keeping that node separate and so we're

going to make the Z node go away which is shown to the right of the arrow by a

dotted circle and we're going to take ab, the Z equals ab and we're going to push it

back inside the fanouts and every place there's a Z, we're going to replace it

with an ab. And so now, we have X is qab plus stuff.

Hence, Y equals cdab plus stuff. And you can immediately see, this is the

kind of example where, if you have some factors, if you think they might not be

doing you enough good to make them stay factors, if you push the factor back in

the fanout, the insides of a node in a Boolean network node get bigger, they get

more complicated. Maybe every so often, we could take a step

back and just optimize them, and see if there's, you know, something in there I

don't need. That's what simplifying a nodes does.

So, these two things are actually simplifying a node and removing a node,

are surprisingly synergistic. But the really interesting thing for us is

going to be adding new nodes. This is something that is technically

called factoring, and this is new and hard.

So, I've got an example on the left, X equals ab plus c plus r, Y equals abd plus

cd, Z equals abrs plus crs. If you were to count the literals, you

would say, oh, there are 16 of them, things on the right-hand side of equal

signs. But this problem is set up in a very

simple way so that I can pull out a divisor.

Q equals ab plus c, a common divisor and it turns out that I can take that Q and X

becomes Q plus r, and Y becomes Qd, and Z become Qrs.

And now, if we count the literals, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Now, I have 10 literals. I saved 6 literals from the design on the

left-hand side. Now, this design has more delay, because

it's got another level of, in this case, SOP logic.

But it has fewer literals, which means less gate areas.

So, hey, we're exploring that tradeoff curve that I told you about.

This is really the heart of, of Boolean, of the Boolean Logic Network model.

This is really the heart of optimizing things in the multilevel form.

So now, that you know what the basic foundational data structure is, we need to

take a step back and say, so, how do I go do this factoring thing, how do I go find

common divisors? So, let's do that next.