Learn · VLSI Physical Design with Timing Analysis
Lecture 22 of 62week-04
Lecture 22: Kernighan – Lin (KL) Algorithm
Prof. Bishnu Prasad Das · IIT Roorkee
Credits and licence
- From
- VLSI Physical Design with Timing Analysis, IIT Roorkee (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the lectures
- Lecture 01 : Introduction to VLSI Design
- Lecture 02 : Introduction to VLSI Physical Design
- Lecture 03 : Complexity Analysis for Algorithms
- Lecture 04 : Graphs for Physical Design
- Lecture 05 : Graph searching Algorithms
- Lecture 06 : Spanning Tree and Shortest Path Algorithms
- Lecture 07 : Overview of Timing Analysis
- Lecture 08: Timing Arcs and Unateness
- Lecture 09: Delay Parameters of a Combinational Circuit
- Lecture 10: Delay Parameters of a Sequential Circuit
- Lecture 11: Timing Analysis in a Sequential Circuit
- Lecture 12: STA in Sequential Circuit with Clock Skew – I
- Lecture 13: STA in Sequential Circuit with Clock Skew – II
- Lecture 14: STA in Sequential Circuit with Clock Jitter
- Lecture 15: STA considering OCV and CRPR (Setup check)
- Lecture 16: STA considering OCV and CRPR (Hold check)
- Lecture 17: STA for Combinational Circuits – I
- Lecture 18: STA for Combinational Circuits – II
- Lecture 19: Introduction to Partitioning – I
- Lecture 20: Introduction to Partitioning – II
- Lecture 21: Partitioning Algorithms
- Lecture 22: Kernighan – Lin (KL) Algorithm
- Lecture 23: Fidduccia-Mattheyeses(FM) Algorithm
- Lecture 24 - Introduction to Floorplanning
- Lecture - 25: Floorplanning Representations
- Lecture – 26: Floorplanning Algorithms - 1
- Lecture – 27: Floorplanning Algorithms – 2
- Lecture – 28: Pin Assignment and Power - Ground Routing
- Lecture 29: Introduction to Placement
- Lecture 30: Wirelength estimation techniques
- Lecture 31: Min-cut placement
- Lecture 32: Placement Algorithms
- Lecture 33: Placement algorithms and legalization
- Lecture 34: Introduction to Clock Tree Synthesis
- Lecture 35: Clock Routing Algorithms – I
- Lecture 36: Clock Routing Algorithms – II
- Lecture 37: Clock Routing Algorithms – III
- Lecture 38 : Introduction and Optimization Goals – Global Routing
- Lecture 39: Single net routing (Rectilinear routing)
- Lecture 40: Global Routing in the connectivity graph
- Lecture 41: Finding Shortest Paths with Dijkstra’s Algorithm
- Lecture 42: Full-Netlist Routing
- Lecture 43: Introduction: Detailed Routing
- Lecture 44: Channel Routing Algorithms – I
- Lecture 45: Channel Routing Algorithms – II
- Lecture 46: Switchbox and Over the cell routing
- Lecture 47: Timing Constraints in latch based system
- Lecture 48: Timing Constraints in Pulsed Latch-based System
- Lecture 49: Time Borrowing in Latch
- Lecture 50: Crosstalk Analysis
- Lecture 51: Standard Cell Library
- Lecture 52: Low Power Cells in Standard Cell Library
- Lecture 53: Sub-threshold Standard Cell Library
- Lecture 54: Timing Library for Standard Cells
- Lecture 55: PDK and Other files
- Lecture 56: Open-Source Tool Installation and Qflow
- Lecture 57: Open-Source tool- YOSYS
- Lecture 58: OpenSTA Static Timing Analyzer
- Lecture 59: OpenROAD Physical Synthesis Flow – I
- Lecture 60: OpenROAD Physical Synthesis Flow – II
- Live Session 27-02-2024
- Live Session 07-03-2025