Beyond Polyhedral Analysis of OpenStream Programs - Archive ouverte HAL Access content directly
Documents Associated With Scientific Events Year :

Beyond Polyhedral Analysis of OpenStream Programs

(1) , (2) , (1) , (1)
Nuno Miguel Nobre
  • Function : Author
  • PersonId : 1058583
Graham Riley
  • Function : Author
  • PersonId : 1058584
Antoniu Pop
  • Function : Author
  • PersonId : 997186


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.
Fichier principal
Vignette du fichier
IMPACT_2019_paper_7.pdf (1.25 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02370558 , version 1 (19-11-2019)


  • HAL Id : hal-02370558 , version 1


Nuno Miguel 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⟩
57 View
57 Download


Gmail Facebook Twitter LinkedIn More