TuTh 3:30-4:50pm TCH LG62
Prof. Hai Zhou
haizhou AT northwestern.edu
L461 Tech Institute
Office Hours: Th 2-3:30pm or by appoitment
L580 Tech Institute
Office Hours: F 2-4pm or by appointment
Beginning with a general introduction to VLSI design flow and CAD, the course mainly focuses on VLSI physical design (layout). It covers partitioning, placement, floorplanning, routing (global and detailed), and compaction. We will discuss why and how to partition a design process into sub-problems and will study how to design good algorithms to solve each of those sub-problems. This course has two purposes. For those who are interested in VLSI design and CAD, they will learn basic concepts and flows in hardware design, and fundamental algorithms in physical design. For those who have general interests in computer engineering, the course will help them to improve their ability to solve problems. To them, the course is just a series of problem solving exercises--only that the problems are all from CAD.
EECS 311 or any data structures and elementary algorithms course.
VLSI design background is not required.
- VLSI Physical Design Automation: Theory and Practice, S. M. Sait & H. Youssef, World Scientific, 1999.
- Combinatorial Algorithms for Integrated Circuit Layout, T. Lengauer, John Wiley & Sons, 1990.
- An Introduction to VLSI Physical Design, M. Sarrafzadeh & C. K. Wong, McGraw Hill, 1996.
Grading: 10% Participation 30% Homework 30% Midterm 30% Project
Late policy: -40% per day
0. EWD340: The humble programmer Pondering about programming--the central task of computing science--Dijkstra urges us "to approach the task with a full appreciation of its tremendous difficulty, ..., stick to modest and elegant programming languages, ..., respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers." Since here we approach not only programming but also hardware design, we should prepare us with doubly humble minds.
*1. Recent Developments in Netlist Partitioning: A Survey. C. J. Alpert and A. B. Kahng. Integration: the VLSI Journal, 19(1-2), 1995, pp. 1-81. Related to my lectures are Chapters 2, 3 (Iterative Improvement), 5 (Network Flows), and 6 (Motivations and Agglomerative Clustering).
2. An Efficient Heuristic Procedure for Partitioning Graphs. B. W. Kernighan and S. Lin. The Bell System Technical Journal, Feb. 1970, pp. 291-307.
3. Efficient Network Flow Based Min-Cut Balanced Partitioning. H. Yang and D. F. Wong. International Conference on Computer Aided Design. 1994.
4. Optimal Orientations of Cells in Slicing Floorplan Designs. L. Stockmeyer. Information and Control. Vol. 57 (1983). pp.91-101.
5. A New Algorithm for Floorplan Design. D. F. Wong and C. L. Liu. Design Automation Conference. 1986. pp. 101-107.
*6. VLSI Cell Placement Techniques. Shahookar and Mazumder. ACM Computing Surveys, June, 1991.
7. Min-Cut Placement. M. A. Breuer. J. Design Automation and Fault Tolerant Computing, Vol. 1, No. 4. Oct, 1977. pp. 343-362.
8. TimberWolf 3.2: A New Standard Cell Placement and Global Routing Package. C. Sechen and A. Sangiovanni-Vincentelli. Design Automation Conference. 1986.
9. Efficient Minimum Spanning Tree Construction without Delaunay Triangulation. H. Zhou, N. Shenoy, and W. Nicholls. Asian South Pacific Design Automation Conference. 2001.
10. On Steiner's Problem with Rectilinear Distance. M. Hanan. SIAM J. Appl. Math.. vol. 14. 1966. pp. 255-265.
11. An Edge-Based Heuristic for Steiner Routing. M. Borah, R. M. Owens, and M. J. Irwin. IEEE Trans. on Computer-Aided Design. Vol. 13, No. 12, 1994. pp. 1563-1568.
Week 1 Introduction: modern VLSI design flow; CAD paradigms; Algorithms 101 (correctness, performance, complexity). READ: Chapter 1, Paper 0. slides
Week 2-3 Partitioning: hypergraph vs. graph modeling; Kernighan-Lin Heuristic; network flow based approaches. READ: 2.1-2.4.2, 2.5-2.7 slides
Week 4-5 Floorplanning: slicing floorplan sizing; global optimization by simulated annealing; analytical methods. READ: 3.1-3.2, 3.3.2-3.3.3, 3.4-3.6 slides
Week 6 Placement: objective functions; partitioning based placement. READ: 4.1-4.3, 4.4.1-4.4.2, 4.6, 4.7 slides FastPlace
Week 7-8 Global routing: geometric spanning trees; Steiner trees; net ordering. READ: 6.1-6.4.1, reading materials 9,10, 11 slides
Week 9 Detailed routing: shortest path and maze search. READ: 5.1-5.6.3 slides
Week 10 Channel routing. READ: 7.1-7.4.3 slides
Homework 1: CAD flow & algorithm basics
Homework 2: Partitioning
Homework 3: Floorplanning & placement submit your program at http://220.127.116.11/
Homework 4: Routing trees & global routing
Homework 5: Maze routing & channel routing
Please check back frequently to this page (www.eecs.northwestern.edu/~haizhou/357) for updates and course material down-loading.