0:00

[MUSIC].

So here in Lecture 10.2, we're going to continue to talk about technology

mapping. And we're actually going to show a very

interesting model of the problem. The problem is going to be solved in a

style called tree covering. And what's interesting is it takes what

feels like a very complicated Boolean algebra kind of approach to a problem.

I've got this giant net list of stuff that comes out of more or less the result

of multilevel logic synthesis. And I've got a library of physical gates

which I get to use which gate goes where to map the output of the synthesis to

what I can actually start working with and lay out.

It turns out we're going to turn it into a very pure kind of a computer science

problem. We're going to take the output of logic

synthesis and require that it be a tree in a certain form, and we're going to

take all of the gates in our standard cell technology library.

And we're going to require that they be trees, tiny little trees in the data

structures style, in a particular form, and we're going to turn it into a

particular kind of a matching problem. It's going to turn into a very pretty, a

very stylized, surprisingly simple computer science matching problem.

So let's go talk about how we can take the technology mapping problem and turn

it into a covering problem with trees. So we're going to talk about a very

famous model of the technology mapping problem may they're the most famous model

a model called tree covering. your logic network to be mapped is put

into a particular form it's a tree of simple gates.

We've already seen the simple gates part, we've seen the NAND gate NOT gate version

of the logic from the previous lecture. It's easiest to assume two input NANDs

and NOT gates makes our lives easiest to describe the structure of the problem.

And your library is also available, your technology library, your standard cell

library of real gates is also represented in this same form: trees of simple gates.

Each gate represented as NAND2s and NOTs, and now there's an associated cost so we

can say something about the quality of the overall mapping by adding the cost of

all the gates that we use. What's interesting is that the method is

surprisingly simple as an algorithm, and even optimal.

Which is to say, once you have your problem mapped into this trees, gates

cost form you actually get an exact and optimal answer.

And I have to say that's actually a pretty rare thing in the VLSI cad

business to, to have an algorithm that gets a best possible example.

In a surprisingly simple, form. in a surprisingly, efficient algorithm.

So, the original reference is, is by, my friend, Kurt Kreutzer, who's, now a

faculty member, at, the University of California at Berkeley.

I believe that he was AT&T Bell Labs when he, when he invented this.

So the papers called DAGON. Technology binding and local optimization

by DAG Matching is in the Design Automation Conference 1987, definitely

worth a read if you can find it. So, what are we staring with?

We are starting with your uncommitted logic that we want to do tech mapping on.

And we are going to assume what came out of the multilevel logic synthesis was a

network of nodes, each which is a sum of product form.

So we replace each sum of product forms in the network nodes that's only NANDS

and only NOTs. And we connect everything up.

And this has a name, it's called the subject tree, and we're going to restrict

things to two input NAND gates and inverters.

It makes everything simple. You can take any piece of logic you want,

even a complicated 2-level sum-of-products form with a big NAND gate

a big OR gate if you will. and you can turn that into NAN gates,

it's just, you know, a little sort of DeMorgan stuff.

I've got a nice little example here on the right.

It's got four inputs, a, b, c, d, on the bottom, and an output called capital Z on

the top. And there are a bunch of internal wires

and they've all got names so input A goes into an inverter makes an output called

P. Inputs B and C go into a nan gate makes

an output called Q. P and Q go into a nan gate makes an

output called R. Input D goes into an inverter.

Makes an output called S. R and S go into an and gate.

Makes an output called T. T goes into inverter makes an output

called Z. That's my subject tree.

That's the little tiny example we're going to play with to see you know, what

what mapping is actually all about. And, interestingly, your technology

library also is an important part of this problem.

And the first problem we have is that the technology library is not represented in

the NAND2/NOT form. Right, so typically the technology

library is just you know, a set of useful small logic functions, so let me give you

an example of a set of useful small logic functions.

This is an example, by the way, that I, I took from chapter ten in Nanni

DeMicheli's book, so this is a nice example.

What's in My Technology Library and inverter which we're just calling a NOT

gate, a NAND2 which is a NAND gate with two inputs an AND2 which is an AND gate

with two inputs. A NOR2, which is a NOR gate with two

inputs, an OR2, which is an OR gate with two inputs.

Something complicated, an AOI21. So this is a layer of AND gates, and then

an OR gate connecting those products. And then an inverter.

At the output and how many inputs are there?

How many or gates are there? Sorry how many and gates are there?

Answer two. How many inputs do they have?

Well the first one has two inputs. And so I'm just going to draw it.

That's the one with two input. How many inputs does the next one have?

Oh it has only one input. That's why we draw it as a wire but I'm

going to draw this in A little sort of a, kind of a dotted,

dotted line way here You know, there's really an AND gate if

you will. There's really an, a vestigial AND gate,

a phantom AND gate there. It's just got one input.

What's a one input indicate? Well, that's actually just a wire.

So this is an AOI21. This is perhaps the first time you've

seen a primitive logic element that is asymmetric.

Right. Not every input is the same.

Here is the symmetric version, a slightly bigger version.

AOI22, again, a layer of and-gates. a single or-gate connecting those

and-gates and then an inverter at the output, how many and-gates are there?

There are two. How many inputs do they each have?

Well, the first one has two and the second one has two.

so that's why this is AOI22, as opposed to the gate on the left, which is AOI21.

Okay. Nice simple, kind of it's easy to explain

why oen would want to be able to use these gates in our, in our logic, but as

I mentioned when we started this slide, the new problem is that it's not in the

required form. Remember, the only thing that I get to

play with are things made out of two input NAND gates, and inverters.

So I have to take this thing and I have to transform it, into, the appropriate

form. Now, that turns out not to be too hard,

so I've got the library again drawn as a little kind of highlighted box in the top

right-hand corner of the slide. A NOT gate, a NAND2, an AND2, a NOR2, and

OR2. AOI21 and AOI22.

Alright? So one, two, three, four, five, six,

seven gates. One, two, three, four, five of them I

would say simple gates, two of them complex gates.

I need to transform this so the only thing I see are two input NANDs and

inverters. That's pretty easy.

So the inverter, well heck, that's just an inverter.

Life is easy. The NAND2 gate is just a NAND gate.

The AND2 gate is just an inverter with I'm sorry, a NAND gate with an inverter.

at the output to get rid of the complement.

I'll admit that the NOR2 looks kind of ugly.

You know, the NOR2 is two inverters going into a NAND gate whose output goes

through an inverter. Right?

This is just the DeMorgan Law that says, you know, x plus y with a bar over it is

x bar and y bar, so there's two input, input inverters giving you x bar and y

bar. But the problem is that it's a NAND gate

so I've got to get rid of the bubble. So, that's why there's another AND

another inverter there. The OR gate is simply the NOR gate

without the output inverter. So, it's two inverters leading to NAND

gate. the nice thing about the ALI structures

is that they really are some of product's forms.

They're supposed to be a layer of AN-, of AND gates and an OR gate then an

inverter. You know that a two-level form and/or

structure, you can just replace the ANDs with a NAND and the OR with a NAND and it

all just works. The only thing you have to be a little

careful of here is that It is an inverting logic, and so it, it has to be

the complement of the sum of products, sort of a form.

So you get an inverter at the output, and if you're careful with the DeMorgan law,

the wire, right? Which was as I said, kind of a one input

AND gate. When you turn that into a NAND gate, you

get a one input NAND gate, and one input NAND gate is an inverter.

So you just got to be a little careful on that one.

So this is A NAND gate with two inputs, a NOT gate with one input, those two

outputs go to the NAND gate. The NAND gate goes through one more

inverter to get the polarity right, and then you get a AOI21.

And AOI22 looks exactly like that, except the wire, with the inverter on it.

is replaced with a NAND gate. So, This is a nice symmetric structure.

2, 2 input nand gates going into a single 2 input nand gate which goes through 1

inverter to get the polarity right. And here we are I have accomplished what

I wanted, my technology library is represented in exactly the same form as

the output I get. From multi-level logic synthesis.

In this form each library element is called a target tree so recall after I

took the output of multi-level logic synthesis and turned it into NANDs and

NOTs. I called it the subject tree after I took

every one of the elements here elementary.

library gates, any of the complex gates in my technology library, and turn them

into NANDs and NOTs, it's now called the, each of them is called a target tree.

So, what's the essential idea of tree covering?

And, and this sounds a little strange, but the idea of tree covering is, I want

to avoid doing any Boolean algebra. Even though we're actually kind of pretty

good at that at this point. I don't want to do this with any Boolean

algebra. I want to do this by just essentially

pattern matching, you know, like, like, like matching a string, you know?

A capital B matches a capital B but a capital B doesn't match a lower case x.

the technology library which I'm again showing at the top left, a NOT, a NAND2.

AND2, NOR2, OR2, AOI21, AOI22 each expressed specifically in NAND2 and NOT

gates. And on the right I've got my little

pattern my little subject. Right, the z.

Tree and so this has a, b,c, and d as inputs, z is outputs,internal nodes p, q,

r,s,t. It's got 3 nands and 3 inverters.

What you will notice is that every one of the gates in my technology library is

nothing but 2 input nands and inverters. And the thing that I am matching.

Right? The thing that I am mapping onto these

gates, is itself, just two input NANDs and inverters.

I can do this mapping process by just making sure that I pick things from the

technology library. Where the gates match exactly.

No Boolean algebra at all. So, I am allowed to match things like

NAND gates to NAND gates and I'm allowed to match things like inverters to

inverters and that's it. So, look, here's a concrete examle.

Let's select the AOI21. So, it's got an inverter on the top and

then a NAND gate and then the inputs to the NAND gate are.

1 nand gate and 1 inverter. And if we look over at the subject tree

what we can see, and I've got it colored in, in a kind of highlighted way, is that

the top of the z tree looks exactly like a AOI 2 1, right?

It starts with an inverter on the top. So I'm going to put a little check mark

by the, by the inverter. And then when I look below it.

The thing going into the inverter is a NAND gate and that looks like it matches.

And then when I look to the left in this case I see a NAND gate going into the

NAND gate and oh yeah, that's what AOI21 has.

And then when I look to the right I see an inverter and it's like oh yeah, that's

exactly the same. I can I can actually make the output of

the z function by putting a aoi 2 1 as the output of this logic network.

This very simple minded matching process has a name, it's called structural

mapping. Find where in the subject graph, the

library pattern matches everywhere. And there's a very simple set of rules,

nand matches nand. NOT matches NOT and so on.

All right so, that's the essential idea in tree covering.

We're going to take elements from the technology library and we're going to put

them on top of the subject tree and make sure everything lines up in some fairly

simple way. With some quite simple rules, and the

only mapping that I have, the only matching that I have to do is like gates

have to match. So just to sort of summarize there, the

general tree cover representation is a structural technology mapping, there is

no Boolean algebra anywhere. We just match the gates and the wires in

a simple pattern matching kind of way, and the result is a surprisingly simple

covering algorithm for the cost-optimal cover.

but first, I want to simplify the way we draw these, because there, there's still

just too much going on in these diagrams. And I want to sort of emphasize the fact

that this really is a very simple kind of a pattern matching kind of a process.

And so, I'm going to show how we're going to represent the trees for

covering. On the left again, I'm showing my little

z subject tree inputs a, b, c, d output z, there are three NAND gates here, three

inverters here internal nodes p, q, r, s, t just as before.

Look, there's only three kinds of things you can match looking at this tree.

And so we're just going to draw it in a really simple-minded way to sort of

remind ourselves that there's only three things going on here.

The first is that there are NAND gates, so instead of drawing a NAND gate, I'm

going to draw a circle, and I'm not going to fill it in.

So I'm just going to draw a white circle. Every place you see a white circle from

now on, that's a two input NAND gate. And the inverters, I'm going to draw a

black circle. Okay, and I'm just this is sort of

arbitrary. the Nanni DeMicheli book has a different

sort of notation for doing this, I'm trying to be even simpler than, than the

way he's doing it, I think this merited. So an inverter is a black circle a manned

gate is a white circle. And then there's also something that's

not so obvious you need, there are inputs, right?

And the inputs are square boxes, okay? So a NAND gate is a white circle .

A NOT gate is a black circle, and input is a square.

So if I take the z subject tree on the left-side of this diagram And I draw it

again on the right, this is what it looks like.

So, there are four inputs, a, b, c, and d.

Those are now square boxes because those are inputs.

We actually have to be careful that we represent those things.

We have to match those things too, carefully.

the a input goes into a black circle, because a is, A goes into an inverter

that makes the output p. B and c go into a white circle.

Because b and c go into a NAND gate, okay?

The p wire output from the inverter. The q wire output from the NAND gate

going to a white circle. Because p and q go into a NAND gate that

makes output r. And so that's a white circle.

Input d goes into an inverter that goes into a black circle.

That makes an s. R and s go into a white circle because

that's a NAND gate, That makes t. T goes into a black circle, that makes z.

So this is just one to one exactly the diagram on the left-hand side here, but

it looks very simple, right? Just the white circles, black circles and

boxes with letters on them. Now You have to actually make the

technology library in exactly the same style in order to execute this algorithm.

And so I'm showing you a picture of the tech library as gates again.

Simple NAND, and NOT gates. So there's a NOT and NAND2 and AND2, a

NOR2 and OR2, AO121, A0122. One, two, three, four, five, six, seven

gates in my technology library. Everyone of these things has to be

represented in the same style wise graph. Form.

So, there's the NOT gate. What does a NOT gate look like?

It's a square representing an input going into a black circle.

There is a NAND2 and an AND2. The NAND2 is just a white circle with two

children left right that are inputs. The AND is a black circle because it's an

inverter. At the output of a NAND which is a white

circle with two, two boxes that make the inputs.

NOR2 and OR2 are a little more complicated.

Remember, NOR2 was a NAND gate with inputs at the inputs and the outputs.

So, it's a white circle. Output goes to a black circle.

Inputs come from black circles. Two input boxes, the OR looks just like

it, but omit the output black circle. AOI21, a black circle at the top, because

it's an inverter, that's fed by an OR, a NAND gate, a white circle, the inputs to

the white circle, one white circle with two inputs, one black circle with one

input. The NAND and the NOT respectively.

AOI22, black circle at the top fed by a white circle, white circle fed by two

white circles, each white circle fed by four square boxes.

Alright, so this looks much simpler than what we started with.

There is no Boolean algebra happening here at all.

This is a very simple structural mapping problem.

And so, I'm showing you now, the, sort of, the

structural mapping problem in its, sort of, precise form.

I'm showing you the technology library at the top of this diagram.

NOT, NAND2, AND2, NOR2, OR2, AOI21, AOI22.

And each one of them is the little set of black and white circles.

And boxes from the previous slide. And at the right hand side, I'm showing

you the little z circuit again, a, b, c, d inputs, z as output, internal nodes p,

q, r, s, t. Three white circles, three black circles.

And structural mapping says I have to find where I can fit the library gates,

which are black circles, white circles, and square boxes, on top of the Z circuit

and match with a simple set of structural Matching rules.

What are the rules? The rules are mostly really easy and

mostly really obvious. A white circle matches a white circle.

Your allowed to put an and gate only where there's an and gate.

So a white circle matches a white circle. A black circle matches a black circle.

Your allowed to put a not gate only where there's a not gate.

And, this is the one that's maybe a little bit complicated.

We need to talk about this just a little bit.

A square box which represents the input to one of the library elements.

Or, the input to the overall subject tree.

The thing that popped out of multilevel synthesis that matches anything.

The way that works, is the way that it matches anything, that's how it's

possible for the output of one gate to connect to the input of another gate.

And, we're going to talk about this with, a little example here.

So let's, let's just start by, by doing a, a sort of a complicated thing.

So, I've got the technology library, again, shown at the top, not NAND and

NOR. Or, AOI21, AOI22.

And I've got my little Z tree on the right.

Four inputs, a, b, c, d, three black circles, three white circles, Z at the

top. The and/or invert 2 1, as we already said

in a previous slide matches as Z Right? It's got, you know, a black circle at the

top and then a white circle one level down, and then one white circle and one

black circle as children and inputs. Right?

The AOI21 matches at Z because of two things, alright?

So the first thing, first reason it matches is that all of the internal nodes

match exactly. And so I'm going to highlight the a AOI21

for you here. And then I'm going to highlight how the

AOI21 matches, right. So at the top there's a black circle and

the black circles match. There's one child of the black circle and

it's a white circle. Those things match.

There are two children of the white circle.

a white one on the left and a black one on the right, turns out that matches

exactly as well, white one on the left, black one on the right, I'm just checking

the little boxes in the AOI21 pictures. Alright, those are all the internal notes

and then, I'm going to put a star by this it's in red over here and the inputs

match anything. And so what that means is, just to be

very clear. The leftmost input of the nand gate

circle. The white circle of the AOI21 matches p.

Which is to say, it matches the black circle that makes p the internal wire/g.

Now, that's an inverter. Inputs match anything, right?

So that, white box, matches the black circle that makes p.

The next input, to the NAND gate, the right input to the NAND gate, that's at

the bottom of the AOI21, matches q. That matches an infer-, matches a

A NAND gate, right? So, just be clear, the left box matches

the inverter, the right box matches the NAND gate at q.

Because, inputs match anything. And going forward, the third white box at

the bottom of the AOI21, the input to the inverter in the AOI21, matches the d

input. It matches a box, another box.

Right? All of this works, all of this is

required in order for, to have the semantics of the overall matching of how

gates cover the tree work out okay. Alright, so, internal nodes must match

exactly. We saw that in a kind of a simple way.

And inputs match anything. Now, there's one kind of a careful thing

you got to just be careful about. we haven't shown this in any of our

examples so far but, the symmetries matter.

So on the left of this diagram here, I am showing you an AOI22 has an output

inverter A NAND gate. I'm connected to that inverter.

And then the inputs to that nand gate are another 2 nand gates.

It has a symmetric tree. You know?

A black circle fed by a w-, a white circle.

Fed by 2 more white circles. Fed by 4 white boxes.

I don't care which way you sort of match. there's no, there, there's nothing

asymmetric about this one. That's not true if you look at something

like the AOI21, right. I mean, I have drawn the AOI21 as a NOT

gate being connected to a NAND gate, being connected on the left.

To a NAND gate on the right to an inverter, but there's no reason on earth

that I couldn't flip that. And I've got a little red arrow here that

flips it. Now, the inverter is on the left and the

NAND gate is on the right. and I'm just showing you the black and

white pattern trees. You know, the one way of doing it has a

white circle on the left and a black circle on the right.

The other one has a black circle on the left and a white circle on the right.

This is not a symmetric pattern. When you're matching you actually have to

rotate it and see whether or either orientation will match in your subject

tree. So how does one actually do a complete

tree cover. suprisingly there are two simple rules.

Every note in the subject tree is covered by some library tree.