Synthesizing parallel graph programs via automated planning
Authors:
Open Access
- 3 June 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 50 (6) , 533-544
Abstract
We describe a system that uses automated planning to synthesize correct and efficient parallel graph programs from high-level algorithmic specifications. Automated planning allows us to use constraints to declaratively encode program transformations such as scheduling, implementation selection, and insertion of synchronization. Each plan emitted by the planner satisfies all constraints simultaneously, and corresponds to a composition of these transformations. In this way, we obtain an integrated compilation approach for a very challenging problem domain. 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 a variety of inputs show that the synthesized implementations perform competitively with hand-written, highly-tuned code.Keywords
This publication has 28 references indexed in Scilit:
- Stochastic superoptimization2013
- Parallel schedule synthesis for attribute grammars2013
- From relational verification to SIMD loop synthesis2013
- Elixir2012
- Concurrent data representation synthesis2012
- Integrated Code Generation for LoopsACM Transactions on Embedded Computing Systems, 2012
- Internally deterministic parallel algorithms can be fast2012
- Inferring locks for atomic sections2008
- DenaliACM Transactions on Programming Languages and Systems, 2006
- Denali2002