CS 402-3
Theory and Applications of Computer Aided Design
Catalog Description
A study of algorithmic techniques which solve high complexity design rules. Graph algorithms and formulations, randomized solutions, techniques from Operations Research and Statistics, Computational Geometry algorithms and data structures are introduced. The techniques are mainly applied on the Physical Design Automation problem for Integrated Circuits and Systems.
Prerequisite:
315 and 330 each with a grade of C or better.
Course Outline
| Lectures | ||
| Part I. Techniques | ||
| 1. | Introduction to Optimization problems
Deterministic, Randomized algorithms and their analysis,Pseudopolynomial,approximation algorithms and heuristics,Upper and lower bounds |
3 |
| 2. | Graph and theoretic methods
Search and path problems, flows and matching Planarity |
4 |
| 3. | Techniques from Operations Research and Statistics
Local search, Simulated Annealing, Markov chains,Linear, Integer, and Dynamic programming,Non linear optimization |
6 |
| 4. | Computational Geometry techniques
Basic data structures and algorithm,Intersection problems,Geometrical search and transformation problems,Decomposition and covering of polygonal regions,Gridless routing |
6 |
| 5. | Introduction to Interconnection Networks | 7 |
| Part II. Applications on Physical Design Automation | ||
| 1. | An Introduction to Physical Design Automation | 2 |
| 2. | Partitioning, placement and floorplanning
Partitioning heuristics,algorithms for planar graphs and trees,Partitioning based placement and floorplanning,Simulated annealing in partitioning and placement,Nonlinear optimization techniques |
6 |
| 3. | Global routing
Maze running,Line searching algorithms |
3 |
| 4. | Channel routing
Two layer channel routing heuristics,LEA based algorithms,Three and multi layer channel routing heuristics |
5 |
| 5. | Compaction
One and two dimension compaction,Hierarchical compaction |
2 |
| Part III. Other Applications | ||
| 1. | Layout problems in Architecture, Multimedia and Robotics | 2 |
| Total | 40 | |