Fiduccia–Mattheyses algorithm

Introduction

• Aims at reducing net-cut costs; the concept of cutsize is extended to hypergraphs.
• Only a single vertex is moved across the cut in a single move.
• Vertices are weighted.
• Can handle "unbalanced" partitions; a balance factor is introduced.
• A special data structure is used to select vertices to be moved across the cut to improve running time.
• Time complexity O, where P is the total # of terminals.

F–M heuristic: notation

• n: # of cells in Net i; e.g., n = 4
• s: size of Cell i
• p: # of pins of Cell i; e.g., p = 4
• C: total # of cells; e.g., C = 13
• N: total # of nets; e.g., N = 4
• P: total # of pins; P = p + … + p = n + … + n
• Area ratio r, 0< r<1

• Cutsetsize is minimized
• |A|/ ≈ r