Wed 17 Jun 2015 15:15 - 15:40 at PLDI Main BLUE (Portland 254-255) - Parallelism Chair(s): Sara Baghsorkhi

We describe a system that uses automated planning to synthesize correct and efficient parallel graph programs from high-level algorithmic specifications. We have used this system to synthesize parallel programs for four graph problems: triangle counting, maximal independent set computation, preflow-push maxflow, and connected components. Experiments on realistic graph inputs show that the synthesized implementations exhibit speedups of up to 45x and often outperform hand-written, highly-tuned implementations.