[SOUND].

So here we are in lecture ten. This is actually sort of the link between

the logic part of this course, and the layout part of this course.

So the course is called VLSI Cad Logic to Layout And the logic stuff.

We've done lots of bouillon algebra, computational bouillon algebra.

Representation, optimization, synthesis, lots of interesting stuff.

And on the layout side, we're going to be placing things.

We're going to be routing things. We're going to be figuring out how their

timing works. There's kind of a link and the link is

interesting. The link is actually a step called

technology mapping and you might think after all that interesting two level and

multilevel optimization that we did that what comes out is logic gates.

And the answer is no, what comes out of multilevel logic synthesis is a Boolean

logic network. Each of whose nodes is a sum of products

form, it's not gates and even worse it's not gates in the actual library of pieces

of gate technology that you get to put on the surface of the chip those are things

called standard cells. So, to start things off, we're just

going to talk about what actually happens at the end of logic synthesis.

And what you actually need to do to get started with layout.

I'm going to talk about the pieces of the optimization problem.

And what the problem is. So let's go talk about technology

mapping. So we are still in, sort of, in the

middle of our transition from logic to layout and one of the things I mentioned

in the last lecture is that there's really a missing step.

And because of our desire to actually start doing some interesting projects

with layout technology, we sort of inverted the order.

So, so we're going to go back to this now.

So, just to review what, what you know from the first half of the class is

computational Boolean algebra. A lot of really interesting

representations, some verification's, some synthesis technology.

This is the so called front end of the ASIC design process.

The back end is the layout the geometry end, and there's a big missing step which

is how do you actually go from the results of multilevel synthesis into real

gates for the layout and perhaps it's a bit of a surprise that you don't actually

get real gates as the result of multilevel synthesis and that's the topic

of this lecture. This stuff goes by a lot of different

names it's most formally called Technology Mapping, it's very frequently

called tech mapping just because it's shorter to say.

It's often just called mapping. depending on the application, sometimes

it's called fitting, sometimes it's called binding, but most commonly, the

stuff is called tech mapping or just mapping.

A nice reference for this stuff is sort of a broad reference of of a variety of

technologies for this stuff is the Nadia McKelly book, Synthesis and Optimization

of Digital Circuits. This is chapter 10 in that book.

So, let's talk about tech mapping, what is the problem?

The problem is that the multi-level model is still a little bit abstract.

So, you know, what happened in the multi-level synthesis technology that we

talked about. We figured out the structure of the

boolean logic network. And so in my, my little example here,

which has input's a, b, c, d. Three nodes in the network, X equals b

plus c, Y equals aX, Z equals Xd. We figured out the right high level

structure of the network. You know, what the nodes are and how

they're connected. And we also did ESPRESSO-style 2-level

simplification on the inside of each of these nodes, the yellow nodes in there,

or so, we optimized them well, but this is not really gates.

And the, the thing to just be, be clear about is that.

This diagram below, those are not logic gates, those are nodes in a graph that

has a particular kind of a structure. The boolean logic network there could be

thousands of those bubbles in a real version of this as the result of

multi-level logic synthesis. What if everyone of those nodes has a

half a dozen or 10 or 15 literals in its sum of products form?

It's not real gates, and the question is how do you get it to be real gates?

So, suppose that you actually have a particular technology library.

And suppose that this is that technology library.

Now, frequently, when we talk about the technology library.

The library of discrete standard cells that we are allowed to use as our basic

logic elements. It's very frequently just called the

technology. So suppose this is the technology that I

get to use. I get to use a 2 input and gate.

AND2 input or gate and a slightly strange looking thing called an OA21.

Its a two input OR gate feeding one of the inputs of an and gate.

And the other one is just a standard input to the and gate.

It's a little bit complicated. So this is the so called complex gate in

our library. The big question that we need to figure

out how to correctly answer, is if I give the output of multilevel optimization, in

this case, my little bouillion logic network with the x-node, the y-node, and

the z-node. How do we build the two Functions, in

this case the y function and the z function.

Functions of a, b, c, and d, specified in this[UNKNOWN] logic network using only

these gates from our library. Now, just drawing this picture again here

in my new slide. So this is a simple example.

So I'm drawing the library as a two input and A2 input or.

And this 0A21 To input or feeding one of the inputs of an and gate.

I'm drawing it with big curly set brackets just to emphasize the fact that

its an important object that we get to, work with and manipulate and play with.

In order to effect our technology mapping.

And I'm coloring this in in yellow, just to highlight it.

What we need to do is look at our Boolean logic network and say, if I only get to

use this and gate, this or gate and this strange OA21 thing, how do I actually

Take the logic function specified in the bouillon logic network.

And turn it into real logic gates. And look, this is just a really simple

example. It's set up to be a simple example.

One of the ways I could do this is I could do this example here.

I'm calling this the obvious mapping because look, you look at the logic

network, the x node is an or gate. The Y note is an end gate.

The Z note is an end gate, maybe we should just make the X note an orgate

with inputs B and C. And connect the output of the orgates to

2 and end gates. And the top end gate has an input A.

And the bottom end gate has an input D. And one of them makes Y and one of them

makes Z. And that's really just pretty obvious.

Now where this stuff gets interesting is that there are.

Less than obvious mappings and I am calling this an un-obvious, may be a non

obvious mapping and in this mapping I use two of these OA21 gates.

So, to implement the Y function I actually do this as 1 OA21 with inputs a,

b, and c. A goes under the AND gate, b and c go

into the OR gate and for output z I go d into the AND gate and b and c go into

the OR gate and you are thinking. Well this is a little bit strange, and

I'm, I'm just putting a little kind of a question mark here on top of the two OR

gates I'll even write two question marks. it would appear that I've duplicated the

Or gate, why why would I do that? You know, why would I choose the

un-obvious mapping? And let me give you an answer.

Why would you choose the non-obvious mapping?

the answer perhaps is cost. Perhaps it is the case that the

un-obvious mapping is superior in some dimension that I can associate with a

number. So imagine that every gate in my

library[UNKNOWN] has a cost associated with it.

May be it's the amount of silicon area in the, in the standard cell gate, may be it

has something to do with the power. That means there are all kinds of ways of

creating matrix for this but you know low cost is better and so I am just putting

cost numbers. The AND2 has a cost of 2, the OR2 has a

cost of 3 and the OA21 has a cost of 4. These are entirely arbitrary and now

somebody has to figure out what the right costs are but now I have got a picture of

the obvious mapping on the left at the bottom, one or two ends.

And then I've got a picture of the un-obvious mapping 2OA21's at the right

and what we can see immediately is if I put the cost values on the cost mapping

the or costs three. Each of the ands cost three.

This entire mapping cost three plus three plus three that's nine, but what if I put

the cost values on the un-obvious mapping?

Well each of these OA21 gates costs four, and so, putting two of those together

costs eight, eight is better than nine, this is a better mapping now (no period)

This is a quite synthetic examThis is a quite simplified example.

But in the real world, where you have large[UNKNOWN] logic networks.

And you have things that have, you know, hundreds or thousands or tens of

thousands of gates in them. What the right answer is is not at all

obvious. You need some kind of metric to guide you

for what the. What the best answer is associate cost

with all of the gates. Map so that you choose the lowest cost

covering. The lowest cost mapping of the Boolean

logic network on to the library that's going to get you an answer that makes

sense. So, the other way of saying why you

choose a non-obvious mapping, the sort of the second answer is that you know the

non-obvious mapping has better complexity.

And really this is just sort of cost in a, in a different way.

So for example, your library might have a bunch of complicated gates, so-called

complex gates. The are really hard to map to by eye, it

is pretty easy to figure out where you can put in 2, put AND gate or to input OR

gate or input invert but I am showing you to realistic gate cells.

On the left I am showing you OR, AND and Invert structure, this is a so-called

OAI22. So, it's a layer of OR gates connected to

an AND gate with an inverter at the output that's why it's called OAI and the

an answer to the question. How many and gates, sorry, how many or

gates are there and what are their structure?

The reason it's called a two two, is that there are two such gates.

That's why there's two digits there. And each of those gates has two inputs.

So you see a two input or gate. And another two input or gate.

So, that's why this is a two two, and let's say that that costs 6.

And next to that, on the right, is an and or invert structure, a different one and

AOI221. Again, an input bank of and gates, then

an or gate, and then a invert, a bubble. In this case, how many or gates are

there? Well, there's kind of three.

Alright the first 1 has 2 inputs the second 1 has 2 inputs and the third 1 has

1 input and, and you know, kind of the obvious way to think about why I'm just

drawing a wire going into this Or structure this Or Invert structure is

that this is really sort of an AND gate with exactly 1 input going into it and

what's an AND gate with 1 input going into it it's a wire.

So this is an AOI-221. Imagine that the AOI-22 cost 6 and the

AOI-221 cost 7. An interesting thing to note, it seem the

OAI and the AOI gate structures are often very efficient at the transistor level.

A bit more efficient than actually discretely using some ends and[UNKNOWN]

and inverts. And you know, for small versions of these

complex gates. These things are actually a sometimes a

better cost match and its much, much more difficult to match where these things go.

To technology map where these things go which is why we need an algorithim so,

It's helpful to introduce what I'm just referring to as a mental model, a kind of

a conceptual way of thinking about what multilevel synthesis does.

This is what multilevel synthesis does. It structures the multiple vertex Boolean

logic network well. What does well mean?

It means that the number of bubbles the structure of the bubbles, the number of

layers of, of you know, bubbles between the input and the output.

The complexity of the logic inside each of the bubbles, you know, pretty good.

And so, you know, following up on that as it minimizes or as it optimizes the

macroscopic structure of the logic network it minimizes the sum of product

contents inside each vertex so that the two level form that each vertex wants to

implement is also well structured in terms of the number of literals in the

sort of the macroscopic. Graph structure is also good.

The big, important thing to note is that optimizing the macroscopic graph

structure of the logic network, and optimizing the sum of products contents

of all of those bubbles is not logic gates.

And in particular, it's not logic gates in the technology library you are

permitted To use, alright? So this result actually has an

interesting name, a new name. actually a couple of names that you may

or may not have heard of. This is often called uncommitted logic.

Which is to say, I have not committed this to a particular set of gates from my

technology library. It is also called technology independent,

because we often call the library that we get to use, the technology.

And when the stuff that pops out of multi-level synthesis is not mapped yet

to the technology. We say that it's technology independent.

And so I've just got a little picture down here, there's an X node, a W node, a

V node, the X and the W nodes go into the Y node.

The Y node is an output, the W and the V node go into the Z node, The Z node Is an

output. Just to sort of highlight this, what

multilevel synthesis does is it gives a good global structure to the nodes, the

X, the Y, the Z, the W and the V in this diagram.

And it gives a good local structure to the insides, the sum of products forms

the sum of products inside the nodes like Z.

But this is not logic gates. So what does technology mapping do?

Technology mapping does something sort of interesting in an interesting way.

The first thing we do typically, is we transform this into uncommitted logic

that is made up of only very simple gates, but real gates, alright.

So a very common way of doing this is to transform every sum of products

expression inside each node, into something very simple, like NAND and NOT

gates, and nothing else. So, I've got a little picture of my

network from the previous page, you know, X, Y, Z, W and V nodes.

And I've got the X node and the Y node highlighted.

We know that those are sum of products 2-level forms.

What do we do? We turn the X node into.

NOT gates, inverters, and NAND gates. Now, one of the things to remember from

way back when in Boolean algebra, is that if you have a sum of products form, you

know, with AND gates for each product term in a big OR gate connecting it, you

can replace every AND gate and the OR gate itself with a NAND gate, and it will

all work properly. It's sort of an interesting side effect

of the De Morgan laws for how compliments work.

And so we're going to take all of the AND gates in the products and replace them

with NAND gates, and we're going to take the output OR and replace it with a NAND

gate. And then we'll just put inverters

wherever we need the literals to be in the complimented form, and we're going to

build, X the node, as real gates, but real simple gates.

So we're going to build it all out of NOTs and NANDs.

And then similarly we're going to take the Y node and then we're going to build

that, out of NANDs and NOTs. And so, it's got, probably a different

number of products, so it's got a different number of the input NANDs.

It's got, maybe a different. You know number of products and so the

size of the output end is different. Its got complements on different places

on the literals and so then the inverter gates are in different places.

But again, I can build the contents of the individual node, which is a sum of

products form, simple two-level form, as nothing but inverters and NAND gates.

We're going to do that for every single node in this network and then we're

going to connect things so, the X node connects as an input to the Y node.

And I'm just making kind of an arbitrary assumption that it connects to one input

on one gate, it could connect to a whole (no period) Bunch of different places

going in to the y node. But the big important idea is that we

need to take a step away from the abstract form of the Boolean logic

network to something that's real. Gates and our first step is an

interesting simple step. We go from the sum of products forms to

nans and nots and we do that for every node in the Boolean logic network.

And so what we're going to get as a consequence of that is this.

Sort of complicated looking diagram here. Where the X node, the W node, the Y node,

the Z node, the V node. Each one of those things is replaced by

some combination of NAND gates for the product terms.

NOT gates for the literals that appear in complimented form in a big NAND gate at

the output to implement the two level form.

A two level not NAND form for every sum of products form, and then the sum of

products forms themselves are connected properly.

So, what I get here is one big, flat and I'm referring to that in a very

particular way, okay? One big flat network of NANDs and NOTs.

This is what you map, what flat means in this context is that the boundaries,

between the X node, the Y node, the W node, the Z node.

All of those things go away. So one of the really important things to

note is that it's not as though I'm restricted to take the gates in my

technology library. And map them against them against the

insides of every yellow bubble on this diagram.

No, I take the logic function specified by every node in the diagram.

I flatten it out into 2 level NAND, NAND not structure.

I connect up everything appropriately and I throw the bouillon logic network away.

This big messy looking logic network with all of these NAND gates and inverters,

this is what we map, this is what happens next.

So, this is our strange and complicated looking starting point multilevel

synthesis produces well the first thing it produced was a bullion logic network

model with well structured microscopic form and well structured sum of product

form and what we did was we in a sort of a dumb brute force simple minded way.

We push that immediately into real gates, but very simple gates, NANDs and NOTs.

This big network, that I'm again highlighting on the, on the pager here,

this is what we start with, this is what we're going to map.

And the big and interesting question for us is algorithmically, how do I transform

this big network of NAND gates and inverters, how do I map this thing onto

the standard cells in our library in some optimal way?

So, this is a pretty algorithm as it turns out, a very nice application of the

ideas from the computer science universe to a really interesting hard problem, in

the[INAUDIBLE] universe, so let's go see how that works next.

[SOUND]

Technology Mapping Basics

VLSI CAD Part II: Layout

Meet the Instructors