Skip to Main content Skip to Navigation
Documents associated with scientific events

Beyond Polyhedral Analysis of OpenStream Programs

Nuno Nobre 1 Andi Drebes 2 Graham Riley 1 Antoniu Pop 1
2 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : 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.
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Andi Drebes <>
Submitted on : Tuesday, November 19, 2019 - 2:47:33 PM
Last modification on : Thursday, July 1, 2021 - 5:58:09 PM


Files produced by the author(s)


  • HAL Id : hal-02370558, version 1



Nuno Nobre, Andi Drebes, Graham Riley, Antoniu Pop. Beyond Polyhedral Analysis of OpenStream Programs. 9th International Workshop on Polyhedral Compilation Techniques, Jan 2019, Valencia, Spain. ⟨hal-02370558⟩



Record views


Files downloads