There are many algorithms for the space-time mapping of nested loops, some of them even with optimality results within their framework. This paper derives a preprocessing phase for these algorithms, which allows them to find space-time mappings which sometimes execute orders of magnitude faster. The basic idea is to split the iteration domain of the loop nests into parts and apply the already existing space-time mapping algorithms to the set of all these parts.
Similar (but very limited) approaches can be found in parallelization techniques \cite{Jem95,Jem96}, but the use of a proper mathematical framework gives us much wider applicability and clearer and better results at acceptable analysis cost.
Erika Cetindag, Martin Griebl