论文标题
基于块的三角计数算法在异质环境上
A Block-Based Triangle Counting Algorithm on Heterogeneous Environments
论文作者
论文摘要
三角计数是图算法中的一个基本构建块。在本文中，我们提出了一种基于块的三角计数算法，以减少顺序和并行执行期间的数据移动。我们基于块的配方使该算法自然适用于异质体系结构。划分图的邻接矩阵的问题是充分研究的。我们的任务分解进一步迈进了一步：它将图中的三角形集划分。通过将这些小任务流式传输到计算资源，我们可以解决不适合设备上的问题。我们通过在具有多个插座，内核和GPU的计算节点上提供实现来证明我们的方法的有效性。三角枚举中的当前最新进程在2.1秒内完成了Friendster图，而不包括CPU和GPU之间的数据复制时间。使用该指标，我们的方法快20％。当包含复制时间时，我们的算法需要3.2秒。这比发布最快的CPU时间快5.6倍。
Triangle counting is a fundamental building block in graph algorithms. In this paper, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.
