============================================================== SPRING 2016 CSEE E6861: COMPUTER-AIDED DESIGN OF DIGITAL SYSTEMS ============================================================== Instructor: Prof. Steven Nowick Class Time: Thursday, 4:10-6:00pm Place: TBA Credits: 3 points -------------- PREREQUISITES: -------------- (i) one semester of basic digital logic (CSEE4823, CSEE3827 [if you are solid on the digital logic material], or another course equivalent, or permission of the instructor) (ii) some basic course in data structures and algorithms (CS 3134/3136/3137, or 3157, or the equivalent). You *must* have familiarity with programming and basic data structures NOTE: *NO VLSI or EE circuits background is required!* ------------------- COURSE DESCRIPTION: u------------------- An introduction to modern CAD tools and algorithms for the design of digital systems. The course is a nice blend of three areas: (i) digital design, (ii) optimization algorithms, and (iii) software tools and applications. It is suitable for students with a range of interests: from those more interested in applied theory and algorithms, to those more interested in digital design and optimization. The course systematically covers the various automated synthesis steps used in modern CAD tools: starting from a high-level specification of an entire digital system down to optimized low-level digital hardware, and considering "design-space tradeoffs" under user-specified cost targets. Many of the techniques presented have been incorporated into state-of-the-art commercial tools. These techniques will be applied to optimize circuits and systems for a variety of key cost functions (power, delay, area, throughput), at a variety of levels in the design flow (register-transfer level [high-level structural view of complex sequential subsystems], controllers, combinational "netlists" [gate-level interconnection], technology mapped implementations [interconnection of VLSI cells]). A key theme of the course is handling large complex designs (entire subsystems or combinational blocks with 1000's or tens of thousands of gates) with very efficient and powerful automated techniques. You will be learning and using a variety of heuristic and exact optimization techniques, including: dynamic programming, iterative improvement, hill climbing, unate and binate covering, greedy algorithms, and physics-based modelling (e.g. force-directed scheduling). When you have completed the course, you will have a good handle on modern research aspects of digital CAD (i.e., the underlying optimization algorithms used to automatically design systems), as well as gain some practical hands-on experience in using existing CAD packages. The course will include assignments that involve programming, as well as use of CAD tools. You should have at least a solid basic background in programming for this course, though you do not need to be a highly-fluent programmer. If you have questions about your background, feel free to contact me by email (nowick@cs.columbia.edu) or set up an appointment. NOTE: This is *not* primarily a project/lab course; while you will use real CAD tools, the focus will be on the optimization algorithms and digital design techniques behind them. Also, you do *not* need to be an experienced digital designer to take this course: you should simply have a basic background in digital logic. --------- SYLLABUS: --------- Introduction to modern digital CAD synthesis and optimization techniques. Topics include: - modern system-level design and optimization (high-level synthesis): Register-transfer level (RTL) modeling; optimal scheduling: area- vs. latency-oriented approaches, list-based and force-directed scheduling (FDS) techniques; optimal resource sharing of registers and function units: lifetime analysis, def-use chains. - sequential logic optimization: retiming Optimizing system-level area and clock cycle time by local repositioning of registers. Leiserson/Saxe's method. Integer-linear programming (ILP) formulation. - two-level logic minimization: Modern techniques for exact and heuristic optimization (espresso, mincov), basic transforms (expand, irredundant, reduce), advanced techniques (make-sparse, last-gasp, super-gasp). - multi-level logic optimization: Basic logic transforms (collapse, extraction, substitution, simplify, decomposition), logic optimization scripts, advanced Boolean optimizations (exploiting don't-cares with ODC's/CDC's), iterative improvement using redundancy addition and removal; combining optimization targets of cycle time and area/power; - technology mapping: Optimal binding of logic gates to VLSI cell layouts in a commercial library; optimizing for delay, power and area; load-independent vs. load-dependent delay models; approximating capacitive loads; recent techniques targeted to FPGA's. - physical design basics: Overview of mapping large-scale circuits to an optimized VLSI layout; large-scale circuit partitioning: Kernighan-Lin method; place-and-route (P&R): problem overview, introduction to simulated annealing. - other advanced techniques: Validating equivalence of large combinational circuits and FSM's; advanced compact Boolean data structures (ordered binary decision diagrams [OBDD's]); SAT solvers and their applications; static timing analysis; low-power design; and synthesis-for-testability. Includes written and hands-on assignments using and creating CAD tools. A project is included, involving software development of a sophisticated CAD tool. ------------------- REQUIRED TEXTBOOK: ------------------- Giovanni De Micheli, "Synthesis and Optimization of Digital Circuits", McGraw-Hill (1994). [NOTE: currently out of print, but it can be purchased online, in new, used and international editions.] -------------- OTHER READING: -------------- A number of research and industrial articles will be provided as supplemental material. ---- URL: ---- http://www.cs.columbia.edu/~cs6861 (under construction for Spring-16) ------------------------------------------------------------------------