[Networkit] Algorithms based on shortest path aggregation are *embarrassingly* parallel
aslobbe at macalester.edu
Fri Oct 9 01:59:57 CEST 2015
Whether or not maximum parallelism should be the default, I think that many
users would appreciate a section in the documentation that explains the
exact trade-off between computation speed and memory requirement (as with
the formula z + 3z * t you mentioned). Also, one or two examples, e.g.
"network 'Name' with n nodes and m edges takes X MB RAM when using Y
threads", could be useful.
On Thu, Oct 8, 2015 at 3:13 PM, Maximilian Vogel <
maximilian.vogel at student.kit.edu> wrote:
> 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.
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the NetworKit