ECE 6095: VLSI CAD Algorithms, Fall 2010, 3 Credits
Tue: 3:30-6:00pm , Room: ITE 430
Dr. Mohammad Tehranipoor
Office: ITE 441
Email: tehrani at engr dot uconn dot edu
Office hours: Tue:1-2pm or by appointment
What is VLSI CAD Algorithms Course about?
CAD Algorithm course aimed at graduate students and serious seniors who want broad exposure to the physical design automation, optimization techniques and data structures inside modern VLSI design tools. Because of the increasingly high complexity of modern chip design, CAD tools become vital for delivering high VLSI system performance. Many of the leading edge CAD algorithms are built upon optimization techniques which will be introduced in this course. The applications of these techniques will be described through realistic VLSI CAD problems, especially VLSI physical design automation algorithms. Physical design automation related issues for the current state of the art will familiarize students with existing techniques in VLSI design. Students will understand the relationships between optimization techniques and various constraints posed by VLSI fabrication and design technology. Critical performance related parameters and their importance in CAD tools will be introduced. The key goals of this course are to prepare students for design and development of CAD tools and for research in physical design automation of VLSI systems.
What is CAD Algorithms Course NOT about?
It's not a circuits class--although we will mention circuits a few times. It's not a digital design class or VLSI design class, in the sense that we design a system or a chip. Instead, we design software for CAD tools.
Topics to be covered:
Introduction to Optimization Techniques
Linear and Nonlinear Programming
Branch and Bound
Divide and Conquer Algorithms
Greedy and Heuristic Algorithms
Spanning and Steiner Trees
Introduction to Physical Design Automation
Design and Fabrication of VLSI Devices
Fabrication Process and its Impact on VLSI Design
Logic and Circuit Partitioning
Floorplanning and Pin Assignment
Physical Design Automation of FPGAs
Synopsys Physical Design Flow
Xilinx Physical Design Flow
Optimization Techniques (Computational Complexity, Algorithm Analysis, Big-O Notation, Tractable/Intractable Algorithms, Local and Global Optima, ...)
Classes P and NP (Class P, Class NP, P examples, NP examples, Solutions, ...)
Branch and Bound, Divide and Conquer (Categorizing Algorithms, Definitions, Branch and Bound, Divide and Conquer, Examples, ...)
Greedy and Heuristic Algorithms (Definitions, Structure Greedy Algorithm, Heuristic Algorithms, Examples, ...)
Shortest Path and MST algorithms (Definitions, Dijkstra's Algorithm, MST, Kruskal's Algorithms, Prim's Algorithm, Boruka's Algorithm, ...)
Steiner Tree (Definition, Example, Steiner Tree Problem, MST vs. ST, Solutions, ...)
Linear and Non-Linear Programming (Linear Programming (LP), Non-linear Programming (NLP), Integer LP (ILP), Tools/Software, ...)
Steiner Tree Presentations
Genetic Algorithm (Definition, Biological Background, Search Space, GA, Examples/Solutions, GA operators, Crossover, Mutation, ...)
Simulated Annealing (Definition, SA Basic Steps, SA Algorithm, Cooling Schedule, ...)
Introduction to VLSI Physical Design (Physical Design Automation, VLSI Design Cycle, New Trends in VLSI Design Cycles, Design Styles, ...)
VLSI Physical Design Automation (Physical Design, Physical Design Cycle, VLSI Design Automation, ...)
Partitioning (Introduction, Circuit Partitioning, Hierarchical Partitioning, Partition Levels, Problem Formulation, Objectives, Constraints, Classification of Partitioning Algorithms, Group Migration Algorithms, K-L Algorithm, Hypergraph, Fiduccia-Mattheyses Alg, Component Replication, ...)
Floorplanning (Floorplanning Phase, Hierarchical Design, Problem Formulation, Aspect Ratio, Wirelength Estimation, Deadspaces, Design-Style Specific Floorplanning, Classification of Algorithms, ILP-based Floorplanning, Rectangular Dualization, Succesive Augmentation, Floorplanning using GA and SA, Slicing and Non-Slicing Floorplans, Pin Assignment, Problem Formulation, Examples, ...)
Placement (Placement Phase, Placement Problem, Placement at Various Levels, Objectives, Methodology, Problem Formulation, Design-Style Specific Placement, Placement Algorithms, Partitioning-based Algorithms, Min-Cut Placement, Placement procedures, Quadrature Placement, Bisection Placement, Group Migration, Placement Using SA and GA, ...)
Routing (Routing Problem, Routing Basics, Traditional Approach, Taxonomy of VLSI Routers, Global Routing, Grid/Checker Graph Model, Ordering Problem, Design-Style Specific Routing, Classification of Global Routing Algorithms, Problem Description, Maze Routing Alg, Lee's Alg, Soukup's Alg, Hadlock's Alg, Multiple Terminal Nets: Steiner Tree, Routing using ILP, Detailed Routing, Channel Routing Problem, Channel Routing Algorithms, Channel Density, ...)
Mid-term: October 19, 2010
Final: December 07, 2010
Assignments and Project:
Assignment 1: Posted ?, Due ?
Assignment 2: Posted ?, Due ?
Assignment 3: Posted ?, Due ?
Assignment 4: Posted ?, Due ?
Assignment 5: Posted ?, Due ?
Project: Posted April 3, Due ?
Sherwani. N., Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, 1999.
C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, Inc., 1998.
Sadiq M. Sait and Habib Youssef, VLSI Physical Design Automation: Theory and Practice, IEEE Press.
Sadiq M. Sait and H. Youssef, VLSI Physical Design Automation: Theory and Practice, World Scientific, 1999.
M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Physical Design, McGraw Hill Publications, 1996.
Basic knowledge on linear algebra, circuit
theory, algorithms and C/C++ programming, or consent of the instructor.
Participation, In-class Exercise 5%
Homework Assignments/Project 55%
Midterm Examination 40%
Links & Notes:
ISCAS'85 and '89 Benchmarks
Asia South Pacific DAC (ASP-DAC)