So here in lecture 10.6 we are going to finish our discussion of technology mapping. we know at this point that we treeify all of our net lists. We know that we match where the technology library fits the gates in the trees. And we know that we can use this lovely recursive minimum cost covering algorithm to figure out where everything goes. Let's just do a big example. We're going to do an example step by step, gate by gate, node by node, and wire by wire, to show you that this is actually a really simple algorithm. a very pretty elegant algorithm. And that it gives really good results. You can understand why the algorithm works and how it works. So let's finish up the technology mapping discussion by showing you this example. >> So, we've come to the point in our tree mapping discussion where it makes sense to just do a great big example. So lets go look at how the minimum cost covering algorithm works on a nice sized example with the library. That we've been showing elvolving as we've gone through the lectures and show step by step how the minimum covering idea works. So, here we've got our subject tree, this is the same example that we've been using. So inputs A B C D Z output at the top, three white nodes for NAND gates, three black nodes for inverters internal nodes PQRST, Z is the output of the subject tree. And on the bottom I'm showing again our pattern tree library, NOT, NAND2, AND2, NOR2, OR2, AOI2, or AOI22. And at the top I've got basically a little table that we're going to fill out to show you how this algorithm works. And it's got three columns that we're going to be filling in. It says at node can, match, with mincost. And so what we're going to do is node by node walk the tree. we're going to figure out what can match there from the pattern library. And then we're going to write a recursive equation for the matching and then we're going to basically solve it. Sort of in the manner in which the recursive algorithm would actually do it. So, the first thing we need is we need cost values so I have now shown cost on the pattern tree. The NOT cost 2, NAND2 cost 3, AND2 cost 4, NOR2 cost 6, OR2 costs 4. AOI21 costs 7 and AOI22 also costs 7. So with that we can start. Looking at the top of the subject tree, what we see is that at node Z and I can put a NOT gate. And that costs 2, that's the cost of the inverter plus the minimum cost of t because the input box on the inverter is going to cover the t node, and that's the recursive, so the recursion. NOT can match here with a cost 2 plus mincost t. What can also match at this node is an AND2. And the cost of matching the AND2 there is 4, the cost of the AND gate plus where the inputs are. The leaf nodes and that turns out to be 4 plus mincost r plus mincost s. What else can we put there? Well we can put something complicated at the z node, AOI21 can match there. That costs 7 plus the minimum cost of covering the leaf nodes, which is the mincost plus p, plus the mincost of q, and in this case it stops. so even though AOI21 has 3 inputs, the other input turns out to match the d input. And since that's a actual of input of the subject tree there's no cost, there's no recursion, we don't have to do any work. Now it turns out that's everything that can match at node Z. And what we know that the way, the mincost, covering algorithm works is you have to look at everything that can match at the node. and you write the recursion what all the matching opportunities are, then you take whatever was the minimum. Now, we don't know what that is, because we don't know what the mincost is for t, r, s, p, and q. So we have to recurse, we have to keep going down the tree. So we look at node t, and we say, okay what can match at node t? And the answer is a NAND2 can match at node t. What does that cost? Well that costs 3, the cost of the NAND gate plus, mincost r, plus, mincost s, because those are the leaf nodes, when I put a NAND at node t. And there's nothing else that can match at node t. And I still can't compute any values numerically, so I have to keep going down. So recurse down, node r. What can match at node r? A NAND2 can match at node r. That also costs 3 plus the cost of recursively of covering the leaf notes. Mincost p plus mincost q. Still can't calculate anything numerically so, down we go. P, what can match at p? A NOT gate can match at p, nothing else can match at p. And that costs 2, which is great because that's a number. I could actually return that and you know, calculate something. I'm just going to keep basically completing the rows of the table because it's just conceptually easier for us. Even if it's not exactly the order in which the recursion would do it. What could match at q? A NAND2 can match at q, that's it, so thats going to cost 3. What can match at s? A NOT can match at s. And that costs 2 and that's basically the sort of the scope of the recursion. And what's going to happen now is as I as the recursion returns, it's going to return with numbers. And some of these equations can have their recursive calls to mincost, we can fill those values in with actual numbers. Right?. So that's going to happen next, well I know the actual costs for covering p and q and s so I can use those. So in the t NOT, recursive covering equation, 3 plus mincost r plus mincost s. The mincost s is a 2. In the AND2 covering NOT z 4 plus mincost r plus mincost s, the mincost s is also a 2. In the pattern for covering node r, 3 plus mincost p plus mincost q, the q can be replaced, that's a 3. In the AOI21 at Node z, 7 plus mincost p plus mincost q, the mincost q can be replaced, that's a 3. In the node r cover NAND2 3 plus mincost p plus mincost q. Well we already covered mincost q that's a 3, mincost p is now a 2. And in the AOI21 covering node z, 7 plus mincost p plus mincost q, the mincost p can also be replaced iwth a 2. So now a whole lot of the recurse equations are now numbers. We can actually simplify them. So let's go forward and do that. Well, what do we know? z can be covered by a NOT, but we still don't know how to do that, that's 2 plus mincost t. Z can be covered with an AND2, that's 4 plus 2 plus mincost r. We don't know that. AOI21, that's 7 plus 2 plus 3 that's 12. Okay that's a good number. T can be covered with a NAND2, 3 plus mincost r plus 2. Okay we're still not quite there, r is NAND2. 3 plus 2 plus 3 is 8. Oh, hey that's great! I can use that and p q and s are still covered at with cost 2 3 and 2 respectively. we can take the mean cost r in the NAND2 matching at node t and replace it. So it's now 3 plus 8 plus 2 and also the AND2 matching at z NOT is now 4 plus 2 plus then mincost r is 8. So, again I can go forward and I can simplify some things and I can get some numbers. So, now where are we. Well, the z node can be matched by a NOT. Which is 2 plus mincost t. The AND2 matches with a cost 4 pus 2 plus 8 that's 14. The AOI21 matches with the cost of 7 plus 2 plus 3 that's 12. I still need the minimum of the NOT the AND2 and the AOI21. At t we match a NAND2 with cost 3 plus 8 plus 2, that's 13. At r we match the NAND2 with 3 plus 2 plus 3 plus 8. And p q and s are still matched with 2 3 at cost of 2 3 and 2 respectively. Now I know node t can be matched with cost 13. So I can replace the 13 in the not at node z that's now 2 plus 13. And I actually have numbers for everything. And so here finally I have numbers for everything. The z node, I can match a not with cost 2 plus 13 is 15. I can match AND2 there. Cost 2 plus 4 plus 8 is 14. I can match an AOI21 with cause 7 plus 2 plus 3 is 12. Looks like it's the 12. T matches a NAND2, 3 plus 8 plus 2 is 13. R matches a NAND2, 3 plus 2 plus 3 is 8. P matches a NOT with 2. Q matches a NAND2 with 3. S matches a NOT with 2. I look up at the top of the tree, the root of the tree at node z, and I say, what's the minimum cost? And the answer is, the minimum cost is a 12. And so, what I know is that the thing I match at the root of the subject tree is the AOI21 that's what I have to deduced. Now it turns out because we have all of these bests costs at every node of the tree. And our algorithm will also remember what gate matched to get that best cost out of all the nodes of the tree. We could just recursively walk down and figure out what the rest of the matching is. So, you know, how do you do that? How do you get the final cover? You look at the best cost at the subject root and you find the pattern p with that cost. In our example the cost was a 12, and the gate was the AOI21. Then you find the leaf nodes within the subject tree with p at the root. So, you go look at the leaf nodes for the AOI21 and in our example that was p and q. You look at the best cost for each of those leaf nodes and you find the pattern which was associated which each of those best costs at the leaf nodes. And you choose that pattern for that node and you just recursing down the tree. So it's easiest to see how this works if we sort of go back in our table, and I just write it again in a slightly different way. So, what can I match at node z? I can match a NOT, it costs 15. How did I get 15? That was 2 plus mincost t. I can match an and too. How did I get that? That cost 14 equals 4 plus mincost r plus mincost s. Sorry, need a bracket there. The AOI21 matches with a cost 12 equals 7 plus mincost p plus mincost q.. The NAND2 matches, with a cost of 13 is 3 plus mincost r plus mincost s. The r matches NAND2 a equals 3 plus mincost p plus mincost q, p matches a NOT with cost 2, q matches a NAND2 with cost 3, s matches a NOT with cost 2. What we know is the best thing we can do at the root as the AOI21 that matches with a minimum cost of 12 and the things that are relevant are that the leaf nodes are p. I'm just going to circle them, and q. And so what we know is we need to go look at p and q and say how did you get covered? And so we look at p and say, oh it's a NOT. And so what I know is that I put the AOI21 at the top and then going down I put the NOT at p. Then I also, I look at q and say, well what was your best answer? And the answer is well there's only one. It's a NAND2 and so I put a q at NAND2. And if these patterns, the thing I put a p or the thing I put a q, if they also had leaf nodes, I just keep doing this down the tree and that's how you match. That's how you'd actually get the cover. So in this particular example if the cost for the NOT, NAND2, AND2, AOI21, etcetera are shown, the best cover to use is 1 AOI21, 1 NAND2 and 1 NOT at nodes Z, q, and p respectfully. this is a lovely simple algorithm. It's optimal which is a, sort of an amazing things given the restrictions of trees and treeification. it turns out there's several nice extensions. For example you can modify the algorithm a little bit to minimize delay instead of cost. Because, you know, delay is like a number associated with a gate. And the delay that you're interested in turns out to be the, you know, again, you know, related to the additive sum of all the delays. And it turns out to be the maximum. So likely what's the longest delay? you need to deal with some technical issues associated with capacitive of loads for the driven gates. But some simple discrete load models can be modeled. And you can still do this dynamic programming kind of solution. many useful and interesting variations starting from this skeleton algorithm. Many, many, many. It's a very, very famous and beautiful algorithm. So that's technology mapping. Synthesis gives you uncommitted or technology independent design. For example, just NAND2 and NOT gates. Mapping is the critical step, the missing step, that turns this into the real gates that you're allowed to use in your library. And they can really determine the difference between a good implementation and a bad one. And tree covering is a nice simple elegant approach to the problem. It's sort of the first real, real serious solution to this problem. Three parts to the idea you treeify the input, you match all the library patterns, and then you find the mincost cover. And, yes, there are other ways to do this. So for example there are some real Boolean algebra based covering where you can do some more complicated computational Boolean algebra. You can get better quality answers. It's a lot more computational expensive, so people do interesting heuristics with that. And there are even other very different applications. So, for example, if you're making a programmable gatorade where you build all of the logic out of little lookup tables. There is a technology mapping problem for how you take the uncommitted logic that comes out of logic synthesis and map it into a look up table than can implement for example any Boolean function of five variables. This is a very interesting universe of problems in the technology mapping space. Still an interesting kind of a problem. But a very important step in the path from logic to layout, a key step. And now you know how this works. [SOUND]