Implicit Decomposition for Write-Efficient Connectivity Algorithms
Implicit Decomposition for Write-Efficient Connectivity Algorithms
复制标题
DOI：
10.1109/ipdps.2018.00081
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
中科院分区：
文献类型：
--
作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
主要记忆的未来似乎位于提供强大的性能比率的新技术的方向，但在延迟，带宽和能量方面，写作操作比阅读要贵得多。由于这种趋势的促进，我们提出了顺序和并行算法，以比常规算法更少的写作来解决图形连接问题。我们的主要算法工具是构建O（n）大小的隐式分解，对n个节点上有界度图G的构造，该分解与G的读取访问相结合，可以快速回答G. G.的连接性和双连接性查询。打破线性写入“屏障”，导致成本渐近低于常规算法，同时仅增加了查询时间的微不足道成本。对于M边缘上的一般非SPARSE图，我们还提供了第一个O（M）写作，O（M）操作并行算法，用于连通性和双连接性。这些算法提供了有关应用如何在具有读写不对称系统的系统中有效地处理大图上的应用程序的洞察力。
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.