Performance Evaluation of Scale-Free Graph Algorithms in Low Latency Non-volatile Memory

The purpose of this study is to quantitatively assess the performance of graph processing algorithms for large scale-free graphs residing in byte-addressable Non-Volatile Memory (NVM). Our study focuses on static and dynamic graph algorithms previously optimized for external memory in the form of locally attached NAND Flash arrays, with data structures tuned to maximize locality. The evaluation is run on a unique resource, an NVM hardware emulator from Intel capable of inserting delays to memory reads through microcode instructions thatdelay load instructions missing in L3; the emulated NVM appears as separate UMA node (identified by a physical address range) and that is not part of the socket-attached NUMA nodes. In this work, we distinguish two graph processing configurations, 'semi-external' in which the graph is fully resident in NVM but in-flight intermediate data structures reside in DRAM, and 'fully external' in which both the graph and the intermediate data structures reside in NVM. Our goal is to assess the performance impact of NVM latency of up to 3.5X DRAM, with (semi-external) and without (fully external) an application-specific scratchpad for the in-flight data structures. We find a performance penalty of 59.6% in the fully external scenario, which is reduced to 5.2% with the scratchpad. Our results show that graph algorithms employing locality aware data structure layout and processing can benefit immediately from emerging NVMs with minimal performance impact, making NVM a high value resource for large scale graph processing.

本研究的目的是定量评估驻留在字节可寻址非易失性存储器（NVM）中的大规模无尺度图形的图形处理算法的性能。我们的研究重点是静态和动态图形算法，以前以本地附加NAND闪存阵列的形式为外部存储器进行了优化，数据结构调整以最大化局部性。评估是在一个独特的资源上运行的，一个来自英特尔的NVM硬件模拟器，能够通过微码指令插入内存读取延迟，延迟L3中缺失的加载指令；仿真的NVM显示为单独的UMA节点（由物理地址范围标识），而不是套接字附加的NUMA节点的一部分。在这项工作中，我们区分了两种图形处理配置：“半外部”，其中图形完全驻留在NVM中，但运行中的中间数据结构驻留在DRAM中；“完全外部”，其中图形和中间数据结构都驻留在NVM中。我们的目标是评估高达3.5倍DRAM的NVM延迟对性能的影响，使用（半外部）和不使用（完全外部）用于运行中的数据结构的特定应用程序刮板。我们发现，在完全外部的情况下，性能损失为59.6%，而在使用刮板的情况下，性能损失降至5.2%。我们的研究结果表明，采用位置感知数据结构布局和处理的图算法可以立即从新兴的NVM中受益，并且性能影响最小，使NVM成为大规模图处理的高价值资源。