[Boost-users] [Parallel BGL] Poor scalability of dijkstra and delta stepping parallel graph algorithms

Subject: [Boost-users] [Parallel BGL] Poor scalability of dijkstra and delta stepping parallel graph algorithms
From: Alexander Frolov (alexndr.frolov_at_[hidden])
Date: 2016-09-21 17:14:55

Hi!

I am evaluating scalability on various graph algorithms and found that base
parallel SSSP algorithms in PBGL does not scale well in my cases. The plots
for rmat (scale=20 and 22) are attached. The source code for the benchmark
are attached as well.

The main issue that makes me think that I'm doing smth wrong is that
execution time of delta stepping algorithm is _increasing_ with node
number.  I tried to check the code but has not found anything suspicious.

Can anybody help me with this issue?

Best,
   Alexander