[SOUND]. So here in Lecture 10.5, we're going to continue our exploration of Technology Mapping. this lecture is really the heart of the technology mapping, algorithm. This is really the interesting bit. What cover of the output of logic synthesis do we pick? And the answer is, the one with the least cost. Every gate in the library has a cost. We pick the cover that has the cheapest total cost. How do we compute that? Amazingly enough, recursively. There's a beautiful, elegant. Surprisingly simple algorithm that operates on trees, because we have tree-ified everything that can compute the cost in a recursive manner. It is surprisingly simple. It is surprisingly effective. It is one of the few places in this business that you actually get an exact answer an exact optimal answer to a problem is a lovely, lovely algorithm. So let's go talk about the minimum cost covering solution for the technology mapping problem. So, here we are finally at the most interesting part of the tree covering method, which is the minimum cost covering problem. So this is a really beautiful, elegant recursive algorithm made possible by the way we constructed the, the, the tree part of our problem. let's go look at how that works. So where are we just by way, way of summary? We have tree-ified the subject tree. And for every node of the subject tree, we know which library pattern matches it. We annotated that information on the tree itself. And now we have, really the interesting part of the problem. What's the best cover, what set of gates should I pick. they're structurally correct, they match in the right ways. the outputs connect to the inputs. But it's also just the best cover. And way we're going to do that is by actually assigning costs to things and picking basically the cheapest solution. So what cover do we choose? We assign a cost to each library pattern and then we choose the minimum cost cover. And I'll be you know, careful to say maybe a minimum cost cover. You know, there might be some ties which is the known cost cover of the subject tree. And I'm just going to refer to that as the mincost cover, because it's easier and shorter to write. But it's also the name of the recursive algorithm that we're going to be creating here shortly. There's really one big ideal that makes this easy to do, and I'm going to say it in words and then I'm going to show you a bunch of pictures of why this works. If pattern, p, from the library, is a mincost match at some node s, in the subject tree, then each leaf of the pattern tree must also be the root of some other minimum cost matching pattern. So, this leads to a very nice recursive algorithm, which we're going to call mincost, which you invoke on any node of the subject tree. And it returns a cost of an, of a best cover of all of the logic, in this case the nodes of the tree, underneath that root. This is a very famous kind of algorithm. It's a algorithm in a category called dynamic programming. If you've taken any sort of formal computer algorithms you may recognize it. If not, now you know a new topic. Dynamic programming, that's what kind of algorithm this is. So, a little bit of terminology here. I've got a big gray triangle, which is the subject tree, and a little, red circle sorry a little, black circle with an r in it. What is that? That is the root of the subject tree. So, r is the node, way up at the top of our subject tree. And the best cover, which is to say the best mapping of this tree has a cost. And that cost is mincost r, if we invoke our recursive algorithm on node r, it's going to calculate a number that number is the cost of the best mapping. And because the subject tree is a tree, we could also invoke mincost r algorithm on an internal node of that tree. So, here's internal node s in the subject tree. And interestingly, the best cover of the sub-tree, because there is a bunch of logic. Represented by the tree nodes underneath node s the best cover of that small piece of things that the best cover of that sub tree also has a cost. And that's just mincost called on node s, which is inside things. And let's just remember, that we tree-ified the net list. So what is s? S is an internal node of the subject tree, but s is also the root of another tree. A little orange tree, that I've drawn there. A smaller tree. And this fact that every node in the subject tree is the root of another tree is why this whole algorithm works, as a very pretty recursive kind of a computation. So, a little more terminology. I've got the pattern library our technology library drawn at the top again NOT, NAND2, AND2, NOR2, OR2, AOI21, AOI22 up at the top, with black circles and white circles and squares. And I've got the subject tree big gray triangle and node r up at the top. >> Suppose library pattern p sub i, the ith pattern in the technology library matches at root r. So let's be concrete about that and say, let's say it's AOI21. Then what we mean is we can put that pattern on top of the tree and the root of the AOI21 will match the root of r and when we start sort of going down the nodes, they will match, too. So we have this great big kind of blue sort of triangle thing that I'm drawing at the top of the subject tree. But let's also note that pattern AOI21 has three input boxes. Those input boxes are going to fall on some nodes inside the subject tree. And so I'm putting little arrows from where it says each of the three input nodes and the library gate will be matched to some nodes in the subject tree, because remember inputs match anything. Those things are nodes x, y and z that I've highlighted. We're going to give those things names. We call those nodes in the subject tree leaf nodes. For this matching library pattern so we put the root of aOI21 up at root node r. The internal nodes the gate nodes the logic nodes match and the input nodes match something. What do they match? They match x and y and z inside our subject tree. So, the final terminology is that every gate pattern in our technology library has a cost. So gate pattern Pi has a cost. We're going to say that's costs of Pi. And we're going to use the library costs to calculate the cost to map the whole complete subject. Tree. And what I've got shown on the left here is a whole bunch of little triangles that each have at their top, their pointy part, a big black circle because that's the root where those things match. And at the bottom of each one of these triangles there a bunch of little black circles because that's where the leaf nodes match. And the way it works is that The top of one triangle that represents a pattern tree, matches the bottom the leaf node of another triangle. We're going to cover all the nodes in the subject tree and then add up all those costs and that's what it costs to map this thing. >> So, here's the idea in a more diagrammatic fashion. So this is a little concrete example. Assume that there are three different library patterns that match at root R of our subject tree. And so I've got three great, big gray triangles that each have an R at the top and they say subject tree. So assume that pattern p1 from our library has two leaf nodes, a and b. And so, what that means is I can put pattern p1 up at the top, and there's a littel purple kind of a triangle, and it has two nodes, a and b, that are covered where the inputs covers. So those are the leaf nodes for putting pattern p1 at the top. I can put pattern P2 at the top also, so pattern P2 goes, its route goes where R goes, and is a big bluish kind of a triangley thing. And it's got three leaf nodes, x, y, and z inside the subject tree in different locations. And similarly, pattern P3 has four leaf nodes, j, k, l, and m, and so there's a big green Not quite triangle thing kind of a four sided blob that has at its bottom j, k, l and m but also the root of pattern p3 matches node r. And so what we're going to talk about now is sort of what's going on with the. Overall matching process, the overall you know cost optimization process. what question do we need to answer? Which of these gates which can fit at the top of the subject tree produces the smallest value of the minimum cost? [SOUND] So here's the really amazing thing[UNKNOWN] I can write an equation for this. And the equation can be recursively solved, or recursively computed. So I've got this picture from the previous slide at the top. Three grey subject trees. One has pattern P1 at the top, with leaf nodes A and B. One has pattern P2 at the top, with leaf nodes X, Y, and Z. And one has pattern P3 at the top, with patters J, K, L, and M. What is the cheapest cover of the root of this subject tree? Well, what do I know is that it has the minimum cost root, minimum cost R. I can write an equation for that. That's the minimum over all of the patterns that match at root R. So that's the minimum over if I put P one at the top, or if I put P two at the top, or if I put P three at the top. I can actually write that as an equation What's the minimum on computing, what's the number on computing if I put P1 at the top? And the answer is, it's the cost of P1, which is the cost of the gate itself, the library gate, plus the minium cost of covering whatever a is the root. And that's why there's a great big triangle drawn there. Plus the minimum cost of covering whatever b is the root of. This is the key sort of recursive link What does it cost to put pattern P1 at the top? Well, it costs whatever pattern P1 costs plus whatever the best way of cost to cover the leaf nodes, the inputs of pattern P1. So that's min cost A plus min cost B, so that's 1 component of this minimum. What's the other thing we have to look at? Well, we have to look at what it costs to put pattern P2 at the top. What's it cost to put pattern P2 at the top well it cost whatever the gate costs cost P2 plus those 3 green triangles the minimum cost of covering x because x is the root of something else, the minimum cost of covering y because y is the root of something else and the minimum cost of covering z because z is the root of something. Something also cost P2 plus mean cost x plus mean cost y plus mean cost z. Where else do we have to look at in this Minimum. We have to look at putting P3 above the top. Okay, what is that cost, same idea, it costs whatever the gate costs which is cost P3 plus the minimum cost of covering all those leaf nodes and so there are 4 triangles now. The mean cost of j plus the mean cost of k plus the mean cost of l plus the mean cost of m. These are three numbers. I can write the equation, but in order to solve this equation or in order to compute this equation, I have to recursively calculate some stuff. So, I can compute this by recursively calling min, by calling mincost at the root r. That's says oh, I have to compute these three numbers and take the minimum, and that cause a recursive calculation of minimum cost on all of these leaf nodes. And eventually, you know, the way these recursive things on trees work is you get down to the bottom and only one gate matches and you get a number. You get a cost number and then it kind of bubbles back up. That's the whole big idea of the recursive tree formulation for covering. So I get a, a surprisingly nice, compact little algorithm called mincost, and you call mincost on a treenode, like the root. And the first thing you do is you say, well the cost is infinite because I'm going to be calculating a bunch of minimums. And so, the first time I do that the infinity will go away. And then there's an outer loop, right? and the outer loop basically says, for each pattern p that matches at the subject tree node, because you call this on a node, so if you call this on the root you're going to look at p1 and p2 and p3. And, in this particular example here I've called it you know, on the top. And I'm looking at pattern p2. And the next thing you say is well, let's let l be all the nodes in the subject tree that are the leaf nodes. And in this particular example, those are x and y and z. So l is x and y and z. And then you do what I showed on the previous slide, which is, you just compute, well, what's it cost to put each one of those patterns there? Well, for p2 it costs whatever p2 costs plus for each node in l. Add the minimum, the recursive step, and I'm putting a little star by the recursion add up to the cost of the gate itself, the minimum cost for recursion of covering all of the leaf nodes, which is x, and y, and z. So then you compute that, and then, you know, you have a little if statement that says if this cost I just calculated is less than the best cost I've seen so far, then remember it. And so there's a sort of a, a part of this algorithm where you basically remember what was the best thing that you saw. What was the best pattern you saw to put at this particular node. So then you can come back later and sort of Figure out what the actual covering is. So that's the algorithm. It's actually surprisingly simple. there's one useful optimization that I have to note. I didn't do it in this algorithm, but it's very easy to add. This algorithm will revisit the same tree node many times during the recursions. In other words, it will recompute the minimum cost cover for that node every time. Can you do better, sure. You make a table with the minimum cost value for each node and it starts with infinity in every table element. And the first time you compute the minimum cost cover of a node inside the subject tree, you put it in the table. And then the next time the algorithm recursively tries to compute it. The first thing you do is you look in the table. You say if I have computed this before then just return it and don't do the work. And the reason that you do something like that is shown in this nice simple little diagram. node y is in the middle of this subject tree, I'm showing the big yellow, the big triangle. Pattern p2 has a leaf node that covers node y. Pattern P3 also has a leaf node that covers node y. So when I put pattern P2 up at the top, I am going to re cursivelycall my mincost algorithm and I am going to call it on node y. So, I'm drawing a little triangle under node y. I'm going to go compute the minimum cost of y Admnd then you know later in this algorithm when I put p3 up at the top I'm going to try to do it again just by doing another triangle at the node y, that's just stupid. Just go the first time you compute the minimum cost of node y, go put it in a table and remember it. So, the second time you want to do this just go look it up in the table, saves a lot of computation, very easy to do. So, that is the core algorithm for technology mapping. That's why we make everything a tree. The subject is a tree. The targets in the library are a tree. Because of this ability to have the mincost algorithm be expressed as the cost of a gate plus recursive calls to mincost on the leaf nodes on the little tree elements. So it's beautiful, it's simply and it works great. Let's go actually look at an example in detail to see how it works.