0:00

[music] So, welcome to Lecture 6 where we start our discussion of multilevel logic.

Now in an ideal world, 2-level logic would be all we need.

You know, a bunch of the and gates and a or gate, we'd be done.

But unfortunately, in real designs, in industrial scale designs, in complex

designs, we need logic that doesn't look like a 2-level form.

We need logic that has multiple, indeed an arbitrary number of, of levels of logic

gates. And it's going to turn out that we need

new data structures, new representations, new math, new models, and new operators.

It turns out it's a really interesting and deep area.

And so, in this lecture, we're going to start taking a look at the first part of

the multilevel logic universe, which is we need a different representational model.

A network of gates and wires is just not sophisticated enough for what we need to

do, so we're going to introduce a new Boolean network model that will give us

the foundation to start really operating on these things.

So, let's go take a look at that. So first, a little bit of context.

Why are we interested in 2-level why are we interested in multilevel logic?

Well, and the honest answer is that 2-level forms are just too restrictive.

They represent a very particular area versus delay tradeoff.

So, I've got this graph shown below. It's got a horizontal axis labeled area

and a vertical axis labeled delay. You can think of area as basically like

gates and wires. These are things that take up space on the

surface of the chip and so the horizontal axis goes from small to big, and the

vertical axis is delay. You can think of this as the maximum

number of levels of logic gates required to compute the function, and the delay

axis goes from fast to slow as we go up. Two-level logic really represents a very

particular area versus delay tradeoff. It is basically the fastest kind of logic

in general because it's only two levels of logic, you know, two levels of gates.

But as a consequence, it's usually also the biggest because it takes a lot of work

to make something go that fast. Now, if we're willing to have things be

not so fast, right, if we're willing to, to, you know, let them be a little bit

slower it turns out we can trace out a very, very, very rich collection of

different area delay tradeoff options. And we just like a synthesis technology

that lets us explore that space a little more reliably.

And so, that's one of the reasons why we're not going to be doing 2-level

designs. It's just too restrictive.

The next reason we're not going to be doing, you know, just 2-level designs, is

that, they're just really tough to do for things that are big.

This is a cartoon. But suppose that I, I had a 1,000 gate

block of logic that I wanted to implement, really, it's not going to get implemented

like this cartoon with 999 and gates connected to a single or gate, in a sum of

products form. And, lets, let's, you know, let's just

say, that's a very unhappy or gate, it's got 1,000 fans in, I don't think so.

This is really not the way a complicated piece of logic is going to get

implemented. And this is going to get implemented in

something like a multilevel form, as I'm showing you on this next slide.

This is a small design done, done by a commercial synthesis tool.

It's got 11 layers of logic, which means to say, 11 layers of gates.

So, I didn't instruct the tool to do anything fancy, I just said, go.

And you'll see some gates in here that are familiar, you'll see some inverters and,

and you'll see some [unknown] gates. But you'll also see some things that look

a bit complicated. We'll talk about what those things are,

and why they're complicated. But this is 11 levels of logic gates.

This has somewhere between 3 and 8 gates per logic level and this thing has

something like about 65 gates in all. This is, you know, pretty, pretty simple,

little, little design but this would be really very impractical to do in a 2-level

form. And we could, we could, you know with,

with the modern synthesis technologies, we could specify how many levels of this

logic we're actually willing to put up with, depending on how fast we need it to

go. So, we just need some technology that's

able to do things that look more like this.

4:16

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.