17EC745 CAD for VLSI syllabus for EC

Data Structures and Basic Algorithms:

Basic terminology, Complexity issues and NP-Hardness. Examples - Exponential, heuristic, approximation and special cases. Basic Algorithms. Graph Algorithms for Search, spanning tree, shortest path, min-cut and max-cut, Steiner tree. Computational Geometry Algorithms: Line sweep and extended line sweep methods. L1, L2

Basic Data Structures.

Atomic operations for layout editors, Linked list of blocks, Bin-based method, Neighbor pointers, corner-stitching, Multi-layer operations, Limitations of existing data structures. Layout specification languages.

Graph algorithms for physical design:

Classes of graphs in physical design, Relationship between graph classes, Graph problems in physical design, Algorithms for Interval graphs, permutation graphs and circle graphs. L1, L2

Partitioning:

Problem formulation, Design style specific partitioning problems, Classification of Partitioning Algorithms. Group migration algorithms: Kernighan-Lin algorithm, Fiduccia-Mattheyses Algorithm, Simulated Annealing, Simulated Evolution.

Floor Planning:

Problem formulation, Constraint based floor planning, Rectangular dualization, Simulated evolution algorithms. L1, L2, L3

Pin Assignment:

Problem formulation. Classification of pin assignment problems, General pin assignment problem.

Placement:

Problem formulation, Classification of placement algorithms. Simulation based placement: Simulated annealing, simulated evolution, force directed placement. Partitioning based algorithms: Breur‘s Algorithm, Terminal propagation algorithm, Other algorithms for placement. L1, L2, L3

Global Routing:

Problem formulation, Classification of Global routing algorithms, Maze routing algorithms: Lee‘s algorithm, Soukup‘s algorithm and Hadlock‘s Algorithm, Line probe algorithms.

Detailed Routing:

Problem formulation, Routing considerations, models, channel routing and switch box routing problems. General river routing problem, Single row routing problem. Two-layer channel routing algorithms: Basic Left Edge Algorithm, Dogleg router, Symbolic router-YACR2. L1, L2, L3

Course Outcomes:

After studying this course, students will be able to:

• Appreciate the problems related to physical design of VLSI
• Use genralized graph theoretic approach to VLSI problems
• Design Simulated Annealing and Evolutionary algorithms
• Know various approaches to write generalized algorithms

Question paper pattern:

• The question paper will have 10 full questions carrying equal marks.
• Each full question consists of 16 marks with a maximum of Three sub questions.
• There will be 2 full questions from each module covering all the topics of the module
• The students will have to answer 5 full questions, selecting one full question from each module.

Text Book:

Algorithms for VLSI Physical Design Automation, 3rd Ed, Naveed Sherwani, 1999 Kluwer Academic Publishers, Reprint 2009 Springer (India) Private Ltd. ISBN 978-81-8128-317-7.