Phased Computation Graphs in the Polyhedral Model
We present a translation scheme that allows a broad class of dataflow graphs to be considered under the optimization framework of the polyhedral model. The input to our analysis is a Phased Computation Graph, which we define as a generalization of the most widely used dataflow representations, inclu...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149319 |
| _version_ | 1826215832244453376 |
|---|---|
| author | Thies, William Lin, Jasper Amarasinghe, Saman |
| author_facet | Thies, William Lin, Jasper Amarasinghe, Saman |
| author_sort | Thies, William |
| collection | MIT |
| description | We present a translation scheme that allows a broad class of dataflow graphs to be considered under the optimization framework of the polyhedral model. The input to our analysis is a Phased Computation Graph, which we define as a generalization of the most widely used dataflow representations, including synchronous dataflow, cyclo-static dataflow, and computation graphs. The output of our analysis is a System of Affine Recurrence Equations (SARE) that exactly captures the data dependencies between the nodes of the original graph. Using the SARE representation, one can apply many techniques from the scientific community that are new to the DSP domain. For example, we propose simple optimizations such as node splitting, decimation propagation, and stead-state invariant code motion that leverage the fine-grained dependence information of the SARE to perform novel transformations on a stream graph. We also propose ways in which the polyhedral model can offer new approaches to classic problems of the DSP community, such as minimizing buffer size, code size, and optimizing the schedule. |
| first_indexed | 2024-09-23T16:37:48Z |
| id | mit-1721.1/149319 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:37:48Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1493192023-03-30T03:04:49Z Phased Computation Graphs in the Polyhedral Model Thies, William Lin, Jasper Amarasinghe, Saman We present a translation scheme that allows a broad class of dataflow graphs to be considered under the optimization framework of the polyhedral model. The input to our analysis is a Phased Computation Graph, which we define as a generalization of the most widely used dataflow representations, including synchronous dataflow, cyclo-static dataflow, and computation graphs. The output of our analysis is a System of Affine Recurrence Equations (SARE) that exactly captures the data dependencies between the nodes of the original graph. Using the SARE representation, one can apply many techniques from the scientific community that are new to the DSP domain. For example, we propose simple optimizations such as node splitting, decimation propagation, and stead-state invariant code motion that leverage the fine-grained dependence information of the SARE to perform novel transformations on a stream graph. We also propose ways in which the polyhedral model can offer new approaches to classic problems of the DSP community, such as minimizing buffer size, code size, and optimizing the schedule. 2023-03-29T14:42:53Z 2023-03-29T14:42:53Z 2002-08 https://hdl.handle.net/1721.1/149319 MIT-LCS-TM-630 application/pdf |
| spellingShingle | Thies, William Lin, Jasper Amarasinghe, Saman Phased Computation Graphs in the Polyhedral Model |
| title | Phased Computation Graphs in the Polyhedral Model |
| title_full | Phased Computation Graphs in the Polyhedral Model |
| title_fullStr | Phased Computation Graphs in the Polyhedral Model |
| title_full_unstemmed | Phased Computation Graphs in the Polyhedral Model |
| title_short | Phased Computation Graphs in the Polyhedral Model |
| title_sort | phased computation graphs in the polyhedral model |
| url | https://hdl.handle.net/1721.1/149319 |
| work_keys_str_mv | AT thieswilliam phasedcomputationgraphsinthepolyhedralmodel AT linjasper phasedcomputationgraphsinthepolyhedralmodel AT amarasinghesaman phasedcomputationgraphsinthepolyhedralmodel |