Repository navigation
New preconfiguration ultra: Jet refinement, unlocked flow model, more global work - #176
Merged
Merged
Conversation
New preconfiguration ultra (kaffpa --preconfiguration=ultra, also kaffpaE and node_separator; interface mode ULTRA = 6, kahip.ULTRA in Python). It starts from strong and spends more work per run: 3 V-cycles for k = 2, otherwise the best of 2 independent runs. Repetitions apply to the top level only (nested partitioner calls run once), and kaffpaE computes one partition per operator. Every other preconfiguration keeps repetitions = 1, so its output is unchanged.
Field flow_unlocked_model, set only by ultra. The flow network of a block pair (A, B) follows the model F_H of Heuer, Sanders and Schlag (ACM JEA 2019): region nodes are connected to source or sink by the weight of their edges to the rest of their own block, and edges to third blocks are left out, so nodes next to the region border can change sides. The value of an s-t cut is then exactly the A-B cut of the partition it induces. Without any source or sink edge the original model is used. The cut values of the pairs with third blocks are updated for nodes that changed sides.
Field jet_refinement, set only by ultra. Jet (Gilbert, Madduri, Boman, Rajamanickam, SIAM J. Sci. Comput. 2024) is a label propagation refinement that also takes negative-gain moves, filters them with an afterburner that evaluates each move against the moves of higher priority, and rebalances overloaded blocks. It runs before the k-way FM on every uncoarsening level.
Two fields, set only by ultra. mh_penalty_for_imbalance: individuals over the balance bound rank behind every balanced one, in the fitness and in the final choice, and a final partition still over the bound is rebalanced with the negative-cycle model. mh_keep_input: when kaffpaE starts from --input_partition, that partition enters the population unchanged as one individual, so the result is never worse than the input.
…x) and version bump
schulzchristian
added a commit
that referenced
this pull request
Nov 17, 2026
New preconfiguration ultra: Jet refinement, unlocked flow model, more global work (to master, see #176)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
This PR adds the preconfiguration
ultrato kaffpa, kaffpaE and KaBaPE. It spends the time that v3.26 saved over v3.25 on better cuts:ultrastarts fromstrong, keeps its balance rule, and stays below the running time of v3.25strongon every job of our benchmark.ultra was developed with Agentic Algorithm Engineering (AAE) [1, 2], run with a focus on solution quality: each change was stated as a hypothesis, implemented, measured on a fixed benchmark against a fixed quality gate, and kept only if the cuts improved.
Against v3.26
strong(imbalance 3%, 73 jobs):strong, and below the time of v3.25strongon every job (geometric mean 0.64 of it);stronginside.Every change is guarded by a configuration field that only
ultrasets, so every other preconfiguration gives exactly the partitions of the base branch. This PR is based on #175 (flow refinement: report no change when no flow problem can be built), which fixes a flow refinement bug for all configurations;ultrarelies on that fix.Usage
--preconfiguration=ultra(kaffpa, kaffpaE, KaBaPE, node_separator, which maps it tostrong);ULTRA(= 6) inkaffpa()and the other calls that take a mode;kahip.ULTRA;configuration::ultrainapp/configuration.h.What ultra does
ultra=strongplus:jet_refinement,lib/partition/uncoarsening/refinement/jet_refinement/). Jet is synchronous label propagation that also accepts bounded negative-gain moves, so FM starts outside its own local optimum.flow_unlocked_model,cut_flow_problem_solver.cpp). For a pair of adjacent blocks (A, B), KaHIP grows a region around their boundary, sized with the flow region factor 8 ofstrong, and solves a max-flow problem on it. In the original model the outer border of the region is tied to source or sink with infinite capacity, so these nodes can never change sides. In F_H, each region node gets a source edge with the weight of its edges to A outside the region and a sink edge with the weight of its edges to B outside the region; edges to third blocks are left out, since they are cut on either side. The value of an s-t cut is then exactly the A-B cut of the partition it induces, and the same region offers a larger space of cuts. Without any source or sink edge, the original model is used. As instrong, the most balanced minimum cut is taken. The cut values of the pairs with third blocks are updated for nodes that changed sides.ultrakaffpa above in every operator (initial population, combine, mutation). Two changes apply to the evolutionary algorithm itself, both set only byultra:mh_penalty_for_imbalance): an individual over the balance bound gets the fitness "total edge weight + 1 + overload", so it ranks behind every balanced individual in selection, exchange and the final choice. If the final partition is still over the bound, a negative-cycle rebalance moves nodes until every block fits.mh_keep_input): if kaffpaE is started with--input_partition, that partition enters the population unchanged, so the result is never worse than the input.Quality and time evidence
Q is the geometric mean over the jobs of (mean cut of ultra + 1) / (mean cut of v3.26
strong+ 1), each mean over the seeds. Lower is better. Every partition was checked by an independent checker that recomputes the cut and the block weights. Benchmark: the 73strongjobs of the benchmark of #171 (mesh, road and social/web graphs, k = 2 to 256), imbalance 3%.strong, median per job): ultra takes 2.0x the time of v3.26strong(total 2.09x, at most 2.9x) and 0.64x (geometric mean) the time of v3.25strong, at most 0.954x on any job.strong: 0 / 265 vs 3 / 265 (tuning), 1 / 100 vs 2 / 100 (held-out graphs), 1 / 219 vs 4 / 219 (seeds 7 to 9). The ultra cases are instances wherestrongalso fails (email-EuAll k = 256, 4elt k = 256).strongkaffpa time), QE = geometric mean cut ratio, ultra inside vsstronginside:No run of ultra inside kaffpaE or KaBaPE missed the balance bound.
These numbers were measured with the flow fix of #175 active in ultra and absent in v3.26
strong; on its own the fix movesstrongcuts by less than 0.01% in geometric mean.Compatibility
Every change is behind a configuration field that only
ultrasets (flow_unlocked_model,jet_refinement,mh_penalty_for_imbalance,mh_keep_input, plusglobal_cycle_iterations/repetitionsinconfiguration::ultra). The repetitions loop now runs nested partitioner calls once and kaffpaE sets repetitions = 1; every other preconfiguration has repetitions = 1 already. No new dependencies, no CMake option or compiler flag changes; one new source file (jet_refinement.cpp). ParHIP (parallel/modified_kahip) is not touched.Checked against the base branch #175:
--time_limit=0(deterministic: initial population only; 1 MPI process; fast, eco, strong, strongsocial on 4elt and PGPgiantcompo, k = 8, imbalance 3% and 0, i.e. kaffpaE and KaBaPE): 16 / 16 bit identical (the same runs of the base branch repeat bit identically). kaffpaE runs with a time limit depend on wall time and were not compared;-DNOMPI=ON), with MPI including ParHIP, and every commit of the series on its own (kaffpa, interface_test);interface_testruns; a copy of it with modeULTRAruns. The Python test of the CI was not run locally (no pybind11 on the test machine).ultraitself gives the same partitions as our development branch, where the numbers above were measured: kaffpa 18 / 18 runs (6 graphs x k = 2, 8, 64), kaffpaE with--time_limit=04 / 4 runs, bit identical. The development branch also had a weighted tabu search and KaBaPE relax-and-rebalance rounds, both switched off inultrabecause they gave no gain; they are left out of this PR.Commits
ultra preconfiguration: strong with more global work: the preconfiguration, command line, C/C++ interface, Python constant, README.ultra: unlocked flow model in pairwise flow refinementultra: Jet refinement before the k-way FM on every levelultra: kaffpaE keeps the balance bound and the input partitionultra: mode constant ULTRA = 6 in the Java wrapper and the Python exampleVersion 3.28: README news (ultra preconfiguration, flow refinement fix) and version bump: CMake project version,lib/version.h, README title and a "NEW in v3.28" section.25 files, +611 / -10.
References