Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
复制标题
DOI：
10.14778/3397230.3397251
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Laxman Dhulipala;Charles McGuffey;H. Kang;Yan Gu;G. Blelloch;Phillip B. Gibbons;Julian Shun
中科院分区：
文献类型：
--
作者：
Laxman Dhulipala;Charles McGuffey;H. Kang;Yan Gu;G. Blelloch;Phillip B. Gibbons;Julian Shun
非易失性主存储器（NVRAM）技术为大规模图形分析提供了一组有吸引力的功能，包括字节寻址能力、低空闲功率和改进的存储器密度。今天的NVRAM系统具有比传统存储器（DRAM）多一个数量级的NVRAM。因此，NVRAM系统可能允许在一台机器上以适度的成本解决非常大的图形问题。然而，实现高性能的一个重大挑战是考虑到NVRAM写入可能比NVRAM读取昂贵得多的事实。在本文中，我们提出了一种方法，并行图分析使用并行半非对称模型（PSAM），其中的图形存储为只读数据结构（在NVRAM中），可变内存的数量保持成比例的顶点数。与流行的半外部和半流模型类似，PSAM方法假设图的顶点适合快速读写存储器（DRAM），但边不适合。在NVRAM系统中，我们的方法消除了对NVRAM的写入，以及其他好处。为了实验研究这种新的设置，我们开发了Sage，一个并行的半不对称图形引擎，我们实现了证明有效的（通常是最佳的）PSAM算法的十几个基本图形问题。我们实验研究的Sage使用48核机器上最大的公开可用的现实世界的图（超链接网络图超过35亿个顶点和128亿条边）配备Optane DC持久性内存，并显示，Sage优于最快的先前系统设计的NVRAM。重要的是，我们还表明，通过有效地隐藏重复访问NVRAM与DRAM的成本，Sage几乎可以与仅在DRAM中运行的最快的先前系统相媲美。
Non-volatile main memory (NVRAM) technologies provide an attractive set of features for large-scale graph analytics, including byte-addressability, low idle power, and improved memory-density. NVRAM systems today have an order of magnitude more NVRAM than traditional memory (DRAM). NVRAM systems could therefore potentially allow very large graph problems to be solved on a single machine, at a modest cost. However, a significant challenge in achieving high performance is in accounting for the fact that NVRAM writes can be much more expensive than NVRAM reads. In this paper, we propose an approach to parallel graph analytics using the Parallel Semi-Asymmetric Model (PSAM), in which the graph is stored as a read-only data structure (in NVRAM), and the amount of mutable memory is kept proportional to the number of vertices. Similar to the popular semi-external and semi-streaming models for graph analytics, the PSAM approach assumes that the vertices of the graph fit in a fast read-write memory (DRAM), but the edges do not. In NVRAM systems, our approach eliminates writes to the NVRAM, among other benefits. To experimentally study this new setting, we develop Sage, a parallel semi-asymmetric graph engine with which we implement provably-efficient (and often work-optimal) PSAM algorithms for over a dozen fundamental graph problems. We experimentally study Sage using a 48-core machine on the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) equipped with Optane DC Persistent Memory, and show that Sage outperforms the fastest prior systems designed for NVRAM. Importantly, we also show that Sage nearly matches the fastest prior systems running solely in DRAM, by effectively hiding the costs of repeatedly accessing NVRAM versus DRAM.