🧬 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.

However, not only is it hard to construct graphs in Rust, but it's also hard to construct dynamic graphs. And even hard to construct massive graphs which can be dynamically manipulated in parallel. If you are working on a single node at a time, things become quite simple in parallel. You can wrap each node in a lock, such as a mutex. But, it is quite common to have to process bigger and bigger neighbourhoods around vertices. One way to do this is 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, resulting in a 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.