OMRGx: Programmable and Transparent Out-of-Core Graph Partitioning and Processing
OMRGx: Programmable and Transparent Out-of-Core Graph Partitioning and Processing
复制标题
DOI：
10.1145/3591195.3595268
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Gurneet Kaur;Rajiv Gupta
中科院分区：
文献类型：
--
作者：
Gurneet Kaur;Rajiv Gupta
在内存有限的单机上划分和处理大型图形是一个挑战。虽然已经开发了许多用于核外处理的自定义解决方案，但在核外分区方面所做的工作有限，因为核外分区可能比处理更占用内存。在本文中，我们提出了OMRGx系统，其编程接口允许程序员快速原型现有的以及新的分区和处理策略，以最小的编程工作量和遗忘的图形大小。OMRGx引擎以核外方式透明地实现这些策略，同时向程序员隐藏管理有限内存、并行计算和并行IO的复杂性。执行模型允许通过在分区之间划分机器内存来同时构造和同时处理多个分区。相比之下，现有系统一次处理一个分区。使用OMRGx，我们开发了流行的MtMetis分区器的第一个核外实现。现有GridGraph和GraphChi核外处理框架的OMRGx实现比其独立优化实现提供更好的性能。OMRGx产生的实现的运行时间随着所请求的分区数量而减少，并随着图形大小线性增加。最后，OMRGx默认实现的性能最好。
Partitioning and processing of large graphs on a single machine with limited memory is a challenge. While many custom solutions for out-of-core processing have been developed, limited work has been done on out-of-core partitioning that can be far more memory intensive than processing. In this paper we present the OMRGx system whose programming interface allows the programmer to rapidly prototype existing as well as new partitioning and processing strategies with minimal programming effort and oblivious of the graph size. The OMRGx engine transparently implements these strategies in an out-of-core manner while hiding the complexities of managing limited memory, parallel computation, and parallel IO from the programmer. The execution model allows multiple partitions to be simultaneously constructed and simultaneously processed by dividing the machine memory among the partitions. In contrast, existing systems process partitions one at a time. Using OMRGx we developed the first out-of-core implementation of the popular MtMetis partitioner. OMRGx implementations of existing GridGraph and GraphChi out-of-core processing frameworks deliver performance better than their standalone optimized implementations. The runtimes of implementations produced by OMRGx decrease with the number of partitions requested and increase linearly with the graph size. Finally OMRGx default implementation performs the best of all.