ECE431 CAD Algorithms

• What is CAD, Examples of Problems and Algorithms
• Fundamental Principles of Algorithms, P and NP Problems, Complexity and managing Complexity, Types and Classes of Algorithms, Abstract Models of Circuits
• Logic Synthesis A: Boolean Algebra Fundamentals, Boolean Space, Axioms and Theorems, Boolean Function Simplifications, Boole/Shannon Expansion, Tautology
• Logic Synthesis B: Automated Synthesis and Minimisation for 2-level Circuits, Cost, Boolean Cube Representation, Quine’s Theorem, Prime Implicant Extraction, the Unate Covering Problem and Constraint Table, Quine-McCluskey Algorithm using Branch and Bound
• Logic Synthesis C: Exact Minimisation Examples, Multiple Output Functions, relationship between minimality of a function and manufacture test (DFT)
• Logic Synthesis D: Positional Cube Encoding, Algebraic Operations and Properties
• Logic Synthesis E: Heuristic Minimisation for 2-level Circuits, the ESPRESSO algorithm, the EXPAND, REDUCE, IRREDUNTANT and ESSENTIALS algorithmic steps, the principle of Hill-climbing to escape local minima, ESPRESSO Minimisation Examples
• BDDs (Binary Decision Diagrams) as a canonical form for the specification and for equivalence checking between Boolean Functions
• Logic Synthesis F: Multi-level Circuit Form, Boolean Networks and the ELIMINATE, DECOMPOSE, EXTRACT, SIMPLIFY and SUBSTITUTE multi-level logic algorithms, Multi-level minimisation examples
• Logic Synthesis G: Area/Delay Trade-off through Boolean or Algebraic Factoring, Algorithms for Boolean Division and Factorisation, Kernels and co-Kernels – Algorithms for Kernel Extraction, Rectangle Covering as a technique for multi-level optimisations
• Logic Synthesis H: Using Internal/External Don’t Cares (DCs) for Multi-level Optimisation, Satisfiability καί Observability DCs (SDC, ODCs), Examples of DC Optimisation
• Technology Mapping for Technology Libraries: Algorithms for Tree and Graph Covering
• Manufacture Testing (DFT): Fault Models, Path Sensitisation and Observability, Internal Scan, Delay Fault Testing, ATPG Algorithms: D and PODEM

The goals of HY437 include gaining understanding, insight and familiarization with state-of-the-art EDA (Electronic Design Automation) Algorithms, and automated flows for the design and testing of digital electronic circuits.

The course focuses on (1) Logic Synthesis Algorithms, (2) Technology Mapping algorithms onto standard-cell technology libraries and (3) ATPG (Automatic Test Pattern Generation) algorithms for testing manufacturing faults, i.e. all implementation stages PRIOR to physical design. The course presents a set of both exact and heuristic algorithms similar to those implemented in commercial tools, such as Synopsys DC (Design Compiler) or Cadence RC Compiler.

Upon successful completion of the course, students will be accustomed with the following concepts and skill sets:

• Understanding and Insight on the theory of Exact and Heuristic CAD Algorithms
• Understanding and Insight on the various types of algorithms and their application/applicability to the solution of a particular problem
• Knowledge of specific practical industrial CAD algorithms for Combinational Circuit Optimisation, Area/Delay Trade-offs, Technology Mapping and Manufacture Testing
• Algorithm Complexity understanding and Evaluation of alternative solution methods
• Insight on the design process of new algorithms