论文标题
递归多节：用于分层图分区和过程映射的共享内存流算法
Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping
论文作者
论文摘要
将图形分配到平衡块中，以使大规模分布式处理之间的关键问题在块之间运行是一个关键问题。分区巨大图的当前趋势是流算算法，该算法使用低计算资源。在这项工作中，我们提出了共享内存流的多回收分区方案，该方案在不知道整体输入图的情况下即时执行递归的多部分。与标准图分区案例的最新非缓冲的一通分区算法相比，我们的方法的运行时间复杂性较低。此外，如果已知分布式系统的拓扑结构，则可以通过将分区映射到处理元素来进一步优化通信成本。我们的实验表明，与竞争工具相比，我们的算法既更快又产生更好的过程映射。在图形分区的情况下，与茴香相比，我们的框架最多要快两个数量级，其切割边缘的成本高5％。
Partitioning a graph into balanced blocks such that few edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge graphs are streaming algorithms, which use low computational resources. In this work, we present a shared-memory streaming multi-recursive partitioning scheme that performs recursive multi-sections on the fly without knowing the overall input graph. Our approach has a considerably lower running time complexity in comparison with state-of-the-art non-buffered one-pass partitioning algorithms for the standard graph partitioning case. Moreover, if the topology of a distributed system is known, it is possible to further optimize the communication costs by mapping partitions onto processing elements. Our experiments indicate that our algorithm is both faster and produces better process mappings than competing tools. In case of graph partitioning, our framework is up to two orders of magnitude faster at the cost of 5% more cut edges compared to Fennel.
