0:00

[SOUND] So, here in 10.3, we're going to do something in the

exploration of technology mapping, that sounds very strange.

We're going to tree-ify, the netlist.

Now.

What we learned in the previous lecture was

that we're going to model the output of

the logic synthesis step and all of the

gates in our standard cell technology library as trees.

And there are going to be trees of

very simple things, nandgates, notgates, inputs and wires.

It turns out that for the particular kinds of algorithms that we want to

be able to do this matching to work, everything needs to be a tree.

And it turns out that under some very natural circumstances, the

stuff that pops out of logic synthesis is not a tree.

And so we sort of coin a word here, what is the act of taking a net list that comes

out of logic synthesis and breaking it apart into things

that are trees and the answer is we tree-ify it.

And so, let's show you in this kind of short little lecture how

we tree-ify the net list so we can move forward with technology mapping.

1:15

So, let's talk about the specific steps that we need for

a complete algorithm for technology mapping

using this technique called tree covering.

Th, there's really three parts.

There is tree-ifying the input netlist, which is

a very strange sounding word, I will admit.

It's a key assumption and that's what this lecture's about.

There's the tree matching step, which is how do you take each node in

your subject tree and ask, well, what

in my library, my technology library, maps there?

And then, the real heart of technique, which is the recursive

minimum cost covering, that assumes that once you know what matches

at any given mode in the large subject tree, you can

actually somehow construct an optimal covering with a, with a good cost.

So the first step is that we have a, we have an important assumption.

This is this thing called tree-ifying the input netlist.

This is actually a really important

assumption we're going to talk about this now.

2:11

So let's talk about this process of tree-ifying the netlist.

Now the big reason we have to do this is that

all the algorithm's we're talking about in the technology mapping lecture.

They only work on trees.

Not more general graphs and as an example of a general graph

I've got the netlist shown at the bottom with the blue gates.

So these are gates, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Gates one, three, and five are inverters and gates

two, four, six, seven, eight, nine, and ten are nand-gates.

So gates one and three drive gate two, gates three and seven

drive gate four, gate seven also has an input from gate six.

Gates seven and eight drive gate nine, gate

four drives gate five, gate nine drives gate ten.

3:09

So their directed acyclic graphs.

And the big idea here is that every place you see a gate with a fanout, which

means that the gate drives more than one other

gate, you have to split the net list there.

And so that's gates three and seven in this picture.

Now the rules for the mechanics of how you

tree-ify are actually pretty simple and, and here they are.

So the first rule is that every gate with fanout

more than one becomes the root of a new sub-tree.

And then the second rule is that each connected fanout becomes a new input.

Now this is much easier to see if we actually just walk through

this net list and do a little surgery on it to fix it.

So the first rule says every gate with a fanout becomes the root of a new subtree.

So let's go look at where the fanouts are.

Well, Gate three fans out to two places and gate seven fans out to two places.

So the way to think of this is I'm just going to cut those wires.

And then I'm going to do some more work on this netlist.

So, the first thing that we can see happens is

that gate three, because it had a fanout of more than

one becomes the root of a new sub tree and the

green circle is circling the entire tree in the tree-ification process.

Now, interestingly enough, gate three is the only gate in

this tree and it's you know, just the way this works.

So three is the root of a new tree and it's got only one gate in it.

5:25

Similarly gates four and five become a new tree.

[COUGH] And, we'll notice that gate three and gate seven were driving gate four.

And those wires don't exist anymore, so we're

going to make one new input to deal with the

connection from gate three and a second new

input to deal with the connection from gate four.

So gates four and five are a new tree.

And similarly gates eight, nine and ten are a new tree.

And we know that gate nine has an input from gate seven.

That was a fan-out.

Right?

So we're going to give gate nine an entirely new input.

6:01

To make it not at all connected to gate seven, and this is what we get.

You'll note that there are five green circles around the new sub-trees.

And what happens is, we split this directed acyclic graph with fan-outs into

five separate trees, and we're going to map all five of these trees separately.

And then after the technology mapping we'll connect them back up so

that it's the original, logically doing the right thing with the original netlist.

Now I need to be careful to say that this entails some

clear loss of optimality because there's some kinds of mapping that might

go across the boundaries of these trees with logic elements

and I simply cannot map across these trees so you win some you lose some.

What we win is that we have tree-ified things and so we can precede

with the rest of this lecture and we will be able to map them.

But there's some kinds of optimality that we just can't get.

6:57

So, looking at this new slide, let's just look at the result.

Now, just to summarize again, all the

algorithms in this lecture require trees not DAGs.

So, every place there's a fanout from a gate you have to cut it and tree-ify.

This is going to lose some optimality.

There are in fact, some ways around this, but

we're not going to discuss them in this this lecture.

We're, we're primarily discussing the most famous

technique in this, space of technology mapping algorithms.

So, on the left of this diagram, I've

got the same net list, from the previous slide.

So this is gates 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Right?

And the netlist is not a tree.

And when we do the tree-ification process we get the results on the right.

We have five separate trees.

So just going from left to right.

Gates one and two are a new tree.

Root of the root of this tree is gate two the end gate, and

gate two has a completely new input which is depicted by that black box.

That's new because we are not a allowed to deal with

any of the fan outs that were in the original net list.

Gate three is it's own tree all by itself and so it's the root.

8:20

And gates eight, nine, and ten are also a new tree.

And because gate nine was driven by a fanout, gate nine gets its own new input.

And so that's the result.

On the left of this slide, the directed acyclic graph

original logic netlist with fanout from gates three and seven.

On the right, five separate trees.

This is a really simple process.

There's not really any decision making going on here.

You just look at a gate that has a fanout, you break the wire.

The gate becomes the root of a new tree and anything

driven by the fanout, you say hey, I'm a new input.

And you just walk through the netlist doing this.

There's really no choices involved.

You get what you get.

So, you get a lot of little trees.

But as we proceed in this lecture, we're actually going to be

able to do a very good job of mapping these individual trees.

And then what's going to happen is we'll

just connect them back together at the end.

9:24

That's in the subject graph.

What about the pattern trees?

What about the target trees, the things

that your technology library is made out of?

You know, those are little things, like nandgates and

notgates and, and you know, mildly complex things like

and or inverts, Are there any ordinary common useful

gates in my technology libraries that can not be trees?

9:59

well, what is it that's in a pattern library that's just the sort

of a, a basic perimeter gate that, that can't be represented as a tree.

And one of the answer is an exclusive war.

So here's a little picture of an exclusive war gate,

go two inputs A and B and an output Z.

Let's recall what an exclusive war is Z is A B bar plus A bar B.

And so now I'm going to draw that as a logic network and so what do you get?

Well, it got an A and a B input at the bottom.

And the a input goes to a nandgate.

And the A input also goes through an inverter to the other nandgate.

Right?

Because it's A in one of those product terms an A bar in the other product term.

And the B input goes in to the other nandgate and then

it goes through an inverter and it goes into the first nandgate.

And then the output of those two nandgates goes into a nandgate

because that's just how you make a sum of products and or form.

And that's an exclusive war represented entirely with Nands and Nots.

And the immediate problem we have is that there's fanout

there and surprisingly the fanout is just from the input wire.

The A goes to the nand and it goes to the inverter,

which means, it's got fan out which means this is not a tree.

And similarly the B input has fanout.

It goes into the nandgate and it goes into the inverter.

It's got fanout.

And if I were to draw this thing as

one of our little black circle white circle box trees,

there would be up at the top the Z output

which comes from a black circle because there's a nandgate.

The two inputs to the black circle

are themselves black circles because they are nandgates.

And the inputs to the two nandgates are, well.

Each one has an A on the left and a B on the

right, and then each one has the other input going through a white circle.

Right so the A box goes to a black circle, and then it

goes from a white circle to a black circle and the B box

does the same thing symmetrically, and the problem is that there's fan out

immediately at the A input and so this thing is not a tree.

Why is this thing not a tree?

Well I can start up at the root.

I'm just going to sort of draw it.

I can start up at the root and I can

go down two different paths to get to the A node.

That's not possible in a tree.

There's only one path from the root to any internal node in a tree.

So, this is not a tree.

And so, interestingly enough, you don't get to use EXOR gates in

the very simple kind of mapping that I'm going to show you.

Now, is it possible to repair this?

Oh yes, absolutely.

It just requires a little bit of technical, messy case analysis.

It's just not worth doing at this time.

So, the tree-ification assumption is kind of simple to deal with.

You take the subject network that pops out of multilevel logic

synthesis and the transformation into nans and inverters and any place you

see a fan out you simply cut the wire and you

break what is a large logic network into probably several smaller networks.

And you just agree that you're not allowed to have a

target library element in your technology library that's not a tree.

Which means you're not allowed to use

an exclusive war gate among some other things.