Optimizing High Performance Markov Clustering for Pre-Exascale Architectures
Optimizing High Performance Markov Clustering for Pre-Exascale Architectures
复制标题
优化 Exascale 之前的架构的高性能马尔可夫集群
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
A. Buluç
中科院分区：
文献类型：
--
作者：
Oguz Selvitopi;Md Taufique Hussain;A. Azad;A. Buluç
HipMCL是流行的马尔可夫聚类算法（MCL）的高性能分布式内存实现，可以使用几千个配备CPU的节点在数小时内对大规模网络进行聚类。它依赖于稀疏矩阵计算，并大量使用稀疏矩阵-稀疏矩阵乘法内核（SpGEMM）。现有的并行算法在HipMCL是不可扩展的Exascale架构，无论是由于他们的通信成本占主导地位的运行时在大并发，也由于他们无法利用加速器是越来越受欢迎的。我们通过在GPU上执行MCL算法的昂贵扩展阶段来启用GPU。我们提出了一个CPU-GPU联合分布式SpGEMM算法称为流水线稀疏SUMMA和集成的概率内存需求估计，是快速和准确的。我们提出了一种新的合并算法，对GPU产生的部分结果进行增量处理，提高了重叠效率和峰值内存使用率。我们还集成了一个最近的和更快的算法在CPU上执行SpGEMM。我们通过广泛的评估来验证我们的新算法和优化。通过启用GPU和集成新算法，HipMCL的速度提高了12.4倍，能够使用ORNL的Summit超级计算机的1024个节点在不到15分钟的时间内将7000万蛋白质和680亿个连接的网络集群化。
HipMCL is a high-performance distributed memory implementation of the popular Markov Cluster Algorithm (MCL) and can cluster large-scale networks within hours using a few thousand CPU-equipped nodes. It relies on sparse matrix computations and heavily makes use of the sparse matrix-sparse matrix multiplication kernel (SpGEMM). The existing parallel algorithms in HipMCL are not scalable to Exascale architectures, both due to their communication costs dominating the runtime at large concurrencies and also due to their inability to take advantage of accelerators that are increasingly popular.In this work, we systematically remove scalability and performance bottlenecks of HipMCL. We enable GPUs by performing the expensive expansion phase of the MCL algorithm on GPU. We propose a CPU-GPU joint distributed SpGEMM algorithm called pipelined Sparse SUMMA and integrate a probabilistic memory requirement estimator that is fast and accurate. We develop a new merging algorithm for the incremental processing of partial results produced by the GPUs, which improves the overlap efficiency and the peak memory usage. We also integrate a recent and faster algorithm for performing SpGEMM on CPUs. We validate our new algorithms and optimizations with extensive evaluations. With the enabling of the GPUs and integration of new algorithms, HipMCL is up to 12.4x faster, being able to cluster a network with 70 million proteins and 68 billion connections just under 15 minutes using 1024 nodes of ORNL’s Summit supercomputer.