Straggler Mitigation Through Unequal Error Protection for Distributed Approximate Matrix Multiplication

Busra Tegin*, Eduin E. Hernandez, Stefano Rini, Tolga M. Duman

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Large-scale machine learning and data mining methods routinely distribute computations across multiple agents to parallelize processing. The time required for the computations at the agents is affected by the availability of local resources and/or poor channel conditions, thus giving rise to the 'straggler problem.' In this paper, we address this problem for distributed approximate matrix multiplication. In particular, we employ Unequal Error Protection (UEP) codes to obtain an approximation of the matrix product to provide higher protection for the blocks with a higher effect on the multiplication outcome. We characterize the performance of the proposed approach from a theoretical perspective by bounding the expected reconstruction error for matrices with uncorrelated entries. We also apply the proposed coding strategy to the computation of the back-propagation step in the training of a Deep Neural Network (DNN) for an image classification task in the evaluation of the gradients. Our numerical experiments show that it is indeed possible to obtain significant improvements in the overall time required to achieve DNN training convergence by producing approximation of matrix products using UEP codes in the presence of stragglers.

Original languageEnglish
Pages (from-to)468-483
Number of pages16
JournalIEEE Journal on Selected Areas in Communications
Volume40
Issue number2
DOIs
StatePublished - 1 Feb 2022

Keywords

  • Distributed computation
  • approximate matrix multiplication
  • stragglers
  • unequal error protection

Fingerprint

Dive into the research topics of 'Straggler Mitigation Through Unequal Error Protection for Distributed Approximate Matrix Multiplication'. Together they form a unique fingerprint.

Cite this