VL 10 - Introduction to FM Algorithm

In this session, we will explore the Fiduccia–Mattheyses (FM) Algorithm, one of the most influential and widely used algorithms in VLSI physical design and partitioning problems. As modern integrated circuits grow in complexity, efficiently partitioning large circuits into smaller, well-balanced blocks becomes critical. Poor partitioning leads to increased interconnect delay, power consumption, and routing congestion. The FM algorithm addresses this challenge by providing a fast and effective heuristic for minimizing cut size while maintaining balance constraints. The FM algorithm is an improvement over the Kernighan–Lin algorithm, offering linear time complexity per pass, making it suitable for handling large-scale netlists. It operates by iteratively moving cells between partitions based on gain values, optimizing connectivity without violating balance requirements.