[POPL'25] Maximal Simplification of Polyhedral Reductions

Louis Narmour presents a method for simplifying polyhedral reductions to lower their asymptotic complexity.

Maximal Simplification of Polyhedral Reductions (Video, POPL 2025) Louis Narmour, Tomofumi Yuki, and Sanjay Rajopadhye (Colorado State University, USA / University of Rennes - Inria - CNRS - IRISA, France; Unaffiliated, Japan; Colorado State University, USA) Abstract: Reductions combine collections of input values with an associative and often commutative operator to produce collections of results. When the same input value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. Simplification often produces a program with lower asymptotic complexity. Typical compiler optimizations yield, at best, a constant fold speedup, but a complexity improvement from, say, cubic to quadratic complexity yields unbounded speedup for sufficiently large problems. It is well known that reductions in polyhedral programs may be simplified automatically, but previous methods cannot exploit all available reuse. This paper resolves this long-standing open problem, thereby attaining minimal asymptotic complexity in the simplified program. We propose extensions to prior work on simplification to support any independent commutative reduction. At the heart of our approach is piece-wise simplification, the notion that we can split an arbitrary reduction into pieces and then independently simplify each piece. However, the difficulty of using such piece-wise transformations is that they typically involve an infinite number of choices. We give constructive proofs to deal with this and select a finite number of pieces for simplification. Article: doi.org/10.1145/3704839 Supplementary archive: doi.org/10.5281/zenodo.14200133 (Badges: Artifacts Available, Artifacts Evaluated — Functional) ORCID: orcid.org/0009-0009-3298-5282, orcid.org/0000-0002-5737-6178, orcid.org/0000-0002-4246-6066 Video Tags: polyhedral compilation, algorithmic complexity, program transformation, popl25main-p13-p, doi:10.1145/3704839, doi:10.5281/zenodo.14200133, orcid:0009-0009-3298-5282, orcid:0000-0002-5737-6178, orcid:0000-0002-4246-6066, Artifacts Available, Artifacts Evaluated — Functional Presentation at the POPL 2025 conference, January 19-25, 2025, popl25.sigplan.org/ Sponsored by , sigplan.org/