1 00:00:00,25 --> 00:00:08,55 [SOUND]. 2 00:00:08,55 --> 00:00:12,498 So here we are in lecture ten. This is actually sort of the link between 3 00:00:12,498 --> 00:00:16,254 the logic part of this course, and the layout part of this course. 4 00:00:16,254 --> 00:00:20,198 So the course is called VLSI Cad Logic to Layout And the logic stuff. 5 00:00:20,198 --> 00:00:23,628 We've done lots of bouillon algebra, computational bouillon algebra. 6 00:00:23,628 --> 00:00:27,410 Representation, optimization, synthesis, lots of interesting stuff. 7 00:00:27,410 --> 00:00:29,690 And on the layout side, we're going to be placing things. 8 00:00:29,690 --> 00:00:31,966 We're going to be routing things. We're going to be figuring out how their 9 00:00:31,966 --> 00:00:33,866 timing works. There's kind of a link and the link is 10 00:00:33,866 --> 00:00:36,415 interesting. The link is actually a step called 11 00:00:36,415 --> 00:00:40,100 technology mapping and you might think after all that interesting two level and 12 00:00:40,100 --> 00:00:45,190 multilevel optimization that we did that what comes out is logic gates. 13 00:00:45,190 --> 00:00:49,90 And the answer is no, what comes out of multilevel logic synthesis is a Boolean 14 00:00:49,90 --> 00:00:53,402 logic network. Each of whose nodes is a sum of products 15 00:00:53,402 --> 00:00:57,824 form, it's not gates and even worse it's not gates in the actual library of pieces 16 00:00:57,824 --> 00:01:02,180 of gate technology that you get to put on the surface of the chip those are things 17 00:01:02,180 --> 00:01:08,662 called standard cells. So, to start things off, we're just 18 00:01:08,662 --> 00:01:13,110 going to talk about what actually happens at the end of logic synthesis. 19 00:01:13,110 --> 00:01:16,898 And what you actually need to do to get started with layout. 20 00:01:16,898 --> 00:01:19,800 I'm going to talk about the pieces of the optimization problem. 21 00:01:19,800 --> 00:01:23,340 And what the problem is. So let's go talk about technology 22 00:01:23,340 --> 00:01:26,533 mapping. So we are still in, sort of, in the 23 00:01:26,533 --> 00:01:31,83 middle of our transition from logic to layout and one of the things I mentioned 24 00:01:31,83 --> 00:01:37,46 in the last lecture is that there's really a missing step. 25 00:01:37,46 --> 00:01:41,133 And because of our desire to actually start doing some interesting projects 26 00:01:41,133 --> 00:01:45,498 with layout technology, we sort of inverted the order. 27 00:01:45,498 --> 00:01:47,460 So, so we're going to go back to this now. 28 00:01:47,460 --> 00:01:50,410 So, just to review what, what you know from the first half of the class is 29 00:01:50,410 --> 00:01:53,979 computational Boolean algebra. A lot of really interesting 30 00:01:53,979 --> 00:01:57,650 representations, some verification's, some synthesis technology. 31 00:01:57,650 --> 00:02:02,360 This is the so called front end of the ASIC design process. 32 00:02:02,360 --> 00:02:05,990 The back end is the layout the geometry end, and there's a big missing step which 33 00:02:05,990 --> 00:02:09,455 is how do you actually go from the results of multilevel synthesis into real 34 00:02:09,455 --> 00:02:13,85 gates for the layout and perhaps it's a bit of a surprise that you don't actually 35 00:02:13,85 --> 00:02:16,440 get real gates as the result of multilevel synthesis and that's the topic 36 00:02:16,440 --> 00:02:22,220 of this lecture. This stuff goes by a lot of different 37 00:02:22,220 --> 00:02:25,433 names it's most formally called Technology Mapping, it's very frequently 38 00:02:25,433 --> 00:02:29,80 called tech mapping just because it's shorter to say. 39 00:02:29,80 --> 00:02:33,372 It's often just called mapping. depending on the application, sometimes 40 00:02:33,372 --> 00:02:36,764 it's called fitting, sometimes it's called binding, but most commonly, the 41 00:02:36,764 --> 00:02:40,140 stuff is called tech mapping or just mapping. 42 00:02:40,140 --> 00:02:42,648 A nice reference for this stuff is sort of a broad reference of of a variety of 43 00:02:42,648 --> 00:02:45,308 technologies for this stuff is the Nadia McKelly book, Synthesis and Optimization 44 00:02:45,308 --> 00:02:49,822 of Digital Circuits. This is chapter 10 in that book. 45 00:02:49,822 --> 00:02:53,950 So, let's talk about tech mapping, what is the problem? 46 00:02:53,950 --> 00:02:58,208 The problem is that the multi-level model is still a little bit abstract. 47 00:02:58,208 --> 00:03:01,664 So, you know, what happened in the multi-level synthesis technology that we 48 00:03:01,664 --> 00:03:04,394 talked about. We figured out the structure of the 49 00:03:04,394 --> 00:03:07,170 boolean logic network. And so in my, my little example here, 50 00:03:07,170 --> 00:03:11,480 which has input's a, b, c, d. Three nodes in the network, X equals b 51 00:03:11,480 --> 00:03:16,428 plus c, Y equals aX, Z equals Xd. We figured out the right high level 52 00:03:16,428 --> 00:03:19,357 structure of the network. You know, what the nodes are and how 53 00:03:19,357 --> 00:03:22,272 they're connected. And we also did ESPRESSO-style 2-level 54 00:03:22,272 --> 00:03:25,836 simplification on the inside of each of these nodes, the yellow nodes in there, 55 00:03:25,836 --> 00:03:30,270 or so, we optimized them well, but this is not really gates. 56 00:03:30,270 --> 00:03:32,745 And the, the thing to just be, be clear about is that. 57 00:03:32,745 --> 00:03:36,969 This diagram below, those are not logic gates, those are nodes in a graph that 58 00:03:36,969 --> 00:03:42,915 has a particular kind of a structure. The boolean logic network there could be 59 00:03:42,915 --> 00:03:46,611 thousands of those bubbles in a real version of this as the result of 60 00:03:46,611 --> 00:03:52,0 multi-level logic synthesis. What if everyone of those nodes has a 61 00:03:52,0 --> 00:03:56,480 half a dozen or 10 or 15 literals in its sum of products form? 62 00:03:56,480 --> 00:04:03,612 It's not real gates, and the question is how do you get it to be real gates? 63 00:04:03,612 --> 00:04:10,286 So, suppose that you actually have a particular technology library. 64 00:04:10,286 --> 00:04:13,996 And suppose that this is that technology library. 65 00:04:13,996 --> 00:04:16,930 Now, frequently, when we talk about the technology library. 66 00:04:16,930 --> 00:04:21,154 The library of discrete standard cells that we are allowed to use as our basic 67 00:04:21,154 --> 00:04:25,328 logic elements. It's very frequently just called the 68 00:04:25,328 --> 00:04:28,124 technology. So suppose this is the technology that I 69 00:04:28,124 --> 00:04:30,634 get to use. I get to use a 2 input and gate. 70 00:04:30,634 --> 00:04:34,110 AND2 input or gate and a slightly strange looking thing called an OA21. 71 00:04:34,110 --> 00:04:39,450 Its a two input OR gate feeding one of the inputs of an and gate. 72 00:04:39,450 --> 00:04:42,930 And the other one is just a standard input to the and gate. 73 00:04:42,930 --> 00:04:46,712 It's a little bit complicated. So this is the so called complex gate in 74 00:04:46,712 --> 00:04:50,202 our library. The big question that we need to figure 75 00:04:50,202 --> 00:04:54,411 out how to correctly answer, is if I give the output of multilevel optimization, in 76 00:04:54,411 --> 00:04:58,376 this case, my little bouillion logic network with the x-node, the y-node, and 77 00:04:58,376 --> 00:05:04,50 the z-node. How do we build the two Functions, in 78 00:05:04,50 --> 00:05:08,590 this case the y function and the z function. 79 00:05:08,590 --> 00:05:13,213 Functions of a, b, c, and d, specified in this[UNKNOWN] logic network using only 80 00:05:13,213 --> 00:05:19,236 these gates from our library. Now, just drawing this picture again here 81 00:05:19,236 --> 00:05:22,720 in my new slide. So this is a simple example. 82 00:05:22,720 --> 00:05:25,690 So I'm drawing the library as a two input and A2 input or. 83 00:05:25,690 --> 00:05:30,10 And this 0A21 To input or feeding one of the inputs of an and gate. 84 00:05:30,10 --> 00:05:34,158 I'm drawing it with big curly set brackets just to emphasize the fact that 85 00:05:34,158 --> 00:05:42,190 its an important object that we get to, work with and manipulate and play with. 86 00:05:42,190 --> 00:05:44,10 In order to effect our technology mapping. 87 00:05:44,10 --> 00:05:47,780 And I'm coloring this in in yellow, just to highlight it. 88 00:05:47,780 --> 00:05:51,875 What we need to do is look at our Boolean logic network and say, if I only get to 89 00:05:51,875 --> 00:05:55,970 use this and gate, this or gate and this strange OA21 thing, how do I actually 90 00:05:55,970 --> 00:06:02,460 Take the logic function specified in the bouillon logic network. 91 00:06:02,460 --> 00:06:05,244 And turn it into real logic gates. And look, this is just a really simple 92 00:06:05,244 --> 00:06:08,20 example. It's set up to be a simple example. 93 00:06:08,20 --> 00:06:11,100 One of the ways I could do this is I could do this example here. 94 00:06:11,100 --> 00:06:13,800 I'm calling this the obvious mapping because look, you look at the logic 95 00:06:13,800 --> 00:06:17,710 network, the x node is an or gate. The Y note is an end gate. 96 00:06:17,710 --> 00:06:21,73 The Z note is an end gate, maybe we should just make the X note an orgate 97 00:06:21,73 --> 00:06:25,590 with inputs B and C. And connect the output of the orgates to 98 00:06:25,590 --> 00:06:28,880 2 and end gates. And the top end gate has an input A. 99 00:06:28,880 --> 00:06:31,660 And the bottom end gate has an input D. And one of them makes Y and one of them 100 00:06:31,660 --> 00:06:33,940 makes Z. And that's really just pretty obvious. 101 00:06:33,940 --> 00:06:36,600 Now where this stuff gets interesting is that there are. 102 00:06:36,600 --> 00:06:40,816 Less than obvious mappings and I am calling this an un-obvious, may be a non 103 00:06:40,816 --> 00:06:46,383 obvious mapping and in this mapping I use two of these OA21 gates. 104 00:06:46,383 --> 00:06:52,83 So, to implement the Y function I actually do this as 1 OA21 with inputs a, 105 00:06:52,83 --> 00:06:56,192 b, and c. A goes under the AND gate, b and c go 106 00:06:56,192 --> 00:06:59,791 into the OR gate and for output z I go d into the AND gate and b and c go into 107 00:06:59,791 --> 00:07:05,186 the OR gate and you are thinking. Well this is a little bit strange, and 108 00:07:05,186 --> 00:07:09,212 I'm, I'm just putting a little kind of a question mark here on top of the two OR 109 00:07:09,212 --> 00:07:15,770 gates I'll even write two question marks. it would appear that I've duplicated the 110 00:07:15,770 --> 00:07:20,36 Or gate, why why would I do that? You know, why would I choose the 111 00:07:20,36 --> 00:07:23,840 un-obvious mapping? And let me give you an answer. 112 00:07:23,840 --> 00:07:26,48 Why would you choose the non-obvious mapping? 113 00:07:26,48 --> 00:07:30,150 the answer perhaps is cost. Perhaps it is the case that the 114 00:07:30,150 --> 00:07:34,758 un-obvious mapping is superior in some dimension that I can associate with a 115 00:07:34,758 --> 00:07:38,790 number. So imagine that every gate in my 116 00:07:38,790 --> 00:07:42,880 library[UNKNOWN] has a cost associated with it. 117 00:07:42,880 --> 00:07:45,718 May be it's the amount of silicon area in the, in the standard cell gate, may be it 118 00:07:45,718 --> 00:07:49,782 has something to do with the power. That means there are all kinds of ways of 119 00:07:49,782 --> 00:07:53,292 creating matrix for this but you know low cost is better and so I am just putting 120 00:07:53,292 --> 00:07:57,670 cost numbers. The AND2 has a cost of 2, the OR2 has a 121 00:07:57,670 --> 00:08:03,224 cost of 3 and the OA21 has a cost of 4. These are entirely arbitrary and now 122 00:08:03,224 --> 00:08:06,788 somebody has to figure out what the right costs are but now I have got a picture of 123 00:08:06,788 --> 00:08:11,658 the obvious mapping on the left at the bottom, one or two ends. 124 00:08:11,658 --> 00:08:15,623 And then I've got a picture of the un-obvious mapping 2OA21's at the right 125 00:08:15,623 --> 00:08:19,718 and what we can see immediately is if I put the cost values on the cost mapping 126 00:08:19,718 --> 00:08:24,725 the or costs three. Each of the ands cost three. 127 00:08:24,725 --> 00:08:28,873 This entire mapping cost three plus three plus three that's nine, but what if I put 128 00:08:28,873 --> 00:08:32,480 the cost values on the un-obvious mapping? 129 00:08:32,480 --> 00:08:36,380 Well each of these OA21 gates costs four, and so, putting two of those together 130 00:08:36,380 --> 00:08:40,340 costs eight, eight is better than nine, this is a better mapping now (no period) 131 00:08:40,340 --> 00:08:46,250 This is a quite synthetic examThis is a quite simplified example. 132 00:08:46,250 --> 00:08:50,10 But in the real world, where you have large[UNKNOWN] logic networks. 133 00:08:50,10 --> 00:08:52,410 And you have things that have, you know, hundreds or thousands or tens of 134 00:08:52,410 --> 00:08:55,620 thousands of gates in them. What the right answer is is not at all 135 00:08:55,620 --> 00:08:57,804 obvious. You need some kind of metric to guide you 136 00:08:57,804 --> 00:09:00,710 for what the. What the best answer is associate cost 137 00:09:00,710 --> 00:09:04,799 with all of the gates. Map so that you choose the lowest cost 138 00:09:04,799 --> 00:09:07,942 covering. The lowest cost mapping of the Boolean 139 00:09:07,942 --> 00:09:11,414 logic network on to the library that's going to get you an answer that makes 140 00:09:11,414 --> 00:09:14,934 sense. So, the other way of saying why you 141 00:09:14,934 --> 00:09:19,557 choose a non-obvious mapping, the sort of the second answer is that you know the 142 00:09:19,557 --> 00:09:24,50 non-obvious mapping has better complexity. 143 00:09:24,50 --> 00:09:27,220 And really this is just sort of cost in a, in a different way. 144 00:09:27,220 --> 00:09:30,570 So for example, your library might have a bunch of complicated gates, so-called 145 00:09:30,570 --> 00:09:33,537 complex gates. The are really hard to map to by eye, it 146 00:09:33,537 --> 00:09:36,637 is pretty easy to figure out where you can put in 2, put AND gate or to input OR 147 00:09:36,637 --> 00:09:41,520 gate or input invert but I am showing you to realistic gate cells. 148 00:09:41,520 --> 00:09:45,678 On the left I am showing you OR, AND and Invert structure, this is a so-called 149 00:09:45,678 --> 00:09:49,613 OAI22. So, it's a layer of OR gates connected to 150 00:09:49,613 --> 00:09:54,263 an AND gate with an inverter at the output that's why it's called OAI and the 151 00:09:54,263 --> 00:10:00,19 an answer to the question. How many and gates, sorry, how many or 152 00:10:00,19 --> 00:10:02,640 gates are there and what are their structure? 153 00:10:02,640 --> 00:10:06,860 The reason it's called a two two, is that there are two such gates. 154 00:10:06,860 --> 00:10:10,370 That's why there's two digits there. And each of those gates has two inputs. 155 00:10:10,370 --> 00:10:13,170 So you see a two input or gate. And another two input or gate. 156 00:10:13,170 --> 00:10:17,840 So, that's why this is a two two, and let's say that that costs 6. 157 00:10:17,840 --> 00:10:21,536 And next to that, on the right, is an and or invert structure, a different one and 158 00:10:21,536 --> 00:10:25,301 AOI221. Again, an input bank of and gates, then 159 00:10:25,301 --> 00:10:30,358 an or gate, and then a invert, a bubble. In this case, how many or gates are 160 00:10:30,358 --> 00:10:32,575 there? Well, there's kind of three. 161 00:10:32,575 --> 00:10:36,662 Alright the first 1 has 2 inputs the second 1 has 2 inputs and the third 1 has 162 00:10:36,662 --> 00:10:40,816 1 input and, and you know, kind of the obvious way to think about why I'm just 163 00:10:40,816 --> 00:10:44,970 drawing a wire going into this Or structure this Or Invert structure is 164 00:10:44,970 --> 00:10:49,124 that this is really sort of an AND gate with exactly 1 input going into it and 165 00:10:49,124 --> 00:10:58,130 what's an AND gate with 1 input going into it it's a wire. 166 00:10:58,130 --> 00:11:02,874 So this is an AOI-221. Imagine that the AOI-22 cost 6 and the 167 00:11:02,874 --> 00:11:06,574 AOI-221 cost 7. An interesting thing to note, it seem the 168 00:11:06,574 --> 00:11:11,260 OAI and the AOI gate structures are often very efficient at the transistor level. 169 00:11:11,260 --> 00:11:14,268 A bit more efficient than actually discretely using some ends and[UNKNOWN] 170 00:11:14,268 --> 00:11:17,124 and inverts. And you know, for small versions of these 171 00:11:17,124 --> 00:11:20,72 complex gates. These things are actually a sometimes a 172 00:11:20,72 --> 00:11:24,170 better cost match and its much, much more difficult to match where these things go. 173 00:11:24,170 --> 00:11:30,890 To technology map where these things go which is why we need an algorithim so, 174 00:11:30,890 --> 00:11:33,992 It's helpful to introduce what I'm just referring to as a mental model, a kind of 175 00:11:33,992 --> 00:11:37,890 a conceptual way of thinking about what multilevel synthesis does. 176 00:11:37,890 --> 00:11:41,950 This is what multilevel synthesis does. It structures the multiple vertex Boolean 177 00:11:41,950 --> 00:11:45,300 logic network well. What does well mean? 178 00:11:45,300 --> 00:11:49,200 It means that the number of bubbles the structure of the bubbles, the number of 179 00:11:49,200 --> 00:11:54,340 layers of, of you know, bubbles between the input and the output. 180 00:11:54,340 --> 00:11:59,110 The complexity of the logic inside each of the bubbles, you know, pretty good. 181 00:11:59,110 --> 00:12:02,582 And so, you know, following up on that as it minimizes or as it optimizes the 182 00:12:02,582 --> 00:12:06,110 macroscopic structure of the logic network it minimizes the sum of product 183 00:12:06,110 --> 00:12:09,806 contents inside each vertex so that the two level form that each vertex wants to 184 00:12:09,806 --> 00:12:13,278 implement is also well structured in terms of the number of literals in the 185 00:12:13,278 --> 00:12:20,110 sort of the macroscopic. Graph structure is also good. 186 00:12:20,110 --> 00:12:24,326 The big, important thing to note is that optimizing the macroscopic graph 187 00:12:24,326 --> 00:12:28,678 structure of the logic network, and optimizing the sum of products contents 188 00:12:28,678 --> 00:12:33,370 of all of those bubbles is not logic gates. 189 00:12:33,370 --> 00:12:38,67 And in particular, it's not logic gates in the technology library you are 190 00:12:38,67 --> 00:12:42,840 permitted To use, alright? So this result actually has an 191 00:12:42,840 --> 00:12:46,518 interesting name, a new name. actually a couple of names that you may 192 00:12:46,518 --> 00:12:50,890 or may not have heard of. This is often called uncommitted logic. 193 00:12:50,890 --> 00:12:54,607 Which is to say, I have not committed this to a particular set of gates from my 194 00:12:54,607 --> 00:13:00,63 technology library. It is also called technology independent, 195 00:13:00,63 --> 00:13:05,230 because we often call the library that we get to use, the technology. 196 00:13:05,230 --> 00:13:09,818 And when the stuff that pops out of multi-level synthesis is not mapped yet 197 00:13:09,818 --> 00:13:14,215 to the technology. We say that it's technology independent. 198 00:13:14,215 --> 00:13:17,873 And so I've just got a little picture down here, there's an X node, a W node, a 199 00:13:17,873 --> 00:13:21,870 V node, the X and the W nodes go into the Y node. 200 00:13:21,870 --> 00:13:25,896 The Y node is an output, the W and the V node go into the Z node, The Z node Is an 201 00:13:25,896 --> 00:13:29,492 output. Just to sort of highlight this, what 202 00:13:29,492 --> 00:13:33,320 multilevel synthesis does is it gives a good global structure to the nodes, the 203 00:13:33,320 --> 00:13:37,400 X, the Y, the Z, the W and the V in this diagram. 204 00:13:37,400 --> 00:13:41,369 And it gives a good local structure to the insides, the sum of products forms 205 00:13:41,369 --> 00:13:45,150 the sum of products inside the nodes like Z. 206 00:13:45,150 --> 00:13:51,817 But this is not logic gates. So what does technology mapping do? 207 00:13:51,817 --> 00:13:55,840 Technology mapping does something sort of interesting in an interesting way. 208 00:13:55,840 --> 00:14:01,88 The first thing we do typically, is we transform this into uncommitted logic 209 00:14:01,88 --> 00:14:07,730 that is made up of only very simple gates, but real gates, alright. 210 00:14:07,730 --> 00:14:11,964 So a very common way of doing this is to transform every sum of products 211 00:14:11,964 --> 00:14:16,563 expression inside each node, into something very simple, like NAND and NOT 212 00:14:16,563 --> 00:14:21,708 gates, and nothing else. So, I've got a little picture of my 213 00:14:21,708 --> 00:14:25,240 network from the previous page, you know, X, Y, Z, W and V nodes. 214 00:14:25,240 --> 00:14:27,660 And I've got the X node and the Y node highlighted. 215 00:14:27,660 --> 00:14:30,550 We know that those are sum of products 2-level forms. 216 00:14:30,550 --> 00:14:34,245 What do we do? We turn the X node into. 217 00:14:34,245 --> 00:14:39,544 NOT gates, inverters, and NAND gates. Now, one of the things to remember from 218 00:14:39,544 --> 00:14:43,249 way back when in Boolean algebra, is that if you have a sum of products form, you 219 00:14:43,249 --> 00:14:47,11 know, with AND gates for each product term in a big OR gate connecting it, you 220 00:14:47,11 --> 00:14:50,602 can replace every AND gate and the OR gate itself with a NAND gate, and it will 221 00:14:50,602 --> 00:14:57,138 all work properly. It's sort of an interesting side effect 222 00:14:57,138 --> 00:15:00,330 of the De Morgan laws for how compliments work. 223 00:15:00,330 --> 00:15:03,244 And so we're going to take all of the AND gates in the products and replace them 224 00:15:03,244 --> 00:15:06,205 with NAND gates, and we're going to take the output OR and replace it with a NAND 225 00:15:06,205 --> 00:15:09,622 gate. And then we'll just put inverters 226 00:15:09,622 --> 00:15:13,516 wherever we need the literals to be in the complimented form, and we're going to 227 00:15:13,516 --> 00:15:18,120 build, X the node, as real gates, but real simple gates. 228 00:15:18,120 --> 00:15:21,410 So we're going to build it all out of NOTs and NANDs. 229 00:15:21,410 --> 00:15:24,802 And then similarly we're going to take the Y node and then we're going to build 230 00:15:24,802 --> 00:15:28,574 that, out of NANDs and NOTs. And so, it's got, probably a different 231 00:15:28,574 --> 00:15:31,840 number of products, so it's got a different number of the input NANDs. 232 00:15:31,840 --> 00:15:34,768 It's got, maybe a different. You know number of products and so the 233 00:15:34,768 --> 00:15:38,872 size of the output end is different. Its got complements on different places 234 00:15:38,872 --> 00:15:42,670 on the literals and so then the inverter gates are in different places. 235 00:15:42,670 --> 00:15:47,10 But again, I can build the contents of the individual node, which is a sum of 236 00:15:47,10 --> 00:15:53,620 products form, simple two-level form, as nothing but inverters and NAND gates. 237 00:15:53,620 --> 00:15:56,570 We're going to do that for every single node in this network and then we're 238 00:15:56,570 --> 00:16:00,890 going to connect things so, the X node connects as an input to the Y node. 239 00:16:00,890 --> 00:16:03,905 And I'm just making kind of an arbitrary assumption that it connects to one input 240 00:16:03,905 --> 00:16:06,785 on one gate, it could connect to a whole (no period) Bunch of different places 241 00:16:06,785 --> 00:16:11,50 going in to the y node. But the big important idea is that we 242 00:16:11,50 --> 00:16:14,295 need to take a step away from the abstract form of the Boolean logic 243 00:16:14,295 --> 00:16:19,540 network to something that's real. Gates and our first step is an 244 00:16:19,540 --> 00:16:23,553 interesting simple step. We go from the sum of products forms to 245 00:16:23,553 --> 00:16:28,760 nans and nots and we do that for every node in the Boolean logic network. 246 00:16:28,760 --> 00:16:33,750 And so what we're going to get as a consequence of that is this. 247 00:16:33,750 --> 00:16:38,634 Sort of complicated looking diagram here. Where the X node, the W node, the Y node, 248 00:16:38,634 --> 00:16:43,482 the Z node, the V node. Each one of those things is replaced by 249 00:16:43,482 --> 00:16:47,570 some combination of NAND gates for the product terms. 250 00:16:47,570 --> 00:16:51,2 NOT gates for the literals that appear in complimented form in a big NAND gate at 251 00:16:51,2 --> 00:16:54,150 the output to implement the two level form. 252 00:16:54,150 --> 00:16:58,542 A two level not NAND form for every sum of products form, and then the sum of 253 00:16:58,542 --> 00:17:03,350 products forms themselves are connected properly. 254 00:17:03,350 --> 00:17:07,158 So, what I get here is one big, flat and I'm referring to that in a very 255 00:17:07,158 --> 00:17:12,10 particular way, okay? One big flat network of NANDs and NOTs. 256 00:17:12,10 --> 00:17:17,113 This is what you map, what flat means in this context is that the boundaries, 257 00:17:17,113 --> 00:17:22,840 between the X node, the Y node, the W node, the Z node. 258 00:17:22,840 --> 00:17:26,59 All of those things go away. So one of the really important things to 259 00:17:26,59 --> 00:17:29,27 note is that it's not as though I'm restricted to take the gates in my 260 00:17:29,27 --> 00:17:33,180 technology library. And map them against them against the 261 00:17:33,180 --> 00:17:36,502 insides of every yellow bubble on this diagram. 262 00:17:36,502 --> 00:17:42,634 No, I take the logic function specified by every node in the diagram. 263 00:17:42,634 --> 00:17:48,120 I flatten it out into 2 level NAND, NAND not structure. 264 00:17:48,120 --> 00:17:53,10 I connect up everything appropriately and I throw the bouillon logic network away. 265 00:17:53,10 --> 00:17:58,35 This big messy looking logic network with all of these NAND gates and inverters, 266 00:17:58,35 --> 00:18:02,678 this is what we map, this is what happens next. 267 00:18:02,678 --> 00:18:07,718 So, this is our strange and complicated looking starting point multilevel 268 00:18:07,718 --> 00:18:13,78 synthesis produces well the first thing it produced was a bullion logic network 269 00:18:13,78 --> 00:18:18,438 model with well structured microscopic form and well structured sum of product 270 00:18:18,438 --> 00:18:28,430 form and what we did was we in a sort of a dumb brute force simple minded way. 271 00:18:28,430 --> 00:18:34,450 We push that immediately into real gates, but very simple gates, NANDs and NOTs. 272 00:18:34,450 --> 00:18:37,510 This big network, that I'm again highlighting on the, on the pager here, 273 00:18:37,510 --> 00:18:41,250 this is what we start with, this is what we're going to map. 274 00:18:41,250 --> 00:18:45,252 And the big and interesting question for us is algorithmically, how do I transform 275 00:18:45,252 --> 00:18:48,732 this big network of NAND gates and inverters, how do I map this thing onto 276 00:18:48,732 --> 00:18:53,654 the standard cells in our library in some optimal way? 277 00:18:53,654 --> 00:18:57,497 So, this is a pretty algorithm as it turns out, a very nice application of the 278 00:18:57,497 --> 00:19:01,706 ideas from the computer science universe to a really interesting hard problem, in 279 00:19:01,706 --> 00:19:07,475 the[INAUDIBLE] universe, so let's go see how that works next. 280 00:19:07,475 --> 00:19:13,316 [SOUND]