Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism
<jats:p>Most systems that support speculative parallelization, like hardware transactional memory (HTM), do not support nested parallelism. This sacrifices substantial parallelism and precludes composing parallel algorithms. And the few HTMs that do support nested parallelism focus on parallel...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135232 |
| _version_ | 1811075151860596736 |
|---|---|
| author | Subramanian, Suvinay Jeffrey, Mark C Abeydeera, Maleen Lee, Hyun Ryong Ying, Victor A Emer, Joel Sanchez, Daniel |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Subramanian, Suvinay Jeffrey, Mark C Abeydeera, Maleen Lee, Hyun Ryong Ying, Victor A Emer, Joel Sanchez, Daniel |
| author_sort | Subramanian, Suvinay |
| collection | MIT |
| description | <jats:p>Most systems that support speculative parallelization, like hardware transactional memory (HTM), do not support nested parallelism. This sacrifices substantial parallelism and precludes composing parallel algorithms. And the few HTMs that do support nested parallelism focus on parallelizing at the coarsest (shallowest) levels, incurring large overheads that squander most of their potential.</jats:p>
<jats:p>We present FRACTAL, a new execution model that supports unordered and timestamp-ordered nested parallelism. FRACTAL lets programmers seamlessly compose speculative parallel algorithms, and lets the architecture exploit parallelism at all levels. FRACTAL can parallelize a broader range of applications than prior speculative execution models. We design a FRACTAL implementation that extends the Swarm architecture and focuses on parallelizing at the finest (deepest) levels. Our approach sidesteps the issues of nested parallel HTMs and uncovers abundant fine-grain parallelism. As a result, FRACTAL outperforms prior speculative architectures by up to 88x at 256 cores.</jats:p> |
| first_indexed | 2024-09-23T10:01:39Z |
| format | Article |
| id | mit-1721.1/135232 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:01:39Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1352322023-09-26T20:24:07Z Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism Subramanian, Suvinay Jeffrey, Mark C Abeydeera, Maleen Lee, Hyun Ryong Ying, Victor A Emer, Joel Sanchez, Daniel Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory <jats:p>Most systems that support speculative parallelization, like hardware transactional memory (HTM), do not support nested parallelism. This sacrifices substantial parallelism and precludes composing parallel algorithms. And the few HTMs that do support nested parallelism focus on parallelizing at the coarsest (shallowest) levels, incurring large overheads that squander most of their potential.</jats:p> <jats:p>We present FRACTAL, a new execution model that supports unordered and timestamp-ordered nested parallelism. FRACTAL lets programmers seamlessly compose speculative parallel algorithms, and lets the architecture exploit parallelism at all levels. FRACTAL can parallelize a broader range of applications than prior speculative execution models. We design a FRACTAL implementation that extends the Swarm architecture and focuses on parallelizing at the finest (deepest) levels. Our approach sidesteps the issues of nested parallel HTMs and uncovers abundant fine-grain parallelism. As a result, FRACTAL outperforms prior speculative architectures by up to 88x at 256 cores.</jats:p> 2021-10-27T20:22:34Z 2021-10-27T20:22:34Z 2017 2021-04-06T12:35:11Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/135232 en 10.1145/3140659.3080218 ACM SIGARCH Computer Architecture News Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Subramanian, Suvinay Jeffrey, Mark C Abeydeera, Maleen Lee, Hyun Ryong Ying, Victor A Emer, Joel Sanchez, Daniel Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism |
| title | Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism |
| title_full | Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism |
| title_fullStr | Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism |
| title_full_unstemmed | Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism |
| title_short | Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism |
| title_sort | fractal an execution model for fine grain nested speculative parallelism |
| url | https://hdl.handle.net/1721.1/135232 |
| work_keys_str_mv | AT subramaniansuvinay fractalanexecutionmodelforfinegrainnestedspeculativeparallelism AT jeffreymarkc fractalanexecutionmodelforfinegrainnestedspeculativeparallelism AT abeydeeramaleen fractalanexecutionmodelforfinegrainnestedspeculativeparallelism AT leehyunryong fractalanexecutionmodelforfinegrainnestedspeculativeparallelism AT yingvictora fractalanexecutionmodelforfinegrainnestedspeculativeparallelism AT emerjoel fractalanexecutionmodelforfinegrainnestedspeculativeparallelism AT sanchezdaniel fractalanexecutionmodelforfinegrainnestedspeculativeparallelism |