[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].

Technology Mapping—Recursive Matching

VLSI CAD Part II: Layout

Conoce a los instructores