Matrix Multiplication with Straggler Tolerance in Coded Elastic Computing via Lagrange Code
Matrix Multiplication with Straggler Tolerance in Coded Elastic Computing via Lagrange Code
复制标题
DOI：
10.1109/icc45041.2023.10279134
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Xi Zhong;Jörg Kliewer;Mingyue Ji
中科院分区：
文献类型：
--
作者：
Xi Zhong;Jörg Kliewer;Mingyue Ji
在云计算系统中，弹性事件和离散事件增加了系统的不确定性，导致计算延迟。Yang等人在2018年引入的编码弹性计算（CEC）是一个框架，它使用最大距离可分离（MDS）编码存储来减轻弹性事件的影响。提出了一种既适用于矩阵-向量乘法又适用于一般矩阵-矩阵乘法的CEC方案。然而，在这些应用中，建议的CEC计划不能容忍由于MDS码的限制而造成的落伍者。在本文中，我们提出了一个新的弹性计算方案，使用非编码存储和拉格朗日编码计算方法。该方案可以有效地减轻弹性和离散的影响。此外，与现有的基于编码存储的方案相比，它产生更低的复杂度和更小的恢复阈值。
In cloud computing systems, elastic events and stragglers increase the uncertainty of the system, leading to computation delays. Coded elastic computing (CEC) introduced by Yang et al. in 2018 is a framework which mitigates the impact of elastic events using Maximum Distance Separable (MDS) coded storage. It proposed a CEC scheme for both matrix-vector multiplication and general matrix-matrix multiplication applications. However, in these applications, the proposed CEC scheme cannot tolerate stragglers due to the limitations imposed by MDS codes. In this paper we propose a new elastic computing scheme using uncoded storage and Lagrange coded computing approaches. The proposed scheme can effectively mitigate the effects of both elasticity and stragglers. Moreover, it produces a lower complexity and smaller recovery threshold compared to existing coded storage based schemes.