search

kahypar / mt-kahypar

Mt-KaHyPar (Multi-Threaded Karlsruhe Hypergraph Partitioner) is a shared-memory multilevel graph and hypergraph partitioner equipped with parallel implementations of techniques used in the best sequential partitioning algorithms. Mt-KaHyPar can partition extremely large hypergraphs very fast and with high quality.
MIT License
114 stars 23 forks source link

Cut Gain Cache #142

Closed kittobi1992 closed 1 year ago

kittobi1992 commented 1 year ago

This change separates the gain cache from our partitioned (hyper)graph data structures and implements a gain cache for the cut metric. All relevant gain cache computation techniques can be found in the folder partition/refinement/gains with a separate folder for each metric. In an upcoming change, I want to move all relevant gain computation techniques to these folders such that I will be easier to integrate a new objective function.

I run some experiments that compares the latest commit in this PR to our master branch. The running times for the tested configurations are comparable.

Here for hypergraph partitioning: running_times_hypergraph

Here for graph partitioning: running_times_graph

All performance profiles (master vs latest) look similar to the performance profile below, which means that the change does not affect the solution quality. quality

Since Mt-KaHyPar can now optimize the cut metric, I also compared Mt-KaHyPar-Q-F to kKaHyPar: kahypar_vs_mt_kahypar_cut

kKaHyPar computes slightly better cuts, but only by a small margin.

codecov[bot] commented 1 year ago

Codecov Report

Merging #142 (ed39369) into master (7136979) will decrease coverage by 1.09%. The diff coverage is 69.83%.

:exclamation: Current head ed39369 differs from pull request most recent head a9ff88e. Consider uploading reports for the commit a9ff88e to get more accurate results

@@            Coverage Diff             @@
##           master     #142      +/-   ##
==========================================
- Coverage   82.46%   81.38%   -1.09%     
==========================================
  Files         142      148       +6     
  Lines       15002    15215     +213     
  Branches     5920     6087     +167     
==========================================
+ Hits        12371    12382      +11     
- Misses       2631     2833     +202
Impacted Files Coverage Δ
...t-kahypar/datastructures/dynamic_adjacency_array.h 91.30% <ø> (-4.16%) :arrow_down:
mt-kahypar/datastructures/dynamic_graph.h 87.55% <0.00%> (-0.93%) :arrow_down:
mt-kahypar/datastructures/dynamic_hypergraph.h 84.91% <ø> (+0.04%) :arrow_up:
...ypar/partition/refinement/gains/cut/cut_rollback.h 0.00% <0.00%> (ø)
...ypar/partition/refinement/rebalancing/rebalancer.h 21.05% <ø> (ø)
mt-kahypar/partition/refinement/flows/scheduler.h 53.48% <33.33%> (-2.61%) :arrow_down:
...ahypar/partition/refinement/gains/gain_cache_ptr.h 41.26% <41.26%> (ø)
mt-kahypar/partition/deep_multilevel.cpp 83.01% <45.00%> (-1.09%) :arrow_down:
...ar/partition/refinement/gains/cut/cut_gain_cache.h 45.97% <45.97%> (ø)
mt-kahypar/datastructures/partitioned_graph.h 78.57% <46.15%> (+1.41%) :arrow_up:
... and 33 more

... and 9 files with indirect coverage changes

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more