Polynomial coding has been proposed as a solution to the straggler mitigation problem in distributed matrix multiplication. Previous works employ univariate polynomials to encode matrix partitions. Such schemes greatly improve the speed of distributed computing systems by making the task completion time to depend only on the fastest workers. However, they completely ignore the work done by the slowest workers resulting in inefficient use of computing resources. In order to exploit the partial computations of the slower workers, we further decompose the overall matrix multiplication task into even smaller subtasks, and we propose bivariate polynomial codes. We show that these codes are a more natural choice to accommodate the additional decomposition of subtasks, and to exploit the heterogeneous storage and computation resources at workers. However, in contrast to univariate polynomial decoding, guarantying decodability with multivariate interpolation is much harder. We propose two bivariate polynomial coding schemes and study their decodability conditions. Our numerical results show that bivariate polynomial coding considerably reduces the computation time of distributed matrix multiplication.

Bivariate Polynomial Coding for Straggler Exploitation with Heterogeneous Workers / Hasircioglu, B.; Gomez-Vilardebo, J.; Gunduz, D.. - 2020-:(2020), pp. 251-256. (Intervento presentato al convegno 2020 IEEE International Symposium on Information Theory, ISIT 2020 tenutosi a usa nel 2020) [10.1109/ISIT44484.2020.9174542].

Bivariate Polynomial Coding for Straggler Exploitation with Heterogeneous Workers

Gunduz D.
2020

Abstract

Polynomial coding has been proposed as a solution to the straggler mitigation problem in distributed matrix multiplication. Previous works employ univariate polynomials to encode matrix partitions. Such schemes greatly improve the speed of distributed computing systems by making the task completion time to depend only on the fastest workers. However, they completely ignore the work done by the slowest workers resulting in inefficient use of computing resources. In order to exploit the partial computations of the slower workers, we further decompose the overall matrix multiplication task into even smaller subtasks, and we propose bivariate polynomial codes. We show that these codes are a more natural choice to accommodate the additional decomposition of subtasks, and to exploit the heterogeneous storage and computation resources at workers. However, in contrast to univariate polynomial decoding, guarantying decodability with multivariate interpolation is much harder. We propose two bivariate polynomial coding schemes and study their decodability conditions. Our numerical results show that bivariate polynomial coding considerably reduces the computation time of distributed matrix multiplication.
2020
2020 IEEE International Symposium on Information Theory, ISIT 2020
usa
2020
2020-
251
256
Hasircioglu, B.; Gomez-Vilardebo, J.; Gunduz, D.
Bivariate Polynomial Coding for Straggler Exploitation with Heterogeneous Workers / Hasircioglu, B.; Gomez-Vilardebo, J.; Gunduz, D.. - 2020-:(2020), pp. 251-256. (Intervento presentato al convegno 2020 IEEE International Symposium on Information Theory, ISIT 2020 tenutosi a usa nel 2020) [10.1109/ISIT44484.2020.9174542].
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1247344
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact