Pingan looked into the push-pull MS-BFS as part of his thesis. An excerpt from the conclusion:
The optimal β is 1.25, at which point the
bottom-up method is slightly faster. There are two main reasons for the unsatisfactory
performance of the bottom-up method. First, when using the bottom-up method, we need
to note mf and mu during the iteration, adding two additional trips to traverse the vertex
list in effect. Second, as we can learn from previous experiments, the algorithm does
not have a very large performance gain with 32 threads when there is no synchronization
mechanism, giving less potential for improvement. So we do not enable bottom-up search
in the final comparison with the serial version.
The bottom-up method has one synchronization step less but does not show significant improvements over only top-down MS-BFS. For now we leave this as is, but might come back on it in the future.
Pingan looked into the push-pull MS-BFS as part of his thesis. An excerpt from the conclusion:
The bottom-up method has one synchronization step less but does not show significant improvements over only top-down MS-BFS. For now we leave this as is, but might come back on it in the future.