Simplifying multiple-statement reductions with the polyhedral model
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, May, 2020
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/127316 |
| _version_ | 1826207194168688640 |
|---|---|
| author | Yang, Jianqiao(Jianqiao Cambridge) |
| author2 | Michael Carbin. |
| author_facet | Michael Carbin. Yang, Jianqiao(Jianqiao Cambridge) |
| author_sort | Yang, Jianqiao(Jianqiao Cambridge) |
| collection | MIT |
| description | Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, May, 2020 |
| first_indexed | 2024-09-23T13:45:31Z |
| format | Thesis |
| id | mit-1721.1/127316 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:45:31Z |
| publishDate | 2020 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1273162020-09-16T03:16:55Z Simplifying multiple-statement reductions with the polyhedral model Yang, Jianqiao(Jianqiao Cambridge) Michael Carbin. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Electrical Engineering and Computer Science. Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, May, 2020 Cataloged from the official PDF of thesis. Includes bibliographical references (pages 77-82). 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 techniques make it possible to optimize reductions, such as prefix sum, in which each component of 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 statements. In such cases, existing approaches can generate incorrect code that violates the data dependencies of the original, unoptimized program. In this work, we identify and formalize the multiple-statement reduction problem as a bilinear optimization problem. We present a heuristic optimization algorithm for these reductions, and we demonstrate that the algorithm provides optimal complexity for a set of benchmark programs from the literature on probabilistic inference algorithms, whose performance critically rely on simplifying these reductions. Specifically, the complexities for 10 of the 11 programs evaluated improve significantly 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 that the speedups in wall-clock time ranges from 30x to over 108x. by Jianqiao (Cambridge) Yang. S.M. S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science 2020-09-15T21:51:50Z 2020-09-15T21:51:50Z 2020 2020 Thesis https://hdl.handle.net/1721.1/127316 1191905955 eng MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided. http://dspace.mit.edu/handle/1721.1/7582 82 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Yang, Jianqiao(Jianqiao Cambridge) Simplifying multiple-statement reductions with the polyhedral model |
| title | Simplifying multiple-statement reductions with the polyhedral model |
| title_full | Simplifying multiple-statement reductions with the polyhedral model |
| title_fullStr | Simplifying multiple-statement reductions with the polyhedral model |
| title_full_unstemmed | Simplifying multiple-statement reductions with the polyhedral model |
| title_short | Simplifying multiple-statement reductions with the polyhedral model |
| title_sort | simplifying multiple statement reductions with the polyhedral model |
| topic | Electrical Engineering and Computer Science. |
| url | https://hdl.handle.net/1721.1/127316 |
| work_keys_str_mv | AT yangjianqiaojianqiaocambridge simplifyingmultiplestatementreductionswiththepolyhedralmodel |