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

Arie Slobbe 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:

> 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
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151008/5839dfc6/attachment-0001.html>

More information about the NetworKit mailing list