8000 Releases · KaHIP/KaHIP · GitHub
[go: up one dir, main page]

Skip to content

Releases

KaHIP v3.29

Choose a tag to compare

@schulzchristian schulzchristian released this 19 Nov 13:48
3611a56

What's New in v3.29

Connected blocks in the library

The connected-blocks partitioning (--connected_blocks, see v3.25) is now also available through the C/C++ interface as kaffpa_connected_blocks, with the same arguments as kaffpa (mode STRONG only; other modes return an edge cut of -1).

The post-processing that makes every block connected moved from the kaffpa program into the library (lib/partition/connected_blocks.cpp). The output of kaffpa and kaffpaE is unchanged. Details are in #181.

KaHIP v3.28

Choose a tag to compare

@schulzchristian schulzchristian released this 17 Nov 12:34
4a996a9

What's New in v3.28

New preconfiguration ultra

A one-page description is in manual/ultra.pdf.

ultra is a new, higher-quality preconfiguration for kaffpa, kaffpaE and KaBaPE. It starts from strong, keeps its balance rule, and spends the time that v3.26 saved over v3.25 on better cuts.

Against v3.26 strong (imbalance 3%, 73 jobs of the v3.26 benchmark):

  • 2.2% smaller cuts in geometric mean (Q = 0.9777 on the tuning graphs and on held-out graphs, 0.9729 on new seeds; about 7% on social graphs);
  • 2.0x the time of v3.26 strong, and still below the time of v3.25 strong on every job (geometric mean 0.64 of it);
  • inside kaffpaE and KaBaPE, at the same time limit: 0.5% to 1.6% smaller cuts than with strong inside.

What it adds to strong:

  • Jet refinement (label propagation with bounded negative-gain moves and an afterburner) before the k-way FM on every level;
  • the unlocked flow model in the pairwise flow refinement, where the outer border of the flow region is no longer fixed to source or sink;
  • more global work: 3 V-cycles for k = 2, the best of 2 runs for k > 2;
  • in kaffpaE and KaBaPE: balanced individuals always rank ahead of overloaded ones, and with --input_partition the input partition is kept in the population, so the result is never worse than the input.

Usage: --preconfiguration=ultra on the command line, mode ULTRA in the C/C++ interface, kahip.ULTRA in Python. All other preconfigurations are unchanged by ultra. Details are in #176.

Bug fix in flow refinement

When no flow network could be built for a pair of blocks, flow refinement could move a whole stripe of nodes while keeping the old cut value. This changes the output of strong and strongsocial in rare cases (cut quality unchanged on average); fast, eco, fastsocial and ecosocial give bit-identical partitions (#175).

Agentic Algorithm Engineering

ultra was developed with Agentic Algorithm Engineering (AAE) (paper), this time 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.

KaHIP v3.27

Choose a tag to compare

@schulzchristian schulzchristian released this 13 Nov 13:25
cbe37b6

What's New in v3.27

Bug fix

Debug builds and the macOS/Homebrew build of v3.26 failed to link node_ordering and other programs with undefined node_hash_map<T>::EMPTY symbols. The constant is now defined outside the class, as C++11 requires (#173). Results are unchanged: Release builds produce the same partitions as v3.26.

All improvements of v3.26 (3.9x faster KaFFPa with unchanged quality, engineered with Agentic Algorithm Engineering) are included; see the v3.26 release.

KaHIP v3.26

Choose a tag to compare

@schulzchristian schulzchristian released this 13 Nov 12:31
27154d0

What's New in v3.26

Faster KaFFPa

kaffpa is now 3.9x faster in total time and 2.8x faster in geometric mean over a benchmark of 537 runs, with partition quality unchanged. The benchmark covers 20 mesh, road and social/web graphs, all six preconfigurations, and k = 2 to 256.

preconfiguration speedup (total time)
fast 3.5x
eco 5.5x
strong 3.4x
fastsocial 2.3x
ecosocial 4.3x
strongsocial 4.0x
all 3.9x

Quality:

  • The geometric mean cut is within 0.1% of v3.25 (ratio 1.0008 on seeds 1 to 3, 1.0003 on seeds 1 to 6).
  • There are no more imbalanced partitions than in v3.25.
  • Most changes give bit-identical partitions for a given seed. The others only change tie breaking or random decisions and passed a quality gate against v3.25.
  • All other command line programs (node separator, node ordering, edge partitioning, global multisection, label propagation, process mapping, ...) were audited against v3.25 as well.

Main changes:

  • fast graph reader and buffered partition writer;
  • 2-way and k-way FM with cached gains, and boundary updates only for kept moves;
  • Boykov-Kolmogorov maximum flows for flow refinement;
  • cache-friendly label propagation on a copy of the graph in visiting order;
  • small-object allocator and reusable per-node data structures;
  • fewer ensemble clusterings in strongsocial.

Details on every change (why it works and how much it saves) are in #171.

Agentic Algorithm Engineering

These improvements were engineered with Agentic Algorithm Engineering (AAE): a loop of profiling, hypothesis, implementation and measurement on a fixed benchmark. A change is kept only if it is faster and passes the correctness or quality gate.

Other

  • Windows (MSVC) build fixes for the new code.
  • kaffpa --version now reports the current version (it printed v3.17).

KaHIP v3.25

Choose a tag to compare

@schulzchristian schulzchristian released this 13 Mar 22:37

What's New in v3.25

Connected Blocks (Experimental)

KaFFPa and KaFFPaE now support --connected_blocks (strong preconfiguration only) to produce partitions where each block is a connected subgraph.

Usage:

./deploy/kaffpa graph.graph --k 4 --preconfiguration=strong --connected_blocks

Details:

  • The input graph must be connected; a warning is printed for disconnected graphs.
  • Only supported with --preconfiguration=strong. Other preconfigurations will print an error.
  • Connectivity is enforced via checkpoint-based component elimination during uncoarsening, combined with connectivity-aware refinement and greedy rebalancing.
  • When --connected_blocks is not used, KaHIP behavior is completely unchanged (identical cuts and running times).

KaHIP v3.24

Choose a tag to compare

@schulzchristian schulzchristian released this 13 Mar 19:25

64-bit Edge Support

The C interface now supports 64-bit edges via a compile-time kahip_idx typedef (int64_t or int32_t). Compile with -D64BITMODE=On to enable.

Changes

  • All edge-related CSR arrays (xadj, adjncy, adjcwgt) and edge-valued outputs (edgecut, infinity_edge_weight) use kahip_idx in the public C interface
  • Internal EdgeID and EdgeWeight become signed int64_t in 64-bit mode
  • UNSAFE_metis_style methods return kahip_idx*
  • MPI broadcast uses conditional MPI_INT64_T/MPI_INT types
  • Node-related parameters (n, vwgt, nparts, part) remain int
  • Added kahip_sizeof_idx() to query index width at runtime (returns 4 or 8)

Windows Support

  • KaHIP now builds on Windows with MSVC (no MPI, library + interface only)
  • Added Windows CI workflow via GitHub Actions
  • Platform guards for POSIX-specific headers (regex.h, sys/mman.h, execinfo.h)
  • Windows pip wheels now available on PyPI (Python 3.9-3.14)

pkg-config Support

  • KaHIP and ParHIP are now discoverable via pkg-config (merged PR #134)

Build & CI

  • Updated cibuildwheel to v3.4.0, GitHub Actions to v5 with Node.js 24
  • Added Python 3.13 and 3.14 wheel builds, dropped EOL Python 3.8

Bug Fixes

  • Fixed type mismatch in tabu_moves_queue.h (declaration vs definition of minValue)
  • Fixed edge_evaluator.cpp using EdgeID instead of PartitionID for partition vectors
  • Fixed CMake target_compile_definitions syntax (merged PR #135)

KaHIP v3.23

Choose a tag to compare

@schulzchristian schulzchristian released this 09 Mar 18:52

KaHIP v3.23

What's New

  • Homebrew support: brew install KaHIP/kahip/kahip
  • Updated README with logo, expanded badges (arXiv, platform, CI, university)
  • Updated references to latest journal versions (ACM JEA 2020 for ILP and process mapping, ALENEX 2021 for node ordering)
  • Added missing citations for mt-KaHIP (IEEE TPDS 2020) and hierarchical process mapping (SEA 2020)

Install

Homebrew:

brew install KaHIP/kahip/kahip

Python:

pip install kahip

From source:

git clone https://github.com/KaHIP/KaHIP && cd KaHIP
./compile_withcmake.sh

KaHIP v3.21

Choose a tag to compare

@schulzchristian schulzchristian released this 03 Nov 19:41
a6f95ec
  • support for PyPi, e.g. pip install kahip, and then use KaHIP in Python
  • minor fixes

KaHIP v3.19a

Choose a tag to compare

@schulzchristian schulzchristian released this 23 Apr 13:27
9d4978c

fixed tag

KaHIP v3.18

Choose a tag to compare

@schulzchristian schulzchristian released this 14 Jan 20:50
17cb2f5

minor changes

0