[SOUND] So, here in 10.3, we're going to do something in the exploration of technology mapping, that sounds very strange. We're going to tree-ify, the netlist. Now. What we learned in the previous lecture was that we're going to model the output of the logic synthesis step and all of the gates in our standard cell technology library as trees. And there are going to be trees of very simple things, nandgates, notgates, inputs and wires. It turns out that for the particular kinds of algorithms that we want to be able to do this matching to work, everything needs to be a tree. And it turns out that under some very natural circumstances, the stuff that pops out of logic synthesis is not a tree. And so we sort of coin a word here, what is the act of taking a net list that comes out of logic synthesis and breaking it apart into things that are trees and the answer is we tree-ify it. And so, let's show you in this kind of short little lecture how we tree-ify the net list so we can move forward with technology mapping. So, let's talk about the specific steps that we need for a complete algorithm for technology mapping using this technique called tree covering. Th, there's really three parts. There is tree-ifying the input netlist, which is a very strange sounding word, I will admit. It's a key assumption and that's what this lecture's about. There's the tree matching step, which is how do you take each node in your subject tree and ask, well, what in my library, my technology library, maps there? And then, the real heart of technique, which is the recursive minimum cost covering, that assumes that once you know what matches at any given mode in the large subject tree, you can actually somehow construct an optimal covering with a, with a good cost. So the first step is that we have a, we have an important assumption. This is this thing called tree-ifying the input netlist. This is actually a really important assumption we're going to talk about this now. So let's talk about this process of tree-ifying the netlist. Now the big reason we have to do this is that all the algorithm's we're talking about in the technology mapping lecture. They only work on trees. Not more general graphs and as an example of a general graph I've got the netlist shown at the bottom with the blue gates. So these are gates, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Gates one, three, and five are inverters and gates two, four, six, seven, eight, nine, and ten are nand-gates. So gates one and three drive gate two, gates three and seven drive gate four, gate seven also has an input from gate six. Gates seven and eight drive gate nine, gate four drives gate five, gate nine drives gate ten. These are directed acyclic graphs. They have directed edges basically from the output of one gate to the input of the next gate. We're not actually drawing arrows, but they are directed. There are no loops in this graph. So their directed acyclic graphs. And the big idea here is that every place you see a gate with a fanout, which means that the gate drives more than one other gate, you have to split the net list there. And so that's gates three and seven in this picture. Now the rules for the mechanics of how you tree-ify are actually pretty simple and, and here they are. So the first rule is that every gate with fanout more than one becomes the root of a new sub-tree. And then the second rule is that each connected fanout becomes a new input. Now this is much easier to see if we actually just walk through this net list and do a little surgery on it to fix it. So the first rule says every gate with a fanout becomes the root of a new subtree. So let's go look at where the fanouts are. Well, Gate three fans out to two places and gate seven fans out to two places. So the way to think of this is I'm just going to cut those wires. And then I'm going to do some more work on this netlist. So, the first thing that we can see happens is that gate three, because it had a fanout of more than one becomes the root of a new sub tree and the green circle is circling the entire tree in the tree-ification process. Now, interestingly enough, gate three is the only gate in this tree and it's you know, just the way this works. So three is the root of a new tree and it's got only one gate in it. Similarly gates six and seven are also going to become a new tree. And gate seven will become the root of this new tree. because gate seven was the gate with the fanout. Gates one and two will become another new subtree because we basically cut that fanout. The output of three. And looking at rule number two, each connected fan out becomes a new input to a new tree. That input that used to come from gate three, well now we are just going to say it's a completely independent input it just comes from the outside world, it's completely unconnected from gate three. We are just going to pretend it has nothing to do with gate three and that way we create an entirely new tree. No fan outs. And we're going to map that new tree with gates one and two in this new input separately. Similarly gates four and five become a new tree. [COUGH] And, we'll notice that gate three and gate seven were driving gate four. And those wires don't exist anymore, so we're going to make one new input to deal with the connection from gate three and a second new input to deal with the connection from gate four. So gates four and five are a new tree. And similarly gates eight, nine and ten are a new tree. And we know that gate nine has an input from gate seven. That was a fan-out. Right? So we're going to give gate nine an entirely new input. To make it not at all connected to gate seven, and this is what we get. You'll note that there are five green circles around the new sub-trees. And what happens is, we split this directed acyclic graph with fan-outs into five separate trees, and we're going to map all five of these trees separately. And then after the technology mapping we'll connect them back up so that it's the original, logically doing the right thing with the original netlist. Now I need to be careful to say that this entails some clear loss of optimality because there's some kinds of mapping that might go across the boundaries of these trees with logic elements and I simply cannot map across these trees so you win some you lose some. What we win is that we have tree-ified things and so we can precede with the rest of this lecture and we will be able to map them. But there's some kinds of optimality that we just can't get. So, looking at this new slide, let's just look at the result. Now, just to summarize again, all the algorithms in this lecture require trees not DAGs. So, every place there's a fanout from a gate you have to cut it and tree-ify. This is going to lose some optimality. There are in fact, some ways around this, but we're not going to discuss them in this this lecture. We're, we're primarily discussing the most famous technique in this, space of technology mapping algorithms. So, on the left of this diagram, I've got the same net list, from the previous slide. So this is gates 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Right? And the netlist is not a tree. And when we do the tree-ification process we get the results on the right. We have five separate trees. So just going from left to right. Gates one and two are a new tree. Root of the root of this tree is gate two the end gate, and gate two has a completely new input which is depicted by that black box. That's new because we are not a allowed to deal with any of the fan outs that were in the original net list. Gate three is it's own tree all by itself and so it's the root. Gates four and five are a new tree, and the root is five. And gate four because it was driven by fanouts now has two new completely new inputs. Gates six and seven are a new tree, and the root is seven. And gates eight, nine, and ten are also a new tree. And because gate nine was driven by a fanout, gate nine gets its own new input. And so that's the result. On the left of this slide, the directed acyclic graph original logic netlist with fanout from gates three and seven. On the right, five separate trees. This is a really simple process. There's not really any decision making going on here. You just look at a gate that has a fanout, you break the wire. The gate becomes the root of a new tree and anything driven by the fanout, you say hey, I'm a new input. And you just walk through the netlist doing this. There's really no choices involved. You get what you get. So, you get a lot of little trees. But as we proceed in this lecture, we're actually going to be able to do a very good job of mapping these individual trees. And then what's going to happen is we'll just connect them back together at the end. Now, let's just ask a question. I just told you that you take the subject graph and you look at every place there's fanout, and you just cut the wire, and you break the network up into trees. That's in the subject graph. What about the pattern trees? What about the target trees, the things that your technology library is made out of? You know, those are little things, like nandgates and notgates and, and you know, mildly complex things like and or inverts, Are there any ordinary common useful gates in my technology libraries that can not be trees? And what's really surprising is the answer is yes. Yes with an exclamation point. And again there's some tricks to deal with this stuff it just sort of makes for some messy case analysis but its not worth talking about here. well, what is it that's in a pattern library that's just the sort of a, a basic perimeter gate that, that can't be represented as a tree. And one of the answer is an exclusive war. So here's a little picture of an exclusive war gate, go two inputs A and B and an output Z. Let's recall what an exclusive war is Z is A B bar plus A bar B. And so now I'm going to draw that as a logic network and so what do you get? Well, it got an A and a B input at the bottom. And the a input goes to a nandgate. And the A input also goes through an inverter to the other nandgate. Right? Because it's A in one of those product terms an A bar in the other product term. And the B input goes in to the other nandgate and then it goes through an inverter and it goes into the first nandgate. And then the output of those two nandgates goes into a nandgate because that's just how you make a sum of products and or form. And that's an exclusive war represented entirely with Nands and Nots. And the immediate problem we have is that there's fanout there and surprisingly the fanout is just from the input wire. The A goes to the nand and it goes to the inverter, which means, it's got fan out which means this is not a tree. And similarly the B input has fanout. It goes into the nandgate and it goes into the inverter. It's got fanout. And if I were to draw this thing as one of our little black circle white circle box trees, there would be up at the top the Z output which comes from a black circle because there's a nandgate. The two inputs to the black circle are themselves black circles because they are nandgates. And the inputs to the two nandgates are, well. Each one has an A on the left and a B on the right, and then each one has the other input going through a white circle. Right so the A box goes to a black circle, and then it goes from a white circle to a black circle and the B box does the same thing symmetrically, and the problem is that there's fan out immediately at the A input and so this thing is not a tree. Why is this thing not a tree? Well I can start up at the root. I'm just going to sort of draw it. I can start up at the root and I can go down two different paths to get to the A node. That's not possible in a tree. There's only one path from the root to any internal node in a tree. So, this is not a tree. And so, interestingly enough, you don't get to use EXOR gates in the very simple kind of mapping that I'm going to show you. Now, is it possible to repair this? Oh yes, absolutely. It just requires a little bit of technical, messy case analysis. It's just not worth doing at this time. So, the tree-ification assumption is kind of simple to deal with. You take the subject network that pops out of multilevel logic synthesis and the transformation into nans and inverters and any place you see a fan out you simply cut the wire and you break what is a large logic network into probably several smaller networks. And you just agree that you're not allowed to have a target library element in your technology library that's not a tree. Which means you're not allowed to use an exclusive war gate among some other things. And so that's the tree assumption. And now that we've got trees for both our subject and our many small targets. Our next problem is how do you match something. How do you take something from the technology library? A small pattern tree and figure out where it fits in the large subject tree. So, let's go look at that next. [SOUND]