0:08

So here in lecture 10.6 we are going to finish our discussion of technology

mapping. we know at this point that we treeify all

of our net lists. We know that we match where the

technology library fits the gates in the trees.

And we know that we can use this lovely recursive minimum cost covering algorithm

to figure out where everything goes. Let's just do a big example.

We're going to do an example step by step, gate by gate, node by node, and

wire by wire, to show you that this is actually a really simple algorithm.

a very pretty elegant algorithm. And that it gives really good results.

You can understand why the algorithm works and how it works.

So let's finish up the technology mapping discussion by showing you this example.

>> So, we've come to the point in our tree

mapping discussion where it makes sense to just do a great big example.

So lets go look at how the minimum cost covering algorithm works on a nice sized

example with the library. That we've been showing elvolving as

we've gone through the lectures and show step by step how the minimum covering

idea works. So, here we've got our subject tree, this

is the same example that we've been using.

So inputs A B C D Z output at the top, three white nodes for NAND gates, three

black nodes for inverters internal nodes PQRST, Z is the output of the subject

tree. And on the bottom I'm showing again our

pattern tree library, NOT, NAND2, AND2, NOR2, OR2, AOI2, or AOI22.

And at the top I've got basically a little table that we're going to fill out

to show you how this algorithm works. And it's got three columns that we're

going to be filling in. It says at node can, match, with mincost.

And so what we're going to do is node by node walk the tree.

we're going to figure out what can match there from the pattern library.

And then we're going to write a recursive equation for the matching and then we're

going to basically solve it. Sort of in the manner in which the

recursive algorithm would actually do it. So, the first thing we need is we need

cost values so I have now shown cost on the pattern tree.

The NOT cost 2, NAND2 cost 3, AND2 cost 4, NOR2 cost 6, OR2 costs 4.

AOI21 costs 7 and AOI22 also costs 7. So with that we can start.

Looking at the top of the subject tree, what we see is that at node Z and I can

put a NOT gate. And that costs 2, that's the cost of the

inverter plus the minimum cost of t because the input box on the inverter is

going to cover the t node, and that's the recursive, so the recursion.

NOT can match here with a cost 2 plus mincost t.

What can also match at this node is an AND2.

And the cost of matching the AND2 there is 4, the cost of the AND gate plus where

the inputs are. The leaf nodes and that turns out to be 4

plus mincost r plus mincost s. What else can we put there?

Well we can put something complicated at the z node, AOI21 can match there.

That costs 7 plus the minimum cost of covering the leaf nodes, which is the

mincost plus p, plus the mincost of q, and in this case it stops.

so even though AOI21 has 3 inputs, the other input turns out to match the d

input. And since that's a actual of input of the

subject tree there's no cost, there's no recursion, we don't have to do any work.

Now it turns out that's everything that can match at node Z.

And what we know that the way, the mincost, covering algorithm works is you

have to look at everything that can match at the node.

and you write the recursion what all the matching opportunities are, then you take

whatever was the minimum. Now, we don't know what that is, because

we don't know what the mincost is for t, r, s, p, and q.

So we have to recurse, we have to keep going down the tree.

So we look at node t, and we say, okay what can match at node t?

And the answer is a NAND2 can match at node t.

What does that cost? Well that costs 3, the cost of the NAND

gate plus, mincost r, plus, mincost s, because those are the leaf nodes, when I

put a NAND at node t. And there's nothing else that can match

at node t. And I still can't compute any values

numerically, so I have to keep going down.

So recurse down, node r. What can match at node r?

A NAND2 can match at node r. That also costs 3 plus the cost of

recursively of covering the leaf notes. Mincost p plus mincost q.

Still can't calculate anything numerically so, down we go.

P, what can match at p? A NOT gate can match at p, nothing else

can match at p. And that costs 2, which is great because

that's a number. I could actually return that and you

know, calculate something. I'm just going to keep basically

completing the rows of the table because it's just conceptually easier for us.

Even if it's not exactly the order in which the recursion would do it.

What could match at q? A NAND2 can match at q, that's it, so

thats going to cost 3. What can match at s?

A NOT can match at s. And that costs 2 and that's basically the

sort of the scope of the recursion. And what's going to happen now is as I as

the recursion returns, it's going to return with numbers.

And some of these equations can have their recursive calls to mincost, we can

fill those values in with actual numbers. Right?.

So that's going to happen next, well I know the actual costs for covering p and

q and s so I can use those. So in the t NOT, recursive covering

equation, 3 plus mincost r plus mincost s.

The mincost s is a 2. In the AND2 covering NOT z 4 plus mincost

r plus mincost s, the mincost s is also a 2.

In the pattern for covering node r, 3 plus mincost p plus mincost q, the q can

be replaced, that's a 3. In the AOI21 at Node z, 7 plus mincost p

plus mincost q, the mincost q can be replaced, that's a 3.

6:23

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]