simple and fast graph-clustering for paralelization of finite element simulations

Question

I'm learning to use OpenCL to optimize some of my simulations. I realized that I need some sort of Graph-clustering or graph-partitioning to exploit efficiently local memory for un-ordered meshes.

example: I implemented elastic cloth simulation with regular mesh of 4-bonded vertexes, which I can separate manually to localized batches. Now I would like to move to general irregular mesh where each node can have any number of edges.

From quick search I found some resources but I'm not sure if it adress very well my needs (I have no experience in area of discrete math and graph theory).

What I want:

• split mesh to batches such that
  1. all batches has approximately same size (number of nodes and edges) e.g. 16 nodes each correspoding to local_size of my OpenCL kernell
  2. the number of edges between different batches is minimal - to minimize overlap between nodes loaded by each workgroup
• Algorithm which is concise and easy to implement by myself - for me this is just side issue not main topic. I do not what to create dependence on some 3rd party software or library even if it is open-source.
  • it does not have to lead to optimal solution, it can be stochastic and rough heuristic
  • it should be fast - $O(n)$ with small prefactor

Answer 1

For a simple (yet not optimal, see below) mesh partitioning algorithm, you can do:

1) sort all the cells of the mesh using Hilbert sort
2) partition the sorted list of cells into chunks of the desired size

Spatial Hilbert sorting is implemented in my GEOGRAM library [1,2] and in CGAL [3]. It is reasonably easy to implement, using the std::nth_element() function of the STL. See also [3] for a nice explanation of spatial sorting.

The solution is not optimal in the sense that it completely ignores the connections between the chunks and thus does not minimize communication between processes, but I think it is an interesting alternative because it is extremely fast (but it is O(n log(n)) rather than O(n) as requested). It can be implemented in a handful of lines, whereas METIS uses a certain amount of memory and has a processing time that sometimes cancels the gain it has on the communications.

To complete this answer, I mention also SCOTCH [4], it has interesting alternative graph partitioning algorithms (but it is not fully satisfactory for you if you do not want to have an external dependency as you said in the question).

[1] http://alice.loria.fr/software/geogram/doc/html/index.html

[2] http://alice.loria.fr/software/graphite/doc/html/mesh__reorder_8h.html

[3] http://doc.cgal.org/latest/Spatial_sorting/index.html

[4] http://www.labri.fr/perso/pelegrin/scotch/