VLSI Physical Design Automation

Prof. David Z. Pan

• Lecture hours and location: MW 9:30-11am at ENS 116.
• Instructor contact information: email dpan at ece.utexas.edu, phone: (512) 471-1436.
• Office: ACES 5.434. Office hours: MW1:30-2:30 and by appointment.
• Course syllabus
• News:

• Midterm date – March 30 in class.
• The web links have been fixed (2/12).
• Class project web site is updated.

---

Course Material (tentative)

• Lec 1: General information and introduction
• Notes: PPT slides
• References
• ITRS executive summary, and design challenges (download from ITRS homepage)
• Lec 2: Review of fundamentals (Guest lecture by Dr. Minsik Cho, IBM T. J. Watson Research Center)
• Notes: PPT slides
• Lec 3: Circuit Partition (I): Kernighan and Lin algorithm (Guest lecture by Dr. Minsik Cho, IBM T. J. Watson ResearchCenter)
• Notes: PPT slides, Example from SY book
• Papers:
• B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning of Electrical Circuits", Bell System Technical Journal", pp291-307, 1970. (pdf)
• Lec 4: Circuit Partition (II): FM, Simulated Annealing, multilevel partition
• Notes: PPT slides; Slides from SY
• Papers:
• C. M. Fiduccia and R. M. Mattheyses. "A linear-time heuristic for improving network partitions". Proceedings of the Design Automation Conference, pp 174-181, 1982. (pdf)
• G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Application in VLSI Domain", Proceedings of the Design Automation Conference, pp 526-529, 1997. (pdf)
• Lec 5: Circuit Partition (III): Spectral method, Flow-based method
• Notes: PPT slides for spectral method; Flow-based method
• Papers:
• H. Yang and D. F. Wong, "Efficient Network Flow Based Min-cut Balanced Partitioning", IEEE Transactions on Computer-Aided Design, pp 1533-1540, 1996. (pdf)
• Lec 6: Floorplanning (I): introduction, Wong-Liu algorithm
• Notes: PPT slides
• References:
• L. Stockmeyer, "Optimal Orientation of Cells in Slicing Floorplan Designs", Information and Control, pp 91-101, 1983. (pdf)
• D. F. Wong and C. L. Liu, "A New Algorithm for Floorplan Design", Proc. Design Automation Conference, pp 101-107, 1986. (pdf)
• Lec 7: Floorplanning (II): finish Wong-Liu and Stockmeyer
• Lec 8: Floorplanning (III): ILP formulation and nonslicing (Sequence Pair)
• Notes: PPT slides
• References:
• S. Sutanthavibul, E. Shragowitz, and J. Rosen, "An analytical approach to floorplan design and optimization", IEEE Trans. on Computer-Aided Design, pp 761-769, 1991. (pdf )
• H. Murata, K. Fujiyoshi, S. Nakatake and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair", IEEE Trans. on Computer-Aided Design, pp 1518-1524, 1996. (pdf)
• Lec 9: Placement (I): introduction, SA and partition-based methods
• Notes:
• Sides
• References
• survey paper by Cong et al. (2005 TODAES)
• A. Dunlop and B. Kernighan, "A Procedure For Placement Of Standard-cell VLSI Circuits", IEEE Trans. on Computer-Aided Design, pp 92-98, 1985. (pdf)
• Capo or Feng-shui (partition-based placement): see GSRC bookshelf.
• Dragon (Simulated Annealing): Dragon Website (or see GSRC bookshelf)
• Resources:
• GSRC bookshelf. http://vlsicad.eecs.umich.edu/BK/Slots/
• Lec 10: Placement (II) Analytical placement
• Notes:
• Sides
• References
• Gordian (quadratic programming with partition)
• Craftwerks: force-directed method
• FastPlace (ISPD 2004)
• Lec 11 : Placement (II): Analytical placement (continue)
• References:
• Engineering Details of a Stable Force-Directed Placer, ICCAD’04
• Aplace2.0: Architecture and Details of a High Quality, Large-Scale Analytical Placer (ICCAD’05)
• mPL5: Multilevel Generalized Force-directed Method for Circuit Placement (ISPD’05). Slides .wmv
• Lec 12: Placement (III): Timing and congestion driven placement
• Notes:
• Sides
• References:
• H. Ren, D. Z. Pan and D. S. Kung, "Sensitivity Guided Netweighting for Placement Driven Synthesis",Proc. International Symposium on Physical Design (ISPD), Phoenix, Arizona, April 2004
• Lec 13: More on placement (industry perspectives, etc.)
• Notes: Slides
• Lec 14: Detailed Placement
• Notes:
• Sides
• References (for more papers, please refer to the class project page)
• Doll, K.; Johannes, F.M.; Antreich, K.J., "Iterative placement improvement by network flow method", TCAD, Volume: 13 , Issue: 10 , Oct. 1994, Pages:1189-1200
• Sung-Woo Hur; Lillis, J. "Mongrel: hybrid techniques for standard cell placement", ICCAD-2000. 5-9 Nov. 2000 Pages:165-170
• Lec 15: Detailed Placement (continue)
• Lec 16: Introduction to Routing and Global Routing (I)
• Notes:
• PPT Sides 
• Lec 17: Global Routing (II)
• Notes: PPT Slides
• PDF Slides on Steiner tree
• Papers:
• M. Hanan, "On Steiner's Problem with Rectilinear Distance", SIAM J. Applied Math, pp. 255-265, 1966.(pdf)
• J. M. Ho, G. Vijayan, and C. K. Wong, "A New Approach to the Rectilinear Steiner Tree Problem", Proc. Design Automation Conference, pp 161-166, 1989. (pdf)
• March 28: Prepare for midterm and class project.
• March 30: Midterm
• Lec 18: Global Routing (III): Recent and new techniques. Discuss on class projects
• Lec 19: Detailed Routing (I)
• Lec 20: Detailed Routing (II)
• Lec 21: Detailed Routing (II) continued
• Papers:
• T. Yoshimura and E. Kuh, "Efficient Algorithms for Channel Routing", IEEE Trans. on CAD, pp 25-35, 1982. (pdf)
• R. Rivest and C. Fiduccia, "A Greedy Channel Router", Proc. Design Automation Conference, pp 418-424, 1982. (pdf)
• Lec 22: Detailed Routing (III)
• Lec 23: Clock/power routing
• Papers:
• J Cong, A. B. Kahng, and G Robins, "Matching-based methods for high-performance clock routing", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp 1157-1169, 1993. (pdf)
• R S Tsay, "An exact zero-skew clock routing algorithm", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp 242-249, 1993. (pdf)
• Lec 28: Other topics and Conclusion