EE 582: Physical Design Automation of VLSI Circuits and Systems

Fall 2014

Information

• Class room: Thompson Hall 105
• Class time: T/Th 12:00pm - 1:15pm
• Instructor: Prof. Dae Hyun Kim
• Office: EME 504
• Email: daehyun@eecs.wsu.edu
• Office hours: T/Th 1:30pm - 3pm

Syllabus

1st Mid-term exam: Oct. 16, 2014.

2nd Mid-term exam: Nov. 20, 2014.

Final exam: 8am - 10am, Dec. 16, 2014.

Lectures

1. Introduction
2. Preliminaries
3. Partitioning
• B. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell System Technical Journal, vol. 49, no. 2, pp. 76 - 80, 1970.
• C. M. Fidducia and R. M. Mattheyses, "A Linear-Time Heuristic for Improving Network Partitions," Proceedings of the Design Automation Conference, pp. 174 - 181, 1982.
• G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel Hypergraph Partitioning: Applications in VLSI Domain," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 7, no. 1, pp. 69 - 79, 1999.
4. Floorplanning
• L. Stockmeyer, "Optimal Orientation of Cells in Slicing Floorplan Designs," Information and Control, vol. 57, no. 2-3, pp. 91 - 101, 1984.
• D. F. Wong and C. L Liu, "Floorplan Design of VLSI Circuits," Algorithmica, vol. 4, issue 1-4, pp. 263 - 291, 1989.
• S. Sutanthavibul, E. Shragowitz, and J. B. Rosen, "An Analytical Approach to Floorplan Design and Optimization", IEEE Trans. on Computer-Aided Design, vol. 10, no. 6, 1991.
• 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, vol. 15, no. 12, 1996.
5. Placement
• M. Breuer, "A Class of Min-cut Placement Algorithms," Design Automation Conference, pp. 284 - 290, 1977.
• J. Kleinhaus, G. Sigl, F. Johannes, K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. on Computer-Aided Design, vol. 10, no. 3, pp. 356 - 365, 1991.
• P. Spindler, U. Schlichtmann, and F. M. Johannes, "Kraftwerk2 - A Fast Force-Directed Quadratic Placement Approach Using an Accurate Net Model," IEEE Trans. on Computer-Aided Design, vol. 27, no. 8, pp. 1398 - 1411, 2008.
6. Interconnect Optimization
• Lukas P.P.P. van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay," International Symposium on Circuits and Systems, pp. 865 - 868, 1990.
• Zhuo Li, "A Fast Algorithm for Optimal Buffer Insertion," IEEE Trans. on Computer-Aided Design, vol. 24, no. 6, pp. 879 - 891, 2005.
• Zhuo Li, "O(mn) Time Algorithm for Optimal Buffer Insertion of Nets with m Sinks," IEEE Trans. on Computer-Aided Design, vol. 31, no. 3, pp. 437 - 441, 2012.

Homework

1. VLSI layout design (Due 9/18 11:59pm)
2. Kernighan-Lin partitioning algorithm (Due 9/25 11:59pm)
3. Fiduccia-Mattheyses partitioning algorithm (Due 10/5 11:59pm)
4. Linear programming-based floorplanning (Due 10/12 11:59pm)
• LP example
5. Floorplanning (Due 10/30 11:59pm)
6. Floorplanning (Simulated Annealing) (Due 11/13 11:59pm)
7. Placement (Due 11/27 11:59pm)
8. Delay computation (Due 12/11 11:59pm)
9. Buffer insertion (Due 12/11 11:59pm)
10. Buffer insertion (Due 12/14 11:59pm)