[flotus1]

Edit for clarification: what I am looking for must meet the following requirements:
-Multi-constraint graph partitioning
-parallel execution. Or at least run significantly faster than gpmetis serial on graphs with 100M+ vertices
-binary file formats for output and especially graph input would be nice

Current state
Right now, I am using gpmetis (http://glaros.dtc.umn.edu/gkhome/metis/metis/overview) to partition my meshes for MPI parallel solver runs.

It works, but I am getting increasingly annoyed with a few limitations. One of them: it is not multi-threaded, so for 100 million and more cells, the time taken up by domain decomposition dominates the non-interactive pre-processing steps.
"Just use the OpenMP parallel version instead" I hear you say. Not so easy, because I need the "ubvec" parameter. Which is implemented in gpmetis serial, but not in OpenMP. At least last time I checked the documentation.

What do I need ubvec for?
skip to question below if you don't need my lengthy and convoluted explanation. It boils down to multi-constraint graph partitioning
Our mesh refinement approach works with distinct grid "levels", where the cell size (and time step size) in each level is half that of the next coarser level.
Let's say for example we have a mesh that consists of 3 different levels. The algorithm performs 2 iterations on the finest level, then one iteration on the medium level. At this point, these two levels are at the same overall time level. To complete a full time step, the finest level does another two iterations, then the medium level does another one. And lastly, the coarsest grid level is iterated once, bringing all grid levels to the same time level, and completing a full time step.
tl;dr: finest level: 4 iterations, medium level: 2 iterations, coarsest level: 1 iteration for a full time step.
This needs to be accounted for in the domain decomposition. cells in the finest level get a weight of 4, medium level gets a weight of 2, and the coarsest level gets weight 1. Only with "ubvec=..." does gpmetis respect each of these weights, resulting in proper load balancing.
If I omit "ubvec", gpmetis still balances the overall sum of weights, i.e. each domain gets approximately the same sum of (Ncells x weigh). But it might decide e.g. that one domain exclusively consists of cells from the coarsest level. Which would leave the core working on this subset idle most of the time. I.e. very poor load balancing.
Only with "ubvec=..." does each domain get approximately the same amount of cells from each level respectively.
Example with numbers
finest level: 1 million cells, medium level: 2 million cells, coarsest level: 8 million cells
For partitioning into 2 domains, gpmetis without ubvec would be happy to put all 8 million cells of the coarsest level into one domain, and the rest into the other. The weighted sum of cells checks out, but load balancing for our algorithm is crap.
With e.g. -ubvec="1.005 1.005 1.005", things work as I need them: each domain gets about the same amount of cells from each level.

Question
So, if you could either point me towards an alternative for gpmetis that does what I need
-or-
tell me that I overlooked something with the OpenMP version of gpmetis, which lets me achieve the same type of load balancing without the "ubvec" parameter.

Another issue I have with metis is the file format for the input graph file. As far as I can tell, there is only an ASCII format available. This file gets huge, and at least with fortran, I am having a hard time writing it somewhat efficiently. I.e. in the same ballpark as the theoretical performance limit of the file system/drives.

Edit: when recommending alternatives, please keep in mind that pretty much the only reason why I chose gpmetis in the first place was this: the documentation is not great, but still miles ahead of any alternatives I found so far. And I need some documentation to work with...

[sbaffini]

Not sure why you call it gpmetis instead of simply metis but, doesn't the OpenMP version work well enough? Not that I ever used it, but seems what you might be looking for.

Still, while again I never used it, it sounds strange that parmetis doesn't have some weight to use for load balancing. You sure it doesn't?

[sbaffini]

Also, I just superficially checked the parmetis manual and I see ubvec there.

[flotus1]

Originally Posted by sbaffini

Not sure why you call it gpmetis instead of simply metis but, doesn't the OpenMP version work well enough? Not that I ever used it, but seems what you might be looking for.

My bad, I mixed them up. What does not support ubvec is the OpenMP parallel version of gpmetis.
Now I would need to check parmetis again. To be perfectly honest with you, I am no longer sure why I ruled that one out in the first place. But I am certain that I had very good reasons to do so

As for why I call it gpmetis... that's the name of the binary you get once you compile the source from the link in my first post. As far as I understood, there are quite a few projects that implement "metis", each one called slightly differently.

[sbaffini]

Oh yes, it's because I never use it as standalone executable that I didn't recall the name.

Maybe you excluded parmetis because of its very restrictive licence

[JBeilke]

One possibility to skip metis ... is to do meshing/solving/postprocessing in decomposed form. Thats how you can do it in ccm+

[flotus1]

I'll need to have another look at parmetis over the weekend. I really can't recall any more why I dropped it so fast.
Edit: I see what you mean by restrictive license. So no parmetis for me unfortunately. See, I had a very good reason to rule it out back then

One possibility to skip metis ... is to do meshing/solving/postprocessing in decomposed form.

You got me a little bit confused here: what exactly do you refer to as "decomposed form"?
The terminology in my head says that I use metis precisely to get that: a decomposition of the whole mesh into load-balanced smaller chunks. I.e. the decomposed form. So at first glance, I don't see where I could skip metis.

[arjun]

any possibility to try this:


https://kahip.github.io/

[JBeilke]

Originally Posted by flotus1

I'll need to have another look at parmetis over the weekend. I really can't recall any more why I dropped it so fast.


You got me a little bit confused here: what exactly do you refer to as "decomposed form"?
The terminology in my head says that I use metis precisely to get that: a decomposition of the whole mesh into load-balanced smaller chunks. I.e. the decomposed form. So at first glance, I don't see where I could skip metis.

You could decompose the geometry infront of the meshing and from this point do everything in decomposed mode. So you don't have to decompose/reconstruct a huge mesh.

[flotus1]

decompose the geometry infront

I see, thanks for the clarification.
That could probably work. But it rather feels like a clunky workaround instead of a solution. It will make the whole process more involved and error-prone. And due to adding additional "information boundaries", it will have a negative impact on the quality of the decomposition. I might give that a go as a last resort. But I am not yet desperate enough

any possibility to try this:
https://kahip.github.io/

If you say that it can do what I need it to do, I will look into it.
My problem really is: there are quite a few projects that do "graph partitioning" in general. But once you get into the specifics of my requirements -see first post- many of them don't cut it. "Just giving it a try" takes quite some time with these things.

[JBeilke]

Originally Posted by flotus1

I see, thanks for the clarification.
That could probably work. But it rather feels like a clunky workaround instead of a solution. It will make the whole process more involved and error-prone. And due to adding additional "information boundaries", it will have a negative impact on the quality of the decomposition. I might give that a go as a last resort. But I am not yet desperate enough

I think that the Formula 1 people were desperate enough to request this feature :-) Maybe because no head node was big enough to hold the complete model.

[flotus1]

Maybe. But I am not at that limit yet with my tools and model sizes. The largest memory requirement in my toolchain is still well below 1GB per 1 million cells.

[arjun]

Originally Posted by flotus1

If you say that it can do what I need it to do, I will look into it.
My problem really is: there are quite a few projects that do "graph partitioning" in general. But once you get into the specifics of my requirements -see first post- many of them don't cut it. "Just giving it a try" takes quite some time with these things.

They do have parallel partioning and if i remember correctly they have benchmark against really large graphs too.

[flotus1]

I just scanned through the manual for kahip (only available for v3.0, while latest software version is 3.1), as well as the landing page.
As of 3.1, they seem to have implemented a binary file format for their parallel partitioning routine. As well as weighted graphs in ASCII format. So I still won't be able to get around my file i/O problems with this.
But what's worse: I don't see any option resembling what "ubvec" does for gpmetis. Neither for their serial, nor for their parallel tools. I need weighted graphs, and I need multiple constraints, one for each grid "level".