Distributed Matrix Computations with Low-weight Encodings

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Straggler nodes are well-known bottlenecks of distributed matrix computations which induce reductions in computation/communication speeds. A common strategy for mitigating such stragglers is to incorporate MDS (maximum distance separable) codes into the framework; this can achieve resilience against an optimal number of stragglers. However, these codes assign dense linear combinations of submatrices to the workers which increase the number of non-zero entries in the encoded matrices, and adversely affect the worker computation time. In this work, we develop a straggler-optimal distributed matrix computation approach where the assigned encoded submatrices are linear combinations of a small number of submatrices so that it is well suited for sparse input matrices. Numerical experiments conducted in Amazon Web Services (AWS) demonstrate up to 30% reduction in worker computation time and 100 times faster encoding compared to several recent methods.

Original languageEnglish (US)
Title of host publication2023 IEEE International Symposium on Information Theory, ISIT 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1979-1984
Number of pages6
ISBN (Electronic)9781665475549
DOIs
StatePublished - 2023
Externally publishedYes
Event2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China
Duration: Jun 25 2023Jun 30 2023

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2023-June
ISSN (Print)2157-8095

Conference

Conference2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/TerritoryTaiwan, Province of China
CityTaipei
Period6/25/236/30/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Keywords

  • Condition Number
  • Distributed computing
  • MDS codes
  • Sparsity
  • Straggler

Fingerprint

Dive into the research topics of 'Distributed Matrix Computations with Low-weight Encodings'. Together they form a unique fingerprint.

Cite this