Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors
When compiling a progam consisting of multiple nested loops for execution on a multiprocessor, processor allocation is the problem of determining the number of processors over which to partition each nested loop. This paper presents processor allocation techniques for compiling such programs for mul...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149194 |
| _version_ | 1826206590794989568 |
|---|---|
| author | Prasanna, G.N. Srinivasa Agarwal, Anant |
| author_facet | Prasanna, G.N. Srinivasa Agarwal, Anant |
| author_sort | Prasanna, G.N. Srinivasa |
| collection | MIT |
| description | When compiling a progam consisting of multiple nested loops for execution on a multiprocessor, processor allocation is the problem of determining the number of processors over which to partition each nested loop. This paper presents processor allocation techniques for compiling such programs for multiprocessors with local memory. Programs consisting of multiple loops, where the precedence constraints between the loops is known, can be viewed as macro dataflow graphs. Macro dataflow graphs comprise several macro nodes (or macro operations) that must be executed subject to prespecified precedence constraints. Optimal processor allocation specifies the number of processors computing each macro node and their sequencing to optimize run time. This paper presents computing each macro node and their sequencing to optimize run time. This paper presents computationally efficient techniques for determining the optimal processor allocation using estimated speedup functions of the macro nodes. These ideas have been implemented in a 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-23T13:35:00Z |
| id | mit-1721.1/149194 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:35:00Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1491942023-03-30T03:37:22Z Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors Prasanna, G.N. Srinivasa Agarwal, Anant When compiling a progam consisting of multiple nested loops for execution on a multiprocessor, processor allocation is the problem of determining the number of processors over which to partition each nested loop. This paper presents processor allocation techniques for compiling such programs for multiprocessors with local memory. Programs consisting of multiple loops, where the precedence constraints between the loops is known, can be viewed as macro dataflow graphs. Macro dataflow graphs comprise several macro nodes (or macro operations) that must be executed subject to prespecified precedence constraints. Optimal processor allocation specifies the number of processors computing each macro node and their sequencing to optimize run time. This paper presents computing each macro node and their sequencing to optimize run time. This paper presents computationally efficient techniques for determining the optimal processor allocation using estimated speedup functions of the macro nodes. These ideas have been implemented in a 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:36:09Z 2023-03-29T14:36:09Z 1992-06 https://hdl.handle.net/1721.1/149194 MIT-LCS-TM-469 application/pdf |
| spellingShingle | Prasanna, G.N. Srinivasa Agarwal, Anant Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors |
| title | Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors |
| title_full | Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors |
| title_fullStr | Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors |
| title_full_unstemmed | Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors |
| title_short | Compile-time Techniques for Processor Allocation in Macro Dataflow Graphs for Multiprocessors |
| title_sort | compile time techniques for processor allocation in macro dataflow graphs for multiprocessors |
| url | https://hdl.handle.net/1721.1/149194 |
| work_keys_str_mv | AT prasannagnsrinivasa compiletimetechniquesforprocessorallocationinmacrodataflowgraphsformultiprocessors AT agarwalanant compiletimetechniquesforprocessorallocationinmacrodataflowgraphsformultiprocessors |