Lecture: Wednesday 9:00 AM-11:50 AM, E1-L1-S4 Rm 103
Instructor: Hongce Zhang (e-mail: hongcezh AT ust DOT hk)
Office Hours: Friday 4:00-5:30 pm, Rm C8-5F-W2-3
We will try to follow the posted schedule below. However, as it is the first time I teach this course, changes are likely.
Week | Date | Lecture | Presentations |
---|---|---|---|
1 | Sep 7 | Introduction | |
2 | Sep 14 | Lexing (I) | |
3 | Sep 21 | Lexing (II), parsing (I) | |
4 | Sep 28 | Parsing (II) | |
5 | Oct 12 | Parsing (III), intermediate representations | (GTA) |
6 | Oct 19 | 2-level synthesis and minimization | (1)(2)(3)(4) |
7 | Oct 26 | Finite-state machine synthesis and minimization | (5)(6)(7) |
8 | Nov 2 | Multi-level synthesis and minimization | (8)(9)(10) |
9 | Nov 9 | Technology mapping, testing, design-for-test | (11)(12) |
10 | Nov 16 | Timing analysis | (13) |
11 | Nov 23 | Functional verification | |
12 | Nov 30 | Guest lecture & student presentation | |
13 | Dec 7 | Final project presentation |
In this course, we will practice the flipped-classroom teaching pedagogy. In the first half when we are on the compiler frontend, the instructor will give lectures and students will be the audience. This is still the traditional mode of teaching and is intended to leave the students some time to transfer into the active-learning mode. For the second half (the logic synthesis), enrolled students are expected to read the references before class and then make presentations in class to demonstrate what they have learned.
Textbook 1 [Aho]: Compilers: Principles, Techniques, and Tools (by A. Aho, M. Lam, R. Sethi & J. Ullman). (This is also known as “the dragon book” because of the dragon on the front cover). We will only use the frontend part of this book.
Textbook 2 [Hachtel]: Logic Synthesis and Verification Algorithms (by G. Hachtel & F. Somenzi).
Reference book 1 [Kohavi]: Switching and Finite Automata Theory (by Z. Kohavi & N. K. Jha)
Reference book 2 [Wang]: Electronic Design Automation: Synthesis, Verification, and Test (by L-T. Wang, Y-W. Chang & K-T. Cheng).
Similar courses taught around the world (so you can also learn from other sources):
There will be two projects in this course. The first project is about lexing & parsing and the second project is about logic synthesis. The two projects are connected so that you should be able to implement a tiny toy logic synthesizer in the end.
Students should take turn to present the algorithms (the presentation sign-up sheet is on Canvas). Depending on the number of students actually enrolled, there could be more than one round of presentation. The suggested topics of the presentations are:
Number | Topic | Reference |
---|---|---|
(1) | Tabular Method of Computing Prime Implicants | [Hachtel] Section 4.4-4.5 |
(2) | Prime Implicant Selection | [Hachtel] Section 4.7-4.8 |
(3) | Branch-and-Bound Algorithm for Unate Covering Problems | [Hachtel] Section 4.9 |
(4) | Heuristic Minimization of Two-Level Circuits | [Hachtel] Section 5.1 |
(5) | FSM State Minimization | [Hachtel] Section 7.4 |
(6) | FSM State Encoding Problem | [Hachtel] Section 8.3 |
(7) | FSM Decomposition | [Hachtel] Section 8.4 |
(8) | Kernels and Co-Kernels | [Hachtel] Section 10.5 |
(9) | Heuristic Factoring Algorithm | [Hachtel] Section 10.6 |
(10) | Boolean Factoring and Decomposition of Logic Networks | Alan Mishchenko, Robert Brayton, and Satrajit Chatterjee. ICCAD 2008. (This is the fundamental of Berkeley-ABC.) |
(11) | Tree-based covering: an example of algorithms for technology mapping | [Kohavi] Section 6.2 |
(12) | The D-Algorithm (an example of ATPG algorithms) | [Wang] Section 14.4.3 |
(13) | Functional Timing Analysis | [Wang] Section 6.5.2 |
If you are interested, there are also some advanced topics on the intersection of machine-learning and logic synthesis (we might not have time to get to these in class):