[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. 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.