Networks & Matrices @ Supercomputing

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.

Graph 500

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.

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s