🧬 Parallel Graphs

How to efficiently use graphs in parallel is more of an advanced topic and poses a wide range of challenges. If your graph is read-only, and reasonably sized, you can optimize your performance by reducing the amount of pointer jumps you do and increase your cache coherence. One possible avenue is to construct your graph through indices.

Constructing graphs correctly and safely in Rust is difficult because the compiler forces you to confront issues you might not think about in other languages. Constructing dynamic graphs is even harder. It's even harder to construct massive graphs which can be dynamically manipulated in parallel. One approach can be to wrap subsections (subgraphs) of your graph in a lock, such as a mutex. But, it is quite common to have to process bigger and bigger neighbourhoods around vertices. One approach can be to alternative between read and write stages. In one stage, each thread reads a relevant neighbourhood, does some processing, and adds changes to a list. Once all changes have been proposed, one or more threads can execute the changes from the list, resulting in a modified or new graph. One such solution is described here.

Sampling and repacking extremely huge graphs for training graph neural networks on GPUs is also a research topic on its own. Meshes, widely used in graphics, is another type of graph. In order to maintain spatial coherency, and improve performance, another active field is how to best sort meshes (graphs) and choosing the right sizes into cohesive meshlets (neighbourhoods), which can be culled individually instead of the entire mesh being culled. Check out this general intro to parallel graph processing.