The Challenges of Non-linear Parameters and Variables in Automatic Loop Parallelisation

With the rise of manycore processors, parallelism is becoming a mainstream necessity. Unfortunately, parallel programming is inherently more difficult than sequential programming; therefore, techniques for automatic parallelisation will become indispensable. This doctoral thesis aims at extending the well-known polyhedron model, which promises this automation, beyond some of its current restrictions. Up to now, loop bounds and array subscripts in the modelled codes must be expressions linear in both the variables and the parameters. This restriction is lifted to allow certain polynomial expressions instead of linear ones. With these extensions, more programs can be handled in dependence analysis, in the transformation of the program model and in code generation.