304-530, Logic Synthesis
INSTRUCTOR: Zeljko Zilic ( zeljko@macs.ee.McGill.CA)
As the significant part of the digital system design becomes incorporated into CAD tools, the designers should become familiar with the operation of such tools. This course provides the basics of logic synthesis. The essential representations of Boolean functions will be given, followed by the algorithms for two-level (sum-of-products), multi-level (Boolean networks) and sequential logic synthesis. The course is suited for logic designers, CAD tool developers and students interested in applications of combinatorial optimizations.
COURSE AIM: After completing this course, students should understand the essential logic synthesis algorithms and tools, be able to reason about problems in logic synthesis in general and be capable of reading critically the recent literature.
TEXTBOOKS: 1) G. Hachtel and F. Somenzi, Logic Synthesis and Verification Algorithms , Springer Verlag, 2006. 2) G. De Micheli, Synthesis and Optimization of Digital Circuits, McGraw-Hill, 1996.
COURSE CONTENT & LECTURE SCHEDULE:
| Background: Boolean Algebra, Graphs & Optimizations, BDDs [4 lectures] |
| Two-Level Combinational Logic Optimization: Principles, Logic Covers, Algorithms& Refinements, Heuristic Optimization[6 lectures] |
| Multi-Level Logic Optimization: Models & Network Transformations, Algebraic Methods, Boolean Methods, Delay Modelling, Recent Results [8 lectures] |
| Sequential Logic Optimization: State-Based Optimizations, Network Model Optimizations [4 lectures] |
| Cell-Library & FPGA Mapping: Library Binding, FPGA Mapping [4 lectures] |
| Presentations: [2 lectures] |
ASSIGNMENTS: There will be 4 assignments. The first assignment will be undertaken after the 1st part of the course (Week#4): The assignment will be of "theoretical" nature. Two assignments will involve using the CAD framework SIS. Lab work required. Lab demo and written report required. The project will consist of doing small CAD programs or reviewing a recent logic synthesis paper. Presentation and written report required.
MIDTERM EXAM: There will be a midterm exam on a pre-announced date.
GRADING SCHEME: Assignments (10% each): 40%. Midterm exam: 30%. Project: 30%