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中。我们的目标是评估NVM延迟（高达DRAM的3.5倍）对性能的影响，包括有（半外部）和没有（完全外部）针对运行中数据结构的特定应用暂存器的情况。我们发现在完全外部的情况下性能损失为59.6%，而使用暂存器时性能损失降低到5.2%。我们的结果表明，采用具有局部性感知的数据结构布局和处理的图算法能够立即从新兴的NVM中获益，且对性能的影响极小，这使得NVM成为大规模图处理的一种高价值资源。