Digital Logic Synthesis
G | 03-IMVP-DLS
(in englischer Sprache)
In this course the students are going to be introduced to the methods used for Digital Logic Synthesis, i.e., to take the design represented at various levels of abstraction down to basic digital gates. The key aspect of this course is to make them aware of the usefulness of abstraction in digital logic synthesis and to optimize the digital circuit for the given set of constraints. This will enable students to not only understand the state of the art optimization techniques but the learning from this course can be used in emerging domains for efficient logic synthesis. Given the complexity of the digital systems in the modern world, automation is key in making the problem of digital logic synthesis feasible. The basic intuition behind optimization will be developed using linear programming and integer linear programming. The first optimization will be at the architectural level. The study at this level deals with capturing the behavior from a macroscopic viewpoint represented in the form of data flow graphs. The optimization of these graphs in terms of resource and time constraints will be done. Scheduling and Binding will be discussed at depth to perform optimizations at the architectural level. Next, we will move at the lower level of abstraction, logic level. The basics of Boolean logic representation and manipulation for digital logic synthesis will be discussed. The next part of the course deals with the two level logic minimization. We will discuss in brief about the Exact minimization algorithms but will discuss in detail about the heuristic based methods for two level logic optimization. Lastly, we will discuss the multilevel logic optimization techniques.
- Introduction Lecture
- Personal Introduction / Research Interests
- Logistics of the course time, assignments, exams
- Outline of the course will be discussed
- Y-Chart
- References for the Course
- “Synthesis and Optimization of Digital Circuits”, by Giovanni De Micheli
- “Logic Synthesis and Verification Algorithms”,by Gary D. Hachtel and Fabio Somenzi
- Introduction to Optimization
- What is optimization
- Optimization using single variable
- Optimization using multiple variable
- Online Libraries to perform optimizations
- Architectural Synthesis - I
- Basics of Architectural Scheduling
- Data flow graphs and sequencing graphs
- Scheduling - ASAP, ALAP
- Hierarchical Sequencing Graphs
- Resource Constrained Scheduling
- Architectural Synthesis - II
- ILP formulation of Scheduling
- Resource Constrained
- Latency Constrained
- Heuristic Based Scheduling - LIST Scheduling
- Architectural Synthesis - III
- Binding Preliminaries
- Resource Sharing
- Register Binding
- ILP formulation for Binding
- Boolean Algebra - I
- Basics of Boolean Algebra
- Tabular Representation
- Graph based Representations
- Boolean Algebra - II
- Cost abstraction in terms of area and delay
- Preliminaries and Terminologies
- Exact Minimization Techniques (Quine McCluskey)
- Heuristic Based Optimizations - I
- Unateness
- Operators for Boolean Algebra
- Matrix Representations
- Cofactor Computations
- Tautology conditions
Heuristic Based Optimizations - II
- Recursive Tautology
- Operations on Logic covers
- Containment and Complementation
Heuristic Based Optimizations - III
- Espresso Minimization
- Expand
- Reduce
- Reshape
- Irredundant
MultiLevel Logic Minimization - I
- Comparison between single valued and multi valued logic optimization
- Elimination
- Decomposition
- Simplification
- Extraction
MultiLevel Logic Minimization - II
- Algebraic Model for Optimization of Multi level Logic
- Algebraic Division
Lecture on Practical Logic Synthesis using Industry Standard/ Academic Tools
- Take the design in High Level Synthesis
- Synthesize it to generate Verilog
- Technology Independent Optimizations
- Technology Dependent Optimization
- Synthesized gate level Netlist.
