Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
© 2018 Association for Computing Machinery. In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135029 |
| _version_ | 1826210978569650176 |
|---|---|
| author | Blelloch, Guy E Gu, Yan Shun, Julian Sun, Yihan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Blelloch, Guy E Gu, Yan Shun, Julian Sun, Yihan |
| author_sort | Blelloch, Guy E |
| collection | MIT |
| description | © 2018 Association for Computing Machinery. In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, k-d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-Parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are ω times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, and α-labeling, which we believe will be useful for designing other parallel write-efficient algorithms. |
| first_indexed | 2024-09-23T14:58:28Z |
| format | Article |
| id | mit-1721.1/135029 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:58:28Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1350292023-10-13T20:20:20Z Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry Blelloch, Guy E Gu, Yan Shun, Julian Sun, Yihan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 Association for Computing Machinery. In this paper, we design parallel write-efficient geometric algorithms that perform asymptotically fewer writes than standard algorithms for the same problem. This is motivated by emerging non-volatile memory technologies with read performance being close to that of random access memory but writes being significantly more expensive in terms of energy and latency. We design algorithms for planar Delaunay triangulation, k-d trees, and static and dynamic augmented trees. Our algorithms are designed in the recently introduced Asymmetric Nested-Parallel Model, which captures the parallel setting in which there is a small symmetric memory where reads and writes are unit cost as well as a large asymmetric memory where writes are ω times more expensive than reads. In designing these algorithms, we introduce several techniques for obtaining write-efficiency, including DAG tracing, prefix doubling, and α-labeling, which we believe will be useful for designing other parallel write-efficient algorithms. 2021-10-27T20:10:24Z 2021-10-27T20:10:24Z 2018 2019-07-03T14:38:01Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/135029 en 10.1145/3210377.3210380 Annual ACM Symposium on Parallelism in Algorithms and Architectures Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Blelloch, Guy E Gu, Yan Shun, Julian Sun, Yihan Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry |
| title | Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry |
| title_full | Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry |
| title_fullStr | Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry |
| title_full_unstemmed | Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry |
| title_short | Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry |
| title_sort | parallel write efficient algorithms and data structures for computational geometry |
| url | https://hdl.handle.net/1721.1/135029 |
| work_keys_str_mv | AT blellochguye parallelwriteefficientalgorithmsanddatastructuresforcomputationalgeometry AT guyan parallelwriteefficientalgorithmsanddatastructuresforcomputationalgeometry AT shunjulian parallelwriteefficientalgorithmsanddatastructuresforcomputationalgeometry AT sunyihan parallelwriteefficientalgorithmsanddatastructuresforcomputationalgeometry |