- 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.

Syllabus and Materials (effective Fall 2011)

- 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.

- 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.

- A. Sangiovanni-Vincentelli, "Circuit Simulation", in

- 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*.

- 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.

- S. Malik, Analysis of Cyclic Combinational Circuits,

- 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.

- 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.

- S. Malik and L. Zhang, Boolean Satisfiability: From Theoretical Hardness to Practical Success,

- 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.

- P. Goel, "An implicit enumeration algorithm to generate tests for combinational logic circuits",

- 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.

Programming aspects of the material above (including the ability to interpret and debug programs) are an integral part of the syllabus. As part of this, facility is expected with basic concepts and structures common to programming and scripting languages (such as C, MATLAB, python, perl, bash), concepts of object oriented programming (including classes, references, inheritance, operator overloading, templates, etc., in languages such as C++ and Java), and the basics of threaded programming (pthreads).