EE 382V: VLSI Physical Design Automation (Spring 2015)

Prof. David Z. Pan

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

2/11: Midterm date: March 25 in class.
2/11: Video recording a class on Feb. 20 (Friday) 9-10:30am at ETC 5.148 due to traveling and no class on 2/25 (Wed).
2/2: The Class Project page is up.
1/20: Welcome back to school!

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

Notes: PPT slides

Lec 3: Circuit Partition (I): Kernighan and Lin algorithm

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:

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:

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)

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
Final project presentation

Homeworks

Class Project