EE 582: Physical Design Automation of VLSI Circuits and Systems

Fall 2014

Prerequisite

   No official prerequisites, but students are expected to have some knowledge of

• Logic circuits
• Linear circuit analysis
• Digital system design
• VLSI
• Basic programming skills (C/C++)

Textbook

  There is no required textbook for this course. However, the following books are recommended:

• VLSI Physical Design Automation: Theory and Practice, Sadiq M. Sait, Wspc, 1999, ISBN 978-9810238834
• Algorithms for VLSI Physical Design Automation, 3/E, Naveed A. Sherwani, Springer, 1998, ISBN 978-0792383932
• Practical Problems in VLSI Physical Design Automation, Sung Kyu Lim, Springer, 2008, ISBN 978-1402066269

Grading

• Assignments: 40%
• Midterm exam 1: 20%
• Midterm exam 2: 20%
• Final exam: 20%

Topics

• Introduction (Week 1-2)
  • Introduction to physical layout design of digital VLSI circuits and systems
  • Design methodologies and optimization problems
  • Algorithms and optimization techniques
• Partitioning (Week 3-4)
  • Kernighan-Lin
  • Fiduccia-Mattheyses
  • Simulated-annealing
  • h-Metis
• Floorplanning (Week 4-5)
  • Basic concepts
  • Sequence-pair
  • Analytical floorplanning
  • Polish-expression
  • Stockmeyer
• Midterm exam 1 (Week 6)
• Placement (Week 6-8)
  • Partitioning-based global placement
  • Analytical global placement
  • Congestion estimation and reduction
  • Detailed placement
• Routing (Week 8-10)
  • Maze routing
  • Integer-programming-based global routing
  • Steiner routing
  • Detailed routing
• Midterm exam 2 (Week 10)
• Interconnects analysis (Week 11)
  • Interconnect modeling
  • Delay computation
  • Timing analysis
  • Power analysis and power integrity
  • Cross-talk and signal integrity
• Interconnect optimization (Week 12)
  • Buffer insertion
  • Gate sizing
  • Wire sizing and routing layer selection
• Clock-tree synthesis (Week 13)
  • H-tree
  • Exact zero-skew algorithm
  • DME algorithm
  • Useful skew
• Thanksgiving (Week 14)
• Low-power design (Week 15)
  • Power gating
  • Clock gating
  • Dynamic and leakage power minimization
• Design for Manufacturability (Week 16)
  • Chemical-mechanical polishing and metal fill insertion
  • Lithography, optical proximity correction, and multiple patterning
  • Process variation
• Final exam (Week 17)

Information on the exams

• You are allowed to bring cheat sheets.
• Some problems will be solving some simple optimization problems (e.g., "Partition the following modules into two sets by the Fiduccia-Mattheyses algorithm").
• Some problems will be more in-depth. For example, "Change the Fiduccia-Mattheyses algorithm to solve the following partitioning problem."