Introduction to Logic Synthesis
Summary: We study the synthesis of a gate-level implementation
from an RTL specification. Here is a detailed course descriptor
- Boolean functions
- Sum-of-Product representations (fix F')
- Exact 2-level minimization: Quine-McCluskey
- Heuristic 2-level minimization: ESPRESSO
- Multi-valued logic
- Multi-level logic circuits
- Factored forms
- Algebraic division
- Boolean division
- Using don't cares to optimize multilevel logic
- Technology mapping
- Timing analysis
- John Croix's PhD thesis on timing models for standard cells
- Timing optimization
- Sequential synthesis
- Leiserson and Saxe's original paper on retiming
- Equivalence checking
- Homework 0: Fill out the biodata form pdf
- Homework 1: Boolean functions Due Monday 2.5.2007, in-class.
- 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:
- Homework 3: BDDs Due Wednesday 2.28.2007, in-class.
- 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
- Remark 6: Paul has installed graphviz at /home/ecelrec/students/zucknick/graphviz
- Homework 5: Multi-level minimization: algebraic methods pdf
- 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.]
- Homework 7: Timing optimization pdf Due Wednesday 5.2.2007
- Midterm 1 - everything upto and including BDDs
- Midterm 2 - everything including BDDs upto and including timing analysis