SSSP implementation in Ligra and Galois

[lushl9301]

Hi Yunming,
I've been testing the sssp implementation of Ligra and Galois on a 10-thread machine and a 24-thread machine. It shows that Bellman-ford algorithm in Ligra takes more than 200 seconds on both machines for solving a single SSSP query on USA road network.
The results of Delta-stepping on Galois is roughly 2 to 3 seconds.
As you mentioned in the Paper, "We run Galois with the Bellman-Ford algorithm so that the algorithms are the same across systems." would like to share how is the implementation you used for testing GraphIt with Ligra and Galois? I suppose it would be similar to Ligra that takes about hundreds of seconds?

[lushl9301]

I'm using g++ 7.5 openmp for both Ligra and Galois.

[yunmingzhang17]

Hi,

Thanks for testing GraphIt out! This is an issue pointed out by some of our collaborators as well. It turns out we made a poor decision at the time to use weight equals one for the road networks in this particular table, resulting in completing SSSP on road with bellman-ford in less than 1 second. This was because we couldn't input the original weighted graph in a consistent way through all the frameworks, and setting the weight equals one was the only mechanism at the time to enforce that every framework uses the same weighted graph. We apologize that we didn't document this clearly in the original GraphIt paper.

Since the original GraphIt paper, we have worked extensively to address this issue with SSSP. Recently, we published a second paper ("Optimizing Ordered Graph Algorithms with GraphIt") at CGO2020 to support delta-stepping and other ordered graph algorithms (https://dl.acm.org/doi/10.1145/3368826.3377909). This time, all the numbers in SSSP and other algorithms are collected running on the original road network weights, or log scale weights. In the CGO2020 paper, the running times for Bellman-Ford on road networks are about 120 seconds for GraphIt and Ligra in our 24-core machine as shown in Table 4, which is consistent with your observation.

In this second paper, we have introduced an improved version of delta-stepping with a new optimization, bucket fusion, that reduces synchronization overhead. This allows GraphIt to run delta-stepping on road networks in 0.224 seconds on our 24-core machine, achieving the fastest performance on SSSP over existing work, including Galois. A few other collaborators tested this implementation on different hardware platforms and verified this result.

[lushl9301]

extraordinary work! thanks. I will check it out.
Thanks for the explanations in details.