Scalable task-based algorithm for multiplication of block-rank-sparse matrices

A task-based formulation of Scalable Universal Matrix Multiplication Algorithm (SUMMA), a popular algorithm for matrix multiplication (MM), is applied to the multiplication of hierarchy-free, rank-structured matrices that appear in the domain of quantum chemistry (QC). The novel features of our formulation are: (1) concurrent scheduling of multiple SUMMA iterations, and (2) fine-grained task-based composition. These features make it tolerant of the load imbalance due to the irregular matrix structure and eliminate all artifactual sources of global synchronization. Scalability of iterative computation of square-root inverse of block-rank-sparse QC matrices is demonstrated; for full-rank (dense) matrices the performance of our SUMMA formulation usually exceeds that of the state-of-the-art dense MM implementations (ScaLAPACK and Cyclops Tensor Framework).

• Publication year

  2015

• Venue

  IA3@SC

• Publication date

  2015-09-01

• Fields of study

  Chemistry, Computer Science

• Identifiers
  DOI 10.1145/2833179.2833186arXiv 1509.00309
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Clustered Low-Rank Tensor Format: Introduction and Application to Fast Construction of Hartree-Fock Exchange.

  2015cited by this paper
• A massively parallel tensor contraction framework for coupled-cluster computations

  2014cited by this paper
• CAST: Contraction Algorithm for Symmetric Tensors

  2014cited by this paper
• A tight distance-dependent estimator for screening three-center Coulomb integrals over Gaussian basis functions.

  2014cited by this paper
• Cyclops Tensor Framework: Reducing Communication and Eliminating Load Imbalance in Massively Parallel Contractions

  2013cited by this paper
• Communication optimal parallel multiplication of sparse random matrices

  2013cited by this paper
• A preliminary analysis of Cyclops Tensor Framework

  2012cited by this paper
• Communication-Optimal Parallel 2.5D Matrix Multiplication and LU Factorization Algorithms

  2011cited by this paper
• Improving communication performance in dense linear algebra via topology aware collectives

  2011cited by this paper
• Flexible Development of Dense Linear Algebra Algorithms on Massively Parallel Architectures with DPLASMA

  2011cited by this paper
• Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments

  2011cited by this paper
• Efficient and accurate local approximations to coupled-electron pair approaches: An attempt to revive the pair natural orbital method.

  2009cited by this paper
• Challenges and Advances in Parallel Sparse Matrix-Matrix Multiplication

  2008influential reference
• Multi-threading and one-sided communication in parallel LU factorization

  2007cited by this paper
• Linear-scaling symmetric square-root decomposition of the overlap matrix.

  2007cited by this paper
• A bibliography on semiseparable matrices*

  2005influential reference
• Iterative refinement method for the approximate factorization of a matrix inverse

  2004cited by this paper
• Tensor Contraction Engine: Abstraction and Automated Parallel Implementation of Configuration-Interaction, Coupled-Cluster, and Many-Body Perturbation Theories

  2003cited by this paper
• Designing Communication-Efficient Matrix Algorithms in Distributed-Memory Cilk

  2002cited by this paper
• Designing Communication-Efficient Matrix Algorithms in Distributed-Memory Cilk

  2001cited by this paper
• A BLAS-3 Version of the QR Factorization with Column Pivoting

  1998cited by this paper
• A flexible class of parallel matrix multiplication algorithms

  1998cited by this paper
• Stable iterations for the matrix square root

  1997cited by this paper
• A fast scalable universal matrix multiplication algorithm on distributed-memory concurrent computers

  1997cited by this paper
• A new parallel matrix multiplication algorithm on distributed-memory concurrent computers

  1997cited by this paper
• A three-dimensional approach to parallel matrix multiplication

  1995cited by this paper
• SUMMA: scalable universal matrix multiplication algorithm

  1995influential reference
• Communication efficient matrix multiplication on hypercubes

  1994cited by this paper
• A high-performance matrix-multiplication algorithm on a distributed-memory parallel computer, using overlapped communication

  1994cited by this paper
• Pumma: Parallel universal matrix multiplication algorithms on distributed memory concurrent computers

  1994cited by this paper
• ScaLAPACK Users' Guide

  1987cited by this paper
• Matrix algorithms on a hypercube I: Matrix multiplication

  1987cited by this paper
• Modern quantum chemistry : introduction to advanced electronic structure theory

  1982cited by this paper
• Gaussian elimination is not optimal

  1969cited by this paper
• A cellular computer to implement the kalman filter algorithm

  1969cited by this paper

• Tensor Algebra Processing Primitives (TAPP): Towards a Standard for Tensor Operations

  2026cites this paper
• Distributed and heterogeneous tensor-vector contraction algorithms for high performance computing

  2025cites this paper
• Accelerating CCSD(T) on Graphical Processing Units (GPUs).

  2025cites this paper
• SeQuant Framework for Symbolic and Numerical Tensor Algebra. I. Core Capabilities

  2025cites this paper
• Integrated Software/Hardware Execution Models for High-Accuracy Methods in Chemistry

  2025cites this paper
• Relativistic core–valence-separated molecular mean-field exact-two-component equation-of-motion coupled cluster theory: Applications to L-edge x-ray absorption spectroscopy

  2025cites this paper
• “Best” Iterative Coupled-Cluster Triples Model? More Evidence for 3CC

  2024cites this paper
• Shifting sands of hardware and software in exascale quantum mechanical simulations

  2024cites this paper
• X-OpenMP - eXtreme fine-grained tasking using lock-less work stealing

  2024cites this paper
• Distributed memory, GPU accelerated Fock construction for hybrid, Gaussian basis density functional theory.

  2023cites this paper
• A Perspective on Sustainable Computational Chemistry Software Development and Integration

  2023cites this paper
• Minimum Cost Loop Nests for Contraction of a Sparse Tensor with a Tensor Network

  2023cites this paper
• Equation generator for equation-of-motion coupled cluster assisted by computer algebra system

  2023cites this paper
• Massively Parallel Tensor Network State Algorithms on Hybrid CPU-GPU Based Architectures

  2023cites this paper
• Roadmap on electronic structure codes in the exascale era

  2022cites this paper
• Coupled cluster Green's function: Past, present, and future

  2021cites this paper
• GQCP: The Ghent Quantum Chemistry Package.

  2021cites this paper
• Molint 1.0: A framework for the computation of molecular integrals and their derivatives for density‐fitted methods

  2021cites this paper
• The Template Task Graph (TTG) - an emerging practical dataflow programming paradigm for scientific simulation at extreme scale

  2020cites this paper
• Distributed-Memory DMRG via Sparse and Dense Parallel Tensor Contractions

  2020cites this paper
• Distributed-memory multi-GPU block-sparse tensor contraction for electronic structure

  2020cites this paper
• Scalable Heterogeneous Execution of a Coupled-Cluster Model with Perturbative Triples

  2020cites this paper
• Overlapping Communications with Other Communications and Its Application to Distributed Dense Matrix Computations

  2019cites this paper
• Distributed-memory tensor completion for generalized loss functions in python using new sparse tensor kernels

  2019cites this paper
• Tensor representations and symmetry in many-electron wave functions

  2019cites this paper
• Enabling Distributed-Memory Tensor Completion in Python using New Sparse Tensor Kernels

  2019cites this paper
• Leveraging Task-Based Polar Decomposition Using PARSEC on Massively Parallel Systems

  2019influential citation
• Exploration of Reduced Scaling Formulation of Equation of Motion Coupled-Cluster Singles and Doubles Based on State-Averaged Pair Natural Orbitals

  2018cites this paper
• State-Averaged Pair Natural Orbitals for Excited States: A Route toward Efficient Equation of Motion Coupled-Cluster.

  2018cites this paper
• Mesh-TensorFlow: Deep Learning for Supercomputers

  2018cites this paper
• A Fill Estimation Algorithm for Sparse Matrices and Tensors in Blocked Formats

  2018cites this paper
• Fill estimation for blocked sparse matrices and tensors

  2018cites this paper
• Development of a modular quantum-chemistry framework for the investigation of novel basis functions

  2018cites this paper
• On extending and optimising the direct product decomposition

  2018cites this paper
• cuTT: A High-Performance Tensor Transpose Library for CUDA Compatible GPUs

  2017cites this paper
• Nuclear Energy Gradients for Internally Contracted Complete Active Space Second-Order Perturbation Theory: Multistate Extensions.

  2016cites this paper
• Massively Parallel Implementation of Explicitly Correlated Coupled-Cluster Singles and Doubles Using TiledArray Framework.

  2016cites this paper
• Combining Internally Contracted States and Matrix Product States To Perform Multireference Perturbation Theory.

  2016cites this paper
• High-Performance Tensor Contraction without BLAS

  2016cites this paper
• High-Performance Tensor Contraction without Transposition

  2016cites this paper
• Sparse Tensor Algebra as a Parallel Programming Model

  2015cites this paper
• Clustered Low-Rank Tensor Format: Introduction and Application to Fast Construction of Hartree-Fock Exchange.

  2015cites this paper
• MADNESS: A Multiresolution, Adaptive Numerical Environment for Scientific Simulation

  2015cites this paper
• Exascale Quantum Mechanical Simulations: Navigating the Shifting Sands of Hardware and Software

  year unknowncites this paper
• Future Generation Computer Systems

  year unknowncites this paper