Multifor for Multicore

We propose a new programming control structure called “multifor”, allowing to take advantage of parallelization mod-els that were not naturally attainable with the polytope model before. In a multifor-loop, several loops whose bodies are run simultaneously can be defined. Respective iteration domains are mapped onto each other according to a run frequency – the grain – and a relative position – the off-set –. Execution models like dataflow, stencil computations or MapReduce can be represented onto one referential it-eration domain, while still exhibiting traditional polyhedral code analysis and transformation opportunities. Moreover, this construct provides ways to naturally exploit hybrid par-allelization models, thus significantly improving paralleliza-tion opportunities in the multicore era. Traditional polyhe-dral software tools are used to generate the corresponding code. Additionally, a promising perspective related to non-linear mapping of iteration spaces is also presented, yielding to run a loop nest inside any other one by solving the prob-lem of inverting “ranking Ehrhart polynomials”