In the node r cover NAND2 3 plus mincost p plus mincost q.

Well we already covered mincost q that's a 3, mincost p is now a 2.

And in the AOI21 covering node z, 7 plus mincost p plus mincost q, the mincost p

can also be replaced iwth a 2. So now a whole lot of the recurse

equations are now numbers. We can actually simplify them.

So let's go forward and do that. Well, what do we know?

z can be covered by a NOT, but we still don't know how to do that, that's 2 plus

mincost t. Z can be covered with an AND2, that's 4

plus 2 plus mincost r. We don't know that.

AOI21, that's 7 plus 2 plus 3 that's 12. Okay that's a good number.

T can be covered with a NAND2, 3 plus mincost r plus 2.

Okay we're still not quite there, r is NAND2.

3 plus 2 plus 3 is 8. Oh, hey that's great!

I can use that and p q and s are still covered at with cost 2 3 and 2

respectively. we can take the mean cost r in the NAND2

matching at node t and replace it. So it's now 3 plus 8 plus 2 and also the

AND2 matching at z NOT is now 4 plus 2 plus then mincost r is 8.

So, again I can go forward and I can simplify some things and I can get some

numbers. So, now where are we.

Well, the z node can be matched by a NOT. Which is 2 plus mincost t.

The AND2 matches with a cost 4 pus 2 plus 8 that's 14.

The AOI21 matches with the cost of 7 plus 2 plus 3 that's 12.

I still need the minimum of the NOT the AND2 and the AOI21.

At t we match a NAND2 with cost 3 plus 8 plus 2, that's 13.

At r we match the NAND2 with 3 plus 2 plus 3 plus 8.

And p q and s are still matched with 2 3 at cost of 2 3 and 2 respectively.

Now I know node t can be matched with cost 13.

So I can replace the 13 in the not at node z that's now 2 plus 13.

And I actually have numbers for everything.

And so here finally I have numbers for everything.

The z node, I can match a not with cost 2 plus 13 is 15.

I can match AND2 there. Cost 2 plus 4 plus 8 is 14.

I can match an AOI21 with cause 7 plus 2 plus 3 is 12.

Looks like it's the 12. T matches a NAND2, 3 plus 8 plus 2 is 13.

R matches a NAND2, 3 plus 2 plus 3 is 8. P matches a NOT with 2.

Q matches a NAND2 with 3. S matches a NOT with 2.

I look up at the top of the tree, the root of the tree at node z, and I say,

what's the minimum cost? And the answer is, the minimum cost is a

12. And so, what I know is that the thing I

match at the root of the subject tree is the AOI21 that's what I have to deduced.

Now it turns out because we have all of these bests costs at every node of the

tree. And our algorithm will also remember what

gate matched to get that best cost out of all the nodes of the tree.

We could just recursively walk down and figure out what the rest of the matching

is. So, you know, how do you do that?

How do you get the final cover? You look at the best cost at the subject

root and you find the pattern p with that cost.

In our example the cost was a 12, and the gate was the AOI21.

Then you find the leaf nodes within the subject tree with p at the root.

So, you go look at the leaf nodes for the AOI21 and in our example that was p and

q. You look at the best cost for each of

those leaf nodes and you find the pattern which was associated which each of those

best costs at the leaf nodes. And you choose that pattern for that node

and you just recursing down the tree. So it's easiest to see how this works if

we sort of go back in our table, and I just write it again in a slightly

different way. So, what can I match at node z?

I can match a NOT, it costs 15. How did I get 15?

That was 2 plus mincost t. I can match an and too.

How did I get that? That cost 14 equals 4 plus mincost r plus

mincost s. Sorry, need a bracket there.

The AOI21 matches with a cost 12 equals 7 plus mincost p plus mincost q..

The NAND2 matches, with a cost of 13 is 3 plus mincost r plus mincost s.

The r matches NAND2 a equals 3 plus mincost p plus mincost q, p matches a NOT

with cost 2, q matches a NAND2 with cost 3, s matches a NOT with cost 2.

What we know is the best thing we can do at the root as the AOI21 that matches

with a minimum cost of 12 and the things that are relevant are that the leaf nodes

are p. I'm just going to circle them, and q.

And so what we know is we need to go look at p and q and say how did you get

covered? And so we look at p and say, oh it's a

NOT. And so what I know is that I put the

AOI21 at the top and then going down I put the NOT at p.

Then I also, I look at q and say, well what was your best answer?

And the answer is well there's only one. It's a NAND2 and so I put a q at NAND2.

And if these patterns, the thing I put a p or the thing I put a q, if they also

had leaf nodes, I just keep doing this down the tree and that's how you match.

That's how you'd actually get the cover. So in this particular example if the cost

for the NOT, NAND2, AND2, AOI21, etcetera are shown, the best cover to use is 1

AOI21, 1 NAND2 and 1 NOT at nodes Z, q, and p respectfully.

this is a lovely simple algorithm. It's optimal which is a, sort of an

amazing things given the restrictions of trees and treeification.

it turns out there's several nice extensions.

For example you can modify the algorithm a little bit to minimize delay instead of

cost. Because, you know, delay is like a number

associated with a gate. And the delay that you're interested in

turns out to be the, you know, again, you know, related to the additive sum of all

the delays. And it turns out to be the maximum.

So likely what's the longest delay? you need to deal with some technical

issues associated with capacitive of loads for the driven gates.

But some simple discrete load models can be modeled.

And you can still do this dynamic programming kind of solution.

many useful and interesting variations starting from this skeleton algorithm.

Many, many, many. It's a very, very famous and beautiful

algorithm. So that's technology mapping.

Synthesis gives you uncommitted or technology independent design.

For example, just NAND2 and NOT gates. Mapping is the critical step, the missing

step, that turns this into the real gates that you're allowed to use in your

library. And they can really determine the

difference between a good implementation and a bad one.

And tree covering is a nice simple elegant approach to the problem.

It's sort of the first real, real serious solution to this problem.

Three parts to the idea you treeify the input, you match all the library

patterns, and then you find the mincost cover.

And, yes, there are other ways to do this.

So for example there are some real Boolean algebra based covering where you

can do some more complicated computational Boolean algebra.

You can get better quality answers. It's a lot more computational expensive,

so people do interesting heuristics with that.

And there are even other very different applications.

So, for example, if you're making a programmable gatorade where you build all

of the logic out of little lookup tables. There is a technology mapping problem for

how you take the uncommitted logic that comes out of logic synthesis and map it

into a look up table than can implement for example any Boolean function of five

variables. This is a very interesting universe of

problems in the technology mapping space. Still an interesting kind of a problem.

But a very important step in the path from logic to layout, a key step.

And now you know how this works.

[SOUND]