Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory
This paper presents a hierarchical approach for compiling macro dataflow graphs for multiprocessors with local memory. Macro dataflow graphs comprise several nodes (or macros operations) that must be executed subject to prespecified precedence constraints. Programs consisting of multiple nested loop...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149190 |
| _version_ | 1811074658748858368 |
|---|---|
| author | Prasanna, G.N. Srinivasa Agarwal, Anant Musicus, Bruce R. |
| author_facet | Prasanna, G.N. Srinivasa Agarwal, Anant Musicus, Bruce R. |
| author_sort | Prasanna, G.N. Srinivasa |
| collection | MIT |
| description | This paper presents a hierarchical approach for compiling macro dataflow graphs for multiprocessors with local memory. Macro dataflow graphs comprise several nodes (or macros operations) that must be executed subject to prespecified precedence constraints. Programs consisting of multiple nested loops, where the precedence constraints between the loops are known, can be viewed as macro dataflow graphs. The hierarchical compilation approach comprises a processor allocation phase followed by a partitioning phase. In the processor allocation phase, using estimated speedup functions for the macro nodes, computationally efficient techniques establish the sequencing and parallelism of macro operations for close-to-optimal run times. The second phase partitions the computations in each macro node to maximize communication locality for the level of parallelism determined by the processor allocation phase. The same approach can also be used for programs consisting of multiple loop nests, when each of the nested loops can be characterized by a speedup function. These ideas have been implemented in a prototype structure-driven compiler, SDC, for expressions of matrix operations. The paper presents the performance of the compiler for several matrix expressions on a simulator of the Alewife multiprocessor. |
| first_indexed | 2024-09-23T09:53:19Z |
| id | mit-1721.1/149190 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:53:19Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491902023-03-30T04:07:10Z Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory Prasanna, G.N. Srinivasa Agarwal, Anant Musicus, Bruce R. This paper presents a hierarchical approach for compiling macro dataflow graphs for multiprocessors with local memory. Macro dataflow graphs comprise several nodes (or macros operations) that must be executed subject to prespecified precedence constraints. Programs consisting of multiple nested loops, where the precedence constraints between the loops are known, can be viewed as macro dataflow graphs. The hierarchical compilation approach comprises a processor allocation phase followed by a partitioning phase. In the processor allocation phase, using estimated speedup functions for the macro nodes, computationally efficient techniques establish the sequencing and parallelism of macro operations for close-to-optimal run times. The second phase partitions the computations in each macro node to maximize communication locality for the level of parallelism determined by the processor allocation phase. The same approach can also be used for programs consisting of multiple loop nests, when each of the nested loops can be characterized by a speedup function. These ideas have been implemented in a prototype structure-driven compiler, SDC, for expressions of matrix operations. The paper presents the performance of the compiler for several matrix expressions on a simulator of the Alewife multiprocessor. 2023-03-29T14:35:51Z 2023-03-29T14:35:51Z 1992-12 https://hdl.handle.net/1721.1/149190 25855884 MIT-LCS-TM-464 application/pdf |
| spellingShingle | Prasanna, G.N. Srinivasa Agarwal, Anant Musicus, Bruce R. Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory |
| title | Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory |
| title_full | Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory |
| title_fullStr | Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory |
| title_full_unstemmed | Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory |
| title_short | Hierarchical Compilation of Macro Dataflow Graphs for Multiprocessors with Local Memory |
| title_sort | hierarchical compilation of macro dataflow graphs for multiprocessors with local memory |
| url | https://hdl.handle.net/1721.1/149190 |
| work_keys_str_mv | AT prasannagnsrinivasa hierarchicalcompilationofmacrodataflowgraphsformultiprocessorswithlocalmemory AT agarwalanant hierarchicalcompilationofmacrodataflowgraphsformultiprocessorswithlocalmemory AT musicusbrucer hierarchicalcompilationofmacrodataflowgraphsformultiprocessorswithlocalmemory |