Approaching Symbolic Parallelization by Synthesis of Recurrence Decompositions

Grigory Fedyukovich
(UW)
Rastislav Bodík
(UW)

We present GraSSP, a novel approach to perform automated parallelization relying on recent advances in formal verification and synthesis. GraSSP augments an existing sequential program with an additional functionality to decompose data dependencies in loop iterations, to compute partial results, and to compose them together. We show that for some classes of the sequential prefix sum problems, such parallelization can be performed efficiently.

In Ruzica Piskac and Rayna Dimitrova: Proceedings Fifth Workshop on Synthesis (SYNT 2016), Toronto, Canada, July 17-18, 2016, Electronic Proceedings in Theoretical Computer Science 229, pp. 55–66.
Published: 22nd November 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.229.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org