Sparse Matrix Dense Matrix Multiplication (SpMM) is an important kernel with application across a wide range of domains, including machine learning and linear algebra solvers. In many sparse matrices, the pattern of nonzeros is nonuniform: nonzeros form dense and sparse regions, rather than being uniformly distributed across the whole matrix. We refer to this property as Intra-Matrix Heterogeneity (IMH). Currently, SpMM accelerator designs do not leverage this heterogeneity. They employ the same processing elements (PEs) for all the regions of a sparse matrix, resulting in suboptimal acceleration. To address this limitation, we utilize heterogeneous SpMM accelerator architectures, which include different types of PEs to exploit IMH. We develop an analytical modeling framework to predict the performance of different types of accelerator PEs taking into account IMH. Furthermore, we present a heuristic for partitioning sparse matrices among heterogeneous PEs. We call our matrix modeling and partitioning method HotTiles. To evaluate HotTiles, we simulate three different heterogeneous architectures. Each one consists of two types of workers (i.e., PEs): one suited for compute-bound denser regions (Hot Worker) and one for memory-bound sparser regions (Cold Worker). Our results show that exploiting IMH with HotTiles is very effective. Depending on the architecture, heterogeneous execution with HotTiles outperforms homogeneous execution using only hot or only cold workers by 9.2-16.8x and 1.4-3.7x, respectively. In addition, HotTiles outperforms the best worker type used on a per-matrix basis by 1.3-2.5 x. Finally, HotTiles outperforms an IMH-unaware heterogeneous execution strategy by 1.4-2.2x.

Community detection algorithms try to identify the underlying community structure (i.e., clearly distinguishable closely interacting groups of vertices) in a graph representing complex systems such as social networks, protein-protein interaction networks, and the World-Wide-Web. The Louvain algorithm iteratively moves vertices from one community to another to construct disjoint sets of vertices to form communities such that the vertices within the same community have more edges within themselves compared to their connections to the vertices outside the community. A property of the Louvain algorithm is that the number of vertex moves drops significantly just after the first few iterations because the community-membership also stabilizes quickly. In this paper, we present a parallel pull-and-push Louvain algorithm that exploits this property to prune unnecessary edge explorations without sacrificing the quality of the solution. We present a collection of parallel Louvain algorithms that prune many edges and vertices, speeding up convergence by an order of magnitude over the previously best-known implementation of the Louvain algorithm from Grappolo, while producing similar or better results.

With the increasing cost of developing robust HPC software, precise data-flow analysis for MPI programs -- the mainstay of HPC programming -- are essential. The knowledge of communication is essential for precise data-flow analysis and the difficulty of statically determining it makes the conventional techniques insufficient. Hybrid methods combining static and dynamic techniques are needed and in this work we demonstrate one such approach in building the parallel control-flow graph which can then be used to leverage the precision of data-flow analyses for MPI programs.

Standard testing methods of MPI programs do not guarantee coverage of all non-deterministic interactions (e.g., wildcard-receives). Programs tested by these methods can have untested paths (bugs) that may become manifest unexpectedly. Previous formal dynamic verifiers cover the space of non-determinism but do not scale, even for small applications. We present DAMPI, the first dynamic analyzer for MPI programs that guarantees scalable coverage of the space of non-determinism through a decentralized algorithm based on Lamport-clocks. DAMPI computes alternative non-deterministic matches and enforces them in subsequent program replays. To avoid interleaving explosion, DAMPI employs heuristics to focus coverage to regions of interest. We show that DAMPI can detect deadlocks and resource-leaks in real applications. Our results on a wide range of applications using over a thousand processes, which is an order of magnitude larger than any previously reported results for MPI dynamic verification tools, demonstrate that DAMPI provides scalable, user-configurable testing coverage.