Introduction to Logic Synthesis

Summary:

Lecture Material

1. Introduction
2. Boolean functions
3. Sum-of-Product representations (fix F')
   • Shannon's MS thesis
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.
   • I have installed espresso at /home/ecelrc/faculty/adnan/bin/espresso. The binary is compiled for the linux machines (e.g., linux18.ece.utexas.edu)
   • Read this page to get an overview of espresso, especially the command options. The input file format is described in detail here.
   • Here is a trivial example. Run expresso -Dexact trivial.pla, and you should get this.
   • Here is a less trivial example, try running espresso with different options on it. Some more examples: bca.pla, ti.pla, cps.pla.
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
  • Here is a sample midterm from 2001
• Midterm 2 - everything including BDDs upto and including timing analysis
  • Here is a sample midterm from 2003

Term projects

• Project Descriptor

Resources

• Job postings
• Read about the latest trends in VLSI design at EE Times
• Don Thomas has a great Introduction to Verilog
• A nice user manual for SIS
• Other classes
  • Logic synthesis class taught at UC Berkeley
  • My VLSI design class