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
Abstract : This paper studies the applicability of polyhedral techniques to the parallel language Open- Stream [25]. When applicable, polyhedral techniques are invaluable for compile-time debugging and for generating efficient code well suited to a target architecture. OpenStream is a two-level language in which a control program directs the initialization of parallel task instances that communicate through streams, with possibly multiple writers and readers. It has a fairly complex semantics in its most general setting, but we restrict ourselves to the case where the control program is sequential, which is representative of the majority of the OpenStream applications. This restriction offers deterministic concurrency by construction, but deadlocks are still possible. We show that, if the control program is polyhedral, one may statically compute, for each task instance, the read and write indices to each of its streams, and thus reason statically about the dependences among task instances (the only scheduling constraints in this polyhedral subset). These indices may be polynomials of arbitrary degree, thus requiring to extend to polynomials the standard polyhedral techniques for dependence analysis, scheduling, and deadlock detection. Modern SMT allow to solve polynomial problems, albeit with no guarantee of success; the approach of Feautrier [10] may offer an alternative solution. We also establish two important results related to deadlocks in OpenStream: 1) a characterization of deadlocks in terms of dependence paths, which implies that streams can be safely bounded as soon as a schedule exists with such sizes, 2) the proof that deadlock detection is undecidable, even for polyhedral OpenStream.
Type de document :
Communication dans un congrès
6th International Workshop on Polyhedral Compilation Techniques (IMPACT'16), held with HIPEAC'16, Jan 2016, Prague, Czech Republic. Available as http://impact.gforge.inria.fr/impact2016/papers/impact2016-cohen.pdf, Proceedings of the IMPACT series. <http://impact.gforge.inria.fr/impact2016>
Liste complète des métadonnées

https://hal.inria.fr/hal-01251845
Contributeur : Alain Darte <>
Soumis le : mercredi 6 janvier 2016 - 18:27:23
Dernière modification le : mercredi 28 septembre 2016 - 15:33:24

Identifiants

  • HAL Id : hal-01251845, version 1

Collections

Citation

Albert Cohen, Alain Darte, Paul Feautrier. Static Analysis of OpenStream Programs. 6th International Workshop on Polyhedral Compilation Techniques (IMPACT'16), held with HIPEAC'16, Jan 2016, Prague, Czech Republic. Available as http://impact.gforge.inria.fr/impact2016/papers/impact2016-cohen.pdf, Proceedings of the IMPACT series. <http://impact.gforge.inria.fr/impact2016>. <hal-01251845>

Partager

Métriques

Consultations de la notice

475