Poros is a nearly bug-for-bug port of METIS into Rust.
Poros is a set of serial programs for partitioning graphs, partitioning finite element meshes, and producing fill reducing orderings for sparse matrices. The algorithms implemented in Poros are based on the multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning schemes developed in the Karypis Lab at UMN.
Poros is not ready for production use.
While the C API is stable, not every function is implemented or well-tested.
The Node-based and mesh routines are somewhat under-tested, and I'm unsure if I
will support the routines provided for ParMETIS (METIS_NodeNDP and
METIS_NodeRefine) since it is unfree software.
Since this is still early, I will not be abiding by semver for 0.0.X
releases. Additionally, I do not currently have functionality for changing
idx_t or real_t. Poros also does not have FORTRAN support (symbols or
1-indexed graphs)
There is also likely still "minor" UB that needs to be addressed.
That being said, if you have applications that use METIS, please try them with Poros and share any issues you run into.
- Nearly bug-for-bug implementations METIS routines
- Some functionality less broken than METIS
- ABI compatibility with METIS 5.2.1 (need to verify)
- Less segfault-y than METIS
- Not Slopcoded
I am not yet regularly running benchmarks. However, Poros is currently around
25% slower than METIS (measuring with hyperfine gpmetis).
This is a rough roadmap of the major milestones
- Literal C port. Nearly every function is literally interchangeable.
- Part of the testing process is literally swapping out individual functions
- Break internal ABI to allow more use of Rust types and less flagrant
Undefined Behavior
- I expect this to become mostly safe
- Still largely going to be unidiomatic Rust
- Still going to have identical observable behavior to upstream
- Likely first nonzero version
- Will be moved to a hard fork and renamed to distinguish from the original
- Optimize into fast and idiomatic Rust (in progress)
- There are a bunch of idioms that make sense in C but not in Rust, let's change those
- To make porting easier, I removed a number of optimizations, most notably around arena allocation. I may try to reintroduce that here.
- I would not expect the Rust version to be faster than the C version until this step nears completion.
- Add a decent Rust API and prepare packaging
- Designing a usable Rust API has been a challenge that's been on my mind throughout the porting process, but I'm still unsure of how to make it idiomatic and match the overhead of the original API.
- I'll also have to figure out how to handle Metis's hard-coded
idx_ttype
While Poros should be able to be built on any system, running the full test
suite should be done under the Nix shell. With that, cargo build should be
sufficient to build. Note that during the porting process, assumptions are made
about the directory structure of the output, so installation most likely will
not work.
It is recommended that you build under the Nix shell.
Some of the larger test graphs are stored in a separate repository for size and
licensing reasons. To run the tests outside of the Nix shell, clone
https://github.com/gfaster/metis-testgraphs and set
METIS_TESTGRAPHS_DIR=/extracted/directory/goes/here.
The normalization feature used for testing against the original METIS
requires running in the Nix shell.
Again, this software is not yet suitable for production. Do not use it because it will break and you will be sad.
Copyright 1998-2020, Regents of the University of Minnesota
Copyright 2023-2026, Gavin Rohrer
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.