Parallel algorithm: calculations on graph

Question

I have general parallel programming question.

Suppose there is a directed graph with cycles. Let’s assume that each node has fairly small amount of incoming edges ~ from 0 to 20 and potentially pretty big amount of outgoing edges ~ from 0 to 500. Let’s say that each node is a function that getting all incoming edges as input parameters, calculates result and then if calculated result differs from previous result of this function it will need to invoke recalculation of all the functions on the outgoing edges.

I need functions to be calculated pretty much in waves from changed function to all that connected to it in the first wave and then all functions connected to functions of first wave and so on. Currently I have this done sequentially, with two lists: current wave with all functions that is calculating now and next wave that is going to be calculated in the next wave. Everything is working correctly, but I want to make it parallel - to be calculated on all available cores.

The problem I am facing is actually each function is very simple and so it gets calculated very fast and so time of calculation is comparable with time to adding to the next wave. As a result, running on 4 cores is slower that sequential code.

Is there a parallel algorithm that can deal with such graphs?

Answer 1

Assuming your graph is sufficiently large, you want to perform edge-contraction until each node represents a sufficently large unit of work to amortize your parallel overhead. Then process the graph normally, but assigning groups of vertices to a thread to process rather than a single one at a time.

The reason you need the graph to be large is, edge contraction is linear time, and it sounds like your problem is also linear time (with a similar constant factor). But since edge-contraction parallelizes well, you should be able to use it to make your program achieve near linear speedup, thus being faster on sufficiently large graphs.

This becomes quite similar to the graph partitioning probelm (of which edge contraction is often a step). There exist several parallel graph partitioning packages which scale relatively well:

• http://glaros.dtc.umn.edu/gkhome/views/metis
• http://algo2.iti.kit.edu/documents/kahip/index.html

Answer 2

First I would profile the parallel code, to see, where it's loosing time. Then start optimising:

You could split the algorithm in two phases: 1. Phase: calculate functions on each node, where something has changed. 2. Phase: propagate values, by fetching from every node, where inputs have changed. Then iterate. Each Phase is worked upon by multiple threads, synchronised after each phase.

Your queue based solution could be worked upon by multiple threads. Problem is to order or prioritize nodes in such away, that you can start calculating the next wave while still some nodes from first wave need processing.

Etc.