Static Analysis of OpenStream Programs

Albert Cohen 1 Alain Darte 2 Paul Feautrier 2
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
2 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Le but de ce rapport est d'évaluer la possibilité d'appliquer des techniques polyédriques au langage parallèle OpenStream [25]. Lorsqu'elles sont applicables, ces techniques sont très utiles pour les analyses à la compilation et l'optimisation du code pour une meilleure adaptation à l'architecture cible. OpenStream est un langage à deux niveaux dans lequel un programme de contrôle dirige l'initialisation d'instances de tâches parallèles qui communiquent au travers de streams qui peuvent avoir des écrivains et lecteurs multiples. OpenStream a une sémantique assez complexe dans sa forme la plus générale, mais nous nous restreignons au cas où le programme de contrôle est séquentiel, cas représentatif de la majorité des applications OpenStream. Avec cette restriction, les programmes OpenStream sont déterministes par construction, mais peuvent avoir des deadlocks (étreintes mortelles). Nous montrons que si le code de contrôle est polyédrique, on peut calculer de façon statique, pour chaque instance d'une tâche, les indices de lecture et d'écriture dans chaque stream, et donc raisonner sur les dépendances entre instances de tâches (les seules contraintes d'ordonnancement dans ce fragment polyédrique). Ces indices peuvent être des polynômes de degré arbitraire, ce qui requiert d'étendre aux polynômes les techniques polyédriques classiques d'analyse de dépendances, d'ordonnancement, de détection de deadlocks. Les solveurs SMT modernes permettent de résoudre de tels problèmes, bien que sans garantie de succès. L'approche de Feautrier [10] peut offrir une alternative. Nous montrons de plus deux résultats importants relatifs aux deadlocks dans OpenStream: 1) une caractérisation des deadlocks en termes de chemins de dépendances qui implique que les streams peuvent être bornés a priori, sans créer de deadlocks à l'exécution, dès lors qu'un ordonnancement existe avec de telles tailles, 2) la démonstration que la détection de deadlocks est indécidable, même pour le fragment polyédrique d'OpenStream.
Type de document :
Rapport
[Research Report] RR-8764, CNRS; Inria; ENS Lyon. 2016, pp.26
Liste complète des métadonnées


https://hal.inria.fr/hal-01184408
Contributeur : Alain Darte <>
Soumis le : mercredi 6 janvier 2016 - 13:22:09
Dernière modification le : mercredi 28 septembre 2016 - 16:17:20
Document(s) archivé(s) le : jeudi 7 avril 2016 - 15:58:33

Fichier

RR-8764.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01184408, version 2

Collections

Citation

Albert Cohen, Alain Darte, Paul Feautrier. Static Analysis of OpenStream Programs. [Research Report] RR-8764, CNRS; Inria; ENS Lyon. 2016, pp.26. <hal-01184408v2>

Partager

Métriques

Consultations de
la notice

261

Téléchargements du document

144