[SOUND]. 
So here in Lecture 10.4, we're going to 
continue our exploration of technology 
mapping. 
We know that we have to require that the 
output of logic synthesis is a set of 
trees, and we now know how to tree-ify 
it. 
And we know that we require that the 
gates in our standard cell technology 
library are themselves little trees. 
The next problem we have is which gate 
that we have available in our technology 
library fits where in the output of logic 
synthesis? 
And because of the way we've now modeled 
this is a very stylized node matching 
problem in sort of Computer Science, we 
have a very simple set of structural 
matching problems to solve. 
Where do these little gates fit in the 
big net list? 
So this is matching. 
And so, let's go show how the matching 
process works to figure out where the 
gate library is used in the technology 
mapping process. 
So, where are we in our discussion of 
technology mapping as tree covering? 
We showed that the, is possible and 
pretty straightforward to take the output 
of multilevel synthesis. 
After it's been converted in simple nand 
not form and make sure that it's a set of 
trees. 
we, we split things on fan out nodes. 
And we're going to map each tree 
individually. 
And we also showed that it's pretty easy 
to make sure that the pattern library, 
the gates in your technology library, are 
themselves trees. 
And imposes to some interesting kind of 
surprising little restrictions. 
Like you can't use x or gates. 
But, but that's not too big a deal. 
And, and honestly there are some ways 
around that. 
The next step in the process is, how do I 
figure out where and how the elements in 
my technology library actually match 
inside my larger subject tree? 
So let's go talk about that. 
That's the tree matching problem. 
So, what's the goal? 
The goal is to determine, for every node 
in the subject tree. 
What library gate or gates. 
Can match there. 
Structurally again, black circles on 
black circles, white circles on white 
circles, input boxes anywhere. 
There is a, a very strict forward 
approach here called recursive matching. 
The simple idea is just to try every 
library gate. 
And every note of the subject tree. 
The library gates, you know the elements 
in your technology library. 
They're small patterns. 
Right? 
They're not, you know, thousands and 
thousands and thousands of nodes. 
They're you know like five or six or 
eight or ten nodes in the graphs, so this 
is just not too much work. 
And the notion of a recursive matching, 
means, basically, you match the root of 
the subject, where you're trying to map 
this little logic gate, with the root of 
the pattern. 
And if those things match, then you 
recursively match the children. 
And it's much easier to see as a little 
illustrative diagram, so let's just go do 
that. 
So how does recursive tree matching work? 
Recursive tree matching is answering this 
question, does the library pattern, p, 
which is itself a little tree, match node 
s inside our subject tree? 
So I've got a picture here, I've got a 
great big gray triangle which is the 
subject tree and I've got a little black 
node, that says node s, a node internal 
to our subject tree. 
And then I've got a little pink triangle 
with a p in it that says oh, I'm pattern 
tree p and I have a node at the top of 
me, which is node r. 
And there's a question, a little arrow 
between node s and node r that says match 
question mark. 
So, this is the question, if I take this 
pattern tree out of my library, maybe 
this is an end or invert22, and I say, 
hey can I put this gate here in the 
subject tree? 
what do you actually have to do? 
Well, the first thing you have to check 
is if node s matches the root r of 
pattern p. 
And then you have to recursively ask if 
the stuff on the left side matches and 
the stuff on the right side matches. 
And that's easy to sort of draw 
schematically. 
So, what does recursive matching do? 
Right? 
So again, I've got a great big gray 
triangle, which is the subject tree with 
a big black circle in the middle of it, 
that's node s. 
And we've got a little pick dotted 
triangle, which is the pattern tree with 
a black circle at the top of it. 
And so the first thing you ask is, does 
note s internal to my subject tree match 
the pattern root r. 
Are they both black circles? 
Are they both white circles? 
Okay? 
Or is one of them actually a square box 
because it's an input? 
And then if that's true, then you say, so 
does the left child of node s inside the 
subject tree match the left child of 
pattern p from my library? 
And you can see why this is a recursive 
algorithm. 
You know what does the recursive 
algorithm say? 
It, you know, you call it on node s right 
with pattern r and you say oh, do the 
roots match? 
Yes. 
Oh, well then, go down one node. 
Go look at the top of the sub tree which 
is the left child and recursively call 
the algorithm on that. 
And when you recursively call it on that 
it's again going to ask, so do the roots 
match? 
And it's just going to kind of walk down 
like that. 
So the first thing you do is you check if 
the pattern root matches the subject 
root. 
And then you recursively check if the 
left child matches, and then you 
recursively check if the right child 
matches. 
I'm not showing a little dotted line like 
I, I did before. 
And, you know, that's it. 
It's and it's not that complicated, 
because the patterns are themselves not 
very big trees, and you just apply it. 
Now the one subtletly here I will again 
remind you of is that you have to be 
careful with matching assymetric library 
patterns. 
The and or invert to one that I'm showing 
here is assymetric. 
Right? 
It has an inverter on the top and then a 
nand gate. 
But the nand gate is fed by one inverter 
and one, not one nand gate. 
So it has one side where you can go down 
and find a white bubble with two 
children. 
And another side where you can go down 
and find a black bubble with one child. 
And you actually have to match it both 
ways. 
Which requires for asymmetric patterns 
asking the question, does the left child 
of the subject match the left child of 
the pattern? 
No. 
Does the left child of the subject match 
the right child of the pattern? 
Maybe. 
Right. 
So, you have to do these complicated left 
left, left right, right left, right 
right, kind of matches. 
it's just some more case analysis. 
It's not particularly complicated. 
But I'm, I'm, I'm just sort of warning 
you that you actually have to do that. 
What do you get after recursive matching? 
The answer is, for every gate-type node 
in the subject tree, for every black node 
or white node, a node that's a nand gate 
or a node that's an inverter, you get a 
list of the pattern trees that match at 
that node. 
Which is to say, you get a lsit of gates 
that have the property that you could put 
them there. 
And their output could make the, the 
output that that gate makes, right? 
So every one of these nodes has a wire 
going into it from the top, with a label 
on it. 
What that means is that you could 
actually put the ga, the pattern gate 
there. 
And make the wire with that output in the 
final logic. 
And so, we annotate each such node in the 
tree with this matching information. 
So I can just, you know, illustrate that 
here, by saying, what do we get in my 
little z tree that we've seen many times 
here, which has ABCD as inputs, Z as 
output and 3 black nodes and 3 white 
nodes, PQRST. 
Well, what do you get? 
You get for the black node that makes 
output z, a little list that says 
patterns p2 p5 p78 match. 
And for the white node that makes output 
t, you get two patterns; p6 and p11 
match. 
And for the black node that makes output 
S, p8 matches. 
And for the white node, that makes output 
r, p6 and p7 match. 
And for the black node that makes output 
P match. 
That makes output p, you get p8 matches. 
And for the white node that makes out, 
put q andyou get p5 that matches. 
So, for every internal node that's like a 
gate of some kind, you have a list of 
gates from your technology library that 
have the property that you could line up 
their root right there. 
And the output would make the name of the 
wire that comes into the top of that 
node. 
So, this is the sort of structural part 
of the mapping. 
Now, we get to what's actually the really 
interesting part of this algorithm. 
What's the best cover? 
There's many ways of actually choosing 
from all of the gates that can be located 
and matched inside the subject tree. 
How do you actually pick the one that has 
the least total cost that's still 
structurally correct? 
That's where we get another, very pretty, 
recursive algorhythm. 
So let's go talk about that. 
[SOUND].