編碼技術(shù)改進(jìn)大規(guī)模分布式機(jī)器學(xué)習(xí)性能綜述

王 艷 李念爽 王希齡 鐘鳳艷

(華東交通大學(xué)軟件學(xué)院 南昌 330013)(wangyann@189.cn)

近年來，由于大規(guī)模機(jī)器學(xué)習(xí)和數(shù)據(jù)分析的計(jì)算范式已經(jīng)轉(zhuǎn)向由單獨(dú)的小型計(jì)算節(jié)點(diǎn)和不可靠的計(jì)算節(jié)點(diǎn)(即低端、商用硬件)組成的大型分布式系統(tǒng)，如像Apache Spark［1]這樣的現(xiàn)代分布式系統(tǒng)和像MapReduce［2]這樣的計(jì)算框架，使大規(guī)模機(jī)器學(xué)習(xí)集群受到了廣泛的關(guān)注.然而，機(jī)器學(xué)習(xí)集群的性能普遍受到一種“系統(tǒng)噪音”——異常系統(tǒng)行為和瓶頸［3]的顯著影響.考慮到這些分布式系統(tǒng)中節(jié)點(diǎn)的個(gè)體不可預(yù)測(cè)性，機(jī)器學(xué)習(xí)集群面臨著如何在不確定性下保證快速高質(zhì)量完成算法執(zhí)行的挑戰(zhàn).

在最近的研究中，許多研究者使用編碼技術(shù)來解決這個(gè)問題.幾十年來，編碼在提供抵抗系統(tǒng)噪聲方面的作用已經(jīng)在其他工程環(huán)境中得到了肯定，它是我們?nèi)粘；A(chǔ)設(shè)施(智能手機(jī)、筆記本電腦、WiFi和蜂窩系統(tǒng)等)的一部分.本論文綜述的是如何將編碼技術(shù)應(yīng)用于分布式機(jī)器學(xué)習(xí)算法以抵抗“噪聲”對(duì)分布式算法的影響.如圖1所示，分布式機(jī)器學(xué)習(xí)算法的工作流程可以分解為3個(gè)功能階段:存儲(chǔ)、通信和計(jì)算階段.

分布式機(jī)器學(xué)習(xí)算法的工作流程如下：大規(guī)模系統(tǒng)接收輸入數(shù)據(jù)，將它們存儲(chǔ)在工作節(jié)點(diǎn)中，然后在分布式網(wǎng)絡(luò)中通信數(shù)據(jù)；每個(gè)分布式節(jié)點(diǎn)在接收到所需數(shù)據(jù)后本地執(zhí)行計(jì)算任務(wù)；系統(tǒng)將各個(gè)工作節(jié)點(diǎn)的計(jì)算結(jié)果進(jìn)行聚合.工作過程中的主要瓶頸(通信、掉隊(duì)節(jié)點(diǎn)、系統(tǒng)故障等)都被抽象成一種在這些階段之間的延遲，用Δ表示.為了開發(fā)和部署復(fù)雜的解決方案以解決機(jī)器學(xué)習(xí)、科學(xué)、工程和商業(yè)中的大規(guī)模計(jì)算問題，了解和優(yōu)化跨計(jì)算、通信、存儲(chǔ)和結(jié)果準(zhǔn)確性的多個(gè)維度的權(quán)衡是很重要的.近年來，分布式存儲(chǔ)編碼領(lǐng)域的再生碼(regenerating codes)和本地可修復(fù)編碼(local repairable codes)的提出，使得編碼技術(shù)廣泛用于分布式系統(tǒng)成為可能，并已開始改變現(xiàn)代數(shù)據(jù)中心分布式系統(tǒng)的存儲(chǔ)層［4-12]，對(duì)工業(yè)產(chǎn)生了重大影響［13-16].

1 背景介紹

在硬件資源豐富的云計(jì)算時(shí)代，數(shù)據(jù)中心通過運(yùn)行在大量商用服務(wù)器上的Hadoop分布式文件系統(tǒng)、Windows Azure存儲(chǔ)、Amazon S3和Google文件系統(tǒng)等分布式存儲(chǔ)系統(tǒng)存儲(chǔ)了海量數(shù)據(jù).由于對(duì)這些數(shù)據(jù)進(jìn)行分析得到的結(jié)果可以為用戶提供見解或建議，因此數(shù)據(jù)中心廣泛部署了各種分布式計(jì)算系統(tǒng)(例如MapReduce，Spark，TensorFlow［17]，MX Net［18])對(duì)數(shù)據(jù)進(jìn)行大規(guī)模的分析.

在分布式存儲(chǔ)系統(tǒng)中，數(shù)據(jù)通常被分為不同的區(qū)塊，存儲(chǔ)在不同的服務(wù)器上.另一方面，在分布式計(jì)算系統(tǒng)中進(jìn)行的作業(yè)通常包含多個(gè)并行運(yùn)行的任務(wù)，這種并行任務(wù)運(yùn)行在不同的服務(wù)器上，每個(gè)任務(wù)處理整個(gè)輸入數(shù)據(jù)的一小部分［19].因此，分布式計(jì)算系統(tǒng)與分布式存儲(chǔ)系統(tǒng)通常是緊密交互的，例如，可以將作業(yè)中的任務(wù)分配給服務(wù)器，該服務(wù)器將盡可能就近存儲(chǔ)相應(yīng)的輸入數(shù)據(jù)塊，以利用數(shù)據(jù)局部性.

但是，分布式存儲(chǔ)和計(jì)算系統(tǒng)在數(shù)據(jù)中心都會(huì)受到系統(tǒng)噪聲的影響，這些噪聲可能會(huì)影響系統(tǒng)的可用性或性能，造成系統(tǒng)故障、負(fù)載不平衡和資源爭用等.例如在數(shù)千個(gè)服務(wù)器集群上運(yùn)行的分布式存儲(chǔ)系統(tǒng)每天可能會(huì)遇到20～100個(gè)由于系統(tǒng)噪聲而導(dǎo)致的不可用事件.在分布式計(jì)算系統(tǒng)中，多個(gè)執(zhí)行并行任務(wù)的服務(wù)器中可能存在某些節(jié)點(diǎn)的計(jì)算時(shí)間相較其他節(jié)點(diǎn)更長，該節(jié)點(diǎn)稱為掉隊(duì)節(jié)點(diǎn)，而完成整個(gè)計(jì)算任務(wù)的時(shí)間通常受制于最慢的計(jì)算節(jié)點(diǎn).因此，掉隊(duì)節(jié)點(diǎn)將成為作業(yè)的瓶頸.

為了減輕系統(tǒng)噪聲的影響，可以采取在分布式存儲(chǔ)系統(tǒng)中預(yù)先增加冗余數(shù)據(jù)或在分布式計(jì)算系統(tǒng)中增加冗余任務(wù)的方法，以容忍受系統(tǒng)噪聲影響的數(shù)據(jù)或任務(wù).為了確保數(shù)據(jù)完整性，將數(shù)據(jù)復(fù)制多份存儲(chǔ)在不同的服務(wù)器上是實(shí)際生產(chǎn)中許多分布式存儲(chǔ)系統(tǒng)采用的方法.同時(shí)，利用存儲(chǔ)系統(tǒng)中的數(shù)據(jù)副本使得在分布式計(jì)算系統(tǒng)中以較小開銷方便地復(fù)制計(jì)算任務(wù)成為可能.因此，受系統(tǒng)噪聲影響的計(jì)算任務(wù)可以被容忍，因?yàn)樵撚?jì)算任務(wù)的結(jié)果仍然可以從另一臺(tái)服務(wù)器獲得.

但是，副本方式給計(jì)算和存儲(chǔ)帶來了非常高的資源開銷.例如3副本(即將數(shù)據(jù)復(fù)制3次)的方式可以容忍任意2個(gè)不可用的副本出現(xiàn)，同時(shí)在分布式存儲(chǔ)系統(tǒng)中產(chǎn)生3倍源文件大小的存儲(chǔ)開銷.為了減少資源開銷，使用糾刪碼(erasure coding， EC)產(chǎn)生冗余數(shù)據(jù)或計(jì)算的方式受到了許多關(guān)注.糾刪碼起源于通信傳輸領(lǐng)域，后來逐漸應(yīng)用到存儲(chǔ)系統(tǒng)中的數(shù)據(jù)檢錯(cuò)和糾錯(cuò)問題中，以提高存儲(chǔ)系統(tǒng)的可靠性.在存儲(chǔ)系統(tǒng)中，糾刪碼技術(shù)主要是通過利用糾刪碼算法將原始的數(shù)據(jù)進(jìn)行編碼得到冗余，并將數(shù)據(jù)和冗余一并存儲(chǔ)起來，以達(dá)到容錯(cuò)的目的.與副本方式相比，糾刪碼允許以更少的資源開銷來達(dá)到容忍同等系統(tǒng)噪聲的效果.以目前廣泛使用的一種糾刪碼方案RS碼［20](Reed-Solomon code)的(n,k)=(4，2)編碼為例，該編碼將原文件分為k=2部分，然后按照RS碼編碼規(guī)則生成m=2個(gè)校驗(yàn)塊，容錯(cuò)能力為2，數(shù)據(jù)收集節(jié)點(diǎn)可以選擇任意2個(gè)塊重建出原始文件，此編碼方式僅需消耗2倍源文件大小的存儲(chǔ)空間，就具有與3副本技術(shù)相同的容錯(cuò)能力，即可以容忍任意2個(gè)塊丟失.同時(shí)，糾刪碼可以應(yīng)用于其他的編碼任務(wù)，來修改一些分布式計(jì)算算法，如矩陣乘法和數(shù)據(jù)洗牌等.編碼任務(wù)將一部分編碼數(shù)據(jù)作為輸入，并且對(duì)所有任務(wù)的一個(gè)子集進(jìn)行解碼后即可得到作業(yè)的結(jié)果，從而實(shí)現(xiàn)了對(duì)掉隊(duì)節(jié)點(diǎn)的容忍.

之前對(duì)EC編碼技術(shù)的研究應(yīng)用大多都集中于分布式存儲(chǔ)領(lǐng)域，研究如何用這一編碼技術(shù)增加相應(yīng)的“冗余存儲(chǔ)”以抵抗“erasure”節(jié)點(diǎn)對(duì)數(shù)據(jù)可靠性造成的影響，其中“erasure”節(jié)點(diǎn)是指由于各種原因?qū)е碌南到y(tǒng)中失效的存儲(chǔ)節(jié)點(diǎn).本文則是聚焦于編碼技術(shù)在分布式計(jì)算領(lǐng)域中的應(yīng)用，介紹近幾年對(duì)于如何用編碼技術(shù)增加相應(yīng)的“冗余計(jì)算”以改進(jìn)大規(guī)模機(jī)器學(xué)習(xí)集群性能的研究進(jìn)展，研究將大規(guī)模機(jī)器學(xué)習(xí)集群中的“straggler”看成是計(jì)算集群中的1個(gè)“erasure”節(jié)點(diǎn)，如何增加相應(yīng)的“冗余計(jì)算”以抵抗“erasure”節(jié)點(diǎn)對(duì)分布式機(jī)器學(xué)習(xí)算法性能造成的影響.

目前基于編碼技術(shù)改進(jìn)大規(guī)模機(jī)器學(xué)習(xí)集群性能的研究，涉及在矩陣乘法、梯度計(jì)算、數(shù)據(jù)洗牌和其他一些機(jī)器學(xué)習(xí)領(lǐng)域的應(yīng)用，本文將在后續(xù)章節(jié)中分別進(jìn)行介紹.

2 編碼技術(shù)應(yīng)用于矩陣乘法

矩陣乘法是許多數(shù)據(jù)分析應(yīng)用程序的關(guān)鍵操作之一，這些應(yīng)用程序應(yīng)用于各種領(lǐng)域，如機(jī)器學(xué)習(xí)、科學(xué)計(jì)算和圖形處理等.此類應(yīng)用程序需要大量的計(jì)算和存儲(chǔ)資源來處理TB甚至PB級(jí)的數(shù)據(jù)量，而這是單臺(tái)機(jī)器無法提供的.因此，在大規(guī)模分布式系統(tǒng)上部署矩陣乘法計(jì)算任務(wù)受到了廣泛的關(guān)注［21-23].本文按照矩陣大小不同將矩陣乘法分成了矩陣-向量乘法和矩陣-矩陣乘法2種，分別介紹了實(shí)現(xiàn)對(duì)于掉隊(duì)節(jié)點(diǎn)魯棒性的2種矩陣乘法的編碼方案，并對(duì)方案之間的部分性能進(jìn)行了對(duì)比.

2.1 編碼應(yīng)用于矩陣-向量乘法

假設(shè)由于系統(tǒng)噪聲，工作節(jié)點(diǎn)的延遲是不可預(yù)測(cè)的.目標(biāo)是在有掉隊(duì)節(jié)點(diǎn)存在的情況下盡可能快地計(jì)算矩陣-向量乘法AX，其中A是一個(gè)m×n的矩陣，X是一個(gè)n×1的一維矩陣，即向量.副本方案、MDS編碼方案、無碼率編碼方案都是基于此目標(biāo)來優(yōu)化矩陣-向量乘法，下面分別介紹這3種方案，并進(jìn)行分析和比較.

2.1.1 副本方案

對(duì)抗掉隊(duì)節(jié)點(diǎn)的一種最基本的方法是使用副本方案，將每個(gè)計(jì)算任務(wù)以副本的形式在多個(gè)工作節(jié)點(diǎn)上并行執(zhí)行，當(dāng)任一節(jié)點(diǎn)完成工作后，該計(jì)算任務(wù)就被完成.本文把副本方案看作諸多編碼方案中的一種特殊情況.圖2給出了副本方案的簡單示例.

首先將矩陣A分成2個(gè)子矩陣，即A=［A1A2]，然后將A1，A2以2副本的形式分別存儲(chǔ)在4個(gè)工作節(jié)點(diǎn)中.主節(jié)點(diǎn)將X發(fā)送給4個(gè)工作節(jié)點(diǎn)，工作節(jié)點(diǎn)執(zhí)行計(jì)算任務(wù)AiX(i=1,2)，并將計(jì)算結(jié)果返還給主節(jié)點(diǎn).主節(jié)點(diǎn)接收到Worker1，Worker2和Worker3，Worker4這2組工作節(jié)點(diǎn)中每組的任一工作節(jié)點(diǎn)的計(jì)算結(jié)果即可計(jì)算出AX.例如，當(dāng)節(jié)點(diǎn)Worker2，Worker3失效時(shí)，主節(jié)點(diǎn)接收到其他2個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果可計(jì)算出AX.

Fig.2 Illustration of replication scheme圖2 副本方案示例

2.1.2 MDS編碼方案

在文獻(xiàn)［24]中Lee等人提出了一種基于最大距離可分(maximum distance separable, MDS)碼的編碼計(jì)算方案，稱為“MDS編碼矩陣乘法”，關(guān)鍵思想如下.想象一個(gè)包含1個(gè)主節(jié)點(diǎn)(master)和3個(gè)工作節(jié)點(diǎn)(worker)的分布式計(jì)算系統(tǒng)，如圖3所示，MDS編碼方案首先將A分成2個(gè)子矩陣，即A=［A1A2]，并計(jì)算2個(gè)子矩陣的奇偶校驗(yàn)，即A3=A1+A2，將A1，A2，A3預(yù)先存儲(chǔ)在工作節(jié)點(diǎn)Worker1，Worker2，Worker3中.然后，主節(jié)點(diǎn)將向量X發(fā)送給每個(gè)工作節(jié)點(diǎn)，工作節(jié)點(diǎn)i(i=1,2,3)執(zhí)行分配給該節(jié)點(diǎn)的計(jì)算AiX的任務(wù).當(dāng)工作節(jié)點(diǎn)i完成任務(wù)后，將結(jié)果發(fā)送回主節(jié)點(diǎn).一旦主節(jié)點(diǎn)接收到3個(gè)計(jì)算結(jié)果中的任意2個(gè)，它就可以計(jì)算出AX.例如當(dāng)節(jié)點(diǎn)Worker2失效時(shí)，主節(jié)點(diǎn)接收到A1X和A3X，它可以通過計(jì)算A2X=A3X-A1X得到A2X，然后計(jì)算出AX.

使用編碼可以利用更多的節(jié)點(diǎn)緩解掉隊(duì)節(jié)點(diǎn)的影響，Lee等人［24]通過分析表明：如果n個(gè)工作節(jié)點(diǎn)執(zhí)行任務(wù)的時(shí)間屬于獨(dú)立同指數(shù)分布，那么最優(yōu)的編碼矩陣乘法會(huì)比未編碼的矩陣乘法平均快Θ(lgn)倍.

Fig.3 Illustration of a system with 1 master and 3 workers圖3 擁有1個(gè)主節(jié)點(diǎn)和3個(gè)工作節(jié)點(diǎn)的系統(tǒng)示例

2.1.3 無碼率編碼方案

2.1.1節(jié)與2.1.2節(jié)中介紹的編碼方案雖然實(shí)現(xiàn)了對(duì)掉隊(duì)節(jié)點(diǎn)的容忍，但是對(duì)于掉隊(duì)節(jié)點(diǎn)所完成的工作沒有進(jìn)行利用，這是對(duì)計(jì)算資源的浪費(fèi)，Mallick等人［25]提出了一種基于LT碼［26]的無碼率噴泉編碼(rateless fountain codes)［27]策略.編碼思想如下:將m×n矩陣A的行a1，a2，…，am看作是基本塊，并對(duì)這m個(gè)行進(jìn)行編碼生成me=αm個(gè)編碼行并將其組成編碼矩陣Ae，其中每個(gè)編碼行是從矩陣A中隨機(jī)均勻的選擇d行并作異或運(yùn)算得到的，選擇d=i的概率正比于

(1)

然后將編碼矩陣Ae的me行分配給p個(gè)工作節(jié)點(diǎn)，每個(gè)工作節(jié)點(diǎn)分配的行的數(shù)量相等，分配給每個(gè)節(jié)點(diǎn)的αm/p行存儲(chǔ)在其本地內(nèi)存中，如圖4所示.當(dāng)需要將矩陣A與向量X相乘時(shí)，主節(jié)點(diǎn)就會(huì)把X發(fā)送給每個(gè)工作節(jié)點(diǎn)，每個(gè)工作節(jié)點(diǎn)將存儲(chǔ)在各自本地內(nèi)存中的編碼矩陣Ae的每一行與X的乘積返還給主節(jié)點(diǎn).另外，為了減少通信負(fù)載，工作節(jié)點(diǎn)可以只向主節(jié)點(diǎn)發(fā)送進(jìn)度更新，來表明它已完成的計(jì)算任務(wù)的數(shù)量，并在主節(jié)點(diǎn)需要時(shí)發(fā)送乘積結(jié)果.

Fig.4 Illustration of rateless code圖4 無碼率編碼方案示例

根據(jù)編碼策略，主節(jié)點(diǎn)利用從工作節(jié)點(diǎn)接收到的編碼的行-向量積的子集(即Be=AeX的元素子集)中逐步恢復(fù)所需的矩陣-向量乘積B=AX.對(duì)于一個(gè)m行的矩陣，解碼過程需要md=m(1+ε)個(gè)行-向量乘積，其中ε是一個(gè)很小的值，取決于編碼時(shí)參數(shù)的設(shè)置，當(dāng)m→∞時(shí)，ε→0.一旦主節(jié)點(diǎn)完成了對(duì)B=AX中所有元素的解碼工作，它會(huì)向所有工作節(jié)點(diǎn)發(fā)送一個(gè)停止信號(hào)來停止它們的本地計(jì)算.在此期間，速度較快的工作節(jié)點(diǎn)比速度較慢的工作節(jié)點(diǎn)完成了更多的計(jì)算任務(wù)，p個(gè)計(jì)算節(jié)點(diǎn)共同完成了m(1+ε)個(gè)計(jì)算任務(wù).

無碼率編碼方案與MDS編碼方案相比具有4個(gè)優(yōu)點(diǎn):

1) 無碼率編碼方案相較于MDS編碼具有更低的時(shí)延，MDS編碼方案不適用于存在不同計(jì)算速度掉隊(duì)節(jié)點(diǎn)的情況，僅僅使用了k個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果，忽略了其他p-k個(gè)節(jié)點(diǎn)的工作;

2) 無碼率編碼方案最多只需完成m(1+ε)個(gè)計(jì)算任務(wù)，而MDS編碼在沒有掉隊(duì)節(jié)點(diǎn)存在時(shí)，工作節(jié)點(diǎn)將會(huì)共同完成mp/k個(gè)計(jì)算任務(wù);

3) 無碼率編碼方案可以容忍p-1個(gè)掉隊(duì)節(jié)點(diǎn)，且冗余計(jì)算開銷可以忽略不計(jì)，而一個(gè)(p,k) MDS編碼方案(即將k個(gè)計(jì)算任務(wù)編碼使用MDS碼編碼成p個(gè)編碼任務(wù)，其中任意k個(gè)編碼任務(wù)的計(jì)算結(jié)果即可解碼出最終結(jié)果)對(duì)p-k個(gè)節(jié)點(diǎn)具有魯棒性，k∈{1,2,…,p}，當(dāng)k降低時(shí)，可以容忍更多的掉隊(duì)節(jié)點(diǎn)，但是會(huì)造成更多的計(jì)算冗余;

4) 無碼率編碼方案擁有O(mlnm)的極快解碼速度，這使得在m的值非常大的時(shí)候仍然可以使用該編碼方案.

表1給出了使用p個(gè)工作節(jié)點(diǎn)計(jì)算m×n矩陣A與n×1向量X相乘的3種策略之間的比較，其中時(shí)延是近似的，計(jì)算負(fù)載是在沒有掉隊(duì)節(jié)點(diǎn)的情況下給出的，τ為執(zhí)行一次計(jì)算任務(wù)所用的時(shí)間，μ為延遲率且延遲的指數(shù)部分不隨工作節(jié)點(diǎn)執(zhí)行計(jì)算任務(wù)的次數(shù)而變化.

Table 1 Comparison of Different Strategies for Matrix-Vector Multiplication表1 矩陣-向量乘法不同策略的對(duì)比

2.2 編碼應(yīng)用于矩陣-矩陣乘法

Fig.5 Example of high-dimensional matrix multiplication problem圖5 高維矩陣乘法問題示例

現(xiàn)今對(duì)這一問題提出了MDS碼、乘積碼、多項(xiàng)式碼等編碼解決方案，下面將對(duì)這些方案進(jìn)行介紹.

2.2.1 MDS編碼方案

應(yīng)用于矩陣-矩陣乘法的MDS編碼方案可以分為一維MDS編碼方案和完全MDS編碼方案

(2)

Fig.6 Illustration of 1D MDS code with 3 workers圖6 3個(gè)工作節(jié)點(diǎn)的1D MDS碼示例

2.2.2 乘積碼編碼方案

Fig.7 Illustration of product code with 9 workers圖7 9個(gè)工作節(jié)點(diǎn)的乘積碼示例

(3)

該方案的恢復(fù)閾值相較于一維MDS碼有著明顯的改進(jìn).

2.2.3 多項(xiàng)式碼編碼方案

Yu等人［29]發(fā)現(xiàn)最優(yōu)恢復(fù)閾值可以遠(yuǎn)遠(yuǎn)小于一維MDS編碼和乘積碼2種方案的恢復(fù)閾值，并指出恢復(fù)的最低閾值不與工作節(jié)點(diǎn)的數(shù)量成比例(即Θ(1)).他們通過設(shè)計(jì)一種新的編碼計(jì)算策略，即多項(xiàng)式編碼來證明這一觀點(diǎn)，該編碼策略實(shí)現(xiàn)了mn的恢復(fù)閾值，并顯著提高了技術(shù)水平.圖8為多項(xiàng)式碼的簡單示例.

在一個(gè)分布式矩陣乘法計(jì)算任務(wù)中，使用5個(gè)工作節(jié)點(diǎn)(即N=5)計(jì)算C=ATB，其中每個(gè)工作節(jié)點(diǎn)能存儲(chǔ)每個(gè)輸入矩陣的一半大小.沿著列將每個(gè)輸入矩陣平均分成2個(gè)子矩陣:

A=［A0A1]，
B=［B0B1].

(4)

因而，實(shí)際所需計(jì)算的內(nèi)容就變成了4個(gè)未編碼的部分:

(5)

現(xiàn)在設(shè)計(jì)一種計(jì)算策略來實(shí)現(xiàn)最優(yōu)恢復(fù)閾值4，每個(gè)工作節(jié)點(diǎn)i(i∈{1,2,…,4})存儲(chǔ)2個(gè)編碼子矩陣:

(6)

為了證明該計(jì)算策略的恢復(fù)閾值為4，需要為擁有4個(gè)工作節(jié)點(diǎn)的任意子集設(shè)計(jì)一個(gè)有效的解碼函數(shù).通過一個(gè)具有代表性的場(chǎng)景來演示這種可解碼性，其中主節(jié)點(diǎn)從工作節(jié)點(diǎn)1，2，3，4接收計(jì)算結(jié)果，工作節(jié)點(diǎn)0為掉隊(duì)節(jié)點(diǎn)，如圖8所示.類似地，其他4種可能場(chǎng)景的可解碼性也可以證明.

Fig.8 Illustration of polynomial code with 5 workers圖8 擁有5個(gè)工作節(jié)點(diǎn)的多項(xiàng)式碼示例

根據(jù)設(shè)計(jì)的計(jì)算策略，可以得到:

(7)

式(7)中的系數(shù)矩陣是范德蒙德矩陣，由于它的參數(shù)1，2，3，4在有限域F7中是不同的，因此該矩陣是可逆的.因此恢復(fù)C的一種方法是直接對(duì)式(7)進(jìn)行反求，這也證明了該式的可解碼性.然而，在更一般的情況下，使用經(jīng)典的反演算法直接計(jì)算這個(gè)逆可能比較復(fù)雜.Yu等人［29]認(rèn)為，由于所設(shè)計(jì)的計(jì)算策略具有特殊的代數(shù)結(jié)構(gòu)，解碼過程可以看作是一個(gè)多項(xiàng)式插值問題(或是一個(gè)解碼Reed-Solomon碼的問題).

具體地說，在本例中，每個(gè)工作節(jié)點(diǎn)i都返回給主節(jié)點(diǎn)結(jié)果:

(8)

也就是多項(xiàng)式在x=i處的值:

(9)

因此，使用4個(gè)工作節(jié)點(diǎn)的計(jì)算結(jié)果恢復(fù)C等價(jià)于在給定值的情況下在第4個(gè)點(diǎn)處插值一個(gè)3次多項(xiàng)式.

Kpolymn=Θ(1).

(10)

這種多項(xiàng)式編碼的主要?jiǎng)?chuàng)新之處和優(yōu)點(diǎn)在于，通過精心設(shè)計(jì)編碼子矩陣的代數(shù)結(jié)構(gòu)，可以確保工作節(jié)點(diǎn)上的任何mn個(gè)中間計(jì)算都足以在主節(jié)點(diǎn)上恢復(fù)矩陣乘法的最終乘積.從某種意義上來說，這是在中間計(jì)算中創(chuàng)建了一個(gè)MDS結(jié)構(gòu)，而不是像以前的工作那樣僅僅是對(duì)矩陣進(jìn)行編碼.此外，通過利用多項(xiàng)式碼的代數(shù)結(jié)構(gòu)，可以將在主節(jié)點(diǎn)上的最終輸出的重構(gòu)問題映射為一個(gè)多項(xiàng)式插值問題(或是一個(gè)RS碼解碼問題)，并可有效求解.這種映射也架起了代數(shù)編碼理論和分布式矩陣乘法之間的橋梁.

Yu等人［29]證明了多項(xiàng)式編碼的最優(yōu)性，指出它在恢復(fù)閾值上達(dá)到了信息理論的下界(至少需要工作節(jié)點(diǎn)返回的mn個(gè)矩陣塊來恢復(fù)最終的輸出，而最終輸出的大小正好是mn塊).因此，所提出的多項(xiàng)式編碼本質(zhì)上支持某種特定的計(jì)算策略，這樣，從任何可恢復(fù)C所需的最小信息量的工作節(jié)點(diǎn)的子集中，主節(jié)點(diǎn)都可以成功地解碼最終的輸出.

在多項(xiàng)式編碼的基礎(chǔ)上，Yu等人［29]又在文獻(xiàn)［30]中提出了一種新的編碼策略，稱為糾纏多項(xiàng)式碼，對(duì)所有可能的參數(shù)值實(shí)現(xiàn)了pmn+p-1的恢復(fù)閾值.糾纏多項(xiàng)式碼的構(gòu)造是基于這樣一個(gè)事實(shí):當(dāng)一個(gè)m×p矩陣和一個(gè)p×n矩陣相乘時(shí)，本質(zhì)上是求一個(gè)由2個(gè)矩陣中元素的成對(duì)乘積張成的雙線性函數(shù)的子空間.雖然可能存在總共p2mn對(duì)元素，但至多pmn對(duì)元素與矩陣乘積直接相關(guān)，存在p階的缺失.糾纏多項(xiàng)式碼的特殊結(jié)構(gòu)將輸入矩陣與輸出相關(guān)聯(lián)，使得系統(tǒng)幾乎可以避免不必要的乘法，并且實(shí)現(xiàn)了pmn階的恢復(fù)閾值.這種編碼策略實(shí)現(xiàn)了用于抵抗掉隊(duì)節(jié)點(diǎn)的傳統(tǒng)非編碼方法、隨機(jī)線性編碼和MDS編碼類型的方法的有序改進(jìn).糾纏多項(xiàng)式編碼是對(duì)多項(xiàng)式編碼的推廣，它是針對(duì)p=1的特殊情況而設(shè)計(jì)的.此外，Yu等人［30]利用雙線性復(fù)雜度，通過改進(jìn)糾纏多項(xiàng)式編碼，在系數(shù)為2的范圍內(nèi)，描述了所有線性編碼策略的最佳恢復(fù)閾值.此外，當(dāng)評(píng)估雙線性復(fù)雜度是一個(gè)眾所周知的挑戰(zhàn)性問題時(shí)，他們指出線性編碼策略的最佳恢復(fù)閾值可以在這個(gè)基本量的2倍以內(nèi).

表2給出了上述6種編碼策略之間的對(duì)比，這些編碼策略的目標(biāo)都是通過輸入矩陣A和B計(jì)算出C=ATB，如圖5所示.計(jì)算工作是在擁有1個(gè)主節(jié)點(diǎn)和N個(gè)工作節(jié)點(diǎn)的分布式系統(tǒng)中進(jìn)行的.其中，2個(gè)輸入矩陣分別被任意劃分為p×m和p×n個(gè)子矩陣塊，每一個(gè)輸入矩陣劃分的子矩陣大小是相同的，且每個(gè)工作節(jié)點(diǎn)只能在本地存儲(chǔ)2個(gè)子矩陣.

Table 2 Comparison of Different Strategies for Matrix-Matrix Multiplication表2 矩陣-矩陣乘法不同策略的對(duì)比

另外，文獻(xiàn)［24]中提出的編碼計(jì)算方法忽略了計(jì)算速度最慢的的n-k個(gè)工作節(jié)點(diǎn)所做的工作，并將這些工作節(jié)點(diǎn)認(rèn)定為掉隊(duì)節(jié)點(diǎn).對(duì)于持久的掉隊(duì)節(jié)點(diǎn)，即永久不可用或非常長時(shí)間不可用的工作節(jié)點(diǎn)，這是理想的策略.然而，在實(shí)踐中，有許多非持久性的掉隊(duì)節(jié)點(diǎn)，他們的計(jì)算速度雖然緩慢，但能夠做一些工作.此時(shí)對(duì)這些非持久性的掉隊(duì)節(jié)點(diǎn)的忽略是對(duì)計(jì)算資源的浪費(fèi).因此Kiani等人［33]提出了一種利用掉隊(duì)節(jié)點(diǎn)的計(jì)算能力的編碼方案.他們首先考慮矩陣-向量乘法，并將MDS碼應(yīng)用于子矩陣的小塊.工作節(jié)點(diǎn)按順序處理塊，一個(gè)塊、一個(gè)塊地工作，完成后將每個(gè)塊的部分結(jié)果發(fā)送給主節(jié)點(diǎn).這種工作策略允許一個(gè)更連續(xù)的處理過程，從而允許充分利用工作節(jié)點(diǎn)所做的工作并減少計(jì)算時(shí)間.然后，Kiani等人［33]使用乘積碼將此技術(shù)應(yīng)用于矩陣-矩陣乘法，證明了計(jì)算子任務(wù)的順序是一種新的設(shè)計(jì)自由度，可以進(jìn)一步利用它來減少計(jì)算時(shí)間，并提出了一種區(qū)別于傳統(tǒng)順序統(tǒng)計(jì)的新型分析結(jié)束時(shí)間的方法.仿真結(jié)果表明，與以前的方法相比，該方案預(yù)期的計(jì)算時(shí)間減少了至少67%.

此外，對(duì)于如何利用掉隊(duì)節(jié)點(diǎn)的計(jì)算能力這一問題，Narra等人［34]和Ramamoorthy等人［35]也分別提出了不同的編碼方案.

3 編碼應(yīng)用于梯度計(jì)算

在求解機(jī)器學(xué)習(xí)算法的無約束優(yōu)化問題時(shí)，梯度下降(gradient descent)是最常采用的方法之一，求解損失函數(shù)的最小值時(shí)，可以通過梯度下降法來迭代求解，得到最小化的損失函數(shù)和模型參數(shù)值.針對(duì)基于梯度計(jì)算提出的編碼方案，本文將編碼方案分為精確梯度編碼和近似梯度計(jì)算編碼2種.

3.1 精確梯度編碼方案

Tandon等人［36]研究了分布式系統(tǒng)中梯度計(jì)算的最優(yōu)編碼設(shè)計(jì)，他們注意到，在許多機(jī)器學(xué)習(xí)問題中，損失函數(shù)的梯度是更簡單的梯度總和(這里更簡單的梯度是指與每個(gè)數(shù)據(jù)點(diǎn)一起計(jì)算的每個(gè)梯度).在考慮到唯一重要的是總梯度的基礎(chǔ)上，Tandon等人［36]提出了一種新的編碼計(jì)算方案，用于計(jì)算函數(shù)的和，展示了對(duì)梯度進(jìn)行編碼可以提供同步梯度下降法對(duì)失效節(jié)點(diǎn)和掉隊(duì)節(jié)點(diǎn)的容忍.他們根據(jù)工作節(jié)點(diǎn)運(yùn)行速度變慢的程度將掉隊(duì)節(jié)點(diǎn)分成完全掉隊(duì)節(jié)點(diǎn)(full stragglers)和部分掉隊(duì)節(jié)點(diǎn)(partial stragglers)兩種，其中完全掉隊(duì)節(jié)點(diǎn)是指完全失效的工作節(jié)點(diǎn)，即不提交任何計(jì)算結(jié)果;部分掉隊(duì)節(jié)點(diǎn)是指沒有完全失效的節(jié)點(diǎn)，即雖然要比正常節(jié)點(diǎn)計(jì)算速度慢但還是可以提交部分計(jì)算結(jié)果.針對(duì)完全掉隊(duì)節(jié)點(diǎn)和部分掉隊(duì)節(jié)點(diǎn)這2種情況，Tandon等人［36]分別提出了一種編碼方案來實(shí)現(xiàn)機(jī)器學(xué)習(xí)集群對(duì)掉隊(duì)節(jié)點(diǎn)的魯棒性.

針對(duì)完全掉隊(duì)節(jié)點(diǎn)，Tandon等人［36]提出的編碼方案是通過復(fù)制工作節(jié)點(diǎn)所需完成的任務(wù)來實(shí)現(xiàn)的.但是這種副本策略僅適用于工作節(jié)點(diǎn)數(shù)量n是(s+1)的倍數(shù)，其中s是該方案能容忍的掉隊(duì)節(jié)點(diǎn)的數(shù)量.編碼方案過程:

2) 所有的組都是彼此的副本;

3) 當(dāng)計(jì)算完成時(shí)，每個(gè)工作節(jié)點(diǎn)傳輸其所計(jì)算部分的梯度的和到主節(jié)點(diǎn).

圖9為n=6,s=2時(shí)的構(gòu)造實(shí)例，對(duì)2個(gè)掉隊(duì)節(jié)點(diǎn)具有魯棒性.

Fig.9 Illustration of full stragglers for n=6,s=2圖9 n=6,s=2時(shí)的full stragglers實(shí)例

針對(duì)部分掉隊(duì)節(jié)點(diǎn)，Tandon等人［36]提出了一種編碼塊與未編碼塊結(jié)合起來的方案.該方案將數(shù)據(jù)分成編碼部分和未編碼部分，每當(dāng)一個(gè)部分掉隊(duì)節(jié)點(diǎn)處理完該節(jié)點(diǎn)上的未編碼部分時(shí)，正常節(jié)點(diǎn)就處理完該節(jié)點(diǎn)上未編碼部分和編碼的部分.任意的(n,s,α)編碼方案描述如下，其中α(α>1)是指部分掉隊(duì)節(jié)點(diǎn)計(jì)算速度為正常節(jié)點(diǎn)的α倍:

3) 再給每個(gè)工作節(jié)點(diǎn)按照(A，B)分配方案分配(s+1)個(gè)編碼塊，這一分配方案對(duì)s個(gè)掉隊(duì)節(jié)點(diǎn)具有魯棒性;

4) 任意工作節(jié)點(diǎn)Workeri，首先處理該節(jié)點(diǎn)上所有的未編碼塊，并將它們的梯度和發(fā)送到主節(jié)點(diǎn)，然后再處理節(jié)點(diǎn)上的編碼塊，并根據(jù)(A，B)分配模式發(fā)送一個(gè)線性組合到主節(jié)點(diǎn).

Fig.10 Illustration of partial stragglers for n=3,s=1,α=2圖10 n=3,s=1,α=2時(shí)的partial stragglers實(shí)例

Ye等人［37]提出了通信計(jì)算高效梯度編碼方案，它從計(jì)算負(fù)載、掉隊(duì)節(jié)點(diǎn)容忍和通信成本3個(gè)方面描述了梯度計(jì)算的基本權(quán)衡.為了有效地計(jì)算梯度(以及更一般的向量和)，利用數(shù)據(jù)子集和向量之間的分布性，確定了這些參數(shù)之間的基本權(quán)衡:

(11)

其中,n為工作節(jié)點(diǎn)的數(shù)量，k為數(shù)據(jù)子集的數(shù)量，d為分配給每個(gè)工作節(jié)點(diǎn)的數(shù)據(jù)子集的數(shù)量，s為掉隊(duì)節(jié)點(diǎn)的數(shù)量，m為通信下降因子.這一權(quán)衡概括了文獻(xiàn)［36]中對(duì)應(yīng)于m=1的結(jié)果.

Ye等人［37]進(jìn)一步給出一種基于遞歸多項(xiàng)式構(gòu)造的顯式編碼方案，實(shí)現(xiàn)了數(shù)據(jù)子集和向量分量的最優(yōu)權(quán)衡，可以使梯度計(jì)算的運(yùn)行時(shí)間最小化.編碼方案的主要步驟:為了減少每個(gè)工作節(jié)點(diǎn)傳輸向量的維數(shù)，首先將梯度向量的坐標(biāo)劃分為m個(gè)相同大小的組；隨后設(shè)計(jì)2個(gè)矩陣B和V，其中(n-s)×n的矩陣V的任意(n-s)×(n-s)的子矩陣是可逆，這一性質(zhì)符合編碼方案中能夠容忍任意s個(gè)掉隊(duì)節(jié)點(diǎn)的要求，并且可以通過將V設(shè)置為(非方)范德蒙德矩陣即可滿足此要求.另外，mn×(n-s)的矩陣B滿足2個(gè)性質(zhì):

1)B的最后m列由n個(gè)大小為n×n的單位矩陣組成;

2) 對(duì)于任意j∈［n]，B的第i行與V的第j列的乘積必須為0，其中i為一組特定的值，基數(shù)為(n-d)m.

性質(zhì)1可以保證梯度向量和的恢復(fù)，性質(zhì)2確保每個(gè)工作節(jié)點(diǎn)最多分配d個(gè)數(shù)據(jù)子集.通過利用范德蒙德構(gòu)造與多項(xiàng)式之間的本質(zhì)聯(lián)系，遞歸構(gòu)造矩陣B，更精確地說，可以把B的每一行看作某個(gè)多項(xiàng)式的系數(shù)，且B和V的乘積只是由這些多項(xiàng)式在某一點(diǎn)的值組成.然后可以通過指定它們的根來定義這些多項(xiàng)式，從而滿足B的2個(gè)性質(zhì).但是，Ye等人［37]的編碼方案所構(gòu)造的條件相較于文獻(xiàn)［36,38-40]中的編碼方案來說更為嚴(yán)格.文獻(xiàn)［24]只要求B的最后m列最多包含n個(gè)非零項(xiàng)，對(duì)這些非零項(xiàng)的位置沒有要求;文獻(xiàn)［38-40]只處理m=1的特殊情況，不允許梯度向量降維.由于條件更為寬松，文獻(xiàn)［36,38-40]中編碼方案的構(gòu)造不具有遞歸多項(xiàng)式結(jié)構(gòu)，而這正是Ye等人［37]編碼方案的主要技術(shù)創(chuàng)新所在.

通過使用帶有mpi4py包的Python在Amazon EC2集群上運(yùn)行，Ye等人［37]發(fā)現(xiàn)，與未編碼方案相比，他們的方案保持了相同的泛化誤差，同時(shí)使運(yùn)行時(shí)間減少了32%，與只關(guān)注掉隊(duì)節(jié)點(diǎn)的文獻(xiàn)［24]中的編碼方案相比減少了23%.

3.2 近似梯度編碼方案

編碼計(jì)算和梯度編碼方面的前期工作主要集中在期望輸出的完全精確恢復(fù)上，然而，稍微不精確的解決方案在抗噪聲的應(yīng)用中是可以接受的，例如通過基于梯度的算法進(jìn)行模型訓(xùn)練.Charles等人［41]提出了基于稀疏圖的簡單梯度編碼，以保證快速和近似精確的分布式計(jì)算，證明了犧牲少量的精度可以顯著提高算法對(duì)掉隊(duì)節(jié)點(diǎn)的魯棒性.這一編碼方案中，Charles等人［41]使用稀疏圖來創(chuàng)建梯度編碼，以一種分布式的方式高效準(zhǔn)確地計(jì)算近似梯度.更一般地說，這些編碼可用于以分布式方式近似計(jì)算函數(shù)的任何和.他們利用編碼理論闡述并正式引入近似恢復(fù)問題，分析并提出了2種近似重建的解碼技術(shù):一種具有多項(xiàng)式時(shí)間復(fù)雜度的最優(yōu)解碼算法和一種輸入稀疏性具有線性復(fù)雜度的快速解碼方法.他們主要關(guān)注2種不同的編碼，2種編碼方案都可以有效地進(jìn)行計(jì)算，并且每個(gè)計(jì)算節(jié)點(diǎn)只需要計(jì)算對(duì)數(shù)級(jí)的任務(wù)數(shù).第1個(gè)是文獻(xiàn)［42]中提出的部分重復(fù)碼(fractional repetition code, FRC)，即使一定比例的計(jì)算節(jié)點(diǎn)是掉隊(duì)節(jié)點(diǎn)，部分重復(fù)碼也能以較高的概率實(shí)現(xiàn)小誤差甚至是零誤差.然而，部分重復(fù)碼易受敵對(duì)掉隊(duì)節(jié)點(diǎn)的影響，即攻擊者可以強(qiáng)迫部分工作節(jié)點(diǎn)成為掉隊(duì)節(jié)點(diǎn).為了解決這個(gè)問題，Charles等人［41]提出了基于稀疏隨機(jī)圖的貝努利梯度碼(Bernoulli gradient code， BGC)和正則化貝努利梯度碼(regularized Bernoulli gradient code, rBGC)，證明了一般編碼的敵對(duì)掉隊(duì)節(jié)點(diǎn)的選擇是NP難問題，表明這些隨機(jī)的編碼對(duì)多項(xiàng)式時(shí)間的掉隊(duì)節(jié)點(diǎn)比部分重復(fù)碼有更好的性能.他們對(duì)BGC和rBGC的誤差給出了明確的界限，表明兩者對(duì)攻擊者的潛在容忍度是以比FRC更糟的平均情況誤差為代價(jià).模擬仿真的結(jié)果表明，梯度碼的解碼復(fù)雜度與其平均性能和最壞性能之間存在一定的權(quán)衡關(guān)系.

Raviv等人［40]利用經(jīng)典編碼理論中的工具設(shè)計(jì)了新的梯度碼，即循環(huán)MDS碼，以獲得既在參數(shù)的適用范圍內(nèi)，又在所涉及算法的復(fù)雜度上，與現(xiàn)有解相比更優(yōu)的確定性結(jié)構(gòu).好處之一是直接應(yīng)用了這些編碼的特性.其次，引入了梯度編碼問題的一個(gè)近似變量，精確計(jì)算整個(gè)梯度的要求被一個(gè)近似的要求所代替.但是使用這種方法時(shí)，參數(shù)s不是系統(tǒng)結(jié)構(gòu)的一部分，系統(tǒng)可以為任何s(s

4 編碼應(yīng)用于數(shù)據(jù)洗牌

數(shù)據(jù)洗牌是許多機(jī)器學(xué)習(xí)應(yīng)用程序的核心元素，以提高學(xué)習(xí)算法的統(tǒng)計(jì)性能而著稱.Lee等人在文獻(xiàn)［24]中證明了在并行機(jī)器學(xué)習(xí)算法中，編碼可以以一種新的方式來權(quán)衡額外的可用存儲(chǔ)空間，從而降低并行機(jī)器學(xué)習(xí)算法中數(shù)據(jù)洗牌的通信成本.他們展示了當(dāng)數(shù)據(jù)矩陣的常數(shù)部分可以緩存在每個(gè)工作節(jié)點(diǎn)上時(shí)(工作節(jié)點(diǎn)的總量為n)，相比于未編碼的洗牌，編碼洗牌可以降低通信成本Θ(γ(n))倍，其中：

另外，如果將消息多播給n個(gè)用戶和將消息單播給1個(gè)用戶所需通信成本相同，那么γ(n)≈n.

4.1 編碼降低洗牌階段的通信開銷

MapReduce是一個(gè)編程模型，它支持在一個(gè)商用服務(wù)器集群上對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行分布式處理.MapReduce的理想特性，例如可伸縮性、簡單性和容錯(cuò)性［44-45]，使得這個(gè)框架在文本/圖形處理、機(jī)器學(xué)習(xí)和生物信息學(xué)中執(zhí)行數(shù)據(jù)密集型工作時(shí)廣受歡迎.考慮一個(gè)用于分布式計(jì)算的通用MapReduce框架，在該框架中，整個(gè)計(jì)算被分解為3個(gè)階段:Map，Shuffle，Reduce，它們?cè)谠S多計(jì)算節(jié)點(diǎn)上分步執(zhí)行.在Map階段，在1個(gè)(或多個(gè))節(jié)點(diǎn)中本地處理每個(gè)輸入文件，以生成中間值.在Shuffle階段，對(duì)于要計(jì)算的每個(gè)輸出函數(shù)，將該函數(shù)對(duì)應(yīng)的所有中間值轉(zhuǎn)移到其中一個(gè)節(jié)點(diǎn)上進(jìn)行還原.最后，在Reduce階段，將函數(shù)的所有中間值還原為最終結(jié)果.

考慮圖11中的MapReduce問題，使用3個(gè)計(jì)算節(jié)點(diǎn)對(duì)6個(gè)輸入文件F1～F6中的3個(gè)輸出函數(shù)分別用圓、方、三角形表示,進(jìn)行分布式計(jì)算.Node1,Node2,Node3分別負(fù)責(zé)最終還原圓、方、三角形輸出函數(shù).首先考慮沒有對(duì)計(jì)算增加冗余的情況，即每個(gè)文件映射1次.如圖11(a)所示，Nodei(i=1，2，3)映射文件2i-1和2i.這種情況下，每個(gè)節(jié)點(diǎn)本地映射2個(gè)輸入文件，獲得輸出函數(shù)所需的6個(gè)中間值中的2個(gè).因此，每個(gè)節(jié)點(diǎn)需要來自其他節(jié)點(diǎn)的4個(gè)中間值，從而產(chǎn)生4×3=12的通信負(fù)載.Li等人［43]提出的編碼方案利用計(jì)算冗余通過網(wǎng)絡(luò)內(nèi)編碼來減少通信負(fù)載.如圖11(b)所示，增加計(jì)算負(fù)載的倍數(shù)，使每個(gè)文件映射到2個(gè)節(jié)點(diǎn)上.顯然，由于增加了更多的本地計(jì)算，每個(gè)節(jié)點(diǎn)只需要另外2個(gè)中間值，因此一個(gè)未編碼的洗牌方案的通信負(fù)載為2×3=6.但是，通過編碼可以達(dá)到更好的效果.如圖11(b)所示，每個(gè)節(jié)點(diǎn)不是將單個(gè)中間值進(jìn)行單播，而是將2個(gè)中間值中的XOR運(yùn)算結(jié)果(由?表示)多播給另外2個(gè)節(jié)點(diǎn)，同時(shí)滿足它們的數(shù)據(jù)需求.例如，已知文件3中的三角形后，Node2可以從Node1發(fā)送的編碼包中減去它，從而恢復(fù)所需文件1中的正方形.因此，該編碼產(chǎn)生的通信負(fù)載為3，相較于未編碼的洗牌方案實(shí)現(xiàn)了2倍的收益.

Fig.11 MapReduce scheme圖11 MapReduce框架

在文獻(xiàn)［43,46]提出的一般CMR方案中，每個(gè)Map任務(wù)的計(jì)算在r個(gè)精心選擇的節(jié)點(diǎn)上重復(fù)執(zhí)行(即導(dǎo)致r的計(jì)算負(fù)載)，以使節(jié)點(diǎn)能夠發(fā)送對(duì)其他r個(gè)節(jié)點(diǎn)同時(shí)有用的編碼多播消息.因此，CMR實(shí)現(xiàn)了1/r(正好為計(jì)算負(fù)載的倒數(shù))的通信負(fù)載，即:

(12)

Li等人［47]將文獻(xiàn)［43]中提出的編碼思想應(yīng)用于TeraSort，提出了一種新的分布式排序算法“Coded TeraSort”，大大提高了Hadoop MapReduce中TeraSort基準(zhǔn)的執(zhí)行時(shí)間.排序不僅是Hadoop MapReduce和Spark等分布式計(jì)算系統(tǒng)的基本基準(zhǔn)，也是推薦系統(tǒng)、SVD和許多圖形算法等許多機(jī)器學(xué)習(xí)算法中的關(guān)鍵步驟，并以數(shù)據(jù)洗牌為主要瓶頸.TeraSort最初是為對(duì)TB大小的數(shù)據(jù)進(jìn)行排序而開發(fā)的一種算法，是Hadoop MapReduce中常用的基準(zhǔn).與MapReduce執(zhí)行的一般結(jié)構(gòu)一致，在TeraSort執(zhí)行過程中，每個(gè)服務(wù)器節(jié)點(diǎn)首先將其本地存儲(chǔ)的每個(gè)數(shù)據(jù)點(diǎn)映射到密鑰空間的特定分區(qū)中，然后將同一分區(qū)中的所有數(shù)據(jù)點(diǎn)轉(zhuǎn)移到一個(gè)節(jié)點(diǎn)上，在該節(jié)點(diǎn)上進(jìn)行分區(qū)內(nèi)的排序，以減少最終的排序輸出.而編碼TeraSort的基本過程為:

1) 輸入數(shù)據(jù)點(diǎn)被分割成不相交的文件，每個(gè)文件存儲(chǔ)在多個(gè)精心選擇的服務(wù)器節(jié)點(diǎn)上，以對(duì)數(shù)據(jù)創(chuàng)建結(jié)構(gòu)化冗余.

2) 每個(gè)節(jié)點(diǎn)按照TeraSort的映射過程映射分配給它的所有文件.

3) 每個(gè)節(jié)點(diǎn)利用數(shù)據(jù)放置中強(qiáng)加的結(jié)構(gòu)化冗余，為數(shù)據(jù)變換創(chuàng)建編碼數(shù)據(jù)包，使得每個(gè)編碼數(shù)據(jù)包的組播同時(shí)將數(shù)據(jù)點(diǎn)發(fā)送到多個(gè)節(jié)點(diǎn)，從而加快了數(shù)據(jù)洗牌速度.

4) 每個(gè)節(jié)點(diǎn)從接收到的編碼報(bào)文中解碼其Reduce階段所需的數(shù)據(jù)點(diǎn)，并遵循TeraSort的Reduce過程.

4.2 一種數(shù)據(jù)洗牌的柔韌索引編碼方法

其次，Song等人［48]還設(shè)計(jì)了一種以約束柔韌索引編碼為組成部分的分層數(shù)據(jù)變換傳輸方案.引入漢明距離測(cè)度來量化洗牌性能，該方案在主節(jié)點(diǎn)具有線性編碼復(fù)雜度的情況下，在傳輸優(yōu)于索引編碼方面可以達(dá)到O(ns/m)，其中s是緩存大小，ns/m是緩存每個(gè)消息的平均工作節(jié)點(diǎn)的數(shù)量.

4.3 分布式學(xué)習(xí)的近最優(yōu)編碼數(shù)據(jù)洗牌

分布式節(jié)點(diǎn)集群之間的數(shù)據(jù)洗牌是實(shí)現(xiàn)大規(guī)模學(xué)習(xí)算法的關(guān)鍵步驟之一.在一組工作節(jié)點(diǎn)中隨機(jī)地洗牌數(shù)據(jù)集，允許不同的節(jié)點(diǎn)在每個(gè)學(xué)習(xí)階段獲得新的數(shù)據(jù)分配.這一過程已被證明可以改善學(xué)習(xí)過程.然而，分布式數(shù)據(jù)洗牌的優(yōu)點(diǎn)在于從主節(jié)點(diǎn)到工作節(jié)點(diǎn)的額外通信開銷較少，但是也可能成為整個(gè)計(jì)算時(shí)間的主要瓶頸之一.目前不少研究者熱衷于研究最小化通信開銷的方法，一種方法是在計(jì)算節(jié)點(diǎn)上增加額外的存儲(chǔ).另一種新興的方法是利用編碼通信原理來最小化總體通信開銷.

Attia等人［49]將重點(diǎn)放在主節(jié)點(diǎn)-工作節(jié)點(diǎn)設(shè)置的編碼數(shù)據(jù)洗牌上，在主節(jié)點(diǎn)-工作節(jié)點(diǎn)設(shè)置中，編碼機(jī)會(huì)是通過利用工作節(jié)點(diǎn)的額外存儲(chǔ)空間來創(chuàng)建的.在每次訓(xùn)練開始之前，主節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行洗牌，以便在每個(gè)工作節(jié)點(diǎn)上分配不同的訓(xùn)練數(shù)據(jù)，這樣會(huì)產(chǎn)生通信開銷.在一種極端情況下，當(dāng)所有工作節(jié)點(diǎn)都有足夠的存儲(chǔ)空間來存儲(chǔ)整個(gè)數(shù)據(jù)集時(shí)，就不需要通過通信來進(jìn)行任何隨機(jī)洗牌.另一方面，當(dāng)存儲(chǔ)空間剛好能夠存儲(chǔ)分配的數(shù)據(jù)時(shí)(也稱為無多余存儲(chǔ)情況)，那么通信開銷將會(huì)達(dá)到最大.因此，目標(biāo)是實(shí)現(xiàn)由洗牌產(chǎn)生的通信開銷與分布式工作節(jié)點(diǎn)中的可用存儲(chǔ)空間之間的基本權(quán)衡.

Attia等人［49]推導(dǎo)了最壞情況下數(shù)據(jù)洗牌問題通信開銷的理論下界.這一工作的進(jìn)行開始于在一些已選擇洗牌的速率上得到了一組下界，由于任意洗牌的速率最好與最壞情況洗牌的速率一樣大，因此得到的下界也可以作為最壞情況下速率的有效下界.然后得出所有選擇洗牌的下界平均值，這里的關(guān)鍵步驟是選擇那些導(dǎo)致作為存儲(chǔ)函數(shù)的通信開銷的最佳下界的洗牌.特別地，考慮一組循環(huán)洗牌，在隨后的2次洗牌中，分配給任何工作節(jié)點(diǎn)的數(shù)據(jù)批處理之間沒有重疊.基于一種新的邊界方法［50-51]，將下界表示為線性方程.然后，求解線性方程，以獲得不同存儲(chǔ)狀態(tài)下通信開銷的最佳下界.

4.4 分布式數(shù)據(jù)洗牌最壞情況下的通信開銷

用于處理大規(guī)模數(shù)據(jù)集的分布式學(xué)習(xí)平臺(tái)正日益流行.在典型的分布式學(xué)習(xí)平臺(tái)中，主節(jié)點(diǎn)將數(shù)據(jù)集分解成更小的快，以便跨分布式工作節(jié)點(diǎn)進(jìn)行并行處理來實(shí)現(xiàn)速度和效率的收益.由于一些計(jì)算任務(wù)是順序執(zhí)行，涉及到數(shù)據(jù)的多次傳遞，在每次數(shù)據(jù)迭代中，通常的做法是在主節(jié)點(diǎn)上隨機(jī)重新洗牌數(shù)據(jù)，為每個(gè)工作節(jié)點(diǎn)分配不同的批處理任務(wù).這種隨機(jī)的重新洗牌操作的代價(jià)是增加額外的通信開銷，因?yàn)樵诿看蜗磁茣r(shí)，需要將新的數(shù)據(jù)點(diǎn)交付給分布的工作節(jié)點(diǎn).

Attia等人［53]研究了無冗余存儲(chǔ)條件下的分布式數(shù)據(jù)洗牌問題的理論最優(yōu)通信開銷.

1) 給出了一個(gè)理論公式，借助一個(gè)描述工作節(jié)點(diǎn)中間數(shù)據(jù)流的洗牌矩陣，提出了一種新的方法來定義通信問題;

2) 提出了一種新的編碼數(shù)據(jù)傳遞方案，在沒有多余存儲(chǔ)的情況下，每個(gè)工作節(jié)點(diǎn)只能存儲(chǔ)分配的準(zhǔn)備處理的數(shù)據(jù)，與現(xiàn)有的方法相比，它利用了一種新的編碼方案來減少通信開銷，該方案適用于任意的洗牌方式和任意數(shù)量的分布式工作節(jié)點(diǎn);

3) 給出了數(shù)據(jù)洗牌最小通信開銷的理論下界，并證明了所提方案符合最壞情況下通信開銷的下界.

5 編碼的其他應(yīng)用

5.1 存在掉隊(duì)節(jié)點(diǎn)的分布式計(jì)算統(tǒng)一編碼框架

Li等人［46]提出了一個(gè)存在掉隊(duì)節(jié)點(diǎn)的分布式計(jì)算的統(tǒng)一編碼框架，在線性計(jì)算任務(wù)的計(jì)算延遲和通信負(fù)載之間進(jìn)行權(quán)衡.通過考慮這種權(quán)衡的2個(gè)極端情況:分別最小化通信負(fù)載和計(jì)算延遲，他們證明，重復(fù)中間計(jì)算以創(chuàng)建編碼多播機(jī)會(huì)以減少通信負(fù)載的文獻(xiàn)［43，54]的編碼方案，以及生成冗余中間計(jì)算以對(duì)抗掉隊(duì)節(jié)點(diǎn)的文獻(xiàn)［24]的編碼方案，可以被視為所提出框架的特殊實(shí)例.此外，所提出的編碼框架實(shí)現(xiàn)的權(quán)衡允許在該權(quán)衡上的任意一點(diǎn)進(jìn)行操作，以執(zhí)行分布式計(jì)算任務(wù).這個(gè)統(tǒng)一的編碼框架本質(zhì)上是最小帶寬碼和最小延遲碼的同時(shí)使用，在計(jì)算的不同階段分別利用這2種編碼技術(shù).在Map階段，使用MDS碼創(chuàng)建編碼任務(wù)，然后將這些任務(wù)以特定的冗余方式分配給節(jié)點(diǎn)，以便本地執(zhí)行.根據(jù)Map階段的特定計(jì)算延遲，只要有一定數(shù)量的節(jié)點(diǎn)完成本地計(jì)算，所有運(yùn)行的Map任務(wù)就會(huì)終止(即最小延遲碼).然后在Shuffle階段，貪心地利用最小帶寬碼指定的編碼組播機(jī)會(huì)，直到滿足所有節(jié)點(diǎn)的數(shù)據(jù)需求.統(tǒng)一編碼框架能夠靈活地選擇權(quán)衡點(diǎn)，以減少整個(gè)作業(yè)的執(zhí)行時(shí)間.例如當(dāng)網(wǎng)絡(luò)速度較慢時(shí)，可以等待更多節(jié)點(diǎn)完成它們的映射計(jì)算，從而創(chuàng)造更好的多播機(jī)會(huì)來進(jìn)一步削減通信數(shù)據(jù)量.另一方面，當(dāng)檢測(cè)到某些節(jié)點(diǎn)運(yùn)行緩慢或響應(yīng)緩慢時(shí)，只要執(zhí)行了足夠多的編碼任務(wù)，就可以通過結(jié)束Map階段將負(fù)載轉(zhuǎn)移到網(wǎng)絡(luò)上.Li等人［46]還證明了延遲負(fù)載權(quán)衡的一個(gè)理論下界，該下界與通信負(fù)載和計(jì)算延遲權(quán)衡關(guān)系之間存在一個(gè)不變的常量差.

5.2 分布式霧計(jì)算

Li等人［55]將文獻(xiàn)［43,54]中提出的編碼思想(稱之為最小帶寬碼)、文獻(xiàn)［24]中提出的編碼思想(稱之為最小延遲碼)和文獻(xiàn)［46]中提出的統(tǒng)一編碼框架應(yīng)用到分布式霧計(jì)算中，進(jìn)行了探討，并通過實(shí)例驗(yàn)證了這些編碼思想、框架的優(yōu)越性(可以加速總響應(yīng)時(shí)間、計(jì)算時(shí)間、增強(qiáng)系統(tǒng)魯棒性).

5.3 存在截止時(shí)間的并行和分布式計(jì)算的編碼卷積

Dutta等人［56]考慮了存在掉隊(duì)節(jié)點(diǎn)的情況下，使用并行處理器計(jì)算2個(gè)長向量的卷積問題，首先證明在簡單的最壞情況下，將向量分割成更小的片段，并使用線性編碼對(duì)這些片段進(jìn)行編碼，與基于副本的方案相比，具有更好的對(duì)抗掉隊(duì)節(jié)點(diǎn)的效果.然后他們證明，在常用的計(jì)算時(shí)間模型下，編碼可以顯著提高在目標(biāo)截止時(shí)間內(nèi)完成計(jì)算的概率.與通常使用的預(yù)期計(jì)算時(shí)間分析技術(shù)不同，Dutta等人［56]量化了失效概率的指數(shù).提出的指數(shù)度量顯示了在指定的截止時(shí)間(即尾部行為)之前未能完成的概率.此外，還允許對(duì)更通用的計(jì)算時(shí)間模型使用簡單的閉式表達(dá)式，例如移位威布爾模型，而不是對(duì)指數(shù)進(jìn)行移位.通過編碼卷積問題，Dutta等人建立了一種新的分布式系統(tǒng)用于分析漸近失效指數(shù)的實(shí)用性.

5.4 基于異構(gòu)集群的編碼計(jì)算

編碼可以有效利用計(jì)算結(jié)果和存儲(chǔ)冗余以減輕同構(gòu)集群中的掉隊(duì)節(jié)點(diǎn)和通信瓶頸的影響.但是虛擬數(shù)據(jù)中心中的計(jì)算環(huán)境是異構(gòu)的，基于同構(gòu)假設(shè)的算法會(huì)導(dǎo)致系統(tǒng)的性能大大降低.Reisizadeh等人［57]研究由各種不同性能的計(jì)算機(jī)組成的通用異構(gòu)分布式計(jì)算集群，提出了一個(gè)編碼框架，通過交換冗余來減少計(jì)算延遲，從而加速存在掉隊(duì)節(jié)點(diǎn)的異構(gòu)集群的分布式計(jì)算.他們提出了一種用于在異構(gòu)集群中加速分布式矩陣乘法的編碼框架，稱為異構(gòu)編碼矩陣乘法(heterogeneous coded matrix multi-plication, HCMM)，用于對(duì)可證明漸近最優(yōu)的異構(gòu)集群執(zhí)行分布式矩陣乘法，證明了如果集群中的工作節(jié)點(diǎn)的數(shù)量為n，HCMM比任何未編碼的框架要快Θ(lgn).

設(shè)TC為隨機(jī)變量，表示接收至少r個(gè)內(nèi)積的等待時(shí)間，即1組可解碼結(jié)果，HCMM所需解決的核心問題是下面的優(yōu)化問題:

minimizeE［TC].

(13)

對(duì)于同構(gòu)集群，為了實(shí)現(xiàn)編碼解決方案，可以將原矩陣分成k個(gè)大小相等的子矩陣，并在這k個(gè)子矩陣中運(yùn)用(n,k) MDS碼進(jìn)行編碼.然后，主節(jié)點(diǎn)可以從任意k個(gè)編碼子矩陣得到最終結(jié)果.在同構(gòu)集群中，找到足夠數(shù)量的內(nèi)積的問題可以映射到找到一組最快響應(yīng)的等待時(shí)間的問題，從而可以使用順序統(tǒng)計(jì)來發(fā)現(xiàn)預(yù)期計(jì)算時(shí)間的封閉形式表達(dá)式.文獻(xiàn)［24]找到了最小化平均運(yùn)行時(shí)間的最優(yōu)的k值.在異構(gòu)集群中，使用同構(gòu)集群中的求解方法是不可能的，因?yàn)樨?fù)載分配是不均勻的(即給每個(gè)工作節(jié)點(diǎn)分配的矩陣大小不是完全相等的).在這種情況下，同構(gòu)集群中求解式(13)顯然不再適用.Reisizadeh等人［57]提出了一種式(13)的替代公式，并證明了該公式是易解的、漸進(jìn)最優(yōu)的.

5.5 多核裝置的編碼計(jì)算

5.6 分布式計(jì)算的層次編碼

Fig.12 Illustration of hierarchical coding圖12 層次編碼示例

Fig.13 Illustration of secret sharing scheme with 3 workers圖13 3個(gè)工作節(jié)點(diǎn)的密鑰共享方案示例

5.7 安全分布式計(jì)算的最小化延遲

在進(jìn)行密集的計(jì)算(例如機(jī)器學(xué)習(xí)算法的一部分)時(shí)，主節(jié)點(diǎn)希望將這些計(jì)算任務(wù)分發(fā)給那些不受信任的工作節(jié)點(diǎn)，其中這些工作節(jié)點(diǎn)是自愿或受到激勵(lì)來幫助完成這項(xiàng)任務(wù)的.然而，這些數(shù)據(jù)(即需要計(jì)算的任務(wù))必須保持私密，不能透露給單個(gè)工作節(jié)點(diǎn).另外，工作節(jié)點(diǎn)可能會(huì)忙于處理其他計(jì)算任務(wù)，甚至沒有響應(yīng)，它們會(huì)隨機(jī)抽時(shí)間來完成分配給它們的任務(wù).一個(gè)已知的解決方案是使用一個(gè)密鑰共享的方案將數(shù)據(jù)劃分為工作節(jié)點(diǎn)可以計(jì)算的密鑰共享［60].Bitar等人［61]提出了一種新的安全編碼，稱為樓梯編碼.圖13是密鑰共享方案的簡單示例.

1) 文獻(xiàn)［60]給出的密鑰共享方案中計(jì)算任務(wù)由3個(gè)工作節(jié)點(diǎn)完成，最多允許1個(gè)工作節(jié)點(diǎn)未響應(yīng).如圖13(b)所示，主節(jié)點(diǎn)Master生成一個(gè)隨機(jī)矩陣R，其維數(shù)與A相同，在相同的域內(nèi)，并將A和R編碼為3個(gè)子矩陣S1=R，S2=R+A,S3=R+2A分別發(fā)送給3個(gè)節(jié)點(diǎn).主節(jié)點(diǎn)收到任意2個(gè)節(jié)點(diǎn)的返回結(jié)果可解碼出計(jì)算結(jié)果.

2) 文獻(xiàn)［61]給出的樓梯編碼方案中主節(jié)點(diǎn)Master將矩陣A和R分成A=［A1A2]T和R=［R1R2]T，將子任務(wù)A1+A2+R1和R1+R2發(fā)送給工作節(jié)點(diǎn)1，將子任務(wù)A1+2A2+4R1和R1+2R2發(fā)送給工作節(jié)點(diǎn)2，將子任務(wù)A1+3A2+4R1和R1+3R2發(fā)送給工作節(jié)點(diǎn)3.主節(jié)點(diǎn)有2種解碼的可能:

① 主節(jié)點(diǎn)接收(A1+A2+R1)x,(A1+2A2+4R1)x,(A1+3A2+4R1)x可解碼出計(jì)算結(jié)果，此時(shí)只需解碼R1x，不需要解碼R2x;

② 主節(jié)點(diǎn)接收任意2個(gè)節(jié)點(diǎn)的全部子任務(wù)結(jié)果可解碼出計(jì)算結(jié)果，此時(shí)需解碼R1x和R2x.

Bitar等人［61]提出了一個(gè)主節(jié)點(diǎn)Master擁有整個(gè)數(shù)據(jù)集的模型，在該模型上Master要執(zhí)行分布式線性計(jì)算，引入了一種新的方法，將線性計(jì)算安全外包給不擁有該數(shù)據(jù)任何部分的n個(gè)工作節(jié)點(diǎn).他們假設(shè)，最多n-k(k

5.8 近似矩陣編碼

文獻(xiàn)［24]的核心思想是利用MDS碼生成冗余計(jì)算來減輕掉隊(duì)節(jié)點(diǎn)的影響，這種方法的一個(gè)特點(diǎn)是直到得到精確解才會(huì)有最終輸出，因此，過多處理器節(jié)點(diǎn)的輸出延遲會(huì)顯著影響總?cè)蝿?wù)的時(shí)延.然而，如果放松對(duì)精確解的要求，那么這個(gè)問題就會(huì)得到有效緩解.針對(duì)這一情況，Nuwan等人［62]提出了一種用于近似矩陣乘法的任意時(shí)刻編碼方案，通過近似計(jì)算的形式來加速分布式計(jì)算.將任務(wù)分解成優(yōu)先級(jí)不同的若干子任務(wù)，在矩陣乘法中表現(xiàn)為矩陣的大小不同，越大的矩陣優(yōu)先級(jí)越高；然后按優(yōu)先級(jí)順序分配工作節(jié)點(diǎn)，矩陣越大，分配的工作節(jié)點(diǎn)數(shù)量就越多.編碼優(yōu)點(diǎn)在于，可以在任意時(shí)刻結(jié)束處理任務(wù)，而且在任意時(shí)刻結(jié)束任務(wù)時(shí)都可以使用已完成任務(wù)的輸出來產(chǎn)生一個(gè)近似解，并可以計(jì)算這個(gè)解的精度.顯然，近似解的精度隨著時(shí)間的推移而提高.文獻(xiàn)［24]關(guān)注于得到精確的結(jié)果，而在Nuwan等人［62]的模型中，不需要等到輸出的特定子集以找到精確的結(jié)果，相反，隨著工作的完成，可以形成一個(gè)增量改進(jìn)的過程，與現(xiàn)有編碼方案相比，該方案能提高近似質(zhì)量，便于近似計(jì)算.

6 總結(jié)與展望

本文將基于編碼技術(shù)改進(jìn)大規(guī)模機(jī)器學(xué)習(xí)集群性能的研究按照應(yīng)用場(chǎng)景分成了應(yīng)用于矩陣乘法、梯度計(jì)算、數(shù)據(jù)洗牌和一些其他應(yīng)用，并分別進(jìn)行了介紹并比對(duì)分析.

編碼在存儲(chǔ)領(lǐng)域的研究成果并不能直接應(yīng)用在機(jī)器學(xué)習(xí)算法中，因?yàn)镋C編碼應(yīng)用于存儲(chǔ)領(lǐng)域抵抗“erasure”節(jié)點(diǎn)對(duì)數(shù)據(jù)可靠性造成的影響與應(yīng)用于大規(guī)模機(jī)器學(xué)習(xí)集群中抵抗掉隊(duì)節(jié)點(diǎn)對(duì)分布式機(jī)器學(xué)習(xí)算法性能造成的影響存在著很大的區(qū)別，前者增加的是數(shù)據(jù)的冗余，后者則是通過增加數(shù)據(jù)冗余來增加計(jì)算任務(wù)的冗余;后者關(guān)注于對(duì)掉隊(duì)節(jié)點(diǎn)的魯棒性，前者相較于對(duì)erasure節(jié)點(diǎn)的魯棒性更加關(guān)注于如何對(duì)失效數(shù)據(jù)進(jìn)行修復(fù).

近幾年，學(xué)術(shù)界對(duì)通過使用編碼技術(shù)來解決分布式計(jì)算系統(tǒng)中的掉隊(duì)節(jié)點(diǎn)問題，以及改進(jìn)大規(guī)模機(jī)器學(xué)習(xí)集群性能等問題進(jìn)行了研究，并取得了一定的成果，但仍然還存在很多問題需要進(jìn)一步的研究.本文提出3個(gè)亟待解決的問題和該領(lǐng)域的研究趨勢(shì)：

1) 目前提出的通過編碼技術(shù)提高對(duì)掉隊(duì)節(jié)點(diǎn)的魯棒性的編碼方案只是針對(duì)矩陣乘法等不需要進(jìn)行迭代的機(jī)器學(xué)習(xí)算法，而對(duì)涉及到迭代的梯度下降算法只是采用了副本這一方式，因?yàn)楦北局獾木幋a方案需要預(yù)先設(shè)計(jì)編碼塊來提供計(jì)算任務(wù)的冗余，從而實(shí)現(xiàn)對(duì)掉隊(duì)節(jié)點(diǎn)的容忍，而涉及到迭代的機(jī)器學(xué)習(xí)算法的每一次迭代的數(shù)據(jù)是不同的，很難實(shí)現(xiàn)對(duì)每次迭代數(shù)據(jù)進(jìn)行編碼.如何使用其他編碼方案而不只是副本改進(jìn)存在迭代的機(jī)器學(xué)習(xí)算法的性能，在我們看來可以作為今后對(duì)基于編碼技術(shù)改進(jìn)大規(guī)模機(jī)器學(xué)習(xí)集群性能的研究方向之一.另外，將本文提到的編碼方案拓展到更多的機(jī)器學(xué)習(xí)應(yīng)用也是今后研究的一個(gè)趨勢(shì).

2) 現(xiàn)有的研究都是理論分析，所進(jìn)行的實(shí)驗(yàn)與測(cè)試也只是模擬分布式場(chǎng)景對(duì)編碼方案進(jìn)行簡單的實(shí)現(xiàn)和測(cè)試其性能，并沒有具體應(yīng)用于現(xiàn)有的機(jī)器學(xué)習(xí)算法.因此，對(duì)編碼技術(shù)的實(shí)際應(yīng)用還需要進(jìn)一步研究，比如，多項(xiàng)式編碼中涉及到很多參數(shù)，在實(shí)際應(yīng)用中不同參數(shù)的設(shè)置對(duì)分布式機(jī)器學(xué)習(xí)集群的性能會(huì)產(chǎn)生不同的影響.

3) 利用計(jì)算機(jī)集群，使機(jī)器學(xué)習(xí)算法更好地從大數(shù)據(jù)中訓(xùn)練出性能優(yōu)良的大模型是分布式機(jī)器學(xué)習(xí)的目標(biāo).為了實(shí)現(xiàn)這一目標(biāo)，一般需要根據(jù)硬件資源與數(shù)據(jù)/模型規(guī)模的匹配情況，考慮對(duì)計(jì)算任務(wù)、訓(xùn)練數(shù)據(jù)和模型進(jìn)行劃分，考慮對(duì)計(jì)算任務(wù)、訓(xùn)練數(shù)據(jù)和模型進(jìn)行劃分，然后對(duì)劃分后的計(jì)算任務(wù)等進(jìn)行分布式存儲(chǔ)和分布式訓(xùn)練．分布式機(jī)器學(xué)習(xí)可以分為計(jì)算并行模式、數(shù)據(jù)并行模式和模型并行模式.現(xiàn)有的編碼技術(shù)目前只應(yīng)用在數(shù)據(jù)并行模式上，對(duì)于如何應(yīng)用在模型并行上尚未有相關(guān)討論.另外，不同的數(shù)據(jù)并行和模型并行方法之間是可以互相結(jié)合的，而在此基礎(chǔ)上如何應(yīng)用編碼技術(shù)更是需要今后進(jìn)行研究與探討.