Implicit Decomposition for Write-Efficient Connectivity Algorithms
© 2018 IEEE. The future of main memory appears to lie in the direction of new technologies that provide strong capacity-To-performance ratios, but have write operations that are much more expensive than reads in terms of latency, bandwidth, and energy. Motivated by this trend, we propose sequential...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136335 |
| _version_ | 1826207479730536448 |
|---|---|
| author | Ben-David, Naama Blelloch, Guy Fineman, Jeremy Gibbons, Phillip Gu, Yan McGuffey, Charles Shun, Julian |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ben-David, Naama Blelloch, Guy Fineman, Jeremy Gibbons, Phillip Gu, Yan McGuffey, Charles Shun, Julian |
| author_sort | Ben-David, Naama |
| collection | MIT |
| description | © 2018 IEEE. The future of main memory appears to lie in the direction of new technologies that provide strong capacity-To-performance ratios, but have write operations that are much more expensive than reads in terms of latency, bandwidth, and energy. Motivated by this trend, we propose sequential and parallel algorithms to solve graph connectivity problems using significantly fewer writes than conventional algorithms. Our primary algorithmic tool is the construction of an o(n)-sized implicit decomposition of a bounded-degree graph G on n nodes, which combined with read-only access to G enables fast answers to connectivity and biconnectivity queries on G. The construction breaks the linear-write 'barrier', resulting in costs that are asymptotically lower than conventional algorithms while adding only a modest cost to querying time. For general non-sparse graphs on m edges, we also provide the first o(m) writes and O(m) operations parallel algorithms for connectivity and biconnectivity. These algorithms provide insight into how applications can efficiently process computations on large graphs in systems with read-write asymmetry. |
| first_indexed | 2024-09-23T13:50:17Z |
| format | Article |
| id | mit-1721.1/136335 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:50:17Z |
| publishDate | 2021 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1363352023-09-13T17:32:03Z Implicit Decomposition for Write-Efficient Connectivity Algorithms Ben-David, Naama Blelloch, Guy Fineman, Jeremy Gibbons, Phillip Gu, Yan McGuffey, Charles Shun, Julian Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 IEEE. The future of main memory appears to lie in the direction of new technologies that provide strong capacity-To-performance ratios, but have write operations that are much more expensive than reads in terms of latency, bandwidth, and energy. Motivated by this trend, we propose sequential and parallel algorithms to solve graph connectivity problems using significantly fewer writes than conventional algorithms. Our primary algorithmic tool is the construction of an o(n)-sized implicit decomposition of a bounded-degree graph G on n nodes, which combined with read-only access to G enables fast answers to connectivity and biconnectivity queries on G. The construction breaks the linear-write 'barrier', resulting in costs that are asymptotically lower than conventional algorithms while adding only a modest cost to querying time. For general non-sparse graphs on m edges, we also provide the first o(m) writes and O(m) operations parallel algorithms for connectivity and biconnectivity. These algorithms provide insight into how applications can efficiently process computations on large graphs in systems with read-write asymmetry. 2021-10-27T20:34:55Z 2021-10-27T20:34:55Z 2018 2019-07-03T14:34:45Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/136335 en 10.1109/IPDPS.2018.00081 Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Ben-David, Naama Blelloch, Guy Fineman, Jeremy Gibbons, Phillip Gu, Yan McGuffey, Charles Shun, Julian Implicit Decomposition for Write-Efficient Connectivity Algorithms |
| title | Implicit Decomposition for Write-Efficient Connectivity Algorithms |
| title_full | Implicit Decomposition for Write-Efficient Connectivity Algorithms |
| title_fullStr | Implicit Decomposition for Write-Efficient Connectivity Algorithms |
| title_full_unstemmed | Implicit Decomposition for Write-Efficient Connectivity Algorithms |
| title_short | Implicit Decomposition for Write-Efficient Connectivity Algorithms |
| title_sort | implicit decomposition for write efficient connectivity algorithms |
| url | https://hdl.handle.net/1721.1/136335 |
| work_keys_str_mv | AT bendavidnaama implicitdecompositionforwriteefficientconnectivityalgorithms AT blellochguy implicitdecompositionforwriteefficientconnectivityalgorithms AT finemanjeremy implicitdecompositionforwriteefficientconnectivityalgorithms AT gibbonsphillip implicitdecompositionforwriteefficientconnectivityalgorithms AT guyan implicitdecompositionforwriteefficientconnectivityalgorithms AT mcguffeycharles implicitdecompositionforwriteefficientconnectivityalgorithms AT shunjulian implicitdecompositionforwriteefficientconnectivityalgorithms |