0:00

[SOUND].

So here in Lecture 10.5, we're going to continue our exploration of Technology

Mapping. this lecture is really the heart of the

technology mapping, algorithm. This is really the interesting bit.

What cover of the output of logic synthesis do we pick?

And the answer is, the one with the least cost.

Every gate in the library has a cost. We pick the cover that has the cheapest

total cost. How do we compute that?

Amazingly enough, recursively. There's a beautiful, elegant.

Surprisingly simple algorithm that operates on trees, because we have

tree-ified everything that can compute the cost in a recursive manner.

It is surprisingly simple. It is surprisingly effective.

It is one of the few places in this business that you actually get an exact

answer an exact optimal answer to a problem is a lovely, lovely algorithm.

So let's go talk about the minimum cost covering solution for the technology

mapping problem. So, here we are finally at the most

interesting part of the tree covering method, which is the minimum cost

covering problem. So this is a really beautiful, elegant

recursive algorithm made possible by the way we constructed the, the, the tree

part of our problem. let's go look at how that works.

So where are we just by way, way of summary?

We have tree-ified the subject tree. And for every node of the subject tree,

we know which library pattern matches it. We annotated that information on the tree

itself. And now we have, really the interesting

part of the problem. What's the best cover, what set of gates

should I pick. they're structurally correct, they match

in the right ways. the outputs connect to the inputs.

But it's also just the best cover. And way we're going to do that is by

actually assigning costs to things and picking basically the cheapest solution.

So what cover do we choose? We assign a cost to each library pattern

and then we choose the minimum cost cover.

And I'll be you know, careful to say maybe a minimum cost cover.

You know, there might be some ties which is the known cost cover of the subject

tree. And I'm just going to refer to that as

the mincost cover, because it's easier and shorter to write.

But it's also the name of the recursive algorithm that we're going to be creating

here shortly. There's really one big ideal that makes

this easy to do, and I'm going to say it in words and then I'm going to show you a

bunch of pictures of why this works. If pattern, p, from the library, is a

mincost match at some node s, in the subject tree, then each leaf of the

pattern tree must also be the root of some other minimum cost matching pattern.

So, this leads to a very nice recursive algorithm, which we're going to call

mincost, which you invoke on any node of the subject tree.

And it returns a cost of an, of a best cover of all of the logic, in this case

the nodes of the tree, underneath that root.

This is a very famous kind of algorithm. It's a algorithm in a category called

dynamic programming. If you've taken any sort of formal

computer algorithms you may recognize it. If not, now you know a new topic.

Dynamic programming, that's what kind of algorithm this is.

So, a little bit of terminology here. I've got a big gray triangle, which is

the subject tree, and a little, red circle sorry a little, black circle with

an r in it. What is that?

That is the root of the subject tree. So, r is the node, way up at the top of

our subject tree. And the best cover, which is to say the

best mapping of this tree has a cost. And that cost is mincost r, if we invoke

our recursive algorithm on node r, it's going to calculate a number that number

is the cost of the best mapping. And because the subject tree is a tree,

we could also invoke mincost r algorithm on an internal node of that tree.

So, here's internal node s in the subject tree.

And interestingly, the best cover of the sub-tree, because there is a bunch of

logic. Represented by the tree nodes underneath

node s the best cover of that small piece of things that the best cover of that sub

tree also has a cost. And that's just mincost called on node s,

which is inside things. And let's just remember, that we

tree-ified the net list. So what is s?

S is an internal node of the subject tree, but s is also the root of another

tree. A little orange tree, that I've drawn

there. A smaller tree.

And this fact that every node in the subject tree is the root of another tree

is why this whole algorithm works, as a very pretty recursive kind of a

computation. So, a little more terminology.

I've got the pattern library our technology library drawn at the top again

NOT, NAND2, AND2, NOR2, OR2, AOI21, AOI22 up at the top, with black circles and

white circles and squares. And I've got the subject tree big gray

triangle and node r up at the top.

>> Suppose library pattern p sub i, the ith pattern in the technology library matches

at root r. So let's be concrete about that and say,

let's say it's AOI21. Then what we mean is we can put that

pattern on top of the tree and the root of the AOI21 will match the root of r and

when we start sort of going down the nodes, they will match, too.

So we have this great big kind of blue sort of triangle thing that I'm drawing

at the top of the subject tree. But let's also note that pattern AOI21

has three input boxes. Those input boxes are going to fall on

some nodes inside the subject tree. And so I'm putting little arrows from

where it says each of the three input nodes and the library gate will be

matched to some nodes in the subject tree, because remember inputs match

anything. Those things are nodes x, y and z that

I've highlighted. We're going to give those things names.

We call those nodes in the subject tree leaf nodes.

For this matching library pattern so we put the root of aOI21 up at root node r.

The internal nodes the gate nodes the logic nodes match and the input nodes

match something. What do they match?

They match x and y and z inside our subject tree.

So, the final terminology is that every gate pattern in our technology library

has a cost. So gate pattern Pi has a cost.

We're going to say that's costs of Pi. And we're going to use the library costs

to calculate the cost to map the whole complete subject.

Tree. And what I've got shown on the left here

is a whole bunch of little triangles that each have at their top, their pointy

part, a big black circle because that's the root where those things match.

And at the bottom of each one of these triangles there a bunch of little black

circles because that's where the leaf nodes match.

And the way it works is that The top of one triangle that represents a pattern

tree, matches the bottom the leaf node of another triangle.

We're going to cover all the nodes in the subject tree and then add up all those

costs and that's what it costs to map this thing.

>> So, here's the idea in a more

diagrammatic fashion. So this is a little concrete example.

Assume that there are three different library patterns that match at root R of

our subject tree. And so I've got three great, big gray

triangles that each have an R at the top and they say subject tree.

So assume that pattern p1 from our library has two leaf nodes, a and b.

And so, what that means is I can put pattern p1 up at the top, and there's a

littel purple kind of a triangle, and it has two nodes, a and b, that are covered

where the inputs covers. So those are the leaf nodes for putting

pattern p1 at the top. I can put pattern P2 at the top also, so

pattern P2 goes, its route goes where R goes, and is a big bluish kind of a

triangley thing. And it's got three leaf nodes, x, y, and

z inside the subject tree in different locations.

And similarly, pattern P3 has four leaf nodes, j, k, l, and m, and so there's a

big green Not quite triangle thing kind of a four sided blob that has at its

bottom j, k, l and m but also the root of pattern p3 matches node r.

And so what we're going to talk about now is sort of what's going on with the.

Overall matching process, the overall you know cost optimization process.

what question do we need to answer? Which of these gates which can fit at the

top of the subject tree produces the smallest value of the minimum cost?

[SOUND] So here's the really amazing thing[UNKNOWN] I can write an equation

for this. And the equation can be recursively

solved, or recursively computed. So I've got this picture from the

previous slide at the top. Three grey subject trees.

One has pattern P1 at the top, with leaf nodes A and B.

One has pattern P2 at the top, with leaf nodes X, Y, and Z.

And one has pattern P3 at the top, with patters J, K, L, and M.

What is the cheapest cover of the root of this subject tree?

Well, what do I know is that it has the minimum cost root, minimum cost R.

I can write an equation for that. That's the minimum over all of the

patterns that match at root R. So that's the minimum over if I put P one

at the top, or if I put P two at the top, or if I put P three at the top.

I can actually write that as an equation What's the minimum on computing, what's

the number on computing if I put P1 at the top?

And the answer is, it's the cost of P1, which is the cost of the gate itself, the

library gate, plus the minium cost of covering whatever a is the root.

And that's why there's a great big triangle drawn there.

Plus the minimum cost of covering whatever b is the root of.

This is the key sort of recursive link What does it cost to put pattern P1 at

the top? Well, it costs whatever pattern P1 costs

plus whatever the best way of cost to cover the leaf nodes, the inputs of

pattern P1. So that's min cost A plus min cost B, so

that's 1 component of this minimum. What's the other thing we have to look

at? Well, we have to look at what it costs to

put pattern P2 at the top. What's it cost to put pattern P2 at the

top well it cost whatever the gate costs cost P2 plus those 3 green triangles the

minimum cost of covering x because x is the root of something else, the minimum

cost of covering y because y is the root of something else and the minimum cost of

covering z because z is the root of something.

Something also cost P2 plus mean cost x plus mean cost y plus mean cost z.

Where else do we have to look at in this Minimum.

We have to look at putting P3 above the top.

Okay, what is that cost, same idea, it costs whatever the gate costs which is

cost P3 plus the minimum cost of covering all those leaf nodes and so there are 4

triangles now. The mean cost of j plus the mean cost of

k plus the mean cost of l plus the mean cost of m.

These are three numbers. I can write the equation, but in order to

solve this equation or in order to compute this equation, I have to

recursively calculate some stuff. So, I can compute this by recursively

calling min, by calling mincost at the root r.

That's says oh, I have to compute these three numbers and take the minimum, and

that cause a recursive calculation of minimum cost on all of these leaf nodes.

And eventually, you know, the way these recursive things on trees work is you get

down to the bottom and only one gate matches and you get a number.

You get a cost number and then it kind of bubbles back up.

That's the whole big idea of the recursive tree formulation for covering.

So I get a, a surprisingly nice, compact little algorithm called mincost, and you

call mincost on a treenode, like the root.

And the first thing you do is you say, well the cost is infinite because I'm

going to be calculating a bunch of minimums.

And so, the first time I do that the infinity will go away.

And then there's an outer loop, right? and the outer loop basically says, for

each pattern p that matches at the subject tree node, because you call this

on a node, so if you call this on the root you're going to look at p1 and p2

and p3. And, in this particular example here I've

called it you know, on the top. And I'm looking at pattern p2.

And the next thing you say is well, let's let l be all the nodes in the subject

tree that are the leaf nodes. And in this particular example, those are

x and y and z. So l is x and y and z.

And then you do what I showed on the previous slide, which is, you just

compute, well, what's it cost to put each one of those patterns there?

Well, for p2 it costs whatever p2 costs plus for each node in l.

Add the minimum, the recursive step, and I'm putting a little star by the

recursion add up to the cost of the gate itself, the minimum cost for recursion of

covering all of the leaf nodes, which is x, and y, and z.

So then you compute that, and then, you know, you have a little if statement that

says if this cost I just calculated is less than the best cost I've seen so far,

then remember it. And so there's a sort of a, a part of

this algorithm where you basically remember what was the best thing that you

saw. What was the best pattern you saw to put

at this particular node. So then you can come back later and sort

of Figure out what the actual covering is.

So that's the algorithm. It's actually surprisingly simple.

there's one useful optimization that I have to note.

I didn't do it in this algorithm, but it's very easy to add.

This algorithm will revisit the same tree node many times during the recursions.

In other words, it will recompute the minimum cost cover for that node every

time. Can you do better, sure.

You make a table with the minimum cost value for each node and it starts with

infinity in every table element. And the first time you compute the

minimum cost cover of a node inside the subject tree, you put it in the table.

And then the next time the algorithm recursively tries to compute it.

The first thing you do is you look in the table.

You say if I have computed this before then just return it and don't do the

work. And the reason that you do something like

that is shown in this nice simple little diagram.

node y is in the middle of this subject tree, I'm showing the big yellow, the big

triangle. Pattern p2 has a leaf node that covers

node y. Pattern P3 also has a leaf node that

covers node y. So when I put pattern P2 up at the top, I

am going to re cursivelycall my mincost algorithm and I am going to call it on

node y. So, I'm drawing a little triangle under

node y. I'm going to go compute the minimum cost

of y Admnd then you know later in this algorithm when I put p3 up at the top I'm

going to try to do it again just by doing another triangle at the node y, that's

just stupid. Just go the first time you compute the

minimum cost of node y, go put it in a table and remember it.

So, the second time you want to do this just go look it up in the table, saves a

lot of computation, very easy to do. So, that is the core algorithm for

technology mapping. That's why we make everything a tree.

The subject is a tree. The targets in the library are a tree.

Because of this ability to have the mincost algorithm be expressed as the

cost of a gate plus recursive calls to mincost on the leaf nodes on the little

tree elements. So it's beautiful, it's simply and it

works great. Let's go actually look at an example in

detail to see how it works.