I’ll be collecting some posts while I’m at super computing here … given my background, I’ll be focusing on the network and matrix algorithms.
Direction-optimized BFS by Scott Beamer and the Berkeley ParLab
They use a combined push and pull BFS scheme to accelerate a BFS on a graph. This is a very good idea — I’m surprised it hasn’t been used before as I thought it was the standard in doing fast shortest path queries. That is, you grow from both end-points and then see where they meet. Of course, they call it top-down vs. bottom-up. The push-pull terminology I’m using comes from gossip algorithms. To be clear, the idea is to push the frontier out initially, then to pull from the frontier in an interim region of the BFS expansion (when the frontier gets large, unvisited nodes are likely to have a frontier neighbor), then finally, push the BFS expansion out again to handle the stragglers.
The new graph 500 benchmark is out. Using one million cores, you can do a BFS at 15 trillion edges per second on a graph with one trillion vertices and 32 trillion edges — if I’ve understood correctly.
See Jason Riedy’s proposal for the new shortest path benchmark for more info about a future proposed test in the Graph500 benchmark.
One issue with Graph500 is that algorithmic performance improvements are allowed.