Static Analysis of OpenStream Programs
Analyse statique de programmes OpenStream
Résumé
The object of this report is to evaluate the possibility of applying polyhedral
techniques to the parallel language OpenStream, which is developed by INRIA
Parkas. When applicable, these techniques are invaluable for compile-time
debugging and for improving the target code for a better adaptation to the
target architecture.
OpenStream is a two-level language, in which a sequential control code
directs the initialization of parallel task instances that communicate through
\emph{streams}. OpenStream programs are deterministic by construction, but
may have deadlocks. If the control code is polyhedral, one may statically
compute, for each task instance, its read and write indices for each stream.
These indices may be polynomials of arbitrary degree. When linear, the full
power of the polyhedral model may be brought to bear for dependence and
dataflow analysis, scheduling and deadlock detection, and program
transformations.
In the general case, one can think of two approaches: the first one consists in
over-approximating dependences until problems become linear. In the second
approach, one first leverage modern developments in SMT solvers, which allow
them to solve polynomial problems, albeit with no guarantee of success.
Furthermore, the task index functions have special properties that may be used
to construct original analysis algorithms. Three preliminary results in this
direction are 1) the proof that deadlock detection is undecidable in general,
2) a characterization of deadlocks in terms of dependence graphs, which implies
that streams can be safely bounded as soon as a schedule exists with such
sizes, and 3) a preliminary analysis of some solvable cases.
Origine : Fichiers produits par l'(les) auteur(s)