ECE444 Physical CAD Algorithms

• General information and introduction
• Review of fundamentals
• Circuit Partition (I): Kernighan and Lin algorithm
• Circuit Partition (II): FM, Simulated Annealing, multilevel partition
• Circuit Partition (III): Spectral method, Flow-based method
• Floorplanning (I): introduction, Wong-Liu algorithm
• Floorplanning (II): finish Wong-Liu and
• Floorplanning (III): ILP formulation and nonslicing (Sequence Pair)
• Placement (I): introduction, SA and partition-based methods
• Placement (II) Analytical placement
• Placement (II): Analytical placement (continue)
• Placement (III): Timing and congestion driven placement
• Detailed Placement
• Introduction to Routing
• Global Routing
• Detail Routing
• Clock/Power Routing
• Clock Skew Scheduling

The goals of HY4xx include gaining understanding, insight and familiarization with state-of-the-art EDA (Electronic Design Automation) Physical Design Algorithms, and automated flows for the physical realization of a synthesized netlist.

The course focuses on the automatic, standard-cell physical layout design for ASIC designs, and related algorithms for (1) Circuit Partitioning, (2) Floorplanning, (3) Placement, (4) Routing and (5) Clock tree design. The course presents a set of both exact and heuristic algorithms similar to those implemented in commercial tools.

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 Physical Design
  Algorithm Complexity understanding and Evaluation of alternative solution methods
• Insight on the design process of new algorithms