How to navigate a graph in parallel with 2 or n processes

Question

I am searching the Internet to find some algorithm that can cross the graph in parallel using 2 or n processes without one process moving to the previously visited node of the other so that I can speed up the general task of scanning the entire graph, but I can not find anything . Is there any algorithm that can help me do such a task in parallel? it's worth it?

Note: n processes use the same memory of visited and available nodes

Thank you

Answer 1

You can try the consumer manufacturer’s model to move around the schedule - but with some changes from the clean model:

• Reading and writing to the queue in blocks, and not in an element at a time, also update visited , installed in blocks. This will save you time synchronization, which will be necessary to perform less often.
• When you change the queue (and the visited set), you must do extra work to make sure that you are not adding data that has already been visited since the last installed set.

Please note that with this approach, you are likely to search several vertices several times, but you can associate it with the frequency at which the queue and visited are updated.

Is it worth it? It is difficult to say in these things - it depends on many things (schedule structure, size, queue implementation, ...).

You should run some tests and try to fine tune the "how often to update" parameter and check what is better empirically. You should use statistical tools (the wilcoxon test is usually facto for this) and determine if the other is better than the other.

Answer 2

If the main part of the time is not spent on the actual bypass, you can cross the graph in one thread and put a queue to work in each node, which will be processed in parallel from several processes. When you are in line, you can use a simple consumer-producer model.