关键词:
分布式存储系统
移位加
锯齿解码
编码分布式计算
神经网络
摘要:
在大数据时代,数据量以翻倍的速度增长。集中式处理数据的方式早已过时,数据的存储,计算离不开分布式的应用。但在分布式应用中,会存在一些不可靠的设备,这些设备的计算速度比平均计算速度慢,其被称为掉队节点。掉队节点的出现会给整体的运算带来延迟。为克服这一问题,编码技术一直备受青睐,具有组合性质(Combination Property,CP)的编码被提出:假设k个数据包被编码成n个编码包,其中n≥k,那么可以在n个编码包中任意选择k个编码包,以此来恢复原始数据。在分布式存储系统中,大部分的编码技术都采用线性编码,在编解码阶段存在着计算复杂度高、资源消耗大的弊端。因此,如何解决线性编码技术给分布式存储系统中带来的难题,降低复杂度,减少存储开销需要进一步的研究。为了解决高计算复杂度的问题,结合移位加(Shift-and-Add,SA)和锯齿解码(Zigzag Decoding,ZD)的编解码方式且具有组合性质的CP-ZD码被提出。然而,现有的元素单次参与编码的CP-ZD码共同存在的缺点就是在m(27)k的应用场景下,开销过大,其中m(31)n-k。所以,聚焦于m(27)k的场景,本文提出了一种具有更低开销的倒序移位码(Rev-Shift码),不仅证明了此码满足CP-ZD性质,而且实验结果显示,在m(27)k的场景下,开销比现有的CP-ZD码都要小。其次,当前元素单次参与编码的CP-ZD码的开销下界还未找到,现有的CP-ZD码没有衡量的标准。所以,在CP-ZD码的必要条件的基础上,本文推断并证明其可能存在的一个开销下界,并且未来的工作可以以此为标准,开展进一步的研究探讨。然而,在元素单次参与编码的情况下,由于开销大的问题,锯齿码还是有其使用局限性。随着n,k等参数的不断增大,开销是以参数的平方增加的。所以,本文创新性地提出了元素多次参与编码的思路,利用柯西矩阵在有限域的良好性质,以此来设计一种基于柯西矩阵的元素多次参与编码的框架。这种编码方案的开销与参数n呈对数关系,与现有平方级别的开销对比,开销大大减少。在编码分布式计算系统(Coded Distributed Computing,CDC)中,线性编码引入的冗余计算可以弥补掉队节点的延迟。然而,由于线性编码不能直接应用于深度神经网络(Deep Neural Network,DNN)训练中的非线性激活函数,需要逐层应用编解码,从而拖慢训练。为了避免逐层编解码,本文提出了一种基于构造编码数据的新型DNN训练方案。该方案在训练之前加入构造新的编码数据操作(该操作可以在训练之前完成,不会给训练效率带来任何的影响)。基于这些额外构造的数据及原有数据,训练阶段可利用(n,k)性质而只需等待前k个返回的数据进行训练,且该训练过程无需编解码操作,从而显著提升训练速率。实验结果表明,基于构造编码数据的训练方案能够实现与集中式近似的预测准确率,并相对逐层线性编解码方案显著降低延迟。