ECE 6095: CAD Algorithms

Course:

            ECE 6095: CAD Algorithms, Fall 2008, 3 Credits

            Tue: 3:30-6:00pm , Room: ITE 127

Instructor: 

Dr. Mohammad Tehranipoor

Office: ITE 441

Phone: 860-486-3471

Email: tehrani at engr dot uconn dot edu

URL: http://www.engr.uconn.edu/~tehrani/teaching/cad/index.html

Office hours: W:3-4pm or by appointment

What is 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

•  Simulated Annealing

•  Genetic Algorithm

•  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

•  Placement

•  Routing

•  Compaction

•  Physical Design Automation of FPGAs

Slides: 

• First Class

• 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, ...)

• Project

Exam: 

• The exam is held on ??????.

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 ?

Text: 

• 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.

References:

• 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.

• Technical papers.

Prerequisite:

Basic knowledge on linear algebra, circuit theory, algorithms and C/C++ programming, or consent of the instructor.
 

Course Evaluation:

• Participation, In-class Exercise                        5%

• Homework Assignments/Project                     55%

• Midterm Examination                                    40%

Links & Notes:

        ISCAS'85 and '89 Benchmarks

Useful Links:

• Design Automation Conference (DAC)

• Design, Automation and Test in Europe (DATE)

• International Conference on Computer-Aided Design (ICCAD)

• International Conference on Computer Design (ICCD)

• Asia South Pacific DAC (ASP-DAC)

• IEEE Transactions on Computers

• IEEE Transactions on Computer-Aided Design

• IEEE Transactions on VLSI

• ieeexplore