ECE/CS 5740/6740 - CAD of Digital Circuits and Systems

CAD of Digital Circuits - Logic Synthesis and Optimization

M, W, F, 11:50am - 12:40pm, LCB 215

Mid-Term Exam: Thursday March 7, 5pm - 7pm in WEB L104

  • Here is the mid-term exam syllabus

    Final Exam: Friday, April 26, WEB 1250, 10:30am - 12:30pm

  • Final Exam Syllabus: final-exam.syllabus
  • Final exam schedule can be found here.
  • Practise test can be downloaded from here: 2019 final exam practise questions.

    Instructor, TA and Office Hours

  • Instructor: Priyank Kalla
  • Office: MEB 2260
  • Office Hours: Tuesday, Wednesday 1pm-2pm

  • TA: No TA. I'll help you :-)

    Course Downloadables

  • Class organization, grading, etc.
  • Course Syllabus
  • Course Objective and Description

    Canvas access and Class Mailing/discussion List

  • I have setup Canvas for all the four sections (ECE/CS 5740/6740) of this course. The Canvas page can be accessed: from this URL.
  • Important: All the course content can be accessed through this website. Canvas can be used for discussions on any course-related topic, tool usage, and also for uploading programming assignments. I may upload some lecture videos also on the Canvas page.

    Textbook

  • Title: Logic Synthesis and Verification Algorithms, by Profs. Gary Hachtel and Fabio Somenzi. Publisher: Springer. Available through the bookstore.
  • This is what the book looks like.

    Lecture Notes and Slides

  • 01/07: An Introduction to CAD and Synthesis . A basic introduction to the course - particularly for those of you who don't really have a good idea about what Logic Synthesis is about.
  • 01/09 - 01/11: Getting started: Slides on Boolean algebra and Boolean operations slides 2 and slides 3 .
  • 01/09-01/11: Shannon's expansion, Boolean Difference, Consensus and Smoothing operations, Unate and binate functions. Introduce the idea of Binary Decision Diagrams as a graph-based data-structure for efficient Boolean function representation and manipulation.
  • Here are some notes on Generalized cofactors, and how they can be used for Boolean function decomposition.
  • 01/14-onwards: Formal study of Binary Decision Diagrams (BDDs). Here is a set of slides for BDDs:
  • 01/23: After we finish BDDs, we will study the Boolean Satisfiability (SAT) problem. The SAT problem is a decision problem that finds wide applications in verification as well as in Logic Synthesis.
  • 01/30: Wrapped up basic concepts of SAT. Moved on to Two-level logic minimization.
  • 2/20 onwards: An overview of multi-level logic synthesis: Algebraic factorization model versus the Boolean function decomposition theory and challenges
  • 02/20: Start with the Boolean Decomposition Model
  • 03/04: Now we will study the Algebraic Model, as employed by the SIS tool.
  • 3/25: The model of AIGs, the ABC tool and Boolean decomposition using SAT solvers.
  • 03/27-03/29: Study of the Partial Logic Synthesis Problem: With application to synthesis of Rectification and Engineering Change Order Patches:
  • 4/01 - 4/10: Minimization of incompletely specified machines. Chapter 8, Sections 8.1 and 8.2.
  • 4/12-4/15: The Input Encoding Problem. Here are the slides: encoding.pdf. Particularly, we study the dichotomy-based input encoding problem (DIET).
  • 4/15: Multi-level encoding, JEDI. Section 8.3.1.
  • 4/22: We studied timing issues (arrival times, required times and slack) false paths, static sensitization. Here are some slides on timing issues and timing optimization. These slides are made available courtesy Andreas Kuelhmann:

    Reading Assignments

  • For the week 01/07-01/11: Chapters 1 and 2 are introductory chapters that give a brief overview of logic synthesis. I suggest the class should read these chapters this week. There is no need to get into the nitty-gritty details, just an overview is what is required.

    Homeworks

  • HW 1 has been assigned. Download it from here. Due on Friday 1/25.
  • HW 1 solutions are here. For Q6, the ROBDD pseudocode, take a look at the solutions here, along with the examples that depict the operation: Solution, HW 1, Q6.

  • Homework 2, A simple programming assignment with BDDs, for you to get used to the BDD package. Due by Monday 18th.
  • HW 2 solutions are here.

  • Homework 3, based on two-level logic optimization, simple disjunctive decomp and Ashenhurst-Curtis Decomp is assigned. Due date: Tuesday March 5.
  • Solutions to HW 3:
  • HW 4 is assigned, to give you some practise with kernel extraction based multi-level synthesis using Weak Division and also Boolean Bi-Decomposition. Download HW 4 from here.
  • HW 5 uploads:

    Options for Class Projects

  • Here is a description of class projects that you could pursue. Take a look. I will keep on updating this document as and when I find more time and more information. Class project document latest update: Feb 20.
  • Many of these projects can easily turn into MS thesis or projects.

    Software, tools, benchmarks

    Binary Decision Diagrams: The ROBDD Package

  • To download the CUDD package, please go to Prof. Fabio Somenzi's website at http://vlsi.colorado.edu/~fabio/ , and download the CUDD package. Also this link takes you to the main documentation for CUDD.

    Boolean SAT tools

    Many SAT tools are available in public domain. For our purposes, Lingeling, PicoSAT and/or zCHAFF will suffice.

    Linear Program

  • Download LPSolve - an integer-linear program solver (executable compiled on LINUX machines) and some sample .lp files:

    SIS-related materials

    Espresso - Two-level logic minimizer

  • Espresso, compiled for Linux download Espresso
  • Espresso manual can be downloaded from at this Berkeley website . BEWARE - there is a whole lot of information here, most of which you don't need right now. Just run 'espresso -h' (h = help) and you'll figure out most of the stuff.
  • Here is the 3-input majority function written in kiss format.

    FSM Minimization and State Assignment

  • State Minimization Download stamina and an example state machine in fsm.kiss file from here .
  • Two-Level State Encoding Download Nova

    Multi-level Logic Optimization System: SIS

  • SIS compiled for linux: Download SIS executable
  • SIS Manual/paper: SIS paper .
  • STD. Cell Library: lib2.genlib , lib2_latch.genlib
  • Here are some .blif and .pla files: des.blif , alu4.pla and 9sym.pla .
  • Here is file script.rugged and script.delay .

    Utility packages - arrays, lists, symbol tables - for your projects

  • Packages: tar'ed and gzipped here .

    The ABC tool from Alan Mishchencko, UCB

  • Go to Alan's website for the ABC synthesis tool and get the ABC tool. This is the most advanced logic synthesis tool (techniques) freely available. Link to Alan's Website is here.
  • This is an older version of my own personal copy of compiled linux binary of ABC.

    Some benchmarks for experimenting with projects

  • Here is a gzipped tarball of a few benchmark designs that you can use for synthesis experiments and for your class projects.