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?