Electronic Design Automation

Course: ESE535

• digital logic (e.g. at least CIS240 or ESE200);
• programming (at least CIS121 or ESE116); will need to be comfortable writing ~1-3K lines of code and working with a large, existing code base

• algorithms and computational theory (e.g. CIS320)
• experience with modest software projects (e.g. CIS350)
• further experience with digital logic designs (e.g. CIS371)
• exposure to VLSI (e.g. ESE570)

Quick Links: [Motivation] [Grading] [Syllabus] [Collaboration Policy] [Reading] [Previous Offerings]

Catalog Level Description: Formulation, automation, and analysis of design mapping problems with emphasis on VLSI and computational realizations. Major themes include: formulating and abstracting problems, figures of merit (e.g. Energy, Delay, Throughput, Area, Mapping Time), representation, traditional decomposition of flow (logic optimization, covering, scheduling, retiming, assignment, partitioning, placement, routing), and techniques for solving problems (e.g. greedy, dynamic programming, search, (integer) linear programming, graph algorithms, randomization, satisfiability).

Rough Lecture Outline

1. Introduction, Motivation, Overview
2. Covering
3. Clustering
4. Two-level logic
5. Multi-level logic
6. Static Timing Analysis
7. FSM Encoding (Sequential logic)
8. Concurrent Error Detection
9. Satisfiability (SAT) solvers
10. Statistical Static Timing Analysis
11. Retiming
12. Simultaneous Retiming and Covering
13. Partitioning I (formulation and KLFM)
14. Partitioning II (spectral, maxflow, replication)
15. Partitioning III (optimal: SAT, pruning search)
16. Placement I (formulation and constructive)
17. Placement II (simulated annealing)
18. Multi-objective covering (area and delay; also simultaneous covering and placement)
19. High-level Synthesis (C-to-dataflow graph)
20. Scheduling I (formulation, List Scheduling/Johnson's approximation algorithm)
21. Scheduling II (force-directed, SAT/ILP, Branch-and-Bound)
22. Routing I (variants, formulation, channel routing, over-the-cell)
23. Routing II (Pathfinder [congestion negotiation, FPGA routing])
24. FSM Equivalence Checking
25. Processor Verification
26. Highly parallel algorithms: spatial routing
27. Highly parallel algorithms: cellular placement

Projects

• power optimization
• spatial/parallel implementation of optimizations
• concurrent error detection (in logic, in FSMs)

• Participation (reading, class discussion) [10%]
• Weekly Assignments [30%]
• Small Project [20%]
• Large Project [40%]

Writeups must be done in electronic form. Use CAD or drawing tools where appropriate. Electronic submission will be preferred (and may be required for some assignments). Handwritten assignments and hand-drawn figures are not acceptable.

For those that want integrated references to backup the reading, consider the following:

@Book{gerez_vlsida99,
  author = 	 {Sabih H. Gerez},
  title = 	 {Alagorithms for VLSI Design Automation},
  publisher = 	 {John Wiley \& Son Ltd},
  year = 	 {1999},
  note = {general reference}

@Book{reconfigurable_computing_mk2008,
  editor =   {Scott Hauck and Andr\'e DeHon},
  title =    {Reconfigurable Computing: The Theory and Practice of FPGA-Based Computation},
  publisher =    {Elsevier},
  year =     2008,
  series =   {Systems-on-Silicon}
  note = {has a section on major components of tool flow for FPGA-like devices}

@book{clrs_algorithms_mitpress2001,
  author={Thomas Cormen and Charles Leiserson and Ronald Rivest and
  Clifford Stein},
  title={Introduction to Algorithms},
  year=2001,
  edition={2nd},
  publisher={MIT Press},
  note = {general algorithms reference}
 }

Past Offerings

• Fall 2005 syllabus available at http://www.cs.caltech.edu/courses/cs137/2005/fall/Schedule.html

• Winter 2006 syllabus available at http://www.cs.caltech.edu/courses/cs137/2006/winter/Schedule.html