If applicable, the polyhedral model provides powerful mathematical abstractions enabling effective optimization of loop nests with respect to given optimization goal, of which one of the most important ones is to enable parallelization. Nevertheless one of the most important parallelism enabling transformations, namely reduction recognition and exploitation, is out of scope of polyhedral schedulers so far.
In this paper we develop different increments of a reduction aware polyhedral scheduler. We show how to recognize opportunities, precisely model the resulting dependences and enable Polly, a state-of-the-art polyhedral optimizer based on LLVM, to take reduction possibilities into account during optimization.
All implemented approaches are evaluated on the full Polybench benchmark suite with respect to runtime, communication overhead and memory consumption.