Sparsity-Preserving Encodings for Straggler-Optimal Distributed Matrix Computations at the Edge

Anindya Bijoy Das, Aditya Ramamoorthy, David J. Love, Christopher G. Brinton

TL;DR

This paper tackles the challenge of performing distributed matrix computations at the edge, a critical task for AI/ML. They introduce novel encoding schemes that preserve the sparsity of input matrices, leading to faster computations and reduced communication overhead, while maintaining resilience to slow or failing "straggler" devices.

What Problem Does This Paper Address?

Edge computing is booming, driven by the need for AI/ML training and inference closer to data sources. Distributed computing is a key strategy to handle the computational demands, where tasks are split and sent to multiple edge devices. A major hurdle in such systems is the presence of "stragglers" – devices that are slower or fail entirely. Existing methods use coded computations to overcome stragglers, but they often destroy the sparsity of the original matrices. This loss of sparsity significantly slows down computations and increases communication costs, which is a major issue for edge devices with limited resources. This paper aims to develop distributed matrix computation methods that are both straggler-resilient and preserve matrix sparsity.

Methods

The authors propose two main algorithms: one for distributed matrix-vector multiplication (Alg. 1) and another for distributed matrix-matrix multiplication (Alg. 2). The core of their approach lies in defining and minimizing a "weight" metric, which represents the number of submatrices combined to form an encoded submatrix. They first derive a theoretical lower bound on this weight to ensure resilience against the maximum possible number of stragglers. Their algorithms are designed to meet this lower bound, using randomized linear combinations of a limited number of submatrices. This limited combination is key to preserving sparsity. They also extend their approach to handle heterogeneous edge devices, where devices have different computational capabilities.

Datasets

The paper does not explicitly mention specific datasets used for training. However, for numerical experiments, they use synthetic sparse matrices with varying sparsity levels (95%, 98%, 99%) and sizes (e.g., 20,000x15,000 for matrix A and 20,000x12,000 for matrix B).

Key Insights and Ideas

  • Sparsity is King (at the Edge): Preserving matrix sparsity is crucial for efficiency at the edge, as dense encodings negate the benefits of distributed computing.
  • Weight Matters: Defining and minimizing the "weight" of encoding (number of submatrices combined) is key to balancing straggler resilience and sparsity preservation.
  • Lower Bound is Achievable: The theoretical lower bound on encoding weight for straggler resilience can be met by their proposed schemes.
  • Heterogeneity is Handled: Their approach can be adapted to systems where edge devices have different processing capabilities.
  • Reduced Complexity: Their methods offer lower computational complexity and communication overhead compared to existing dense and even some sparse-focused approaches.

Key Results

  • Straggler Resilience: Their schemes achieve resilience to the maximum possible number of stragglers for given storage constraints.
  • Computational Speedup: Numerical experiments on AWS show significant reductions in worker computation time and communication delay compared to dense coded methods ([25], [32], [33]) and even some sparse-specific methods ([29], [31]). For instance, in one scenario, their approach showed a 25% decrease in computational complexity compared to a method in [31].
  • Numerical Stability: The proposed methods demonstrate good numerical stability, achieving competitive worst-case condition numbers (Kworst) compared to other stable approaches.
  • Efficient Coefficient Determination: Their approach requires less time to find suitable random coefficients for numerical stability compared to methods that partition matrices into larger blocks.

Limitations and Future Work

  • Straggler Assumption: The current work assumes that the number of stragglers is known beforehand.
  • Heterogeneous System Extension: While they extend to heterogeneous systems, the proof of straggler resilience for this case is based on prior work [31].
  • Future Directions:
    • Exploring server-less architectures where edge devices collaborate more directly.
  • Allocating multiple jobs with varying weights in heterogeneous settings.
  • Developing schemes where device knowledge is limited prior to job assignment.
  • Investigating scenarios with unknown straggler counts.

Summary updated

Abstract

Matrix computations are a fundamental building block of the edge computing systems, with a major recent uptick in demand due to their use in AI/ML training and inference procedures. Existing approaches for distributing the matrix computations involve allocating coded combinations of submatrices to worker nodes, to build resilience to slower nodes, called stragglers. In the edge learning context, however, these approaches will compromise sparsity properties that are often present in the original matrices found at the edge server. In this study, we consider the challenge of augmenting, such approaches to preserve input sparsity when distributing the task across the edge devices, thereby retaining the associated computational efficiency enhancements. First, we find a lower bound on the weight of coding, i.e., the number of submatrices to be combined to obtain coded submatrices to provide the resilience to the maximum possible number of straggler devices (for given number of devices and their storage constraints). Next, we propose distributed matrix computation schemes which meet the exact lower bound on the weight of the coding. Numerical experiments conducted in amazon Web services (AWSs) validate our assertions regarding straggler mitigation and computation speed for the sparse matrices.
BibTeX
@article{das2024sparsity,
  author = {Anindya Bijoy Das and Aditya Ramamoorthy and David J. Love and Christopher G. Brinton},
  title = {{Sparsity-Preserving Encodings for Straggler-Optimal Distributed Matrix Computations at the Edge}},
  journal = {IEEE Internet of Things Journal},
  year = {2024},
  url = {https://openreview.net/forum?id=vVcFi9l92D},
}
Figure