Course

Unit 1

VLSI Design methodologies- Introduction to VLSI design automation tools-Data structures for the representation of graphs-computational complexity- Graph algorithms – Combinatorial optimization problems-Decision problems – Complexity classes – NP-completeness and NP-hardness

Unit 2

VLSI Physical Design Cycle – Placement algorithms – Partitioning-Kernighan-Lin partitioning algorithm – Terminology and floor plan representation – Optimization problems in floor planning – Types of local routing problems – Classification of compaction algorithms.

Unit 3

Combinational Logic Synthesis- Binary Decision Diagrams-hardware models for high level synthesis-Allocation-Assignment and scheduling- scheduling algorithms.

• To introduce physical design cycle.
• To introduce VLSI Design methodologies and provide an understanding of the VLSI design automation tools.
• To emphasize placement, floor planning and routing.
• To provide an understanding of evaluation of combinational logic synthesis.

At the end of the course, the student should be able to

• CO1: Understand the VLSI physical design cycle
• CO2: Apply the VLSI design automation tools
• CO3: Analyze placement, floor planning and routing algorithms
• CO4: Evaluate combinational logic synthesis.

Skills Acquired: Provide a platform for understanding and applying CAD tools for VLSI physical design.

CO-PO Mapping:

1. H. Gerez, Algorithms for VLSI Design Automation, John Wiley & Sons, 2002.
2. A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, 2002.
3. Sadiq M. Sait, Habib Youssef, VLSI Physical Design automation: Theory and Practice, World Scientific      
4. Golshan, Physical Design Essentials: An ASIC Design Implementation Perspective, Springer, 2010.
5. Sarrafzadeh and C.K. Wong, “An introduction to physical design”, McGraw Hill.