Syllabus For Preliminary Examination In CAD

Revised March 2011

• Each student will be examined by the entire group of examiners. The exam will last about 1h; expect 3 questions of 20m each. The format is oral. As a component of the exam, you may be asked questions somewhat outside the syllabus or your domain of knowledge. It is understood that you may not know the answer; the intent is to see how you approach such problems.

1. Timing
   • Fundamental algorithms for timing analysis of circuits and systems. Concepts include setup/hold time, slack, clock skew, critical paths, DAG timing models, static and incremental timing analysis, longest path algorithms, false paths, delay intervals, controlling values, static sensitization and co-sensitization, static timing analysis, linear and nonlinear optimization frameworks for timing. Re-timing: goals, graph abstractions, register insertion/deletion concepts for re-timing, re-timing formulation and solution techniques (Bellman-Ford, FEAS). Obtaining delays using continuous-time circuit and interconnect analysis. Applications to software and circuits.
   • Suggested reading:
     • S. Sapatnekar, Timing. Chap. 5.
     • E.A. Lee and S.A. Seshia, Introduction to Embedded Systems, A Cyber-Physical Systems Approach. Chapter 15 and Appendix B.
     • S. Devadas, K. Keutzer and S. Malik, "Computation of Floating Mode Delay: Theory and Algorithms", IEEE Transactions on CAD, vol. 12, no. 12, pp. 1913--1923, December 1993.
     • L. Lavagno, T. Villa and A. Sangiovanni-Vincentelli, "Advances in Encoding for Logic Synthesis", Digital Logic Analysis and Design, 1994.
     • N. Shenoy, "Retiming: Theory and Practice", Integration: the VLSI Journal, vol. 21, pp. 1-21, 1997.
2. Continuous-Time Modelling and Simulation
   • Modelling continuous-time systems (circuits, simple mechanical systems, reaction rate equations) as differential-algebraic equations. Quiescent steady-state analysis; the Newton-Raphson algorithm. Solving sparse systems of linear equations: Gaussian Elimination and LU factorization. Numerical solution of differential equations: existence/uniqueness, Picard-Lindelof theorem, Lipschitz condition; ODE solution fundamentals; Forward Euler, Backward Euler, Trapezoidal methods; LMS methods; use of ODE techniques for DAEs; stability of LMS methods; accuracy, truncation error of LMS methods. Sinusoidal steady state analysis of linear time-invariant systems: DAE linearization, frequency-domain computation of sinusoidal steady state responses, connection with Laplace transforms. Stationary noise analysis of linear time invariant systems: propagation of stationary noise through LTI systems, transfer functions from DAEs, direct and adjoint computation of noise power spectral densities.
   • Suggested reading:
     • A. Sangiovanni-Vincentelli, "Circuit Simulation", in Design Systems for VLSI Synthesis, Martinus Nijhoff Publishers, 1987.
     • J. Roychowdhury, Numerical Simulation and Modelling of Electronic and Biochemical Systems, Foundations and Trends® in Electronic Design Automation: Vol. 3: No 2-3, pp 97-303, 2009. Chaps 2-8.
     • L.O. Chua and P.-M. Lin, Computer-Aided Analysis of Electronic Circuits: Algorithms and Computational Techniques, Prentice-Hall, 1975. Chaps. 11-13.
3. Boolean Reasoning and Synthesis
   • Boolean functions and their interpretation as sets. On/off/don't care sets. Cubes and literals. Truth tables. CNF and DNF representations. Two-level minimization: Implicants, prime implicants; covers, prime, irredundant and minimum covers; Quine-McCluskey exact minimization; heuristic minimization via the Espresso algorithm. Multi-level logic optimization: Boolean networks; Simplification, Elimination, Decomposition, Extraction and Substitution operations on Boolean networks; Boolean and algebraic division; Boolean kernels and kernel-finding algorithms. Binary Decision Diagrams: co-factors, Shannon expansions, and their properties; binary decision trees; variable ordering; reduction rules and how they lead to reduced, ordered binary decision diagrams (ROBDDs); canonicity of ROBDDs; if-then-else operator on ROBDDs; ROBDD implementation concepts; multi-rooted BDDs; BDD size bounds; dynamic variable re-ordering by sifting. Technology mapping; strategies for design and implementation of parallel software.
   • Suggested reading:
     • R.K. Brayton, C. McMullen, G.D. Hachtel and A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.
     • R. Rudell and A. Sangiovanni-Vincentelli, "Multiple-Valued Minimization for PLA Optimization", IEEE Transactions on CAD, vol. 6, no. 5, pp. 727--750, September 1987.
     • K. Keutzer, "DAGON: Technology Binding and Local Optimization by DAG Matching", in Proceedings of the 24th Design Automation Conference, pp. 341-347, June 1987.
     • R.K. Brayton, G. Hachtel and A. Sangiovanni-Vincentelli, "Multi-Level Logic Synthesis" (sections I-IV), Proceedings of the IEEE, vol. 78, February 1990.
     • R.E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams", ACM Computing Surveys, September 1992.
     • Donald Knuth, Binary Decision Diagrams (draft), in Vol. 4 of The Art of Computer Programming.
4. Models of Computation
   • Sequential circuits. Feedback in cyclic combinational circuits: well-formed and ill-formed models. Expressing feedback using fixed-point semantics and synchronous abstractions. Constructive semantics. The Knaster-Tarski (Tarski Fixed Point) theorem: partial ordering and posets; Scott order, "bottom", Hasse diagrams; total orders; least upper bounds (joins); monotonic (order-preserving) functions; fixed-point theorem and its proof. Bourdoncle's algorithm. Constructiveness over a range of different inputs: motivation for symbolic execution. Replacing Boolean and "bottom" symbols with functions of input values. Characteristic functions; operations on characteristic functions. Monotonicity of gate operations. Proof of convergence via the Knaster-Tarski theorem. Extension of symbolic execution to handle state machines. Constructive composition of state machines. Concepts of synchronous languages.
   • Suggested reading:
     • S. Malik, Analysis of Cyclic Combinational Circuits, IEEE Trans. CAD, vol. 13, no. 7, July 1994.
     • S.A. Edwards and E.A. Lee, The semantics and execution of a synchronous block-diagram language, Science of Computer Programming (Elsevier), no. 48, pp. 21-42, 2003.
     • E.A. Lee, Concurrent Models of Computation: An Actor-Oriented Approach, draft version 0.01, 2011.
     • Tadao Murata, "Petri Nets: Properties, Analysis and Applications", Proceedings of the IEEE, April 1989.
     • E.A. Lee and A. Sangiovanni-Vincentelli, "A Framework for Comparing Models of Computation", IEEE Transactions on CAD, vol. 17, no. 12, December 1998.
5. Scheduling
   • Connected and disconnected dataflow models. Balance equations: production-consumption matrix, unique least-positive solution, consistent and inconsistent models. Solving the balance equations: fractional iteration vector, least integer solution via the LCM/GCD, Euclid's algorithm. Symbolic execution, periodic sequential schedules. Sequential scheduling for SDFs: least positive integer null space of the production/consumption matrix. Parallel scheduling. Unbounded compute resources. Modelling separate hardware for each actor; modelling synchronous circuits as dataflow; retiming as dataflow firings. Parallel scheduling with bounded resources. Acyclic precedence graphs; list scheduling; Hu Level Scheduling technique. Max-Plus algebra and dynamics.
   • Suggested reading:
     • Lee/Messerschmitt: Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing," IEEE Trans. on Computers, Vol. C-36, No. 1, pp. 24-35, January, 1987.
     • Baccelli, F., G. Cohen, G. J. Olster and J. P. Quadrat (1992). Synchronization and Linearity, An Algebra for Discrete Event Systems. New York, Wiley.
     • Sih/Lee: "Declustering: A New Multiprocessor Scheduling Technique," IEEE Trans. on Parallel and Distributed Systems, vol. 4, no. 6, pp. 625-637, June 1993.
     • Bhattacharyya, Murthy, Lee: Software Synthesis from Dataflow Graphs, Kluwer Academic Press, 1996.
     • Geilen, M. and S. Stuijk. Worst-case Performance Analysis of Synchronous Dataflow Scenarios. CODES+ISSS, Scottsdale, Arizona, USA, October 2010.
6. Formal Verification and Constraint Solving
   • The SAT problem and its applications. CNF representation for SAT. Worst-case and typical complexity. 2-SAT, 3-SAT and Horn-SAT. Resolution and the Davis-Putnam (DP) algorithm. Davis-Logemann-Loveland (DLL) algorithm. Conflict analysis and backtracking. Branching and decision heuristics. Chaff SAT solver heuristic. Boolean Constraint Propagation (BCP). 2-literal watching. Sequential equivalence checking: consensus (universal quantification) and smoothing (existential quantification) operators. Limitations of low-level circuit equivalence techniques for sequential circuits. Equivalence concepts for finite state machines. Composing FSMs for equivalence checking. Representing states and transitions as Boolean functions/sets; FSM encoding via BDDs. Reachability analysis. Sequential equivalence checking via reachability analysis and SAT. Execution trace of a state machine. Propositional logic on execution traces. Properties over a single time-line: Linear Temporal Logic (LTL). LTL operators: G, F, X, U. Safety and liveness. Monitor state machines for temporal logic formulae. Properties over all possible executions: Computation Tree Logic (CTL*, CTL). Path qualifiers: A, E. Backward Reachability Analysis. Verifying safety properties using forward and backward reachability analysis. CTL property verification via fixpoint computation. Use of BDDs: symbolic model checking. Bounded model checking and SAT-based model checking. Timed automata; basics of verification of infinite-state systems and SMT solving.
   • Suggested reading:
     • S. Malik and L. Zhang, Boolean Satisfiability: From Theoretical Hardness to Practical Success, Communications of the ACM, vol. 52, no. 8, August 2009.
     • E.A. Lee and S. Seshia, Introduction to Embedded Systems, A Cyber-Physical Systems Approach. Chaps. 12 and 14.
     • Handbook of Satisfiability, IOS Press, 2008:
       • Chapter 3: Adnan Darwiche and Knot Pipatsrisawat, "Complete Algorithms".
       • Chapter 4: Joao Marques-Silva, Ines Lynce and Sharad Malik, "Conflict-Driven Clause Learning SAT Solvers".
     • E.A. Clarke, O. Grumberg and D.E. Long, "Verification Tools for Finite-State Concurrent Systems", in A Decade of Concurrency — Reflections and Perspectives, Springer LNCS, vol. 803, 1994.
     • R. Alur, "Timed Automata", tutorial, 11th International Conference on Computer-Aided Verification, LNCS 1633, pp. 8-22, Springer-Verlag, 1999.
7. Logic-level Testing, Fault Diagnosis and Reliability
   • Logic-level controllability and observability concepts. Defects and fault models; stuck-at faults. Formulating the stuck-at fault problem for combinational and sequential circuits. Fault activation, propagation and justification. Single path sensitization (SPS). Redundant faults. Multiple path sensitization. Automatic test pattern generation (ATPG). Formulating ATPG as a SAT problem.
   • Suggested reading:
     • P. Goel, "An implicit enumeration algorithm to generate tests for combinational logic circuits", IEEE Trans. on Computers, C-30(3):215-222, March 1981.
     • T. Larrabee, "Test Pattern Generation using Boolean Satisfiability", IEEE Transactions on CAD, vol. 11, no. 1, January 1992.
     • Murray and Hayes, IEEE Computer, 1996.
8. Fundamentals of Algorithms, Data Structures and Graphs
   • Sorting: bubble sort, quicksort, heapsort, radix sort, bucket sort, etc.. Data structures: stacks, queues, linked lists, hash tables, binary search trees, B-trees, heaps. Graph concepts: vertices, edges, valency, isomorphism, directedness; walks, paths, cycles; weighted graphs; vertex colouring; trees; spanning trees; bipartite graphs and matchings; directed graphs, networks and critical paths; cuts, flows; max-flow min-cut theorem. Graph algorithms: sorting and searching algorithms; minimum spanning tree algorithms; shortest and longest path algorithms; Dijkstra, Bellman-Ford, Prim, Kruskal, Kernighan-Lin algorithms.
   • Suggested reading:
     • Cormen, Leisorson, Rivest and Stein, Introduction to Algorithms, MIT Press.
     • Norman Biggs, Discrete Mathematics, Oxford Science Publications. Chapters on graphs and graph algorithms.
     • B.W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", Bell System Technical Journal, vol. 49, 1970.
     • Alberto Sangiovanni-Vincentelli, Automatic Layout of Integrated Circuits, in Design Systems for VLSI Circuits: Logic Synthesis and Silicon Compilation (eds: De Micheli, Sangiovanni-Vincentelli, Antognetti), NATO Science Series E, Kluwer, 1987. (amazon.com link)
     • Sung Kyu Lim, Practical Problems in VLSI Physical Design Automation, Springer, 2010.
     • J. Kleinhaus, G. Sigl, F. Johannes and K.J. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming in Slicing Optimization", IEEE Transactions on CAD, March 1991.
     • T. Lengauer, "Combinatorial Algorithms for Integrated Circuit Layout", Chapter 10, Compact, pp. 579--649, Wiley and Teubner, 1990.
     • C.M. Fiduccia and R.M. Mattheyses, "A Linear Time Heuristic for Improving Network Partitions", in Proceedings of the 19th Design Automation Conference, 1982.
     • R.L. Rivest and C.M. Fiduccia, "A 'Greedy' Channel Router", in Proceedings of the 19th Design Automation Conference, pp. 418-424, June 1982.
     • C.Y. Lee, "An Algorithm for Path Connections and its Applications", IRE Transactions on Electronic Computers, EC-10, pp. 346--365, September 1961.