[Networkit] Algorithms based on shortest path aggregation are *embarrassingly* parallel
maximilian.vogel at student.kit.edu
Thu Oct 8 22:13:41 CEST 2015
> Tests are okay, but I am not yet confident that it is correct. Would
> be thankful for peer review.
I've changed two things, 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.
More information about the NetworKit