Welcome to VLSI CAD, Part 1 Logic. 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 first of a two course sequence on very large scale integrated circuit computer aided design, VLSI CAD. This sequence was a few years ago introduced on the Coursera MOOC platform as a single long course about ten weeks in length, and it was called VLSI CAD logic to layout. We've not broken this into two more easily accessed parts. VSLI CAD part one logic and VSLI CAD part two, layout. So this is the introduction VSLI CAD part one. Now a modern integrated circuit is a gigantically complicated artifact. Billions, literally billions of transistors. Perhaps a hundred million foundational logic gates, millions and millions of basic memory cells. Billions of shapes that represent the logic elements and the wires, and the electrical artifacts that build one of these things arranged optimally on the surface of the chip. How given this enormous level of complexity, does anybody do this? And the answer is, a really cool sequence of computer aided design tools that allow people to take these incredibly complicated artifacts from slightly more abstract descriptions, increasingly in a stepwise manner to concrete descriptions. And so, the first part of our two course sequences is the logic part. How does one take something abstract like, Boolean algebra, a desire for ones and zeroes to do a particular set of interesting things and turn it into something concrete like a block of a million optimally designed synthesized logic gates? That's what we're actually going to be doing in this course. In this introduction we're going to be talking about the structure of the course, that it's about four weeks of lecture. That there are about four problem assignments, basically associated every week. That there are two optional software programming assignments that are part of the honors track that you can choose to do, or decide that you don't want to do them. Where we will give you actually realistic inputs from realistic designs, and let you build some software tools and actually engage with these things. This is entirely optional. You might want to do the software if you like building code. You might want to do the software if you want a deeper engagement with the material. And you might want to do the software because, hey, you decide you like this stuff and you might actually want to get a job in this industry. What sort of background do you need to do a class like this? You need some fundamental experience with basic digital design, logic and flip flops. You need some basic undergraduate kind of math. Some basic discreet math, some basic calculus, some basic linear algebra. It's helpful if you've done some software, and you understand algorithms and data structures, because this course is about the basic design of the CAD tools themselves. Their inner workings that like people do these interesting design projects. Therefore large topics in the first part of our two part sequence. The first is computational Boolean algebra, which is how do we move from the vision of Boolean algebra that you have as, say, an undergraduate student where Boolean algebra is an equation you write like physics. To Boolean algebra as a computational artifact, a data structure with methods and operators that let you actually do stuff at scale. To the second topic which is verification, how do I actually look at a blob of a million logic gates and ask a question, is it right to, the last two topics in the course which are the two great forms of basic synthesis for two level logic and synthesis for multi level logic. So lets get started with the detailed overview of the mechanics of the course, and grading in the course, and the basic topics in the course for VLSI CAD part one logic. What we are about in this sequence of classes remember this is actually a two class sequence VLSI CAD part one and part two. And the answer to this is that we are primaly interested in the design of the tools themselves that are able to take an abstract idea for a large and complicated integrated circuit, and actually turn it into a big chip. So we are not in this course primarily going to use tools. Although there will actually be some software that we have put on the Coursera website that lets you use some tools. We are primarily in this course focused on the design of the algorithms and foundational data structures that make it possible to build the tools themselves. So just a little bit of history of how we got here. There's an original version of the VSLI CAD sequence that we put on the Coursera MOOCt website in 2013. And it was one longer MOOC, it was a 10 week long course. [COUGH] And it emphasized the entire flow of CAD tools from logic topics that focus on Boolean stuff to layout topics that focus on the geometric arrangement of the components on the integrated circuit. And that course had a slightly different and somewhat longer name, it was called VLSI CAD Logic to Layout. And it had 8 weeks of lectures and eight problem assignments and four optional programming tasks. And what we have done is to take that material and redesign it, so that it's now two MOOCs in two parts. You are in the first of these parts, VLSI CAD part 1, Logic. This leads onto the second part of the course, VLSI CAD part 2, Layout. Each of the two parts is half of the original longer single massive open online course. So it's all of the original material, but now into more easy to consume parts, we hope. At the end of this sequence of courses you're going to know a lot about the logic part of CAD tools and the layout part of CAD tools for how you actually get to a real live integrated circuit. A little of an aside, because the material in this new two part, two course sequence came from the original single MOOC. This is why the intro slides in every lecture say, as you can see on the left hand side here, they all say VLSI CAD Logic to Layout. But we'll label first lecture in each of the series part one or part two. And this is also why the lectures are numbered continuously. The lectures in the first part, which is what we are about today, as we introduce things. Those are lectures 1, 2, 3, 4, 5, 6, 7, and 8, those form part one logic of the two course sequence. And then the lectures 9, 10, 11, and 12 form the second part, part two, the layout part of our course sequence. So just so you know as you go through the entire two course sequence, the lectures are basically numbered from1 to 12. So what's in a video lecture? It has a title with some content and description, like we just showed. This is an example from a little bit further on. This is lecture 6.4, Logic Synthesis, Multi-Level Logic, Kernels, and co-Kernels, and factoring. It tells you in a very detailed kind of a way, what the content is. This then segways into a talking head intro. And so this is me. I'll be doing a little few minutes of introduction that explains exactly what are we about in this course. And I'll connect it from the last lecture that you saw on the video Coursera site to the lecture that you're about to start. And then we go into some really detailed technical content, and there will be video of slides as you can see here. And I will be writing on them extensively, developing the materials, in particular doing the math kinds of components. So there will always be something dynamic going on, on many of the slides, that I think will be easier to understand if you watch me actually developing the material live. The class logistics is that overall, it's intended to be about five weeks long. There are four weeks of video lectures, and then there is a free week and then a final exam. There'll be videos every week. There'll be two or three hours in total of video. But they're broken down into a lot of little small parts that tend to be on average about 15 minutes long. There are four problem sets associated, basically one per week of the lectures. So these are our homework assignments. And I'll leave a week open at the end so you can finish up all your work. In particular, if you're working on the fourth homework assignment after the four week of lectures, you have another week to get that done. There are also two software programming assignments and these are optional, and I'm just going to emphasize that they're optional. These lead to honors track, honors assignments, so there's some extra bonus credentialing that will happen as a result of the honors assignments. It involves some conventional software coding, and also some scripts that run through the CAD-centric tools that are running on the servers that live on the Coursera website. So let's talk a bit about grading. It's mastery-based, and what that means is that you get multiple submissions, multiple attempts on the assignments. Which are each randomly changed each time you retry them. You need to pass all of the assignments individually to be able to pass this course. The problem sets because there's four weeks of lectures and one problem set for each week. They're each designed to take bout a week. The final exam is at the end of the class. It looks actually basically like a problem set, but unlike a problem set it is comprehensive. So it covers material from all four weeks of the technical topics in the class. And if you go look at the class website on the Coursera site, there are a lot more details about the specific logistics of each of these sorts of assignments and deadlines and so on. There are also programming assignments which again I will emphasize are optional. These are honors assignments, you can do them if you want to. One reason to do them would be that you're interested in a deeper engagement with the technical material; because, instead of just doing a homework assignment where you try a concept or an algorithm or a data structure by hand on a little problem, you're going to build a piece of software that's actually going to do it on a realistic problem. This will give you, I think, a deeper sense of how this stuff actually works. And the other reason that you might actually want to do the software assignments is that you're actually interested in a job in the VLSI CAD and electronic design automation industry where in the real world, most people build software. This is what you do if you're actually part of a CAD group or a cad company, you spend a lot of time actually designing the basic software here. So if you're interested in a job in the business, doing some of the programming would actually be helpful and I can actually confidently tell you that there are people who have taken this course online on the Coursera site and gotten jobs in the electronic design automation industry. Because I've talked to the companies in this domain and people can actually get jobs from this material. So mechanically, we are going to provide you realistic inputs that model each problem and we're going to just give you that as a file. So this will actually just be an ASCII text file. It'll be a readable file format in simple ASCII format. Your software needs to use that and then generate output. Your output will also be in a simple ASCII file form that you can read. You're going to upload your output to the Coursera website, and we will auto-grade it with software that we've written. And we'll also give some feedback on the quality of your solution. So as a consequence of this, you can run the code on your own computer, so you're not going to actually run any of the software you design on the Coursera website. You can also use any programming language you like. So if you like programming in C, or you like programming in C++, or you like programming in Java, or you like programming in Python or anything, you can use any language you want as long as you can read an ASCII test file, and write an ASCII text file. And you can run it on any platform you like. All you have to be able to do is generate the right file. Send it up to the Coursera website and we'll grade it and you can get credit. Some other important stuff, obviously there's an honor code for the class and the Coursera website has a lot more information about this. It's okay to talk with and work with other people in the class, but what you submit has to be your own work for homework and for any code, and please don't post any solutions to any of the assignments on the Coursera site or share these solutions face to face, or in email, or via the web with others in the course. It just makes it harder for other people in the course to be able to do their own work. Please use the Coursera interaction mechanisms. Coursera supports discussion forums to ask questions. We're going to make use of these to help connect you with each other and with the course assistants and so on. So there will always be someone that you can interact with to help you make forward progress in the course. What background material do you need to be able to do this course? Well, let's say four basic areas. You need to know some basic computer science, you need to have some basic programming skills and understand data structures. Even if it's not your intention to do the software part of the assignments, the honors part, you need to understand what programming is because we're going to be describing our algorithms using pseudocode kinds of descriptions. And so, you need some familiarity and comfort with what describing something as a program looks like, and you especially need to understand what data structures are about. So if I say that something is a stack, or I say that something is a queue, or I say that something is a graph, you need to be able to understand how you might build that. You need also some basic computer engineering skills, and that means, primarily basic digital design. So you know what logic gates are. What flip flops are, what Boolean algebra is, what simple optimization methods like Kalno maps to minimize a Boolean equation that involves combinational logic, and you need to understand basic combinational sequential design, so finite state machines. This is the sort of material you would get in any introductory digital logic design sort of class, in an undergraduate college education. Mathematically, you need to know a little bit of discrete math. What a set is, what a function is, and be willing to deal with some careful notation. A little bit of exposure to graph theory is nice but it's not really essential and for the second part of our class, some continuous math. Basic calculus, basic derivatives, basic integrals and even for the first part, the logic part, what a matrix is, rows and columns of numbers. We're going to be using those concepts in this class. A little bit of basic VLSI is not a bad thing. Some chip layout exposure, it's nice, but it's not essential. We'll be teaching you what you actually need to know. What's this course all about on a purely technical front, this is CAD for semi custom ASICs and there's a couple of acronyms here which we should talk about. An ASIC is an application specific integrated circuit. This is a circuit that'S really designed to do one sort of a thing so this is not a processor, this is a chip that's designed to be a network or designed to recognize a finger print, designed to compute one particular kind of a thing. Semi-custom is the idea that we're going to try to do this complicated chip design thing, reusing some already previously designed parts. Which means we're not going to be designing this thing one transistor at a time. And CAD, computer aided design, is the flow through a sequence of design steps and design tools. So in the real world, we'd start with a description in some sort of a high-level design language. So that could be something like Verilog of VHDL. These things are called HDLs, high-level description languages. And we would use that stuff to drive the input to logic synthesis which gives you the logic macroscopic structure, the gates and the wires. And then, we'd be using that large network of gates and wires to drive the layout side of the design. Which is, where do you put a million gates? Where do you put a billion wires, and how do you connect them? There's a lot of support for these design processes. These things are generically called libraries, so there's libraries for all sorts of useful stuff for what's going on in the chip. This course is really sort of from the start of logic synthesis to the end of the layout synthesis part. So this is why the course has two parts, one about logic, and one about layout. A little more discussion of some of these useful acronyms. A semi-custom ASIC, an application-specific integrated circuit, This is the design of a chip for a specific task using semi-custom techniques. Because you do not expect to make a billion of them, you can't really afford to be full custom. You can't really afford to design this thing a transistor at a time, you've gotta have some building blocks that are already built and assemble them. So these things are not quite as dense, which means transistors per unit area. And they're not quite as fast, let's say, gigahertz as full custom, [COUGH] but they are a lot less expensive to design, and they're a lot faster to design. It takes a lot of people and a lot of money to design a microprocessor, or say, the core processor baseband chip in a modern cellphone, there's not that many applications where you're going to sell a billion things. It takes a lot fewer people and a lot less money to design things in a semi-custom way. Semi-custom versus full-custom is really about design using mostly pre-existing parts versus designs that spend more time going right down to the design of individual transistors, which one does because one needs, say, speed or power. Today, only things like microprocessors are really full custom, and even those chips have very big semi-custom parts on them. So another really important acronym to just talk about is EDA. Computer-aided design, CAD, is what we used to call this world of tools for chip designs. And one of the problems is other people do CAD today, too. Mechanical engineers do CAD, architects who do buildings do CAD. Civil engineers do CAD, lots of people do CAD. What this area of technical work, what this industry is actually honestly called today is electronic design automation, EDA. This is what most insider chip folks call it, it's more accurate and it's more descriptive. But there's a kind of a problem, and the problem is that people who are outside of our business are not always clear on what it means. So I called the class VLSI CAD, very large scale integrated circuits computer-aided design, to be maximally accessible and easy for people to understand, but really honestly, it's VLSI EDA. So if you want to immediately sound smarter, start talking about this stuff as EDA. Now, another important acronym is a System-on-a-Chip, an SOC, sort of an ASIC. A System-on-a-Chip integrates many blocks of functions on one big chip, so most common, there are rows of things called standard cells, which are gates and flip flops. And big static random access memory, SRAM memory, and maybe some pre-designed blocks, like maybe CPUs. So these things look like a bunch of big rectangles of function, either be CPUs, random logic, memories, and just rows and rows and rows of individual logic gates and lots and lots of wires and when you zoom in and you look at them. And we'll be doing that in the second part of this class. You're going to see a bunch of rows of logic gates and a bunch of wires connecting them. And that's how we actually build things down deep, like, say, a big arithmetic unit, a data path, a multiplier, an adder or a divider, or a block of random control logic. This is a tiny, tiny little example of a small system-on-chip. This is actually an automotive controller, but because it's got all the blocks labelled on it, it's sort of interesting. It's got some big memories, which are big rectangle regions at the top. It's got some random control logic. And if you actually look at it, this is a somewhat older technology. You can actually see dark and light areas. Those are rows of gates and places for the wires to go in between them. This little blob over on the right hand side of this chip image, which is a bunch of just sort of adjacent rectangles, is the CPU core. And it is itself just rows of individual logic gates, and there's a big sort of randomly complicated looking rectangle at the bottom here. That's actually an analog interface, this is an engine controller, this thing lives under the hood of an automobile and talks the things with strange voltages and strange currents. But that stuff is controlled by the digital part up on the top. Another important term that we're going to be mentioning over and over in this course is the idea of a CAD flow. So how do you attack a big design like a system-on-chip design? And the big idea is levels of abstraction. You have to break a big problem down into smaller steps. And every step is a CAD tool, or a few CAD tools. And every step renders the design a little bit more real, a little bit more concrete, a little bit less abstract. And so there's two kinds of steps. There are synthesis steps that go forward in a design. They make new stuff, right? So synthesis steps mostly go down. I'm going to put a big S by the little block diagram at the right that says, Step 1, Step 2, Step 3, Step N. Synthesis steps go down the CAD flow diagram, and they make things more and more concrete until a real chip comes out the bottom. Verification steps actually go backwards, they go up the flow. I'm going to put a V next to my arrows here. Verification steps say hey, after you did step 2, is the design in the form of step 2 right, correct, valid? Is it the same as what I had in Step 1, but a little less abstract? Verification steps answer questions, did I make it right? Did I make an error? Does it still do the right thing after I did a synthesis step? When you put this complete set of steps together, it's called a flow. This is what our class CAD tool flow is going to look like over the two parts, part 1 logic and part 2 layout. We're going to do logic synthesis and logic verification. In the first class, we're going to do layout synthesis and timing verification in the second class. So we start with some Boolean logic description, we end up with gates and wires located at (x, y) coordinates on the surface of a physical chip. So we are going to be starting shortly to talk about the first two of these steps, logic synthesis and logic verification. And the big goals for both of these classes are to explain the critical algorithms, show you the critical data structures, and the modeling assumptions that are used in each one of these big steps. So you know enough about the models and the methods to actually write a piece of software to do this if you should choose to do so. Or at least have an intelligent conversation with someone who's using this kind of software to design a real integrated circuit. What are the topics in part 1, specifically, logic? There are four big topics over the four weeks, and those four topics are, first, computational Boolean algebra. Where we need to move from this idea that Boolean equations are things you write, but that you can't solve them, or manipulate them, or do something with them automatically. All right, we need to move your understanding of Boolean equations to be that they are computational artifacts, that there are data structures that represent them. That there are computational methods that manipulate them, and that you can do things entirely automatically with huge and complicated Boolean equations. We are then going to talk about Boolean verification. Two critical methods, something called BDDs, binary decision diagrams, and something called SAT, satisfiability methods. Boolean verification methods let you answer questions like, are these two different logic networks the same? Is this set of Boolean equations and this set of gates and wires the same? Do they do the same thing? That's a really critical thing in verification. And then we're going to talk about the two critical kinds of synthesis, where we go from an abstract idea for a logic block to real live gates. And that's 2-level logic synthesis, which is the kind of synthesis for the simplest sort of logical structures, AND/OR structures. And then the more generic industrial strength sort of logic, and this is which is called multi-level logic synthesis, logic synthesis for the general case. So those are our four topics over our four weeks of lectures. Congratulations, you're about to start something very exciting, VLSI CAD Part 1, talking about logic and getting into those four interesting topics. So without further ado, here we go. Next lectures will be on real technical topics and VLSI CAD Part 1, logic. [MUSIC]
