vyges-par — hypergraph partitioning

Foundation, not a command. vyges-par is a library: it has no binary and is not installed on its own. vyges-mpl links it, and that is how you use it. Source: vyges-tools/par.

A macro placer clusters a design before it places anything. When a cluster is one flat block of tens of thousands of standard cells, it has to be cut into smaller ones along its connectivity — a hypergraph partition: cells are vertices, nets are hyperedges, and the cut is the set of nets that end up spanning both halves. vyges-par does that cut, deterministically: for the same call it returns the same blocks on every run and every machine, so the placement built on it is reproducible too.

What it does

• Multilevel partitioning: coarsen the graph by first-choice matching, partition the smallest level, then carry the answer back up, refining at each level.
• Initial partitions: random and round-robin starts, and an exact (integer-programming) partition for small graphs, keeping the best few.
• Refinement: k-way Fiduccia–Mattheyses, pairwise FM and greedy hyperedge moves; cut-overlay clustering and V-cycles to escape local minima.

The exact stages

The exact partitions are solved by vyges-ortools-lib: OR-Tools with the SCIP backend, built at pinned versions with a pinned compiler, so a tie between optimal answers resolves the same way everywhere. It is built for x86_64 Linux; that is the vyges-mpl release that links the partitioner. A build without it refuses a call that reaches an exact stage, rather than answering differently.

Where it sits

vyges-mpl run  ──(a large flat cluster)──▶  vyges-par  ──(exact stages)──▶  vyges-ortools-lib