Rateless Codes for Distributed Computations with Sparse Compressed Matrices
| Autor: | Gauri Joshi, Ankur Mallick |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Matrix (mathematics)
Computer science 020204 information systems Computation 0202 electrical engineering electronic engineering information engineering 020206 networking & telecommunications 02 engineering and technology Parallel computing Linear combination Sparse matrix computations Bottleneck Sparse matrix |
| Zdroj: | ISIT |
| DOI: | 10.1109/isit.2019.8849306 |
| Popis: | Unpredictable slowdown of worker nodes, or node straggling, is a major bottleneck when performing large matrix computations such as matrix-vector multiplication in a distributed fashion. For sparse matrices, the problem is compounded by irregularities in the distribution of non-zero elements, which leads to an imbalance in the computation load at different nodes. To mitigate the effect of stragglers we use rateless codes that generate redundant linear combinations of the matrix rows (or columns) and distribute them across workers. This coding scheme utilizes all partial work done by worker nodes, and eliminates tail latency. We also propose a balanced row-allocation strategy for allocating rows of a sparse matrix to workers that ensures that equal amount of non-zero matrix entries are assigned to each worker. The entire scheme is designed to work with compressed, memory-efficient formats like CSR/CSC that are used to store sparse matrices in practice. Theoretical analysis and simulations show that our balanced rateless coding strategy achieves significantly lower overall latency than conventional sparse matrix-vector multiplication strategies. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|