1 00:00:00,25 --> 00:00:08,43 [SOUND]. 2 00:00:08,43 --> 00:00:11,541 So here in Lecture 10.4, we're going to continue our exploration of technology 3 00:00:11,541 --> 00:00:14,768 mapping. We know that we have to require that the 4 00:00:14,768 --> 00:00:18,733 output of logic synthesis is a set of trees, and we now know how to tree-ify 5 00:00:18,733 --> 00:00:21,937 it. And we know that we require that the 6 00:00:21,937 --> 00:00:25,765 gates in our standard cell technology library are themselves little trees. 7 00:00:25,765 --> 00:00:30,55 The next problem we have is which gate that we have available in our technology 8 00:00:30,55 --> 00:00:34,560 library fits where in the output of logic synthesis? 9 00:00:34,560 --> 00:00:39,40 And because of the way we've now modeled this is a very stylized node matching 10 00:00:39,40 --> 00:00:43,450 problem in sort of Computer Science, we have a very simple set of structural 11 00:00:43,450 --> 00:00:48,967 matching problems to solve. Where do these little gates fit in the 12 00:00:48,967 --> 00:00:51,510 big net list? So this is matching. 13 00:00:51,510 --> 00:00:55,292 And so, let's go show how the matching process works to figure out where the 14 00:00:55,292 --> 00:00:59,578 gate library is used in the technology mapping process. 15 00:00:59,578 --> 00:01:06,270 So, where are we in our discussion of technology mapping as tree covering? 16 00:01:06,270 --> 00:01:10,755 We showed that the, is possible and pretty straightforward to take the output 17 00:01:10,755 --> 00:01:15,752 of multilevel synthesis. After it's been converted in simple nand 18 00:01:15,752 --> 00:01:19,666 not form and make sure that it's a set of trees. 19 00:01:19,666 --> 00:01:24,228 we, we split things on fan out nodes. And we're going to map each tree 20 00:01:24,228 --> 00:01:26,920 individually. And we also showed that it's pretty easy 21 00:01:26,920 --> 00:01:29,600 to make sure that the pattern library, the gates in your technology library, are 22 00:01:29,600 --> 00:01:32,778 themselves trees. And imposes to some interesting kind of 23 00:01:32,778 --> 00:01:35,938 surprising little restrictions. Like you can't use x or gates. 24 00:01:35,938 --> 00:01:38,678 But, but that's not too big a deal. And, and honestly there are some ways 25 00:01:38,678 --> 00:01:42,640 around that. The next step in the process is, how do I 26 00:01:42,640 --> 00:01:47,840 figure out where and how the elements in my technology library actually match 27 00:01:47,840 --> 00:01:53,470 inside my larger subject tree? So let's go talk about that. 28 00:01:53,470 --> 00:01:57,776 That's the tree matching problem. So, what's the goal? 29 00:01:57,776 --> 00:02:01,740 The goal is to determine, for every node in the subject tree. 30 00:02:01,740 --> 00:02:05,378 What library gate or gates. Can match there. 31 00:02:05,378 --> 00:02:09,602 Structurally again, black circles on black circles, white circles on white 32 00:02:09,602 --> 00:02:13,717 circles, input boxes anywhere. There is a, a very strict forward 33 00:02:13,717 --> 00:02:18,751 approach here called recursive matching. The simple idea is just to try every 34 00:02:18,751 --> 00:02:22,140 library gate. And every note of the subject tree. 35 00:02:22,140 --> 00:02:26,180 The library gates, you know the elements in your technology library. 36 00:02:26,180 --> 00:02:28,746 They're small patterns. Right? 37 00:02:28,746 --> 00:02:32,390 They're not, you know, thousands and thousands and thousands of nodes. 38 00:02:32,390 --> 00:02:35,705 They're you know like five or six or eight or ten nodes in the graphs, so this 39 00:02:35,705 --> 00:02:39,865 is just not too much work. And the notion of a recursive matching, 40 00:02:39,865 --> 00:02:43,495 means, basically, you match the root of the subject, where you're trying to map 41 00:02:43,495 --> 00:02:47,634 this little logic gate, with the root of the pattern. 42 00:02:47,634 --> 00:02:51,290 And if those things match, then you recursively match the children. 43 00:02:51,290 --> 00:02:54,947 And it's much easier to see as a little illustrative diagram, so let's just go do 44 00:02:54,947 --> 00:02:58,438 that. So how does recursive tree matching work? 45 00:02:58,438 --> 00:03:02,95 Recursive tree matching is answering this question, does the library pattern, p, 46 00:03:02,95 --> 00:03:06,349 which is itself a little tree, match node s inside our subject tree? 47 00:03:06,349 --> 00:03:09,529 So I've got a picture here, I've got a great big gray triangle which is the 48 00:03:09,529 --> 00:03:13,133 subject tree and I've got a little black node, that says node s, a node internal 49 00:03:13,133 --> 00:03:18,39 to our subject tree. And then I've got a little pink triangle 50 00:03:18,39 --> 00:03:21,756 with a p in it that says oh, I'm pattern tree p and I have a node at the top of 51 00:03:21,756 --> 00:03:26,688 me, which is node r. And there's a question, a little arrow 52 00:03:26,688 --> 00:03:30,204 between node s and node r that says match question mark. 53 00:03:30,204 --> 00:03:33,984 So, this is the question, if I take this pattern tree out of my library, maybe 54 00:03:33,984 --> 00:03:37,404 this is an end or invert22, and I say, hey can I put this gate here in the 55 00:03:37,404 --> 00:03:42,910 subject tree? what do you actually have to do? 56 00:03:42,910 --> 00:03:46,622 Well, the first thing you have to check is if node s matches the root r of 57 00:03:46,622 --> 00:03:50,33 pattern p. And then you have to recursively ask if 58 00:03:50,33 --> 00:03:55,50 the stuff on the left side matches and the stuff on the right side matches. 59 00:03:55,50 --> 00:03:58,8 And that's easy to sort of draw schematically. 60 00:03:58,8 --> 00:04:00,950 So, what does recursive matching do? Right? 61 00:04:00,950 --> 00:04:03,926 So again, I've got a great big gray triangle, which is the subject tree with 62 00:04:03,926 --> 00:04:07,340 a big black circle in the middle of it, that's node s. 63 00:04:07,340 --> 00:04:10,316 And we've got a little pick dotted triangle, which is the pattern tree with 64 00:04:10,316 --> 00:04:15,844 a black circle at the top of it. And so the first thing you ask is, does 65 00:04:15,844 --> 00:04:21,40 note s internal to my subject tree match the pattern root r. 66 00:04:21,40 --> 00:04:26,261 Are they both black circles? Are they both white circles? 67 00:04:26,261 --> 00:04:29,423 Okay? Or is one of them actually a square box 68 00:04:29,423 --> 00:04:35,82 because it's an input? And then if that's true, then you say, so 69 00:04:35,82 --> 00:04:40,538 does the left child of node s inside the subject tree match the left child of 70 00:04:40,538 --> 00:04:46,702 pattern p from my library? And you can see why this is a recursive 71 00:04:46,702 --> 00:04:49,259 algorithm. You know what does the recursive 72 00:04:49,259 --> 00:04:52,836 algorithm say? It, you know, you call it on node s right 73 00:04:52,836 --> 00:04:58,164 with pattern r and you say oh, do the roots match? 74 00:04:58,164 --> 00:05:01,880 Yes. Oh, well then, go down one node. 75 00:05:01,880 --> 00:05:05,345 Go look at the top of the sub tree which is the left child and recursively call 76 00:05:05,345 --> 00:05:09,101 the algorithm on that. And when you recursively call it on that 77 00:05:09,101 --> 00:05:11,612 it's again going to ask, so do the roots match? 78 00:05:11,612 --> 00:05:13,810 And it's just going to kind of walk down like that. 79 00:05:13,810 --> 00:05:17,653 So the first thing you do is you check if the pattern root matches the subject 80 00:05:17,653 --> 00:05:20,386 root. And then you recursively check if the 81 00:05:20,386 --> 00:05:23,54 left child matches, and then you recursively check if the right child 82 00:05:23,54 --> 00:05:25,894 matches. I'm not showing a little dotted line like 83 00:05:25,894 --> 00:05:28,360 I, I did before. And, you know, that's it. 84 00:05:28,360 --> 00:05:31,643 It's and it's not that complicated, because the patterns are themselves not 85 00:05:31,643 --> 00:05:36,289 very big trees, and you just apply it. Now the one subtletly here I will again 86 00:05:36,289 --> 00:05:40,257 remind you of is that you have to be careful with matching assymetric library 87 00:05:40,257 --> 00:05:44,629 patterns. The and or invert to one that I'm showing 88 00:05:44,629 --> 00:05:47,420 here is assymetric. Right? 89 00:05:47,420 --> 00:05:49,610 It has an inverter on the top and then a nand gate. 90 00:05:49,610 --> 00:05:55,210 But the nand gate is fed by one inverter and one, not one nand gate. 91 00:05:55,210 --> 00:05:58,516 So it has one side where you can go down and find a white bubble with two 92 00:05:58,516 --> 00:06:01,403 children. And another side where you can go down 93 00:06:01,403 --> 00:06:05,83 and find a black bubble with one child. And you actually have to match it both 94 00:06:05,83 --> 00:06:07,932 ways. Which requires for asymmetric patterns 95 00:06:07,932 --> 00:06:12,27 asking the question, does the left child of the subject match the left child of 96 00:06:12,27 --> 00:06:14,960 the pattern? No. 97 00:06:14,960 --> 00:06:19,762 Does the left child of the subject match the right child of the pattern? 98 00:06:19,762 --> 00:06:20,936 Maybe. Right. 99 00:06:20,936 --> 00:06:25,160 So, you have to do these complicated left left, left right, right left, right 100 00:06:25,160 --> 00:06:29,610 right, kind of matches. it's just some more case analysis. 101 00:06:29,610 --> 00:06:34,587 It's not particularly complicated. But I'm, I'm, I'm just sort of warning 102 00:06:34,587 --> 00:06:40,430 you that you actually have to do that. What do you get after recursive matching? 103 00:06:40,430 --> 00:06:44,450 The answer is, for every gate-type node in the subject tree, for every black node 104 00:06:44,450 --> 00:06:48,230 or white node, a node that's a nand gate or a node that's an inverter, you get a 105 00:06:48,230 --> 00:06:53,239 list of the pattern trees that match at that node. 106 00:06:53,239 --> 00:06:56,684 Which is to say, you get a lsit of gates that have the property that you could put 107 00:06:56,684 --> 00:07:00,320 them there. And their output could make the, the 108 00:07:00,320 --> 00:07:05,320 output that that gate makes, right? So every one of these nodes has a wire 109 00:07:05,320 --> 00:07:09,320 going into it from the top, with a label on it. 110 00:07:09,320 --> 00:07:12,220 What that means is that you could actually put the ga, the pattern gate 111 00:07:12,220 --> 00:07:15,710 there. And make the wire with that output in the 112 00:07:15,710 --> 00:07:18,528 final logic. And so, we annotate each such node in the 113 00:07:18,528 --> 00:07:22,848 tree with this matching information. So I can just, you know, illustrate that 114 00:07:22,848 --> 00:07:26,940 here, by saying, what do we get in my little z tree that we've seen many times 115 00:07:26,940 --> 00:07:30,966 here, which has ABCD as inputs, Z as output and 3 black nodes and 3 white 116 00:07:30,966 --> 00:07:36,470 nodes, PQRST. Well, what do you get? 117 00:07:36,470 --> 00:07:40,745 You get for the black node that makes output z, a little list that says 118 00:07:40,745 --> 00:07:45,747 patterns p2 p5 p78 match. And for the white node that makes output 119 00:07:45,747 --> 00:07:48,770 t, you get two patterns; p6 and p11 match. 120 00:07:48,770 --> 00:07:52,389 And for the black node that makes output S, p8 matches. 121 00:07:52,389 --> 00:07:56,790 And for the white node, that makes output r, p6 and p7 match. 122 00:07:56,790 --> 00:08:00,790 And for the black node that makes output P match. 123 00:08:00,790 --> 00:08:04,781 That makes output p, you get p8 matches. And for the white node that makes out, 124 00:08:04,781 --> 00:08:09,480 put q andyou get p5 that matches. So, for every internal node that's like a 125 00:08:09,480 --> 00:08:13,512 gate of some kind, you have a list of gates from your technology library that 126 00:08:13,512 --> 00:08:19,250 have the property that you could line up their root right there. 127 00:08:19,250 --> 00:08:23,94 And the output would make the name of the wire that comes into the top of that 128 00:08:23,94 --> 00:08:26,390 node. So, this is the sort of structural part 129 00:08:26,390 --> 00:08:29,566 of the mapping. Now, we get to what's actually the really 130 00:08:29,566 --> 00:08:33,920 interesting part of this algorithm. What's the best cover? 131 00:08:33,920 --> 00:08:38,12 There's many ways of actually choosing from all of the gates that can be located 132 00:08:38,12 --> 00:08:43,507 and matched inside the subject tree. How do you actually pick the one that has 133 00:08:43,507 --> 00:08:48,19 the least total cost that's still structurally correct? 134 00:08:48,19 --> 00:08:52,350 That's where we get another, very pretty, recursive algorhythm. 135 00:08:52,350 --> 00:08:53,665 So let's go talk about that. 136 00:08:53,665 --> 00:08:59,947 [SOUND].