Complex Data-structure Scheduling – CODAS

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.