The course will introduce techniques and algorithms for physical and logic-level design automation. Discussed optimization methods contemplate various
performances such as silicon area, timing, power consumption, noise and crosstalk.

Goals

Upon complition of this course, the students will be able to develop state-of-the-art tools and algorithms for VLSI logic and physical level design.
Tools will address design tasks such as floorplanning, module placement and signal routing. Also, automated optimization of combinational and
sequential circuits will be presented.

Course Syllabus

Text Books:

• 1. N. Sherwani, ``Algorithms for VLSI Physical Design Automation'', Kluwer Academic Publishers, 1999.

• 2. S. Sait, H. Youssef, ``VLSI Physical Design Automation. Theory and practice'', McGraw-Hill Book Company, 1995.
• 3. M. Sarrafzadeh, C. K. Wong, ``An Introduction to VLSI Physical Design'', McGraw-Hill Book Company, 1996.
• 4. G. De Micheli, ``Synthesis and Optimization of Digital Circuits'', McGraw-Hill Inc, 1994.


• Published papers will be provided in class.


 1) A. Khang, "Futures of Partitioning in Physical Design", Proceedings of the ISPD Conference, 1998.
 2) H. Yang, D. F. Wong, "Efficient Network Flow Based Min-Cut Balanced Partitioning", Proceedings of DAC, 1994.
 3) H. Liu, D. F. Wong, "Network-Flow-Based Multiway Partitioning with Area and Pin Constraints", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, No. 1, January 1998.
 4) Maximum Flow in a Network.
 5) D. Whitley, "A Genetic Algorithm Tutorial."
 6) F. Glover, "Tabu Search: A Tutorial", Interfaces 20, July 1990.

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): 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 September 12 2001 - due October 3 2001.
Mini project 2: Placement and global routing (starts October 17 - due Nov 7).
Mini project 3 (starts in week 11 - ends in week 15).
 

Office Hours:

        Monday 5-7pm (Light Engineering Bldg. 261).

Exams

   Midterm: Wednesday, October 24 - 7-10pm
  Final exam: Exam week

Grading

 Final Grade = Homework1 * 0.1 + Homework2 * 0.1 + Homework3 * 0.1 + Mid-term * 0.2 + Final * 0.2 + Mini Project * 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 Aug 21 2001.