Beyond Polyhedral Analysis of OpenStream Programs

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Polyhedral techniques are, when applicable, an effective instrument for automatic parallelization and data locality optimization of sequential programs. This paper motivates their adoption in OpenStream, a task-parallel streaming language following the dataflow model of execution. We show that (1) it is possible to exploit the parallelism that naturally arises from dataflow task graphs with loop tiling transformations provided by the polyhedral model and (2) that a combination of dataflow task-parallelism and polyhedral optimizations performs significantly better than polyhedral parallelization techniques applied to sequential programs and dataflow task-parallelism without polyhedral optimization techniques. Our technique obtains parallel speedups superior to 1.2× when compared to state-of-the-art polyhedral-tiled OpenMP, and 1.6× when compared to manually tiled OpenStream implementations , for a simple Gauss-Seidel kernel. However, stream indexing is often polynomial in the general case, severely limiting the set of OpenStream programs amenable to polyhedral tools and hindering the automation of our technique. We further investigate how the approach of Feautrier may offer a path not only to automatically convert fine-grained task-level concurrency to coarser-grained tasks, but also for scheduling under resource constraints.

Bibliographical metadata

Original languageEnglish
Title of host publicationIMPACT 2019 - 9th International Workshop on Polyhedral Compilation Techniques
Place of PublicationValencia, Spain
Publication statusPublished - 23 Jan 2019