Unit-I

Introduction of Design Methodologies and Graph Theory: The VLSI Design Problems- Design Methods –Design Cycle – Physical Design Cycle-Design Styles.

Unit-II

Algorithmic and System Design-Structural and Logic Design-Layout Design. Graph terminologies – Data structures for the representation of Graphs – Algorithms: DFS-BFS- Dijkstra’s shortest path algorithm – Prim’s algorithm for minimum spanning trees. Combinatorial Optimization Problems – Complexity Class-P-NP Completeness and NPHardness problems.

Unit-III

Placement, Partitioning and Floor Planning: Types of Placement Problems – Placement Algorithms – K-L Partitioning Algorithm. Optimization Problems in Floor planning – Shape Function and Floor plan Sizing

Unit-IV

Routing and Compaction: Types of Routing Problems – Area Routing – Channel Routing – Global Routings.

Unit-V

1D and 2D Compaction. Gete level – Switch level Modeling and Simulations.

Course Outcomes
CO-1: Understand the basic concepts of VLSI design problems.
CO-2: Understand various definitions of graphs and apply to some algorithms.
CO-3: Understand and apply the placement and partitioning algorithms.
CO-4: Understand and apply the routing algorithms.
CO-5: Understand the concepts of 1D and 2D compactions.

1. Gerez, “Algorithms for VLSI Design Automation”, John Wiley & Sons, 2000.
2. Naveed Sherwani, “Algorithms for VLSI Physical Design Automation”, Second Edition, Kluwer Academic Publishers, 1995.
3. Sadiq M Sait and Habib Youssef, “VLSI Physical Design Automation: Theory and Practice”, IEET, 1999.
4. M. Sarrafzadeh and C. K. Wong, An Introduction to VLSI Physical Design, McGraw-Hill, New York, NY, 1996.
5. Giovanni De Micheli, Synthesis and Optimization of Digital Circuits, Tata McGraw Hill, 1994