Welcome to VLSI CAD part two layout. My name is Rob Rutenbar, I'm a Professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. And this is the second course in a two course sequence on very large scale integrated circuit computer rated design VSLI CAD. I'm assuming that you've been successfully through the first half of our course sequence which was the logic part. This course was originally a single longer MOOC course offered on the Coursera platform called VSLI CAD logic to layout. We've now separated it into two, more easily accessible parts. And congratulations, you've made it through the first part and we're going to start the second part. So a modern integrated circuit is an incredibly complicated beast. A billion or so transistors, hundreds of millions of logic gates. Billions possibly trillions of geometric shapes they comprise the electrical reality of building and implementing these things. The only way that anybody can actually manage these kinds of things is through a sequence of complex and sophisticated software tools CAD tools. To take these designs step by step from something very abstract to something very concrete. And so as we sit here, at the end of part one logic, where are we? We have a bunch of big blocks of logic gates that have popped out of our logic synthesis methods. And presumably we've actually used some of our verification techniques and we're pretty confident that they actually do the right thing. But at this point they are still very abstract, they are literally like little graphs of little blobs of logic and little wires, they're not physical yet. And part of the design of the geometry of an integrated circuit, the layout of an integrated circuit. It's actually called the physical design, because we're actually going to start dealing with questions like. What actual gates in our library of physically implementable transistor based gates do we get to use? Where do we put them on the surface of the chip? How do we connect all the wires? And when we're done with this, how fast does this thing going to go? How many gigahertz is this thing going to do? So we're going to make the pivot from talking mostly about Boolean things and Boolean algebra and computational Boolean algebra to things that are physical. Things in a physical library of implementable logic elements, questions about where we locate things. Questions about where we locate connections for things, and questions over more quantitative nature like, how fast is it going to go? So there are four great foundational topics in the layout side of this course. The first is called technology mapping. It's the process by which you go from the somewhat abstract gates that come out of multi-level logic synthesis to real things that you can actually build on your integrated circuit. The next topic is placement. Where do the gates go? The next topic is routing. How do you connect a billion wires on the surfaces of the chips so that everything works? And the fourth topic is timing analysis, how fast is this thing going to go? And this is actually going to involve both how fast are the gates going? And at a somewhat relatively light level, a little bit of electricity, which is how fast are the wires slowing things down? So welcome to the second part of our two part course, feels like CAD, part two layout, let's get started. What are we about in this sequence of classes? Just as in part one, we are interested in the design of the tools themselves. Their fundamental algorithms, their fundamental mathematics, their fundamental data structures, that make it possible to build something complicated. Like the big picture of the integrated circuit shown at the right of this diagram. And just another reminder, the original version of the VLSI CAD sequence was single, 10 week long MOOC offered starting in 2013 on the Coursera platform. And it emphasized the CAD flow from logic topics, the Boolean topics of part one of our course sequence to layout topics. The geometry topics that form the second part of our layout sequence. And we have taken all of the material in the original class, VLSI CAD, Logic to Layout, and divided it into these two new courses. So you are now in the second part of our course, VLSI CAD 2 focusing on layout topics. This is the second half of our original course, starting with the logic that comes out of multi-level logic synthesis. The last topic in VLSI CAD 1, and proceeding forward in both layout synthesis and verification topics in this course. So at the end, we're going to have everything we need to get to the geometric layout of a real integrated circuit. So again just a reminder, this is still why the introductory slides of the lecture say, logic to layout. Because all of the materials in this two course sequence were derived form the initial one, ten week long mook. And this is again why the lectures are numbered continuously. So in part 1 of our series, you saw lectures 1 through 8. And now in part 2, you're going to see lectures 9, 10, 11, 12 after this introductory lecture that's still numbered lecture 1 just for convenience. The video lectures are going to look exactly like the video topics in the first MOOC on Logic. There's a title that talks about the content and locates you in the overall sequence of lectures. There's a talking head introduction in which I am going to appear briefly and explain what was the topic of the previous video lecture. And how does it lead us naturally to the topics of the current video lecture. And then that's followed by some deep technical content with appropriate diagrams and mathematics and there's live writing on many of the slides. So there's a dynamic component to the lectures which I think helps give you a sense of what's going on by watching me actually drive some components of the technical content. The logistics are just like the first course in the sequence 5 weeks of lectures. 5 weeks of material, which is 4 weeks of lecture, and then 1 free week and a final exam. There are videos every week totaling 2 to 3 hours of content divided into approximately 15 minute segments. There are 4 problem sets, the homework assignments, because they're 4 weeks of video material, and so there are 4 assignments. And in the last week of the material, we've leave a week open at the end for you to finish all of your work. In particular, to finish the homework assignment and any programming assignments that you're doing. There are two programming assignments that are completely optional, need to emphasize that. So these are if you will, the honors assignment honors track, you don't have to do them. They involve conventional software coding and also working with some scripts that run on CAD-centric tools that run on our servers. So grading is mastery based, this means you are allowed multiple submissions on the assignments, multiple attempts at each assignment. And they're each randomly changed, so you get a slightly different assignment each time you try. You need to pass all of the assignments individually to pass the course. The problem sets because there are four weeks of lectures. And there is a problem set for each week, there is about 4 weeks of problems, they should take about a week. And then there's an extra week at the end of the class to get ready to finish the problems. And for a final exam, the final exam looks just like a problem set. But it's comprehensive over the course, so it has material from all 4 weeks not just from 1 week. And please go look at the class website if you want to know more details about the logistics. The programming assignments about building software are optional. They are honors assignments, you can do them if you'd like a deeper engagement with the technical material or maybe more practically if you are interested in a job in this industry. People who are employed doing this kind of technical work are generally writing software to implement these algorithms and data structures. To build the software that goes to let chip designers actually designs chips. And I'm happy to say that in earlier renditions of this MOOC, people who have taken this course online on the Coursera platform have actually successfully gotten jobs in this industry. Mechanically the way the programming assignments are going to work is that we're going to provide you realistic inputs for the problems that we'd like you to solve. And that's just going to be in the form of file, and it's going to be human readable. You're actually going to be able to read it, it's ASCII text. Your software is going to take as input an ASCII text file that describes the problem. And it's going to write as output in ASCII text file, and then you upload your output to the Coursera web site. We automatically grate it, and we'll give you some feedback about how well you're doing. And again, you can do multiple submissions. The nice feature of this style for the assignments is, that your code runs on your own computer, we don't care what the machine is. You can do it anywhere, you can use any programming language you like. If you like C, or you like Java, or you like Python, or something a little more exotic. And you can run it on any platform, you just have to be able to generate a file. And if you can generate a file and upload it to the platform, we can grade your work and you can actually see how well you're doing. Other important stuff, just as with the first part of the course, there's an honor code. It's okay to talk with other people, but please, submit your own work. And please, don't be posting solutions to any of the materials you see here on the Coursera site or on the web. It just makes it harder for other people, and please use the Coursera interaction mechanisms. There are forums and such to ask questions. And we'll make use of these to help you connect to the other people who are working on the same problems and having the same interesting questions as you. What background do you need? For this MOOC, well again you need to know some basic computer science, basic programming skills, and data structures. Even if you don't choose to do the software assignments that are optional. We are still going to be describing the methods that are underlying these CAD tools as algorithms. And in particular, we're going to be writing a lot of pseudocode. So you need to be comfortable with methods described in the form of algorithms. And lots of the things that we're doing are going to come in the form of data structures. Still important to know basic computer engineering, gates and flip flops, sorts of things. Although in this case, pretty much the gates are already given. We're going to be primarily worrying about where they go, geometrically on the surface of the chip. On the Math side, you still need to know sets and functions and careful notations. A little bit of graph theory is helpful, but I'll be explaining it in this MOOC, just like I did on the first part. And for this one, we're actually going to be seeing a little bit more of the continuous side of the world. So basic calculus, the ability to write an equation, the ability to take a derivative. The ability to understand what an integral means, matrices. These things actually show up for real in the the geometric side of the world. We're actually going to be doing things like writing an equation whose solution tells you where to put a million gates on the surface of a chip. And interestingly enough, the mathematics of that is going to involve calculus, derivatives, linear algebra and matrices. So all of that stuff you learned in introductory calculus some place, it’s going to come back and we’re going to get to use it in this time. And again, a little bit of VLSI knowledge is nice, if you’ve ever seen any chip layout issues, if you’ve been exposed to them, that’s nice. It's not essential, I'm going to be telling you everything that you need to know in the course of this MOOC. The course is about CAD for semi-custom Application Specific Integrated Circuits. Things that are sort of designed for a purpose. They're semi-custom because we're reusing already designed parts. And the parts that we're actually already reusing for us are primarily logic gates that come from a logic library. And again CAD is a flow through of a sequences of design steps. The overall course sequence starts from the logic side and goes to the layout side. We are now primarily talking in this MOOC about the layout side. Again, a system-on-a-chip, ASIC is a design in SOC that integrates lots of blocks of function on one big chip, as shown in this diagram. There’s a lot of rectangular regions that are each rows of individual. In this case they’re little colored bars, but those things, if you zoom in, as show in the bottom right. Those are actually rows of individual logic gates. The logic gates come from an artifact called a technology library that tells you what you get to use to design this integrated circuit. And what we're about in this course is how do you actually go from the abstract representation of logic that comes out of logic synthesis, to real gates in a really implementable library of physical devices. How do you arrange them on the surface of the chip? And how do you connect a zillion wires, so that you actually get the right function? And then how do you tell how fast is it actually going to go as an actual designed artifact. This is the same example of a small SOC controller that I showed at the beginning of part one. Again, modern system on chip designs has lots of block some of the blocks are pre-designed by people who do circuit sort of things. Like the memories, some of them are maybe analog as shown on the bottom. The bottom block here which is a type of big A on that rectangular part of the bottom part of the chip. That's analog it talks to, in this case currents involve to design of the hood of the car. And what we're primarily interested in this part of the course because I'm showing on this two components of the chip are those rows of dark features. Those are literally gates that have been appropriately arranged on the surface of the chip and connected by wires to form on the left a blob of random control logic, that's controlling that analog. And on the right, that's actually a little tiny processor. It's very small, it's probably a 4-bit processor. But in the modern universe of SOC design, people are actually building fairly complicated CPUs sorts of processors entirely with logic synthesis. And then geometric synthesis, physical synthesis to place and route and time the designs. So we're going to talk about how to do that in this half of the course. Still important for us is this notion of a flow, the way you attack a big design problem is levels of abstraction. You divide the big problem into a lot of smaller steps, synthesis steps go sort of down this chain. Verification steps go up this chain checking if the thing you designed is actually doing what you want. And the overall top to bottom path is called a flow. We are now going to be talking about the physical side of things. And so our overall sequence for the course is still as shown on the left, logic synthesis, logic verification. Now layout synthesis, and layout verification, the top two blocks, logic synthesis and logic verification, that was the MOOC part 1. We are now in part 2, going to talk about layout synthesis and timing verification. So in layout synthesis, where do you put the gates? How do you figure out where the wires go? And in timing verification, where are you going to figure out if it's fast enough? If you're chip is supposed to run at 1 gigahertz of clock tick speed, does it? All right, well this is actually your problem to figure out if you got it right. What are the exact topics that we're going to be talking about in part 2 of Layout. We're going to be talking about four big topics. One of them is perhaps not something that you've heard about before, technology mapping. How do you go from the somewhat abstract form of logic that actually comes out of multi-level synthesis. This is the last topic in part 1, to real gates that turns out to be a CAD problem, it's called mapping. And then there's the placement problem, so you have a million gates. Where do they go? What are you trying to optimize? because you could just put them down randomly, but that would be such a bad solution. You have to arrange them on the surface of the chip optimally. It turns out optimally means so that you can connect the wires and the chip will run at the speed you need it to run. Which leads naturally to the next topic, which is called routing. Which is the process of connecting millions and millions of wires to all the gates on the chip. So that you can actually fit them, and the chip will run at the appropriate will, it'll be functionally correct and it'll run at the right speed. And then timing analysis, this is the sort of verification topic for this half of our course. Can you verify that the logic that you have synthesized and that you have placed and routed is running at the speed you need at the appropriate clock speed. And it turns out there is a logical form of these analysis, and there is a geometric form. Which requires analysis of real wires and this is the one and only place in this whole MOOC sequence where we're actually going to talk just a little bit about electricity. We're just going to mention circuits a little bit, because it turns out we need to model wires as actual electrical artifacts. And the mathematics will rapidly move to into something where we can just give you a nice mathematical model. And you don't have to worry about the circuits anymore. As a quick aside, the ordering of the topics in part 2, is not what I just showed you on that previous slide. So the real order for the CAD flow, right? The real order for the way people would do it, the real order would be you do technology mapping. That would go from the form of gates in the library, sorry, the form of gates at the end of logic synthesis to real gates in a library, that's a technology mapping. Then you place them on the surface of the chip optimally. Then you'd route them to connect the wires, and then you'd do some timing. Our order is actually going to exchange the two topics we're going to talk about placement first and then technology mapping. And the only reason or that is that for the two optional programming assignments. One of them is about placement and one of them is about routing. And in order to give you a couple of weeks to do each one we're going to talk about placement first. So then if you want to do software, you have a couple of weeks to do that software, and then routing. And if you want to do that software, you have a couple of weeks to do that. But that's the only reason, we changed the order of the topics. Normally in a real tool, you'd technology map, you'd place, you'd route, and you'd do timing. Congratulations, we are now starting part 2 of our two part MOOC series on VLSI CAD. You've already finished, I hope VLSI CAD part 1 logic and you know how to do multi level synthesis and you have a few million gates sitting around. And your new problem is how do I map them onto a real library of implementable artifacts? How do I arrange them on the surface of the chip? How do I generate and connect the wires and how do I ask questions about how fast it goes? So here is VLSI CAD part 2 about Layout. Let's go talk about the detailed, technical topics now. [SOUND]