0:00
[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].