[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]
