Simplification of Polyhedral Reductions in Practice
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909405572759552 |
|---|---|
| author | Narmour, Louis Job, Ryan Yuki, Tomofumi Rajopadhye, Sanjay |
| author_facet | Narmour, Louis Job, Ryan Yuki, Tomofumi Rajopadhye, Sanjay |
| contents | Reductions combine collections of inputs with an associative (and here, also commutative) operator to produce collections of outputs. When the same value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. We provide the first complete push-button implementation of reduction simplification in a compiler. We evaluate its effectiveness on a range of real-world applications, and show that simplification rediscovers several key results in algorithmic improvement across multiple domains, previously only obtained through clever manual human analysis and effort. We also discover alternate, previously unknown algorithms, albeit without improving the asymptotic complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_17498 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Simplification of Polyhedral Reductions in Practice Narmour, Louis Job, Ryan Yuki, Tomofumi Rajopadhye, Sanjay Programming Languages Reductions combine collections of inputs with an associative (and here, also commutative) operator to produce collections of outputs. When the same value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. We provide the first complete push-button implementation of reduction simplification in a compiler. We evaluate its effectiveness on a range of real-world applications, and show that simplification rediscovers several key results in algorithmic improvement across multiple domains, previously only obtained through clever manual human analysis and effort. We also discover alternate, previously unknown algorithms, albeit without improving the asymptotic complexity. |
| title | Simplification of Polyhedral Reductions in Practice |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2411.17498 |