Description

The course will discuss state-of-the-art algorithms for VLSI physical and logic-level design automation. The discussed CAD
methods contemplate various performance aspects such as silicon area, timing, power consumption, noise and crosstalk.
Project assignments include software development for each of the studied tasks.
 

Goals

Upon completion of the course, students will know to develop and implement modern algorithms for VLSI logic and physical
level design. The studied CAD techniques will address design tasks such as partitioning, floorplanning, module placement and
signal routing. Automated optimization of combinational and sequential circuits will be also studied.
 

Course Syllabus
 

Office Hours:

Monday, Wednesday 1-3pm (Light Engineering Bldg. 261).

Text Books:

• N. Sherwani, "Algorithms for VLSI Physical Design Automation'', Kluwer Academic Publishers, 1999.
• G. Hachtel, F. Somenzi, "Logic Synthesis and Verification Algorithms", Kluwer Academic Publishers, 1996.
• G. De Micheli, "Synthesis and Optimization of Digital Circuits'', McGraw-Hill Inc, 1994.


Other Material:

• S. Sait, H. Youssef, "VLSI Physical Design Automation. Theory and practice'', McGraw-Hill, 1995.
• Published papers will be provided in class:
• A. Khang, "Futures of Partitioning in Physical Design", Proceedings of the ISPD Conference, 1998.
• D. Whitley, "A Genetic Algorithm Tutorial."
• F. Glover, "Tabu Search: A Tutorial", Interfaces 20, July 1990.
• H. Yang, D. F. Wong, "Efficient Network Flow Based Min-Cut Balanced Partitioning", Proceedings of DAC, 1994.
• H. Liu, D. F. Wong, "Network-Flow-Based Multiway Partitioning with Area and Pin Constraints", IEEE Transactions on
          CAD of Integrated Circuits and Systems, Vol. 17, No. 1, January 1998.
• Maximum Flow in a Network.

Course schedule
 

Lecture Slides

 Lecture 1 (week 1): VLSI Physical Design Automation.Design and fabrication of VLSI chips.Basic data structures & algorithms..
 Lecture 2 (week 2-3): Partitioning.
 Lecture 3 (week 4): Placement and floorplanning.
 Lecture 4 (week 5): Global routing.
 Lecture 5 (week 6): Detailed routing.
 Lecture 6 (week 7): Specialized routing.
 Lecture 7 (week 9): Floorplanning, placement and routing for analog and mixed-signal designs.
 Lecture 8 (week 10): Two-level combinational logic optimization. Exact optimization algorithms. Heuristic optimization algorithms.
 Lecture 9 (week 11): Multi-level combinational logic optimization.. Timing issues.
 Lecture 10 (week 13): Sequential logic optimization.
 Lecture 11 (week 14): Cell-library binding.
 Lecture 12 (week 15): Current research problems in logic-level CAD.

Mini Projects

Mini project 1: Partitioning; starts 02/03 - due 03/01
Mini project 2: Placement; starts 03/12 - due 04/12
Mini project 3; starts 04/12 - due 05/09
 

Exams

 
Midterm: Thursday, March 11 2004 - 3.50-5.10pm
Final exam: Exam week

Grading

 Final Grade = Mini project 1 * 0.1 + Mini project 2 * 0.2 + Mini project 3 * 0.2 + Mid-term * 0.2 + Final * 0.3

If you want to share comments or anything else related to the class please send an e-mail to Alex Doboli . Last updated Jan 27 2004.