EECS 357 Introduction to VLSI CAD

Time & Place

TuTh 3:30-4:50pm TCH LG62

Instructor

Prof. Hai Zhou
haizhou AT northwestern.edu
L461 Tech Institute
(847) 491-4155
Office Hours: Th 2-3:30pm or by appoitment

TA

Peng Kang
pengkang2011@u.northwestern.edu
L580 Tech Institute
(847) 491-9925
Office Hours: F 2-4pm or by appointment

Overview

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.

Prerequisites

EECS 311 or any data structures and elementary algorithms course.
VLSI design background is not required.

Text

References:

Policies

Grading: 10% Participation    30% Homework     30% Midterm     30% Project
Late policy: -40% per day

Reading materials (* indicates recommended but not required)

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.

Lecture schedule (Even though I do not use slides, they are included for your study)

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 (due before the class on each date)

Homework 1: CAD flow & algorithm basics
Homework 2: Partitioning
Homework 3: Floorplanning & placement submit your program at http://129.105.6.97/
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.