Beyond Polyhedral Analysis of OpenStream Programs - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Document Associé À Des Manifestations Scientifiques Année : 2019

Beyond Polyhedral Analysis of OpenStream Programs

Nuno Miguel Nobre
  • Fonction : Auteur
  • PersonId : 1058583
Graham Riley
  • Fonction : Auteur
  • PersonId : 1058584
Antoniu Pop
  • Fonction : Auteur
  • PersonId : 997186

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02370558 , version 1

Citer

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⟩
60 Consultations
65 Téléchargements

Partager

Gmail Facebook X LinkedIn More