Abstract:

Distributed matrix multiplication is a fundamental operation in many distributed machine learning and scientific computing applications， but its performance is greatly influenced by the stragglers commonly existed in the systems. Recently， researchers have proposed a fountain code based coded matrix multiplication method， which can effectively mitigate the effect of stragglers by fully exploiting the partial results of stragglers. However， it lacks the consideration of the storage cost of worker nodes. By considering the tradeoff relationship between the storage cost and the finish time of computation， the computational deadline-aware storage optimization problem for heterogeneous worker nodes was proposed firstly. Then， through the theoretical analysis， the solution based on expectation approximation was presented， and the problem was transformed into a convex optimization problem by relaxation for efficient solution. Simulation results show that in the case of ensuring a large task success rate， the storage overhead of the proposed scheme will rapidly decrease as the task duration is relaxed， and the scheme can greatly reduce the storage overhead brought by encoding. In other words， the proposed scheme can significantly reduce the extra storage overhead while guaranteeing that the whole computation can be finished before the deadline with high probability.

Key words: distributed computation, matrix multiplication, straggler, convex optimization, deadline aware

摘要：

分布式矩阵相乘是众多分布式机器学习、科学计算等应用中的关键操作，但其性能会受到系统中常见的落后节点的严重影响。最近研究者提出了基于喷泉码的编码矩阵相乘方法，能够充分利用落后节点的部分计算结果，从而大幅度减轻落后节点问题，但忽略了工作节点的存储开销。在考虑存储开销与计算完成时间之间的权衡关系的基础上，首先提出了面向异构工作节点的计算期限感知的存储优化问题；然后进一步通过理论分析，提出了基于期望近似的解决思路，并通过松弛将问题转化为凸优化问题以方便高效求解。仿真实验表明，在保证较大的任务成功率的情况下，所提方案的存储开销会随着任务期限的放宽迅速下降，并且该方案能够更大幅度降低编码带来的存储开销。也就是说，所提方案能够在保障整体计算在期限内大概率完成的前提下，大幅度降低总体的额外存储负载。

关键词: 分布式计算, 矩阵相乘, 落后节点, 凸优化, 期限感知