[Networkit] Algorithms based on shortest path aggregation are *embarrassingly* parallel

Maximilian Vogel maximilian.vogel at student.kit.edu
Thu Oct 8 22:13:41 CEST 2015


Hi,

> Tests are okay, but I am not yet confident that it is correct. Would 
> be thankful for peer review.
I've changed two things[1], that should be reviewed aswell:
- SignalHanding::assureRunning() throws an exception when it received 
SIGINT. This probably won't work wit OpenMP. Therefore, 
SignalHandling::isRunning() is utilized. If it returns false, the 
function computeDependencies just returns.
- utilize SSSP::getStack() instead of creating it separately.

I also think that the merging of the local data, the extrapolation step 
and the optional normalization could be simplified or merged, maybe 
increasing performance a little bit if done right.

> Should it be parallel? Max has raised the point that the memory 
> footprint grows with the number of threads:
The alternative for ApproxBetweenness2 is utilizing the 
direction-optimizing BFS (which is parallel) as the memory footprint 
won't grow. The drawback probably is that the potential performance 
increase might be less than just running several sequential BFS in 
parallel. But more measurements in that regard have to be done.

[1]: 
https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/changeset/c1318e04a347dc4c8e08fc4fcaec5d4bbec34087


Max



More information about the NetworKit mailing list