OMS (Online Multi-Section) is a shared-memory streaming algorithm for process mapping and hierarchical graph partitioning via recursive multi-section. Part of the KaHIP organization.
| What it solves | Streaming process mapping and graph partitioning for large-scale hierarchical topologies |
| Techniques | Recursive multi-section, Fennel scoring, OpenMP parallelization, multi-pass restreaming |
| Interfaces | CLI (streammultisection) |
| Requires | C++17, CMake 3.10+, OpenMP |
brew install KaHIP/kahip/omsgit clone https://github.com/KaHIP/OnlineMultiSection.git
cd OnlineMultiSection
./compile.shAlternatively, use the standard CMake build process:
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
make -j$(nproc)The resulting binary is deploy/streammultisection.
# Process mapping (1024 PEs, hierarchy 4:16:16, distances 1:10:100)
./deploy/streammultisection graph.graph --k=1024 --enable_mapping \
--hierarchy_parameter_string=4:16:16 --distance_parameter_string=1:10:100
# Graph partitioning (recursive b-section, default b=4)
./deploy/streammultisection graph.graph --k=1024
# Graph partitioning with b=2 (recursive bisection)
./deploy/streammultisection graph.graph --k=1024 --stream_rec_bisection_base=2
# Multi-pass restreaming with b=5
./deploy/streammultisection graph.graph --k=1024 --stream_rec_bisection_base=5 --num_streams_passes=2
# Full parameter list
./deploy/streammultisection --help- 64-bit edge IDs are enabled by default.
- For the METIS graph format, refer to the KaHIP manual.
If you use OMS in your research, please cite:
@inproceedings{OnlineMultiSection2022,
author = {Marcelo Fonseca Faraj and Christian Schulz},
title = {Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms
for Hierarchical Graph Partitioning and Process Mapping},
booktitle = {{IEEE} International Conference on Cluster Computing ({CLUSTER} 2022)},
pages = {473--483},
publisher = {{IEEE}},
year = {2022},
doi = {10.1109/CLUSTER51413.2022.00057}
}OMS is distributed under the MIT License. See LICENSE for details.