Widespread use of stochastic flow based graph clustering algorithms, e.g. Markov Clustering (MCL), has been hampered by their lack of scalability and fragmentation of output. Multi-Level Regularized Markov Clustering (MLR-MCL) is an improvement over Markov Clustering (MCL), providing faster performance and better quality of clusters for large graphs. However, a closer look at MLR-MCL's performance reveals potential for further improvement. In this paper we present a fast parallel implementation of MLR-MCL algorithm via static work partitioning based on analysis of memory footprints. By parallelizing the most time consuming region of the sequential MLR-MCL algorithm, we report up to 10.43x (5.22x in average) speedup on CPU, using 8 datasets from SNAP and 3 PPI datasets. In addition, our algorithm can be adapted to perform general sparse matrix-matrix multiplication (SpGEMM), and our experimental evaluation shows up to 3.50x (1.92x in average) speedup on CPU, and up to 5.12x (2.20x in average) speedup on MIC, comparing to the SpGEMM kernel provided by Intel Math Kernel Library (MKL).

Tensor contractions represent the most compute- intensive core kernels in ab initio computational quantum chemistry and nuclear physics. Symmetries in these tensor contractions make them difficult to load balance and scale to large distributed systems. In this paper, we develop an efficient and scalable algorithm to contract symmetric tensors. We introduce a novel approach that avoids data redistribution during contraction of symmetric tensors while also bypassing redundant storage and maintaining load balance. We present experimental results on two parallel supercomputers for several symmetric contractions that appear in the coupled cluster singles and doubles (CCSD) quantum chemistry method. We also present a novel approach to tensor redistribution that can take advantage of parallel hyperplanes when the initial distribution has replicated dimensions, and use collective broadcast when the final distribution has replicated dimensions, making the algorithm very efficient.

Tensor contractions are extremely compute intensive generalized matrix multiplication operations encountered in many computational science fields, such as quantum chemistry and nuclear physics. Unlike distributed matrix multiplication, which has been extensively studied, limited work has been done in understanding distributed tensor contractions. In this paper, we characterize distributed tensor contraction algorithms on torus networks. We develop a framework with three fundamental communication operators to generate communication-efficient contraction algorithms for arbitrary tensor contractions. We show that for a given amount of memory per processor, the framework is communication optimal for all tensor contractions. We demonstrate performance and scalability of the framework on up to 262,144 cores on a Blue Gene/Q supercomputer.

In this paper, we report on the development of an efficient GPU implementation of the Strassen-Winograd matrix multiplication algorithm for matrices of arbitrary sizes. We utilize multi-kernel streaming to exploit concurrency across sub-matrix operations in addition to intra-operation parallelism. We evaluate the performance of the implementation in comparison with CUBLAS-5.0 on Fermi and Kepler GPUs. The experimental results demonstrate the usefulness of Strassen's algorithm for practically relevant matrix sizes on GPUs, with up to 1.27X speedup for single-precision and 1.42X speedup for double-precision floating point computation.

In this paper, we introduce the Dynamic Load-balanced Tensor Contractions (DLTC), a domain-specific library for efficient task parallel execution of tensor contraction expressions, a class of computation encountered in quantum chemistry and physics. Our framework decomposes each contraction into smaller unit of tasks, represented by an abstraction referred to as iterators. We exploit an extra level of parallelism by having tasks across independent contractions executed concurrently through a dynamic load balancing runtime. We demonstrate the improved performance, scalability, and flexibility for the computation of tensor contraction expressions on parallel computers using examples from Coupled Cluster (CC) methods.