編碼技術改進大規模分布式機器學習性能綜述

王 艷 李念爽 王希齡 鐘鳳艷

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

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

在最近的研究中，許多研究者使用編碼技術來解決這個問題.幾十年來，編碼在提供抵抗系統噪聲方面的作用已經在其他工程環境中得到了肯定，它是我們日常基礎設施(智能手機、筆記本電腦、WiFi和蜂窩系統等)的一部分.本論文綜述的是如何將編碼技術應用于分布式機器學習算法以抵抗“噪聲”對分布式算法的影響.如圖1所示，分布式機器學習算法的工作流程可以分解為3個功能階段:存儲、通信和計算階段.

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

1 背景介紹

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

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

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

為了減輕系統噪聲的影響，可以采取在分布式存儲系統中預先增加冗余數據或在分布式計算系統中增加冗余任務的方法，以容忍受系統噪聲影響的數據或任務.為了確保數據完整性，將數據復制多份存儲在不同的服務器上是實際生產中許多分布式存儲系統采用的方法.同時，利用存儲系統中的數據副本使得在分布式計算系統中以較小開銷方便地復制計算任務成為可能.因此，受系統噪聲影響的計算任務可以被容忍，因為該計算任務的結果仍然可以從另一臺服務器獲得.

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

之前對EC編碼技術的研究應用大多都集中于分布式存儲領域，研究如何用這一編碼技術增加相應的“冗余存儲”以抵抗“erasure”節點對數據可靠性造成的影響，其中“erasure”節點是指由于各種原因導致的系統中失效的存儲節點.本文則是聚焦于編碼技術在分布式計算領域中的應用，介紹近幾年對于如何用編碼技術增加相應的“冗余計算”以改進大規模機器學習集群性能的研究進展，研究將大規模機器學習集群中的“straggler”看成是計算集群中的1個“erasure”節點，如何增加相應的“冗余計算”以抵抗“erasure”節點對分布式機器學習算法性能造成的影響.

目前基于編碼技術改進大規模機器學習集群性能的研究，涉及在矩陣乘法、梯度計算、數據洗牌和其他一些機器學習領域的應用，本文將在后續章節中分別進行介紹.

2 編碼技術應用于矩陣乘法

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

2.1 編碼應用于矩陣-向量乘法

假設由于系統噪聲，工作節點的延遲是不可預測的.目標是在有掉隊節點存在的情況下盡可能快地計算矩陣-向量乘法AX，其中A是一個m×n的矩陣，X是一個n×1的一維矩陣，即向量.副本方案、MDS編碼方案、無碼率編碼方案都是基于此目標來優化矩陣-向量乘法，下面分別介紹這3種方案，并進行分析和比較.

2.1.1 副本方案

對抗掉隊節點的一種最基本的方法是使用副本方案，將每個計算任務以副本的形式在多個工作節點上并行執行，當任一節點完成工作后，該計算任務就被完成.本文把副本方案看作諸多編碼方案中的一種特殊情況.圖2給出了副本方案的簡單示例.

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

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

2.1.2 MDS編碼方案

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

使用編碼可以利用更多的節點緩解掉隊節點的影響，Lee等人［24]通過分析表明：如果n個工作節點執行任務的時間屬于獨立同指數分布，那么最優的編碼矩陣乘法會比未編碼的矩陣乘法平均快Θ(lgn)倍.

Fig.3 Illustration of a system with 1 master and 3 workers圖3 擁有1個主節點和3個工作節點的系統示例

2.1.3 無碼率編碼方案

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

(1)

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

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

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

無碼率編碼方案與MDS編碼方案相比具有4個優點:

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

2) 無碼率編碼方案最多只需完成m(1+ε)個計算任務，而MDS編碼在沒有掉隊節點存在時，工作節點將會共同完成mp/k個計算任務;

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

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

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

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

2.2 編碼應用于矩陣-矩陣乘法

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

現今對這一問題提出了MDS碼、乘積碼、多項式碼等編碼解決方案，下面將對這些方案進行介紹.

2.2.1 MDS編碼方案

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

(2)

Fig.6 Illustration of 1D MDS code with 3 workers圖6 3個工作節點的1D MDS碼示例

2.2.2 乘積碼編碼方案

Fig.7 Illustration of product code with 9 workers圖7 9個工作節點的乘積碼示例

(3)

該方案的恢復閾值相較于一維MDS碼有著明顯的改進.

2.2.3 多項式碼編碼方案

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

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

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

(4)

因而，實際所需計算的內容就變成了4個未編碼的部分:

(5)

現在設計一種計算策略來實現最優恢復閾值4，每個工作節點i(i∈{1,2,…,4})存儲2個編碼子矩陣:

(6)

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

Fig.8 Illustration of polynomial code with 5 workers圖8 擁有5個工作節點的多項式碼示例

根據設計的計算策略，可以得到:

(7)

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

具體地說，在本例中，每個工作節點i都返回給主節點結果:

(8)

也就是多項式在x=i處的值:

(9)

因此，使用4個工作節點的計算結果恢復C等價于在給定值的情況下在第4個點處插值一個3次多項式.

Kpolymn=Θ(1).

(10)

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

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

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

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

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

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

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

3 編碼應用于梯度計算

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

3.1 精確梯度編碼方案

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

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

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

3) 當計算完成時，每個工作節點傳輸其所計算部分的梯度的和到主節點.

圖9為n=6,s=2時的構造實例，對2個掉隊節點具有魯棒性.

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

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

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

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

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

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

(11)

其中,n為工作節點的數量，k為數據子集的數量，d為分配給每個工作節點的數據子集的數量，s為掉隊節點的數量，m為通信下降因子.這一權衡概括了文獻［36]中對應于m=1的結果.

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

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

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

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

通過使用帶有mpi4py包的Python在Amazon EC2集群上運行，Ye等人［37]發現，與未編碼方案相比，他們的方案保持了相同的泛化誤差，同時使運行時間減少了32%，與只關注掉隊節點的文獻［24]中的編碼方案相比減少了23%.

3.2 近似梯度編碼方案

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

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

4 編碼應用于數據洗牌

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

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

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

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

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

Fig.11 MapReduce scheme圖11 MapReduce框架

在文獻［43,46]提出的一般CMR方案中，每個Map任務的計算在r個精心選擇的節點上重復執行(即導致r的計算負載)，以使節點能夠發送對其他r個節點同時有用的編碼多播消息.因此，CMR實現了1/r(正好為計算負載的倒數)的通信負載，即:

(12)

Li等人［47]將文獻［43]中提出的編碼思想應用于TeraSort，提出了一種新的分布式排序算法“Coded TeraSort”，大大提高了Hadoop MapReduce中TeraSort基準的執行時間.排序不僅是Hadoop MapReduce和Spark等分布式計算系統的基本基準，也是推薦系統、SVD和許多圖形算法等許多機器學習算法中的關鍵步驟，并以數據洗牌為主要瓶頸.TeraSort最初是為對TB大小的數據進行排序而開發的一種算法，是Hadoop MapReduce中常用的基準.與MapReduce執行的一般結構一致，在TeraSort執行過程中，每個服務器節點首先將其本地存儲的每個數據點映射到密鑰空間的特定分區中，然后將同一分區中的所有數據點轉移到一個節點上，在該節點上進行分區內的排序，以減少最終的排序輸出.而編碼TeraSort的基本過程為:

1) 輸入數據點被分割成不相交的文件，每個文件存儲在多個精心選擇的服務器節點上，以對數據創建結構化冗余.

2) 每個節點按照TeraSort的映射過程映射分配給它的所有文件.

3) 每個節點利用數據放置中強加的結構化冗余，為數據變換創建編碼數據包，使得每個編碼數據包的組播同時將數據點發送到多個節點，從而加快了數據洗牌速度.

4) 每個節點從接收到的編碼報文中解碼其Reduce階段所需的數據點，并遵循TeraSort的Reduce過程.

4.2 一種數據洗牌的柔韌索引編碼方法

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

4.3 分布式學習的近最優編碼數據洗牌

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

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

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

4.4 分布式數據洗牌最壞情況下的通信開銷

用于處理大規模數據集的分布式學習平臺正日益流行.在典型的分布式學習平臺中，主節點將數據集分解成更小的快，以便跨分布式工作節點進行并行處理來實現速度和效率的收益.由于一些計算任務是順序執行，涉及到數據的多次傳遞，在每次數據迭代中，通常的做法是在主節點上隨機重新洗牌數據，為每個工作節點分配不同的批處理任務.這種隨機的重新洗牌操作的代價是增加額外的通信開銷，因為在每次洗牌時，需要將新的數據點交付給分布的工作節點.

Attia等人［53]研究了無冗余存儲條件下的分布式數據洗牌問題的理論最優通信開銷.

1) 給出了一個理論公式，借助一個描述工作節點中間數據流的洗牌矩陣，提出了一種新的方法來定義通信問題;

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

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

5 編碼的其他應用

5.1 存在掉隊節點的分布式計算統一編碼框架

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

5.2 分布式霧計算

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

5.3 存在截止時間的并行和分布式計算的編碼卷積

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

5.4 基于異構集群的編碼計算

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

設TC為隨機變量，表示接收至少r個內積的等待時間，即1組可解碼結果，HCMM所需解決的核心問題是下面的優化問題:

minimizeE［TC].

(13)

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

5.5 多核裝置的編碼計算

5.6 分布式計算的層次編碼

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

Fig.13 Illustration of secret sharing scheme with 3 workers圖13 3個工作節點的密鑰共享方案示例

5.7 安全分布式計算的最小化延遲

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

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

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

① 主節點接收(A1+A2+R1)x,(A1+2A2+4R1)x,(A1+3A2+4R1)x可解碼出計算結果，此時只需解碼R1x，不需要解碼R2x;

② 主節點接收任意2個節點的全部子任務結果可解碼出計算結果，此時需解碼R1x和R2x.

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

5.8 近似矩陣編碼

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

6 總結與展望

本文將基于編碼技術改進大規模機器學習集群性能的研究按照應用場景分成了應用于矩陣乘法、梯度計算、數據洗牌和一些其他應用，并分別進行了介紹并比對分析.

編碼在存儲領域的研究成果并不能直接應用在機器學習算法中，因為EC編碼應用于存儲領域抵抗“erasure”節點對數據可靠性造成的影響與應用于大規模機器學習集群中抵抗掉隊節點對分布式機器學習算法性能造成的影響存在著很大的區別，前者增加的是數據的冗余，后者則是通過增加數據冗余來增加計算任務的冗余;后者關注于對掉隊節點的魯棒性，前者相較于對erasure節點的魯棒性更加關注于如何對失效數據進行修復.

近幾年，學術界對通過使用編碼技術來解決分布式計算系統中的掉隊節點問題，以及改進大規模機器學習集群性能等問題進行了研究，并取得了一定的成果，但仍然還存在很多問題需要進一步的研究.本文提出3個亟待解決的問題和該領域的研究趨勢：

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

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

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