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

Christian Staudt christian.staudt at kit.edu
Thu Oct 15 08:55:46 CEST 2015


My overnight analysis of a 3.3 billion edge network was crashed by ApproxBetweenness2. I believe the algorithm did exhaust the 256 GB RAM, because the graph already takes about 90GB. I think that answers the question whether default parallelism is better: no. I am going to make it optional.

Chris


On 09 Oct 2015, at 01:59, Arie Slobbe <aslobbe at macalester.edu> wrote:

> 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
> 
> _______________________________________________
> 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/20151015/b90b283b/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151015/b90b283b/attachment-0001.sig>


More information about the NetworKit mailing list