Analyse statique de programmes OpenStream

Corresponding publication at IMPACT'16 (http://impact.gforge.inria.fr/impact2016)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 andfor generating efficient code well suited to a target architecture. OpenStream is a two-level languagein which a control program directs the initialization of parallel task instances that communicatethrough streams, with possibly multiple writers and readers. It has a fairly complex semantics in itsmost 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 offersdeterministic concurrency by construction, but deadlocks are still possible.We show that, if the control program is polyhedral, one may statically compute, for each taskinstance, the read and write indices to each of its streams, and thus reason statically about thedependences among task instances (the only scheduling constraints in this polyhedral subset).These indices may be polynomials of arbitrary degree, thus requiring to extend to polynomialsthe standard polyhedral techniques for dependence analysis, scheduling, and deadlock detection.Modern SMT allow to solve polynomial problems, albeit with no guarantee of success; the approachof Feautrier [10] may offer an alternative solution. We also establish two important results relatedto 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.Le but de ce rapport est d'évaluer la possibilité d'appliquer destechniques polyédriques au langage parallèleOpenStream [25]. Lorsqu'elles sont applicables, cestechniques sont très utiles pour les analyses à la compilation etl'optimisation du code pour une meilleure adaptation à l'architecturecible. OpenStream est un langage à deux niveaux dans lequel unprogramme de contrôle dirige l'initialisation d'instances de tâchesparallèles qui communiquent au travers de streams qui peuventavoir des écrivains et lecteurs multiples. OpenStream a une sémantiqueassez complexe dans sa forme la plus générale, mais nous nousrestreignons au cas où le programme de contrôle est séquentiel, casreprésentatif de la majorité des applications OpenStream. Aveccette restriction, les programmes OpenStream sont déterministes parconstruction, mais peuvent avoir des deadlocks (étreintes mortelles).Nous montrons que si le code de contrôle est polyédrique, on peut calculer defaçon statique, pour chaque instance d'une tâche, les indices de lecture etd'écriture dans chaque stream, et donc raisonner sur les dépendances entreinstances de tâches (les seules contraintes d'ordonnancement dans ce fragmentpolyédrique). Ces indices peuvent être des polynômes de degré arbitraire, cequi requiert d'étendre aux polynômes les techniques polyédriques classiquesd'analyse de dépendances, d'ordonnancement, de détection de deadlocks. Lessolveurs SMT modernes permettent de résoudre de tels problèmes, bien que sansgarantie de succès. L'approche de Feautrier [10] peut offrir unealternative. Nous montrons de plus deux résultats importants relatifs auxdeadlocks dans OpenStream: 1) une caractérisation des deadlocks en termes dechemins de dépendances qui implique que les streams peuvent être bornés apriori, sans créer de deadlocks à l'exécution, dès lors qu'un ordonnancementexiste avec de telles tailles, 2) la démonstration que la détection dedeadlocks est indécidable, même pour le fragment polyédrique d'OpenStream