Circuit partitioning

Partitioning is the act of cutting a giant chip netlist — millions of gates wired together — into a handful of smaller blocks, with the goal of slicing through as few wires as possible. Picture a tangled city map where you must draw a fence that splits the population in two: you want roughly equal halves, but you also want the fence to cross as few roads as possible, because every road it crosses becomes an expensive bridge. In a chip, every cut wire becomes a connection that must travel between blocks, costing area, delay, and power.

The classic engine is the Kernighan–Lin / Fiduccia–Mattheyses (FM) heuristic: start with any two-way split, then repeatedly move the single cell that most reduces the cut, locking it so you can climb out of local minima, and keep the best snapshot seen. Modern tools wrap this in a multilevel scheme — coarsen the netlist by clustering tightly-connected cells, partition the tiny coarse graph, then uncoarsen and refine — which is how partitioners like hMETIS handle designs with tens of millions of nodes in seconds. Partitioning underpins floorplanning, FPGA mapping across multiple chips, and even how a placer divides the canvas.