# Polly's Polyhedral Scheduling in the Presence of Reductions

arXiv: https://arxiv.org/abs/1505.07716 · HTML: https://mlsanity.com/paper/1505.07716/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2015.

## Built on by (most cited first, 3 of 3)

- [DNNFusion: Accelerating Deep Neural Networks Execution with Advanced Operator Fusion](https://mlsanity.com/paper/2108.13342/) (2021)
- [mlirSynth: Automatic, Retargetable Program Raising in Multi-Level IR using Program Synthesis](https://mlsanity.com/paper/2310.04196/) (2023)
- [ParaCodex: A Profiling-Guided Autonomous Coding Agent for Reliable Parallel Code Generation and Translation](https://mlsanity.com/paper/2601.04327/) (2026)

## Abstract (arXiv)

The polyhedral model provides a powerful mathematical abstraction to enable effective optimization of loop nests with respect to a given optimization goal, e.g., exploiting parallelism. Unexploited reduction properties are a frequent reason for polyhedral optimizers to assume parallelism prohibiting dependences. To our knowledge, no polyhedral loop optimizer available in any production compiler provides support for reductions. In this paper, we show that leveraging the parallelism of reductions can lead to a significant performance increase. We give a precise, dependence based, definition of reductions and discuss ways to extend polyhedral optimization to exploit the associativity and commutativity of reduction computations. We have implemented a reduction-enabled scheduling approach in the Polly polyhedral optimizer and evaluate it on the standard Polybench 3.2 benchmark suite. We were able to detect and model all 52 arithmetic reductions and achieve speedups up to 2.21× on a quad core machine by exploiting the multidimensional reduction in the BiCG benchmark.