EECS 527 : Layout Synthesis and Optimization

3 Credits, Winter 2002, M, W: 12:00 - 13:30
Room: 3437 EECS Bldg
Instructor: Pinaki Mazumder
University of Michigan, Ann Arbor


This course envisages studying algorithms and optimization techniques used in the design of high-performance IC layout tools. The course will emphasize on the following topics: Full Custom v. Semi-Custom Design, Partitioning, Floorplanning, Standard and Macro Cell Placement techniques; High-performance wire routing; Layout compaction techniques; Array layout styles: Field-programmable gate arrays (FPGA's), cell synthesis, and layout compilation techniques.

Lecture Schedule: Timetable
Prerequisite: Instructor consent
Text Materials: Selected set of papers and written handouts.
Reference Book: Physical Design of VLSI Systems: Theory and Practice, IEEE Press.

Course Outline

  • Partitioning: Partitioning using simulated annealing, ratio-cut genetic algorithm, spectral (eigenvalue based) technique, and adaptive neural networks; multiway partitioning algorithms.
  • Placement: Linear passive resistive network based placement techniques; evolution-based and distributed genetic-based placement techniques; numerical optimization based placement techniques. Algorithms for both standard-cell and macro-cell layouts will be studied.
  • Routing: Multilayer channel routing; Switch-box and Topological routing; Performance-driven routing - delay and crosstalk issues; Multilayer routing techniques for MCMs; Acceleration Techniques: hardware routing accelerators with emphasis on interactive rip-up and rerouting; coarse-grained parallel routing on message-passing parallel machines; fine-grained parallel rout- ing on content-addressable array parallel processors (CAAPP).
  • Floorplanning: Graph algorithms, min-cut based floorplanning algorithms, simulated annealing based floorplanning algorithm, analytical approach to floorplan design optimization.
  • Compaction: One-dimensional, one-and-half dimensional, two-dimensional algorithms.
  • Array Layouts: FPGA's - different architecture styles, mapping, place and route techniques; Gate matrix: representation, layout optimization techniques; Datapath, memory and other macro compilation and layout generation.
    Evaluation Criteria: Three written/programming Homeworks (30%), Three Quizzes (20%)and Final Project (50%)
    Lecture Organization: See Reading List