## Introduction to Logic Synthesis

### Summary:

We study the synthesis of a gate-level implementation from an RTL specification. Here is a detailed course descriptor

### Lecture Material

1. Introduction
2. Boolean functions
3. Sum-of-Product representations (fix F')
4. Exact 2-level minimization: Quine-McCluskey
5. Heuristic 2-level minimization: ESPRESSO
6. BDDs
7. Multi-valued logic
8. Multi-level logic circuits
9. Factored forms
10. Algebraic division
11. Boolean division
12. Using don't cares to optimize multilevel logic
13. Technology mapping
14. Timing analysis
• John Croix's PhD thesis on timing models for standard cells
15. Timing optimization
16. Sequential synthesis
• Leiserson and Saxe's original paper on retiming
17. CNF-SAT
18. Equivalence checking

### Homeworks

1. Homework 0: Fill out the biodata form pdf
2. Homework 1: Boolean functions Due Monday 2.5.2007, in-class. Solution sketch.
3. Homework 2: 2-level minimization Due Monday 2.12.2007, in-class.
4. Homework 3: BDDs Due Wednesday 2.28.2007, in-class.
5. Homework 4: BDD package Due Friday 3.23.2007, 5:00pm in my office
• Remark 1: I recompiled the vis and glu libraries the Makefile in template pointed to (at 12:30pm 3.14.2007), the previous libraries were out of date
• Remark 2: You need to set the VIS_LIBRARY_PATH environment variable to pick up the nawk script vis uses to read blif files - setenv VIS_LIBRARY_PATH /home/projects/ece/verif/vis-1.2/share will do fine in tcsh (ignore any warnings when doing read_blif about replacing escape sequence `\.' treated as plain `.')
• Remark 3: I have two small test cases, ex1.bdd and ex2.bdd - both have two outputs, in the first they should be the same function, for the second, they are different. The example ex3.bdd has a single output, and is considerably larger, over 200k BDD nodes. If this fails to complete in 1-2 minutes, it's likely you are not using the caches correctly. You can use the variable ordering ex3.bdd.order to reduce the size to roubly 7.7k BDD nodes (6993 nodes with complement pointers, adding 10% for the noncomplement pointer case).
• Remark 4: valgrind is installed on the linux machines in LRC - it's in /usr/bin. You run it as valgrind utavis to get basic seg fault problems figured out, and valgrind --leak-check=full utavis to look for memory leaks.
• Remark 5: I've made some changes to the code based on our discussion in class. Look for AA AA - update code 3.21.2007 for the changes. I've also updated the examples in the directory to have two outputs, so copy over the new ex1/2/3.bdd files in /home/projects/ece/verif/v-1.0/template
• Remark 6: Paul has installed graphviz at /home/ecelrec/students/zucknick/graphviz
6. Homework 5: Multi-level minimization: algebraic methods pdf
7. Homework 6: Multi-level minimization: Boolean methods, technolog mapping pdf Due Monday 4.23.2007, in class. [Updated 1pm, 4.17.2007 - added problem 3, clarified XOR is 2 inputs.]
8. Homework 7: Timing optimization pdf Due Wednesday 5.2.2007

### Midterms

• Midterm 1 - everything upto and including BDDs
• Midterm 2 - everything including BDDs upto and including timing analysis