[MUSIC]. So here in Lecture 10.2, we're going to continue to talk about technology mapping. And we're actually going to show a very interesting model of the problem. The problem is going to be solved in a style called tree covering. And what's interesting is it takes what feels like a very complicated Boolean algebra kind of approach to a problem. I've got this giant net list of stuff that comes out of more or less the result of multilevel logic synthesis. And I've got a library of physical gates which I get to use which gate goes where to map the output of the synthesis to what I can actually start working with and lay out. It turns out we're going to turn it into a very pure kind of a computer science problem. We're going to take the output of logic synthesis and require that it be a tree in a certain form, and we're going to take all of the gates in our standard cell technology library. And we're going to require that they be trees, tiny little trees in the data structures style, in a particular form, and we're going to turn it into a particular kind of a matching problem. It's going to turn into a very pretty, a very stylized, surprisingly simple computer science matching problem. So let's go talk about how we can take the technology mapping problem and turn it into a covering problem with trees. So we're going to talk about a very famous model of the technology mapping problem may they're the most famous model a model called tree covering. your logic network to be mapped is put into a particular form it's a tree of simple gates. We've already seen the simple gates part, we've seen the NAND gate NOT gate version of the logic from the previous lecture. It's easiest to assume two input NANDs and NOT gates makes our lives easiest to describe the structure of the problem. And your library is also available, your technology library, your standard cell library of real gates is also represented in this same form: trees of simple gates. Each gate represented as NAND2s and NOTs, and now there's an associated cost so we can say something about the quality of the overall mapping by adding the cost of all the gates that we use. What's interesting is that the method is surprisingly simple as an algorithm, and even optimal. Which is to say, once you have your problem mapped into this trees, gates cost form you actually get an exact and optimal answer. And I have to say that's actually a pretty rare thing in the VLSI cad business to, to have an algorithm that gets a best possible example. In a surprisingly simple, form. in a surprisingly, efficient algorithm. So, the original reference is, is by, my friend, Kurt Kreutzer, who's, now a faculty member, at, the University of California at Berkeley. I believe that he was AT&T Bell Labs when he, when he invented this. So the papers called DAGON. Technology binding and local optimization by DAG Matching is in the Design Automation Conference 1987, definitely worth a read if you can find it. So, what are we staring with? We are starting with your uncommitted logic that we want to do tech mapping on. And we are going to assume what came out of the multilevel logic synthesis was a network of nodes, each which is a sum of product form. So we replace each sum of product forms in the network nodes that's only NANDS and only NOTs. And we connect everything up. And this has a name, it's called the subject tree, and we're going to restrict things to two input NAND gates and inverters. It makes everything simple. You can take any piece of logic you want, even a complicated 2-level sum-of-products form with a big NAND gate a big OR gate if you will. and you can turn that into NAN gates, it's just, you know, a little sort of DeMorgan stuff. I've got a nice little example here on the right. It's got four inputs, a, b, c, d, on the bottom, and an output called capital Z on the top. And there are a bunch of internal wires and they've all got names so input A goes into an inverter makes an output called P. Inputs B and C go into a nan gate makes an output called Q. P and Q go into a nan gate makes an output called R. Input D goes into an inverter. Makes an output called S. R and S go into an and gate. Makes an output called T. T goes into inverter makes an output called Z. That's my subject tree. That's the little tiny example we're going to play with to see you know, what what mapping is actually all about. And, interestingly, your technology library also is an important part of this problem. And the first problem we have is that the technology library is not represented in the NAND2/NOT form. Right, so typically the technology library is just you know, a set of useful small logic functions, so let me give you an example of a set of useful small logic functions. This is an example, by the way, that I, I took from chapter ten in Nanni DeMicheli's book, so this is a nice example. What's in My Technology Library and inverter which we're just calling a NOT gate, a NAND2 which is a NAND gate with two inputs an AND2 which is an AND gate with two inputs. A NOR2, which is a NOR gate with two inputs, an OR2, which is an OR gate with two inputs. Something complicated, an AOI21. So this is a layer of AND gates, and then an OR gate connecting those products. And then an inverter. At the output and how many inputs are there? How many or gates are there? Sorry how many and gates are there? Answer two. How many inputs do they have? Well the first one has two inputs. And so I'm just going to draw it. That's the one with two input. How many inputs does the next one have? Oh it has only one input. That's why we draw it as a wire but I'm going to draw this in A little sort of a, kind of a dotted, dotted line way here You know, there's really an AND gate if you will. There's really an, a vestigial AND gate, a phantom AND gate there. It's just got one input. What's a one input indicate? Well, that's actually just a wire. So this is an AOI21. This is perhaps the first time you've seen a primitive logic element that is asymmetric. Right. Not every input is the same. Here is the symmetric version, a slightly bigger version. AOI22, again, a layer of and-gates. a single or-gate connecting those and-gates and then an inverter at the output, how many and-gates are there? There are two. How many inputs do they each have? Well, the first one has two and the second one has two. so that's why this is AOI22, as opposed to the gate on the left, which is AOI21. Okay. Nice simple, kind of it's easy to explain why oen would want to be able to use these gates in our, in our logic, but as I mentioned when we started this slide, the new problem is that it's not in the required form. Remember, the only thing that I get to play with are things made out of two input NAND gates, and inverters. So I have to take this thing and I have to transform it, into, the appropriate form. Now, that turns out not to be too hard, so I've got the library again drawn as a little kind of highlighted box in the top right-hand corner of the slide. A NOT gate, a NAND2, an AND2, a NOR2, and OR2. AOI21 and AOI22. Alright? So one, two, three, four, five, six, seven gates. One, two, three, four, five of them I would say simple gates, two of them complex gates. I need to transform this so the only thing I see are two input NANDs and inverters. That's pretty easy. So the inverter, well heck, that's just an inverter. Life is easy. The NAND2 gate is just a NAND gate. The AND2 gate is just an inverter with I'm sorry, a NAND gate with an inverter. at the output to get rid of the complement. I'll admit that the NOR2 looks kind of ugly. You know, the NOR2 is two inverters going into a NAND gate whose output goes through an inverter. Right? This is just the DeMorgan Law that says, you know, x plus y with a bar over it is x bar and y bar, so there's two input, input inverters giving you x bar and y bar. But the problem is that it's a NAND gate so I've got to get rid of the bubble. So, that's why there's another AND another inverter there. The OR gate is simply the NOR gate without the output inverter. So, it's two inverters leading to NAND gate. the nice thing about the ALI structures is that they really are some of product's forms. They're supposed to be a layer of AN-, of AND gates and an OR gate then an inverter. You know that a two-level form and/or structure, you can just replace the ANDs with a NAND and the OR with a NAND and it all just works. The only thing you have to be a little careful of here is that It is an inverting logic, and so it, it has to be the complement of the sum of products, sort of a form. So you get an inverter at the output, and if you're careful with the DeMorgan law, the wire, right? Which was as I said, kind of a one input AND gate. When you turn that into a NAND gate, you get a one input NAND gate, and one input NAND gate is an inverter. So you just got to be a little careful on that one. So this is A NAND gate with two inputs, a NOT gate with one input, those two outputs go to the NAND gate. The NAND gate goes through one more inverter to get the polarity right, and then you get a AOI21. And AOI22 looks exactly like that, except the wire, with the inverter on it. is replaced with a NAND gate. So, This is a nice symmetric structure. 2, 2 input nand gates going into a single 2 input nand gate which goes through 1 inverter to get the polarity right. And here we are I have accomplished what I wanted, my technology library is represented in exactly the same form as the output I get. From multi-level logic synthesis. In this form each library element is called a target tree so recall after I took the output of multi-level logic synthesis and turned it into NANDs and NOTs. I called it the subject tree after I took every one of the elements here elementary. library gates, any of the complex gates in my technology library, and turn them into NANDs and NOTs, it's now called the, each of them is called a target tree. So, what's the essential idea of tree covering? And, and this sounds a little strange, but the idea of tree covering is, I want to avoid doing any Boolean algebra. Even though we're actually kind of pretty good at that at this point. I don't want to do this with any Boolean algebra. I want to do this by just essentially pattern matching, you know, like, like, like matching a string, you know? A capital B matches a capital B but a capital B doesn't match a lower case x. the technology library which I'm again showing at the top left, a NOT, a NAND2. AND2, NOR2, OR2, AOI21, AOI22 each expressed specifically in NAND2 and NOT gates. And on the right I've got my little pattern my little subject. Right, the z. Tree and so this has a, b,c, and d as inputs, z is outputs,internal nodes p, q, r,s,t. It's got 3 nands and 3 inverters. What you will notice is that every one of the gates in my technology library is nothing but 2 input nands and inverters. And the thing that I am matching. Right? The thing that I am mapping onto these gates, is itself, just two input NANDs and inverters. I can do this mapping process by just making sure that I pick things from the technology library. Where the gates match exactly. No Boolean algebra at all. So, I am allowed to match things like NAND gates to NAND gates and I'm allowed to match things like inverters to inverters and that's it. So, look, here's a concrete examle. Let's select the AOI21. So, it's got an inverter on the top and then a NAND gate and then the inputs to the NAND gate are. 1 nand gate and 1 inverter. And if we look over at the subject tree what we can see, and I've got it colored in, in a kind of highlighted way, is that the top of the z tree looks exactly like a AOI 2 1, right? It starts with an inverter on the top. So I'm going to put a little check mark by the, by the inverter. And then when I look below it. The thing going into the inverter is a NAND gate and that looks like it matches. And then when I look to the left in this case I see a NAND gate going into the NAND gate and oh yeah, that's what AOI21 has. And then when I look to the right I see an inverter and it's like oh yeah, that's exactly the same. I can I can actually make the output of the z function by putting a aoi 2 1 as the output of this logic network. This very simple minded matching process has a name, it's called structural mapping. Find where in the subject graph, the library pattern matches everywhere. And there's a very simple set of rules, nand matches nand. NOT matches NOT and so on. All right so, that's the essential idea in tree covering. We're going to take elements from the technology library and we're going to put them on top of the subject tree and make sure everything lines up in some fairly simple way. With some quite simple rules, and the only mapping that I have, the only matching that I have to do is like gates have to match. So just to sort of summarize there, the general tree cover representation is a structural technology mapping, there is no Boolean algebra anywhere. We just match the gates and the wires in a simple pattern matching kind of way, and the result is a surprisingly simple covering algorithm for the cost-optimal cover. but first, I want to simplify the way we draw these, because there, there's still just too much going on in these diagrams. And I want to sort of emphasize the fact that this really is a very simple kind of a pattern matching kind of a process. And so, I'm going to show how we're going to represent the trees for covering. On the left again, I'm showing my little z subject tree inputs a, b, c, d output z, there are three NAND gates here, three inverters here internal nodes p, q, r, s, t just as before. Look, there's only three kinds of things you can match looking at this tree. And so we're just going to draw it in a really simple-minded way to sort of remind ourselves that there's only three things going on here. The first is that there are NAND gates, so instead of drawing a NAND gate, I'm going to draw a circle, and I'm not going to fill it in. So I'm just going to draw a white circle. Every place you see a white circle from now on, that's a two input NAND gate. And the inverters, I'm going to draw a black circle. Okay, and I'm just this is sort of arbitrary. the Nanni DeMicheli book has a different sort of notation for doing this, I'm trying to be even simpler than, than the way he's doing it, I think this merited. So an inverter is a black circle a manned gate is a white circle. And then there's also something that's not so obvious you need, there are inputs, right? And the inputs are square boxes, okay? So a NAND gate is a white circle . A NOT gate is a black circle, and input is a square. So if I take the z subject tree on the left-side of this diagram And I draw it again on the right, this is what it looks like. So, there are four inputs, a, b, c, and d. Those are now square boxes because those are inputs. We actually have to be careful that we represent those things. We have to match those things too, carefully. the a input goes into a black circle, because a is, A goes into an inverter that makes the output p. B and c go into a white circle. Because b and c go into a NAND gate, okay? The p wire output from the inverter. The q wire output from the NAND gate going to a white circle. Because p and q go into a NAND gate that makes output r. And so that's a white circle. Input d goes into an inverter that goes into a black circle. That makes an s. R and s go into a white circle because that's a NAND gate, That makes t. T goes into a black circle, that makes z. So this is just one to one exactly the diagram on the left-hand side here, but it looks very simple, right? Just the white circles, black circles and boxes with letters on them. Now You have to actually make the technology library in exactly the same style in order to execute this algorithm. And so I'm showing you a picture of the tech library as gates again. Simple NAND, and NOT gates. So there's a NOT and NAND2 and AND2, a NOR2 and OR2, AO121, A0122. One, two, three, four, five, six, seven gates in my technology library. Everyone of these things has to be represented in the same style wise graph. Form. So, there's the NOT gate. What does a NOT gate look like? It's a square representing an input going into a black circle. There is a NAND2 and an AND2. The NAND2 is just a white circle with two children left right that are inputs. The AND is a black circle because it's an inverter. At the output of a NAND which is a white circle with two, two boxes that make the inputs. NOR2 and OR2 are a little more complicated. Remember, NOR2 was a NAND gate with inputs at the inputs and the outputs. So, it's a white circle. Output goes to a black circle. Inputs come from black circles. Two input boxes, the OR looks just like it, but omit the output black circle. AOI21, a black circle at the top, because it's an inverter, that's fed by an OR, a NAND gate, a white circle, the inputs to the white circle, one white circle with two inputs, one black circle with one input. The NAND and the NOT respectively. AOI22, black circle at the top fed by a white circle, white circle fed by two white circles, each white circle fed by four square boxes. Alright, so this looks much simpler than what we started with. There is no Boolean algebra happening here at all. This is a very simple structural mapping problem. And so, I'm showing you now, the, sort of, the structural mapping problem in its, sort of, precise form. I'm showing you the technology library at the top of this diagram. NOT, NAND2, AND2, NOR2, OR2, AOI21, AOI22. And each one of them is the little set of black and white circles. And boxes from the previous slide. And at the right hand side, I'm showing you the little z circuit again, a, b, c, d inputs, z as output, internal nodes p, q, r, s, t. Three white circles, three black circles. And structural mapping says I have to find where I can fit the library gates, which are black circles, white circles, and square boxes, on top of the Z circuit and match with a simple set of structural Matching rules. What are the rules? The rules are mostly really easy and mostly really obvious. A white circle matches a white circle. Your allowed to put an and gate only where there's an and gate. So a white circle matches a white circle. A black circle matches a black circle. Your allowed to put a not gate only where there's a not gate. And, this is the one that's maybe a little bit complicated. We need to talk about this just a little bit. A square box which represents the input to one of the library elements. Or, the input to the overall subject tree. The thing that popped out of multilevel synthesis that matches anything. The way that works, is the way that it matches anything, that's how it's possible for the output of one gate to connect to the input of another gate. And, we're going to talk about this with, a little example here. So let's, let's just start by, by doing a, a sort of a complicated thing. So, I've got the technology library, again, shown at the top, not NAND and NOR. Or, AOI21, AOI22. And I've got my little Z tree on the right. Four inputs, a, b, c, d, three black circles, three white circles, Z at the top. The and/or invert 2 1, as we already said in a previous slide matches as Z Right? It's got, you know, a black circle at the top and then a white circle one level down, and then one white circle and one black circle as children and inputs. Right? The AOI21 matches at Z because of two things, alright? So the first thing, first reason it matches is that all of the internal nodes match exactly. And so I'm going to highlight the a AOI21 for you here. And then I'm going to highlight how the AOI21 matches, right. So at the top there's a black circle and the black circles match. There's one child of the black circle and it's a white circle. Those things match. There are two children of the white circle. a white one on the left and a black one on the right, turns out that matches exactly as well, white one on the left, black one on the right, I'm just checking the little boxes in the AOI21 pictures. Alright, those are all the internal notes and then, I'm going to put a star by this it's in red over here and the inputs match anything. And so what that means is, just to be very clear. The leftmost input of the nand gate circle. The white circle of the AOI21 matches p. Which is to say, it matches the black circle that makes p the internal wire/g. Now, that's an inverter. Inputs match anything, right? So that, white box, matches the black circle that makes p. The next input, to the NAND gate, the right input to the NAND gate, that's at the bottom of the AOI21, matches q. That matches an infer-, matches a A NAND gate, right? So, just be clear, the left box matches the inverter, the right box matches the NAND gate at q. Because, inputs match anything. And going forward, the third white box at the bottom of the AOI21, the input to the inverter in the AOI21, matches the d input. It matches a box, another box. Right? All of this works, all of this is required in order for, to have the semantics of the overall matching of how gates cover the tree work out okay. Alright, so, internal nodes must match exactly. We saw that in a kind of a simple way. And inputs match anything. Now, there's one kind of a careful thing you got to just be careful about. we haven't shown this in any of our examples so far but, the symmetries matter. So on the left of this diagram here, I am showing you an AOI22 has an output inverter A NAND gate. I'm connected to that inverter. And then the inputs to that nand gate are another 2 nand gates. It has a symmetric tree. You know? A black circle fed by a w-, a white circle. Fed by 2 more white circles. Fed by 4 white boxes. I don't care which way you sort of match. there's no, there, there's nothing asymmetric about this one. That's not true if you look at something like the AOI21, right. I mean, I have drawn the AOI21 as a NOT gate being connected to a NAND gate, being connected on the left. To a NAND gate on the right to an inverter, but there's no reason on earth that I couldn't flip that. And I've got a little red arrow here that flips it. Now, the inverter is on the left and the NAND gate is on the right. and I'm just showing you the black and white pattern trees. You know, the one way of doing it has a white circle on the left and a black circle on the right. The other one has a black circle on the left and a white circle on the right. This is not a symmetric pattern. When you're matching you actually have to rotate it and see whether or either orientation will match in your subject tree. So how does one actually do a complete tree cover. suprisingly there are two simple rules. Every note in the subject tree is covered by some library tree. And the output of every library gate overlaps the input of the next library pattern, it's basically it right so, everybody is connect to something or everybody uses some gate. Right? And, and wherever the output of a gate is connec-, is mapped onto the subject tree. Well then, that has to be overlapped by the input of some other gate. And you just sort of go from the bottom to the top. So, let's just say that, I'm only going to use nand2s and not gates to map this tree. What's a complete mapping? Alright, so here's a complete mapping. So, on the right hand side again the z subject tree a b c d, white box inputs at the bottom, z at the top. Three white circles, three black circles p, q, r, s, t nodes. Intermediate the outputs of gates let us talk about the, the matching. The first thing I can do is I can put a not gate at note p. And so what that means is that the output of the not gate is connected to the p wire. The black circle matches the black circle and the input to the not gate matches the a input to the overall z circuit. And similarly I can put a NAND2 gate at the q node, which means the output of the NAND gate matches the white circle that generates q and the inputs to the NAND match the b and c inputs. And here's where that output input thing becomes critical, I can put a NAND gate, a NAND2 gate after the r node. So what that means the white circle. Matches the r node. But the inputs match on the left. The p node, which is a black circle. And on the right, the q node, which is a white circle. And what we're already noticing is, hey, I've already mapped something else there. Yes you have. The output of the not gate. At p drives the input to the NAND gate also at p, the output of the NAND gate at q drives the input to the NAND gate also at q, that's how that works. So I can also put a NAND gate at node s, black circle matches black circle, input matches input. I could put a NAND gate at node t. Again, you're looking and you say hey node r is covered twice, node S is covered twice. Yes, of course it has to be. The output of the NAND2 at r is the input of the NAND2 at t. The output of the NOT at s is the input to the NAND2 at t. I could put a NOT gate at node z and again the input to the NOT gate matches NOT but, that's the output of the NAND gate. This is a legitimate mapping. Everything is covered and the output of one gate pattern. Connects to the input of the next gate pattern, and everything is covered, you know, this is a real gate network. You could actually draw this as logic, real logic. It's not a very interesting mapping, I will admit, but it's a, it's a structurally correct mapping. So this is one correct tree cover with three NAND2s and three NOT gates. So usually there are many, many different legal covers. Which one do you choose? The answer, and this is what we're going to spend the rest of this lecture on, is the one with minimum cost because every gate has a cost associated with it. [COUGH] So now let's assume that the library has a little more interesting stuff and it has a NAND2, a NOT, and an AOI21, which I'm drawing. And again the z tree on the right, a, b, c, d inputs, three black circles, three white circles, z at the top, p, q, r, s, t internal notes. I can do that same exercise. I could put a NOT gate at node p. That matches correctly. I could put a NAND Gate at node Q. That matches correctly. Its inputs are on b and c. I could put an AOI21 at node z, and it maps everything else because the AOI21 is a great, big, complex gate pattern. So the AOI21 covers node z, node t, node r, node s. And its inputs, okay? its inputs map to the output of node p, the output of node q, and the d input. And so this is another legal cover, another legal mapping of this design. A different tree cover, one NAND gate, one NOT gate, and one AOI21. Oh, which one do I pick? Answer, I pick the one with the minimum cost. I have a cost associated with every gate. I add it up. I pick that one. How do I compute that? Answer a beautiful, a lovely, a really elegant, delightful algorithm which is, no surprise to anybody in this class at this point, a recursive algorithm. So let's go talk about how that works next. [MUSIC]