Simplifying dependent reductions in the polyhedral model
© 2021 Owner/Author. A Reduction-an accumulation over a set of values, using an associative and commutative operator-is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics. Contemporary polyhedral-based co...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/134205 |
| _version_ | 1826216445790388224 |
|---|---|
| author | Yang, Cambridge Atkinson, Eric Carbin, Michael |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Yang, Cambridge Atkinson, Eric Carbin, Michael |
| author_sort | Yang, Cambridge |
| collection | MIT |
| description | © 2021 Owner/Author. A Reduction-an accumulation over a set of values, using an associative and commutative operator-is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics. Contemporary polyhedral-based compilation techniques make it possible to optimize reductions, such as prefix sums, in which each component of the reduction's output potentially shares computation with another component in the reduction. Therefore an optimizing compiler can identify the computation shared between multiple components and generate code that computes the shared computation only once. These techniques, however, do not support reductions that-when phrased in the language of the polyhedral model-span multiple dependent statements. In such cases, existing approaches can generate incorrect code that violates the data dependences of the original, unoptimized program. In this work, we identify and formalize the optimization of dependent reductions as an integer bilinear program. We present a heuristic optimization algorithm that uses an affine sequential schedule of the program to determine how to simplfy reductions yet still preserve the program's dependences. We demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically relies on simplifying these reductions. The complexities for 10 of the 11 programs improve siginifcantly by factors at least of the sizes of the input data, which are in the range of 104 to 106 for typical real application inputs. We also confirm the significance of the improvement by showing speedups in wall-clock time that range from 1.1x to over 106x. |
| first_indexed | 2024-09-23T16:47:48Z |
| format | Article |
| id | mit-1721.1/134205 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:47:48Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1342052023-08-11T17:16:09Z Simplifying dependent reductions in the polyhedral model Yang, Cambridge Atkinson, Eric Carbin, Michael Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2021 Owner/Author. A Reduction-an accumulation over a set of values, using an associative and commutative operator-is a common computation in many numerical computations, including scientific computations, machine learning, computer vision, and financial analytics. Contemporary polyhedral-based compilation techniques make it possible to optimize reductions, such as prefix sums, in which each component of the reduction's output potentially shares computation with another component in the reduction. Therefore an optimizing compiler can identify the computation shared between multiple components and generate code that computes the shared computation only once. These techniques, however, do not support reductions that-when phrased in the language of the polyhedral model-span multiple dependent statements. In such cases, existing approaches can generate incorrect code that violates the data dependences of the original, unoptimized program. In this work, we identify and formalize the optimization of dependent reductions as an integer bilinear program. We present a heuristic optimization algorithm that uses an affine sequential schedule of the program to determine how to simplfy reductions yet still preserve the program's dependences. We demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically relies on simplifying these reductions. The complexities for 10 of the 11 programs improve siginifcantly by factors at least of the sizes of the input data, which are in the range of 104 to 106 for typical real application inputs. We also confirm the significance of the improvement by showing speedups in wall-clock time that range from 1.1x to over 106x. 2021-10-27T20:03:58Z 2021-10-27T20:03:58Z 2021 2021-09-27T14:50:12Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/134205 en 10.1145/3434301 Proceedings of the ACM on Programming Languages Creative Commons Attribution NoDerivatives 4.0 International License. http://creativecommons.org/licenses/by-nd/4.0/ application/pdf Association for Computing Machinery (ACM) ACM |
| spellingShingle | Yang, Cambridge Atkinson, Eric Carbin, Michael Simplifying dependent reductions in the polyhedral model |
| title | Simplifying dependent reductions in the polyhedral model |
| title_full | Simplifying dependent reductions in the polyhedral model |
| title_fullStr | Simplifying dependent reductions in the polyhedral model |
| title_full_unstemmed | Simplifying dependent reductions in the polyhedral model |
| title_short | Simplifying dependent reductions in the polyhedral model |
| title_sort | simplifying dependent reductions in the polyhedral model |
| url | https://hdl.handle.net/1721.1/134205 |
| work_keys_str_mv | AT yangcambridge simplifyingdependentreductionsinthepolyhedralmodel AT atkinsoneric simplifyingdependentreductionsinthepolyhedralmodel AT carbinmichael simplifyingdependentreductionsinthepolyhedralmodel |