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
  • $\begingroup$ METIS is used precisely for such problems. $\endgroup$
    – Vikram
    Commented Apr 18, 2017 at 10:19
  • $\begingroup$ thanks, but I'm looking for some simple algorithm which I would be able to implement myself, not a big 3rd party library. Nevertheless, form the webpage I can read multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning so perhaps I should look on these. Still I would like point out which specific algorithm, and idealy get some short code sample. $\endgroup$ Commented Apr 19, 2017 at 11:12

1 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/


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.