So, here in lecture 5.2, we're going to continue looking at 2-level logic synthesis. And I have to admit, this is probably one of the most complex sounding talk titles I've got, The Reduced-Expand-Irredundant Loop, which sounds very impressive, indeed. And is the name of an extremely famous heuristic for doing 2-level synthesis, 2-level optimization, that uses the idea of reshaping a cover so that we get a good, but not necessarily perfect, solution. And so, what we're going to do in this lecture is, we're going to take a high level tour through all of the key steps of this famous heuristic method for 2-level logic optimization. So, let's go see how that works. So, let's assume we are starting with a truth table. But just to make this a little more realistic, let's note that we're going to start with a truth table that can have input don't cares. And what input don't cares means is that each row of the truth table can match many rows of the full truth table and we do that by just allowing people to put an asterisk which says, you can match either a 0 or a 1. So, for example on the input truth table that I'm showing on the, on the bottom right here there are one, two, three, four, five rows of the truth table, table and they're going to each turn into some sort of a cube and they're called P, Q, R, S and T, respectively. And I've got a Karnaugh map on the upper right of the diagram four by four, a typical four by four grid ab on the top, cd on the left. 1s in the top, left two by two squares, bottom right, two by two squares, the entire bottom row is 1s, and the entire second row of the Karnaugh map is 1s. And I've got a bunch of covers here, I'm going to talk through them one at a time. So, let's talk about the, the row of the truth table 0 star 0 star that's really just this 1 right here, the upper left two by two. This is cubed P because obviously a is 0 for those 1s and c is 0 for those 1s, but b and d can be anything. So, that's just a very simple way of specifying more than one row of the truth table, more than one single one in the Karnaugh map. 0 star 10, which is cube Q will be this one here on the bottom. That will be the bottom left two, bottom column left two 1's, that's cube Q. Of course, if you'd like, it's always possible to specify individual 1s in, in the Karnaugh map that, that's these guys right here. So, this one in the Karnaugh map is S and this one in the Karnaugh map is R. Second row of the Karnaugh map, right two squares. And T is going to turn out to be the bottom right corner bottom right corner of the Karnaugh map. That will be cube T. So, this just makes it easy to specify a function with lots and lots of variables. You know, you got a function with like 25 variables in it, you do not want to write out a truth table with two to the 25 rows, believe me. You just want to specify where the function is a one and that's probably a whole lot less than two to the 25 rows. You can specify these with these input don't cares. It makes a very, very tidy and very convenient way of doing that. So, this truth table with its input don't cares each row with its pattern match ability, specifies a product, a cube, it might not be prime, that's important to know. There's nothing that says this is a very good cover, but it surely is a cover of all the 1s. So, if you will, it's a bad Karnaugh map. Our goal is to start with this, and then, do some optimization. Now, the first step is to expand each cube to be a prime. So, expand is a heuristic and this is actually going to get done one cube at a time. So, we're going to take each cube in some appropriate heuristic order and we're going to make it as big as we can possibly be and what that means is that we're going to make it prime. Now, let's be clear. There might be different ways of doing this for any specific cube. You know, you might be able to grow it in one direction or a different direction. And we're not really talking yet about how we do that. And so, we've got three cubes in our current design that have been expanded. The S cube is no longer a single one in the Karnaugh map. The S cube is now the entire second row of the Karnaugh map. And the R cube is no longer a single one in the Karnaugh map. The R cube is a two by two square of cubes in the Karnaugh map, it's the middle two rows in the right two columns. And the Q cube is no longer the left two 1s in the bottom row of the Karnaugh map, the Q cube as it has been expanded is now the whole bottom row of the Karnaugh map. So, the new solution is a prime cover. Every cube is as big as it can be. But it's not the best we can necesarily do. There's more work we might be able to do on this to improve it. So, what's the next step we do? Well, the next step is we try to remove redundant cubes. And the name of this heuristic is irredundant. Okay. The irredundant operation removes redundant cubes from the cover, and a cube is redundant if I can remove it, and all of its 1s are still covered by other cubes in the rest of the cover. And it's important to note that we can clearly remove cube R. And I'm just going to put some little hash marks across R here, so you can sort of see it. Cube R is the right two columns intersected with the middle two rows. Cube R is covered entirely by every, by, by some combination of the other cubes. So, we can get rid of it and if we remove it, the new solution will still be a prime cover and it is technically minimal and what minimal means is I cannot remover another cube without breaking it, without uncovering some 1s. This is one of these local minimum things like I showed on this conceptual graph a couple of slides ago. However, we might not be done. We might still be able to do better, so what do we do next. This is a very interesting idea. We're going to reduce the prime cover. Reduce is another heuristic. We're going to take each cube. And we're going to shrink it as much as possible, but we are not allowed to uncover any 1. So, we're not allowed to break the function, but we're simply going to take the cubes that are covering the function and shrink them, so that none of them overlap. What's going to happen here is that we can shrink the S cube. Which is suddenly going to become the right two 1s in the second column and we're going to shrink the Q cube and so we're going to become the left two 1s in the bottom most row. This is our reduced reshaped cover, this is a really strange beast. This is, if it uses a Karnaugh map, I'd failed you, right? I mean this is this is a bad solution. But this is a really amazing essential step. This new solution has a different shape and what's going to happen is that from this seed, we are going to expand it again and perhaps when we expand it, we'll be able to find yet another superior solution. This is the critical step in this key chain of heuristics that we're showing here. This is the idea that I said in the intro talk. I need a way of, of you know, making a big step from one solution to a different solution, from one local minimum to a different local minimum. And the big trick is you reduce things to the strange non-overlapping non-prime cover, and then, when you expand it again you might get a different answer. You might get a better answer. You might find some new cubes that are redundant that you can kill. So, if we apply the same heuristic expand heuristic again you might get a different answer because you started from a different starting point. And again, when you run expand, part of the goal is going to be to see if you can overlap some other cubes so that they can go away. Oh, look, I've done that in this particular example. I've expanded the S cube by basically growing it down and I've expanded the Q cube, which is the bottom row, by growing it to the right. And suddenly, if we will go take a look at the T cube, we see, oh, look, I can make the T cube go away. Because I had a different solution after reduction, because when I did expand I got a new solution, I found a new local minimum. I can, I can work with this. So now, we, again, run the irredundant heuristic, but it is starting from a different cover so I can get a different answer. We took each cube and we expanded it to make it prime, but we also tried to cover the cubes to make them redundant. It's part of the heuristic. So, in this example we can kill the T cube, and I'm just drawing that in. So, the T cube is now the bottom right two by two square, right most 2 columns, bottom most 2 rows of the Karnaugh map. That cube can go away. Just going to circle that and sort of draw it. That cube can go away as the result of, of redundant. After this, the cover is again and prime and it's irredundant and I can't remove anything to make it smaller. So, it's still some sort of a, of a local optimum, we're just not sure how good a local optimum. Now, look, in this particular example, I got lucky, I got the best answer. Right, after that set of reduce expand irredundant heuristics, I got the best answer. This will generally not happen, you know, exclamation point, exclamation point, I cannot guarantee you that this is going to happen, but what I can guarantee you and this is the big important takeaway, what I can guarantee you is that this thing is prime. I can't take any cube and make it bigger. This thing is minimal, can't remove anything and irredundant, which is sort of the same thing. This is a really good local minimum. This is a really good local solution. And it turns out in practice that this iterative improvement by reshaping can produce really excellent solutions and can do so really fast. This entire sequence of ideas is really famous. This is the rude expand irredundant loop which was the, basically, the name of the title of this lecture. And so, you know, what do you start with. Well, you start with some sort of a prime cover, right. You could do that by taking, for example, your bad truth table cover, and then, expanding it. Right, you could then run reduce on it which gives you something that is not prime. You could then run expand on that which will give you something that's prime and different, but also may be redundant. You actually, you hope its redundant, because you are trying to get rid of some cubes. You can then run irredundant on that and you will get something that is prime and irredundant. And then, you go back and you do it again. What are you going to do next? You're going to reduce it, maybe you get it something with a different shape, it's kind of a pivot. Lets you see, well, maybe I can get out of this local minimum and get myself to a better local minimum, and so, you keep running reduce expand irredundant, reduce expand irredundant, and basically until it stops getting better. This is a really famous idea. Maybe the most famous idea in the 2-level synthesis universe. And there's also a famous tool called ESPRESSO. So, ESPRESSO started at IBM and it finished at Berkeley. There's a very famous book from 1984 by Bob Brayton, Gary Hachtel, Curtis McMullen, and Alberto Sangiovanni-Vincentelli, that's definitely kind of the key reference for this stuff. Rick Rudell master's thesis from Berkeley in 1986 is also a pretty good source for, for a lot of the deep structure. And [unknown] De Michelis textbook from McGraw Hill in 1994 is also another really good place to look for the you know, a kind of a textbook level presentation of this stuff. So, this is the high level tour of 2-level synthesis. Boy, there's just a lot of really interesting stuff in this universe. I wish I had time to talk about a lot of it. So, what I'm going to do in the next lecture is just give you one tour of one step to try to give you some of the flavor of how this stuff actually works. So, let's go take a look at that.
