[SOUND]. So here we are in lecture nine and as you know the title of the course is VLSI Cad Logic to Layout. So we had to get to layout eventually and here we are. So we've done lots of work in the boolean algebra logic hardware universe. We've done representation, we've done optimization, we've done synthesis. We sort of know how to make the gates. Right, what we have to do next is we have to figure out geometrically where they go and how we connect them. And so, we're going to move into the part of the course where we get to talk about layout. And we're going to start by talking about ASIC placement And so this is the question of, now that I have a million gates, where do they go on the surface of the chip? And so, what we're going to start with is a sort of an overview of just what's the terminology? What does the technology landscape look like? What do we have as the basic placeable elements? What's the technology components of this problem. And then we can start actually talking about some interesting new geometric algorithms. So, let's go look at the basics to get us started with ASIC placement. So, this is a little bit of review here. What do you know? I think you know a lot about computational boolean algebra at this point, I think you know a lot about representation You know a little bit of verification. You know a lot of things about synthesis and optimization for two-level and multilevel logic. This has a name. This is called the front end of the ASIC design process. So if you, you want to think of this at a very high level. Give a high level description. You know, something that comes in, in say VHDL or Verilog. There's some compiler like things that happen that, that turn that into a form that, to which we can actually apply, all of the synthesis and verification technologies that you now know. And what comes out of that is a connected set of gates and wires in the Technology associated with your chip, that has a name that's called a netlist, we'll, we'll revisit that in a minute. What you don't know is the next part of the ASIC design process, which is called the back end problem. Turning these IC's into masks to build real chips this is called layout. it's also called physical design, which is a named that is kind of a hold over from a very early[INAUDIBLE] . Days of the the electronic business when people were putting little you know, little packages on big boards in order to build any kind of electronic system. We're going to start with something called the placement problem, which is how do you locate those gates on the surface of a Of a piece of silicon. But, but to do that, I need to back up just a little bit. So, in honest fact, there's 1 missing key step. So, what comes out of multi level synthesis is not actually gates. it's a Boolean network model. It's a, it's a graph of nodes. Each of which is a, a 2 level sum of products form. as I'm showing here I'm actually picking one of the pictures from one of the assignments for this class and and just showing it here. What comes out of multi-level synthesis is actually not logic gates. We have to do something to turn it into logic gates. And there's a key step. And that step is called Technology Mapping. That transforms the abstract form of the above network. The result of multi-level logic synthesis into real logic gates and wires. I'm going to cover this next week and not this week because. We're actually going to do a programming assignment in this mook, that's a placer. And I need to just get you the, the methods and models and mathematics and algorithms of placement in order to let you do that. So we're doing this a little bit out of order, and I just want to explain why we're doing that. So, placement for ASICs. We're going to focus on the most common tasks in, in layout, and what we're going to focus on are layout tasks associated with row based standard cells. So, synthesis and mapping is going to give us a net list of gates and wires. Our job is to place them optimally in rows on regions of the chip and to route the wires that connect everything. So this is a chip I showed way back when at the very early, lecture. introduction to the class. And I'm just highlighting. Two two regions on this chip that are actually rows of standard cell logic. that's the job that we're going to do when we start looking at the layout problem. Now, what do you start with? You start with something called a standard cell library. And this is a slightly confusing name. So, just to very clear about this. This is a library. And the things that are in this library are themselves called standard cells. And a standard cell is a basic logic gate or a small logic element, that you get to use to create the substance of your design. So, the way to think of this is, this is the set of allowed logic elements you get to use to build your chip, so you get, for example, you know, inverters, and you get NAND gates with, let's say, you know, a couple of different numbers of inputs, and you get NOR gates, and you get some little tiny Useful things that are, are used all over the place like one bit ADDERs and two to one multiplexers, and so on. And you also get sequential elements things like d flip flops and registers. Why do we restrict ourselves to operating with these, if you will, predefined elements? And the answer is that there's lots of complicated electricity stuff going on at the transistor level. Each of these cells in our standard cell library hides all of this difficult electrical detail and presents a simple geometric abstraction that we can use for our geometry design algorithms to work with. So, an interesting question, how big is a standard cell library? how many cells are there in a cell library? And the interesting answer is they're often pretty big. you have to have all of the logic functions that you need. You have to have all of the input and output variants, in terms of how many pins. There are often several timing variants things that are fast but have higher power or slow and have lower power. Different sorts of electrical drive strengths, and so on. At a very high level the way to think about this is that there's a lot of different logic functions. So, you know, and and nand, or and nor, xor and xnor. Things like that. And a bunch of different kinds of flip flops. There's a lot of fan in and fan out variants, so you probably want NAND gates that have two inputs and three inputs and four inputs for example. Ditto for all the other kinds of basic logic gates. There's a lot of different timing variations. There's a lot of different kinds of flip flops. there are a lot of, if you understand anything about how Testability is done on a modern chip with scan chains. There are a lot of different scan variations on flip flops. And if you don't know what that means, don't worry about it. I'm just sort of mentioning it as to one of the things that adds variation to a cell library. And there's a lot of different electrical variants, let's say drive strength kinds of variants. You multiply all those things together, it's easy to have a library with 1,000 or more. Standard cells. How should we think about what's inside a standard cell? think of a standard cell as a, as a, as a geometric container for the circuits, the electrical circuits, the transistor-level circuits that you need to make the logic functions. So inside the cell, there's complex devices, you know, transistors and wires and things, complex geometric mask things happening right down at the, sort of the nanoscale surface of the, of the integrated circuit. Complicated electrical issues, but outside the standard cell, it's a box with pins. And that sounds you know, a little simple minded, but really in order for the geometry things that we need to be able to do to optimize at the level of millions and millions of standard cells and wires, we need a simple abstraction. And the abstraction that it's a box with pins is going to work for us. let's look at a few real standard cells. This is in an older technology. This is 130 nanometers CMOS. You know, where we are today you know, lots of things are at the 32 nanometer node. There are some things, you know, popping out at the 22 nanometer node now things at sort of 15 nanometer node are in, are in, are in research. So this is an, an older technology. these are some pictures of some things from a website, www.vlsitetechnology.org, that has a bunch of open-source cells, so if you want to actually look at Transistor level designs. And, and, you know? Geometry designs. It's just an interesting place to go. 2 things that I want you to take away from this. The first is, here's a first fact. They all have the same height. And the reason is that we want to be able to arrange them in rows. And when we arrange them in rows, we can snap them together, if you will. We can. Put the power grids down so that the, the vdd and the vss power connect, we can make all of this stuff work. The second geometric fact to be aware of is they have very different widths as I'm, I'm showing you here. So, the cell on the left hand side is a NAND2, that's a, that's just a two input NAND gate, and the cell on the right is and Edge-triggered, D Flip Flop, so it's, it's going to have, a D input, it's going to have a queue and a queue bar going out, it's going to have a clock. Right, going in the D Flip Flop is much, much bigger than the NAND. And the reason it's got a lot more transistors in it to be able to do what it does. So standard cells, they all have the same height. We snap them together in rows. And they have different widths because they have different circuit complexity. In a realistic context, what we are talking about is placing the insides of one block on a, on a big system on chip kind of design. So here's an actually a real SOC design courtesy of my My friend and colleague Larry Pileggi at Carnegie Mellon University, Big, system on chip designs, big SOCs are often designed hierarchically, which means you figure out how, what each of the blocks is supposed to be, and then you may have, you know, hundreds of blocks that get put together in an appropriate way. To make a big SOC, and what's being shown in this particular picture of an SOC that's in the middle of being designed is there's a lot of pins around the edges and those are all the little slice things with the little colors. And then there's a bunch of blocks inside the SOC and some of them have a colored boarder, but they're gray. Those things are actually big memories, and you don't get to play with their insides. They get generated by some other kinds of CAD tools. But the things that have blobs of primary color, those are actually blocks that are being placed. And the reason that there are sort of funny shapes of the colors is that we are actually tagging and color coding where the blocks came from in the original source. let's say the verilog or the VHDL, and we're seeing sort of where did the gates actually go when we're doing the layout task. For our purposes, you can pick one of those rectangles and say, how am I going to place the however many hundred thousand or you know, half a million or a million gates Associated with the insides of one of those blocks. How am I going to arrange them in rows in some optimal fashion? How am I going to place them in rows, and how am I going to route them? That's actually what we're going to look at. So, let's just talk for a little bit about the size distribution on standard cells. The big thing to note is that small cells dominate but there's lots of wide cells, too. So this is an old example, but a published example. It's about 206,000 gates from an IBM ASIC. It's actually part of an IBM processor, way back when, in the late 1990's. It's done by Jens Vygen Of the University of Bonne. And this would be, sort of, 1 small block today on a, on a big SOC. You know, a big SOC may be, you know, 20 million gates, 50 million gates, 100 million gates, a really, really big one. And what I'm showing on this graph is that on the horizontal axis, we are showing, basically, the width of the cells. Right, and you can think of the width as being how many pins wide is the cell, as I showed on the previous example. And on the vertical axis we're showing the number of cells, and so there's about 200,000 cells, 200,000 gates in this design. And what you're seeing is something is one cell wide, that's just some sort of a filler, but you know, you know how many cells are two pins wide, oh something like, you know, 27,000, three pins wide, maybe 27,000 Four, five, six pins wide, a few more than 20,000, seven pins wide, only 10,000, eight pins wide, again 25,000, that's a nice round number, nine, ten, 11, 12, 13, 14 pins wide, you know, just a couple thousand, but then an interesting bump out around 17 and 18 pins wide, you know, more than 10,000 cells, and then you know, down in the noise. The way you can sort of think of this is that most of the small gates dominate, you know, the things with the two, three, four inputs, that's mostly what the net list is made out of. and just as a concrete example you know, what is this bar over here with 27 or 28,000 things that are two pins wide? and the answer is that you know, that's an inverter, right, because as a standard cell that's got one pin for the input and one pin for the output. And what's this peak out here with things that are 17 or 18 standard cell widths wide. Probably, that's a mix of things, like little registers with, maybe, 4 bits, maybe 8 bits depending on how it was how it was implemented. But that's also probably things like flip flops, you know, with a D input and a Q output in a clock. So, mostly small cells dominate. Very small cells, things like two input NANDs, two input NORs, one input, one output inverters, but there's also a lot of things like flip flops in a modern design. there's an interesting, sort of an aside that I just wanted to share with everybody. it's, it's sort of the way people use language to talk about chip size. So this is a strange question. How bit is a 100 million gate ASIC? And surprisingly, it is almost not 100 million gates. the numbers are usually referred to in one of two ways, and the most common is, let's say, equivalent small gates. So the idea is that because there are lots of things on the surface of the chip, little gates, big gates, Adders, flip flops, all kinds of other stuff,we sort of transform them into an equivalent number of let's say 2 input NAND gates. So if we, as I'm showing you in the middle of this picture so here's a two input NAND gate, so how big is that? Well that's like one input. And here's something called a AOI22, so its 22 input and, a two input OR and an inverter, that's an atomic gate in a lot of cmoss libraries. That's maybe four gates in size. And then I've got a picture of a one gate adder, how big is that? maybe six gates. And then I got a picture of a D flip flop, how big is that? maybe ten gates, maybe more. the idea is you take all of your real logic elements, the ones you get to use in your technology library. And you sort of replace them with an equivalent number of gates. And when someone says, how big is your design, you add up those numbers of 2-input NANDs and you use that. So, there's two things that people might tell you when they tell you how many millions of gates in their ASIC. One of them is gates. This is usually an equivalent little NAND gates, so this is usually a big number. The other is a term you might not have heard before called instances. This is the number of things you really used in your library. This is the number of things you really placed, you know, the number of things you actually had to find space for and put wires to connect to on the surface of your chip. And the basic rule today is that the instances is basically the gates divided by 4 or 5. So, you know big round numbers, if someone tells you they have a hundred million gate ASIC, how many instances are there? Probably 20 million. Five is probably the best number to use today, and honestly, they might not even all be gates. people might be taking their very large static RAM, SRAM memories and other blocks and converting those into, an approximate equivalent number of gates in terms of their silicon area, so If someone tells you they have a 100 million gate ASIC, they probably don't actually have 100 million logic gates. They probably have a maximum of 20 million, might be less. So, what's our first problem as we actually talk about layout in in our MOOC? Our first problem is placement, and I've got a nice little diagram here. Up at the top, there's a picture of a netlist. The netlist goes through a box that says placement. And that turns into a bunch of rows of little gates and standard cells. That goes into a box that's called routing. And suddenly, little wires appear that connect all the gates. What does a placer do? A placer starts with a netlist of gates and wires and the output is the exact location of each gate. You know, where does it go? And the goal of the placer is to be. Creating a placement that allows us to route, which is to say to connect all of the wires. That is the most fundamental plask...uh, the most fundamental task of the placer. Is this hard? Oh yes, very, very, hard. A bad placement could lead to an enormous amount of extra wire, and if you have more wire, your chip may need to be bigger in order to be able to fit those wires. And it's going to be slower because there's delay to get your signal through those wires, and there's going to be more power because taking voltages up and down on all those wires is actually you know, consuming energy. It's very bad. And if the placement is extremely bad, the next tool in the flow, which is called the router, might actually be unable to connect all the wires or to meet the timing requirements of your chip. So, placement is an extremely important task. Very critical task. Very critical for us to get right and so, it's the first task we're going to focus on. So, let's go talk about how we really do placement. [MUSIC]