  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.
