Initial Partitioning: Perform n-level RB-based partitioning multiple times #38

SebastianSchlag · 2019-06-06T09:02:22Z

Currently, our RB-based initial partitioner is only called once, and only calls the actual flat initial 2-way partitioning algorithms multiple times (i.e., in its own initial partitioning phase). However, we might be able to improve initial k-way partitions by calling the entire RB-based initial partitioner multiple times.

RoccoLoter · 2025-03-29T08:46:06Z

Hi @SebastianSchlag ,
Does the current k-way hypergraph partitioning support user-defined initial partitioning? I am using KaHyPar through the Python API, with the configuration file: "km1_kKaHyPar_sea20.ini".

SebastianSchlag · 2025-03-30T05:18:11Z

Hi @RoccoLoter, could you elaborate what you mean by user-defined initial partitioning? Would you be interested in plugging in your own initial partitioning algorithm?

The framework itself provides a variety of config options for the initial partitioning phase:

kahypar/config/km1_kKaHyPar_sea20.ini

Lines 37 to 62 in 8917e08

    
           i-mode=recursive 
        
           i-technique=multi 
        
           # initial partitioning -> coarsening 
        
           i-c-type=ml_style 
        
           i-c-s=1 
        
           i-c-t=150 
        
           # initial partitioning -> coarsening -> rating 
        
           i-c-rating-score=heavy_edge 
        
           i-c-rating-use-communities=true 
        
           i-c-rating-heavy_node_penalty=no_penalty 
        
           i-c-rating-acceptance-criterion=best_prefer_unmatched 
        
           i-c-fixed-vertex-acceptance-criterion=fixed_vertex_allowed 
        
           # initial partitioning -> initial partitioning 
        
           i-algo=pool 
        
           i-runs=20 
        
           # initial partitioning -> bin packing 
        
           i-bp-algorithm=worst_fit 
        
           i-bp-heuristic-prepacking=false 
        
           i-bp-early-restart=true 
        
           i-bp-late-restart=true 
        
           # initial partitioning -> local search 
        
           i-r-type=twoway_fm 
        
           i-r-runs=-1 
        
           i-r-fm-stop=simple 
        
           i-r-fm-stop-i=50 
        
           # main -> local search

For kKaHyPar, the initial partitioning algorithm is itself an n-level recursive bipartitioning algorithm with configurable coarsening, initial partitioning, and refinement algorithm configuration.

It is possible to plug user-defined algorithms into any of these stages. I just requires a bit of framework glue code. If you are interested in doing this, I would be happy do provide guidance.

SebastianSchlag assigned SebastianSchlag and kittobi1992 Jun 6, 2019

SebastianSchlag added the enhancement label Jun 6, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Initial Partitioning: Perform n-level RB-based partitioning multiple times #38

Initial Partitioning: Perform n-level RB-based partitioning multiple times #38

Uh oh!

Uh oh!

Initial Partitioning: Perform n-level RB-based partitioning multiple times #38

Initial Partitioning: Perform n-level RB-based partitioning multiple times #38

Comments

Uh oh!

Uh oh!

Uh oh!