Projet de recherche doctoral numero :3000


Date depot: 1 janvier 1900
Titre: Polyhedral compilation for a data-flow model of execution
Directeur de thèse: Albert COHEN (Google)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini

Resumé: Future embedded and high-performance microprocessors will include, not 2 or 4, but hundreds of computing units, organized as heterogeneous clusters of general-purpose cores and more specialized accelerators. State-of-the-art parallelizing compilers are rarely capable of generating scalable and/or efficient code, for essential reasons deeply rooted into the semantics of programming languages, the undecidability of static analyses and the complexity of modern computer architectures. As a result, most programmers rely on low-productivity programming models that have not evolved significantly in two decades. These models suffer from well known flaws (non-deterministic, not compositional, not modular), and induce massive productivity and robustness losses compared to sequential programming languages. The dynamic data-flow model of execution is a parallel operational semantics for Kahn process networks. We are working on extending this model with more flexible scheduling constraints, such as transactional execution (for in-place operations, reductions, or more complex data structure operations). In this extended model, static guarantees must be obtained about determinism, boundedness of communication buffers and bounded time reactivity. The polyhedral model of compilation is an ideal tool to extract such properties automatically from a high-level description of the denotational invariants of the program. It is also a well known framework to design advanced code generation algorithms. Both assests make it very suitable to adapt the concurrency of the source program to the target architecture, leveraging a rich algebra of static data-flow properties. This thesis will start from the mapping of a polyhedral representation to a data-flow model of execution, then progressively extend the code generator and optimization heuristics to support other forms of scheduling constraints (transactions). The polyhedral representation itself will capture static properties from a data-flow extension of the source language, in the form of an extended set of OpenMP pragmas. Experiments and validation of the proposed algorithms will take place in the GNU Compiler Collection (GCC). The student will participate to the development of the Graphite optimization framework of this compiler.

Doctorant.e: Li Feng