DS07 - Société de l'information et de la communication

Complex Data-structure Scheduling – CODAS

Submission summary

The advent of parallelism in supercomputers, in embedded systems, and in more classical end-user computers increases the need for high-level code optimization and improved compilers. Being able to deal with the complexity of the upcoming software and hardware is one of the main challenges of the compilation community.

The Hipeac Roadmap (http://www.hipeac.net/system/files/hipeac_roadmap1_0.pdf) reports that exposing and optimizing data movement in applications
both at runtime and compile time will remain a hot topic for the next decades. Thus, there is an increasing need for better scheduling techniques for all kinds of programs, especially those manipulating huge amounts of data.

The long-term objective of our project is to develop a general way to reason about and manipulate programs with general control flow and complex data structures beyond arrays. We plan to enhance the polyhedral framework, known to be effective for regular regions, both theoretically and algorithmically in order to deal with more general programs.

For the period of the current proposal, our project proposes to study the scheduling of programs in the presence of specific complex data structures such as lists and trees. We propose to use the polyhedral model as a baseline to represent data dependencies and formalize the notion of schedule, and to build on existing work in the abstract interpretation and rewriting termination communities to properly reason about the complex data structures. The objective is to find a compact solution to represent data and computations at the same time, and then to provide algorithms to schedule programs from this representation.

The research will be an experimental loop from benchmarks to theory followed by experimental evaluation. The experimental evaluation includes as proof of concept the application to termination proofs and also a code generator prototype that demonstrate the applicability of our method on simple cases.

Project coordinator

Madame Laure Gonnord (ENSL / Laboratoire d'informatique du parallélisme)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.


ENSL/LIP ENSL / Laboratoire d'informatique du parallélisme

Help of the ANR 174,960 euros
Beginning and duration of the scientific project: February 2018 - 42 Months

Useful links

Explorez notre base de projets financés



ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter