鄭騰飛 周桐慶 蔡志平 吳虹佳

(國防科技大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)沙 410073)

隨著機(jī)器學(xué)習(xí)和大數(shù)據(jù)分析應(yīng)用的涌現(xiàn)，相關(guān)數(shù)據(jù)集規(guī)模不斷增長(zhǎng)，分布式地執(zhí)行應(yīng)用的計(jì)算任務(wù)可有效整合資源、緩解計(jì)算壓力.然而，分布式計(jì)算所需的頻繁數(shù)據(jù)洗牌常導(dǎo)致較高的通信負(fù)載，等待計(jì)算速度緩慢或發(fā)生故障節(jié)點(diǎn)的響應(yīng)還會(huì)引入計(jì)算延遲，而節(jié)點(diǎn)的可信問題進(jìn)一步制約著分布式計(jì)算范式的應(yīng)用和發(fā)展.

近年來，研究人員將編碼理論應(yīng)用到分布式計(jì)算領(lǐng)域，提出了一種新的計(jì)算框架——編碼計(jì)算(code computing, CC)，旨在借助靈活多樣的編碼技術(shù)，降低通信負(fù)載，緩解計(jì)算延遲，并抵抗系統(tǒng)中的拜占庭攻擊，保護(hù)數(shù)據(jù)隱私.例如，文獻(xiàn)[1]通過對(duì)分布式計(jì)算任務(wù)的中間結(jié)果進(jìn)行異或編碼，減少工作節(jié)點(diǎn)之間需要傳輸?shù)男畔?shù)量和大小，以此顯著減少通信負(fù)載.在另一個(gè)例子中，文獻(xiàn)[2]利用糾刪碼對(duì)工作節(jié)點(diǎn)的任務(wù)進(jìn)行編碼，使得主節(jié)點(diǎn)能夠從部分完成任務(wù)的節(jié)點(diǎn)中恢復(fù)最終結(jié)果，從而減少計(jì)算延遲.

鑒于其在通信、存儲(chǔ)和計(jì)算復(fù)雜度等方面的優(yōu)勢(shì)，編碼計(jì)算一經(jīng)提出便引起研究人員的廣泛關(guān)注，逐漸成為支撐有效分布式計(jì)算的熱門研究方向.當(dāng)前編碼計(jì)算方案種類繁多、編碼形式多樣，有必要對(duì)當(dāng)前方案進(jìn)行總結(jié)和分析，以此為分布式計(jì)算、高性能計(jì)算、安全計(jì)算以及分布式機(jī)器學(xué)習(xí)、聯(lián)邦學(xué)習(xí)的研究人員提供啟發(fā)和思考.我們將本文和當(dāng)前相關(guān)綜述文獻(xiàn)覆蓋的編碼方案進(jìn)行了對(duì)比，如表1所示:

Table 1 Comparison of Existing Reviews on Coded Computing表1 已有編碼計(jì)算相關(guān)綜述文獻(xiàn)對(duì)比

其中，文獻(xiàn)[3]總結(jié)了利用編碼技術(shù)改進(jìn)分布式機(jī)器學(xué)習(xí)性能的研究進(jìn)展，缺少對(duì)基于編碼計(jì)算解決通信和安全隱私問題的總結(jié)和評(píng)述.同時(shí)，除分布式機(jī)器學(xué)習(xí)之外，在其他分布式計(jì)算場(chǎng)景中(例如，無線分布式網(wǎng)絡(luò)、異構(gòu)分布式網(wǎng)絡(luò)、邊緣計(jì)算網(wǎng)絡(luò))編碼計(jì)算技術(shù)面臨的挑戰(zhàn)也不盡相同，本文結(jié)合技術(shù)分析對(duì)編碼計(jì)算在多場(chǎng)景下的使用進(jìn)行挖掘分析.另一方面，文獻(xiàn)[4]的綜述內(nèi)容局限于對(duì)相關(guān)領(lǐng)域內(nèi)一部分工作的細(xì)化闡述，缺乏對(duì)編碼計(jì)算相關(guān)技術(shù)進(jìn)展的細(xì)粒度對(duì)比和解析，參考價(jià)值有限.為滿足分布式計(jì)算研究者靈活運(yùn)用編碼計(jì)算技術(shù)，構(gòu)建更為實(shí)用的分布式計(jì)算應(yīng)用(例如聯(lián)邦遷移學(xué)習(xí))，尚且需要對(duì)涉及多場(chǎng)景，多類問題的編碼計(jì)算架構(gòu)與技術(shù)予以全面綜述.

本文貢獻(xiàn)為：據(jù)作者所知，本文首次相對(duì)全面地總結(jié)了編碼計(jì)算的當(dāng)前研究進(jìn)展.首先，對(duì)編碼計(jì)算的基本原理進(jìn)行介紹，并對(duì)現(xiàn)有編碼計(jì)算方案進(jìn)行分類.根據(jù)不同的應(yīng)用目標(biāo)，本文將編碼計(jì)算方案分為面向通信瓶頸、面向計(jì)算延遲、面向安全隱私3類.進(jìn)一步，分別從這3個(gè)方向?qū)ΜF(xiàn)有編碼計(jì)算方案進(jìn)行了綜述，重點(diǎn)包括：1)介紹分析了Master-Worker架構(gòu)下的面向通信瓶頸的編碼計(jì)算方案；2)根據(jù)不同的計(jì)算任務(wù)(矩陣乘法、梯度下降等)，分別對(duì)面向計(jì)算延遲的編碼計(jì)算方案進(jìn)行了討論和總結(jié)；3)從對(duì)抗惡意節(jié)點(diǎn)和防止數(shù)據(jù)泄露2方面分析總結(jié)了編碼計(jì)算在分布式計(jì)算安全和隱私方向的研究進(jìn)展.

1 編碼計(jì)算概述

1.1 問題分析

分布式計(jì)算相關(guān)技術(shù)和理念已經(jīng)在各種應(yīng)用和場(chǎng)景中得以運(yùn)用，然而，當(dāng)在大量節(jié)點(diǎn)上分布式執(zhí)行計(jì)算任務(wù)時(shí)，分布式計(jì)算系統(tǒng)將面臨3個(gè)挑戰(zhàn)：

1) 數(shù)據(jù)洗牌帶來的通信瓶頸.數(shù)據(jù)洗牌是分布式計(jì)算系統(tǒng)的核心步驟，其目的是在分布式計(jì)算節(jié)點(diǎn)之間交換中間值或原始數(shù)據(jù).例如，在MapReduce架構(gòu)中，數(shù)據(jù)從Mapper被傳輸?shù)絉educer.通過對(duì)Facebook的Hadoop架構(gòu)進(jìn)行追蹤分析，平均有33%的作業(yè)執(zhí)行時(shí)間都花費(fèi)在數(shù)據(jù)洗牌上[5].在TeraSort，WordCount，RankedInvertedIndex和SelfJoin等應(yīng)用程序中，50%～70%的執(zhí)行時(shí)間用于數(shù)據(jù)洗牌[6].然而，在每一次數(shù)據(jù)洗牌過程中，整個(gè)數(shù)據(jù)集都通過網(wǎng)絡(luò)進(jìn)行通信.頻繁數(shù)據(jù)交互帶來的通信開銷造成了分布式計(jì)算系統(tǒng)的性能瓶頸.

2) 掉隊(duì)節(jié)點(diǎn)帶來的計(jì)算延遲.分布式計(jì)算系統(tǒng)由大量計(jì)算節(jié)點(diǎn)執(zhí)行計(jì)算任務(wù)，其中一部分工作節(jié)點(diǎn)的計(jì)算速度可能比平均速度慢5～8倍，甚至?xí)霈F(xiàn)未知故障[7]，這類節(jié)點(diǎn)被稱為“掉隊(duì)節(jié)點(diǎn)(straggler)”.等待掉隊(duì)節(jié)點(diǎn)的反饋會(huì)給整個(gè)計(jì)算任務(wù)造成不可預(yù)測(cè)的延遲[8]，降低系統(tǒng)性能.

3) 安全和隱私.計(jì)算分布引入的另一個(gè)重要問題是計(jì)算/工作節(jié)點(diǎn)存在不可控，不可靠等問題.與傳統(tǒng)集中式計(jì)算不同，分布式計(jì)算中的工作節(jié)點(diǎn)很可能是多個(gè)所有人的資產(chǎn)，這就使得數(shù)據(jù)輸入到系統(tǒng)后訪問面被動(dòng)增加，導(dǎo)致數(shù)據(jù)的隱私受到威脅.例如，將涉及到用戶個(gè)人健康情況的醫(yī)療數(shù)據(jù)分發(fā)到多個(gè)節(jié)點(diǎn)可能會(huì)造成隱私泄露.與此同時(shí)，拜占庭攻擊是分布式系統(tǒng)面臨的一個(gè)傳統(tǒng)的安全威脅，節(jié)點(diǎn)提交錯(cuò)誤信息將誤導(dǎo)最終的計(jì)算結(jié)果，極大地影響系統(tǒng)可用性.

1.2 編碼計(jì)算方案分類

由1.1分析可知分布式計(jì)算系統(tǒng)主要面臨3個(gè)方面的挑戰(zhàn)：1)數(shù)據(jù)洗牌帶來的通信瓶頸；2)掉隊(duì)節(jié)點(diǎn)造成的不可預(yù)測(cè)的延遲；3)系統(tǒng)安全和數(shù)據(jù)隱私.這三者嚴(yán)重制約著系統(tǒng)的擴(kuò)展性和服務(wù)性能.為應(yīng)對(duì)上述挑戰(zhàn)，研究人員提出了一系列編碼計(jì)算方案.根據(jù)各方案的主要功能和目標(biāo)，可以相應(yīng)地將編碼計(jì)算方案分為3類：

1) 優(yōu)化通信負(fù)載編碼.以降低分布式計(jì)算系統(tǒng)的通信開銷.優(yōu)化通信負(fù)載編碼方案通過增加額外的計(jì)算操作，創(chuàng)建編碼機(jī)會(huì)，從而減少數(shù)據(jù)洗牌所需的通信負(fù)載.文獻(xiàn)[1]是該方向的第一篇研究，其在分布式計(jì)算負(fù)載和通信負(fù)載之間實(shí)現(xiàn)了逆線性平衡——將計(jì)算負(fù)載增加r倍(即在r個(gè)節(jié)點(diǎn)上計(jì)算每個(gè)任務(wù))，則可以將通信負(fù)載降低r倍.隨后，文獻(xiàn)[9-12]將文獻(xiàn)[1]方案分別擴(kuò)展到無線分布式網(wǎng)絡(luò)，多階段數(shù)據(jù)流應(yīng)用程序，計(jì)算任務(wù)密集型分布式系統(tǒng)和異構(gòu)分布式網(wǎng)絡(luò)中，有效降低了不同分布式計(jì)算場(chǎng)景下的通信負(fù)載.Attia等人[13]提出了一種用于分布式機(jī)器學(xué)習(xí)的近乎最佳的編碼數(shù)據(jù)洗牌方案，得到工作節(jié)點(diǎn)不同存儲(chǔ)方式下通信開銷的最優(yōu)下界.Li等人[14]提出了一種壓縮編碼分布式計(jì)算方案，相比于文獻(xiàn)[1]方案進(jìn)一步降低了分布式計(jì)算系統(tǒng)中的通信負(fù)載.Song等人[15]對(duì)索引編碼方案[11]進(jìn)行修改，并在此基礎(chǔ)上提出了一種用于分布式計(jì)算系統(tǒng)的半隨機(jī)柔韌性索引編碼數(shù)據(jù)洗牌方案，該方案平均能節(jié)省87%的傳輸開銷.

2) 最小化計(jì)算延遲編碼.以減輕分布式計(jì)算系統(tǒng)的掉隊(duì)節(jié)點(diǎn)導(dǎo)致的延遲弊端.最小化計(jì)算延遲編碼計(jì)算方案能夠在計(jì)算負(fù)載和計(jì)算延遲(即整個(gè)作業(yè)響應(yīng)時(shí)間)之間進(jìn)行逆線性平衡.換言之，該方向的編碼計(jì)算方案利用編碼來有效地注入冗余計(jì)算，以此來減輕掉隊(duì)節(jié)點(diǎn)的影響，并通過注入與冗余量成比例的乘法因子來加速計(jì)算.Lee等人[2]利用最大距離可分碼(maximum distance separable code, MDS碼)首次解決分布式矩陣-向量乘法中的延遲問題，并且降低了分布式機(jī)器學(xué)習(xí)算法中數(shù)據(jù)洗牌的通信成本.和文獻(xiàn)[2]目標(biāo)一致，文獻(xiàn)[16-18]分別提出了不同的編碼計(jì)算方案，以降低分布式矩陣-向量乘法中的計(jì)算延遲.除此之外，針對(duì)其他分布式計(jì)算任務(wù)如矩陣-矩陣乘法[19-23]、梯度下降[24-29]、卷積計(jì)算、傅里葉轉(zhuǎn)換[30-31]和非線性計(jì)算[32]等中的計(jì)算延遲，研究人員也提出了相應(yīng)的編碼計(jì)算方案.

為了處理異構(gòu)分布式計(jì)算系統(tǒng)中的掉隊(duì)節(jié)點(diǎn)，必須考慮到為異構(gòu)節(jié)點(diǎn)設(shè)計(jì)負(fù)載平衡策略[33-38]，以最大程度地減少總體作業(yè)執(zhí)行時(shí)間.考慮到分布式計(jì)算系統(tǒng)中掉隊(duì)節(jié)點(diǎn)的動(dòng)態(tài)性，如何有效地利用掉隊(duì)節(jié)點(diǎn)所做的計(jì)算結(jié)果優(yōu)化計(jì)算延遲也引起了研究人員的廣泛關(guān)注[39-43].

3) 安全和隱私編碼.為分布式計(jì)算系統(tǒng)提供安全的計(jì)算過程.為抵抗梯度下降中的拜占庭攻擊，Chen等人[44]利用編碼理論的思想提出了DRACO編碼計(jì)算方案.Gupta等人[45]利用“響應(yīng)冗余”，可在梯度聚合時(shí)檢測(cè)出計(jì)算錯(cuò)誤的節(jié)點(diǎn).Data等人[46]通過對(duì)數(shù)據(jù)進(jìn)行編碼，基于錯(cuò)誤校正[47]設(shè)計(jì)了一種抗拜占庭攻擊的分布式優(yōu)化算法.Yu等人[48]提出一種拉格朗日編碼計(jì)算(Lagrange coded computing, LCC)方案，該方案對(duì)輸入數(shù)據(jù)進(jìn)行編碼，不僅可以減少計(jì)算延遲，而且可以抵抗惡意節(jié)點(diǎn)的攻擊，保護(hù)數(shù)據(jù)隱私.作為L(zhǎng)CC的擴(kuò)展，So等人[49]提出了一種快速且具有隱私保護(hù)功能的分布式機(jī)器學(xué)習(xí)框架——CodedPrivateML. Nodehi等人[50]將多項(xiàng)式碼與BGW方案[51]結(jié)合在一起，提出了一種多項(xiàng)式共享方案.隨后，針對(duì)矩陣乘法，研究人員分別提出了單邊隱私[52-54]和雙邊隱私[55-58]的編碼計(jì)算方案.文獻(xiàn)[59]針對(duì)邊緣計(jì)算架構(gòu)中源節(jié)點(diǎn)、工作節(jié)點(diǎn)、主節(jié)點(diǎn)不同的隱私需求設(shè)計(jì)了相應(yīng)的編碼計(jì)算方案.

表2按照分類思路列出了代表性工作，將在第3～5節(jié)詳細(xì)介紹，分析各分類的典型工作.

Table 2 Classification of Coded Computing Schemes表2 編碼計(jì)算方案分類

1.3 編碼計(jì)算定義

編碼計(jì)算目前還未有一個(gè)嚴(yán)格的統(tǒng)一的定義，為簡(jiǎn)要說明編碼計(jì)算的思想，列舉2個(gè)示例：

示例1.降低通信負(fù)載編碼[2].假設(shè)一個(gè)分布式計(jì)算系統(tǒng)具有2個(gè)工作節(jié)點(diǎn)和1個(gè)主節(jié)點(diǎn)，現(xiàn)有一個(gè)大數(shù)據(jù)矩陣被分為4個(gè)子矩陣，即A1,A2,A3,A4，分別存儲(chǔ)在節(jié)點(diǎn)W1和W2中，如圖1(a)所示.其目標(biāo)是主節(jié)點(diǎn)將A3傳輸至W1，并將A2傳輸至W2.可以設(shè)計(jì)這樣一種編碼，使主節(jié)點(diǎn)發(fā)送多播編碼信息A2+A3到2個(gè)工作節(jié)點(diǎn)，后者使用本地已存儲(chǔ)的數(shù)據(jù)便可解碼獲得所需的數(shù)據(jù).顯然，與未編碼的數(shù)據(jù)洗牌方案相比，編碼方案可降低50%的通信開銷.

示例2.減少計(jì)算延遲編碼[2].接下來考慮另一個(gè)簡(jiǎn)單例子，圖1(b)展示一個(gè)具有3個(gè)工作節(jié)點(diǎn)和1個(gè)主節(jié)點(diǎn)的分布式計(jì)算系統(tǒng)，其目標(biāo)是計(jì)算矩陣乘法AX，其中A∈q×r，X∈q×r.數(shù)據(jù)矩陣A被劃分為A1和A2兩個(gè)子矩陣.可以這樣設(shè)計(jì)編碼，在進(jìn)行計(jì)算任務(wù)分配前，由主節(jié)點(diǎn)對(duì)子矩陣進(jìn)行編碼生成數(shù)據(jù)A3=A1+A2.而后，主節(jié)點(diǎn)將A1，A2，A3分別分配給W1，W2，W3.當(dāng)工作節(jié)點(diǎn)接收到矩陣X時(shí)，每個(gè)節(jié)點(diǎn)將X與存儲(chǔ)的數(shù)據(jù)相乘，并將計(jì)算結(jié)果返回給主節(jié)點(diǎn).通過觀察可知，主節(jié)點(diǎn)在接收到任意2個(gè)工作節(jié)點(diǎn)的結(jié)果時(shí)都可以恢復(fù)最終結(jié)果AX，而不用等待最慢的節(jié)點(diǎn)(掉隊(duì)節(jié)點(diǎn))響應(yīng).

Fig. 1 Simple example of coded computing圖1 編碼計(jì)算簡(jiǎn)單示例

值得注意的是，示例1為了在傳輸數(shù)據(jù)時(shí)可以進(jìn)行編碼，引入了冗余，即節(jié)點(diǎn)W1和W2分別額外存儲(chǔ)了數(shù)據(jù)A2和A4.示例2同樣引入了冗余——給W3分配了額外的計(jì)算任務(wù)(A1+A2)X，以此使得分布式計(jì)算系統(tǒng)可以容忍1個(gè)掉隊(duì)節(jié)點(diǎn)的存在.由此可見，編碼計(jì)算的核心思想是注入并充分利用分布式計(jì)算系統(tǒng)中的數(shù)據(jù)或計(jì)算冗余.本文將編碼計(jì)算定義如下：編碼計(jì)算是利用編碼理論注入冗余，通過對(duì)存儲(chǔ)-通信-計(jì)算的權(quán)衡，從而解決或緩解分布式計(jì)算系統(tǒng)中通信瓶頸，計(jì)算延遲，安全和隱私等問題的一系列技術(shù)手段.

2 面向通信瓶頸的編碼計(jì)算

近年來，研究人員對(duì)Master-Worker分布式計(jì)算架構(gòu)下的數(shù)據(jù)洗牌問題進(jìn)行了大量研究.其中根據(jù)主節(jié)點(diǎn)是否參與運(yùn)算及存儲(chǔ)數(shù)據(jù)，Master-Worker架構(gòu)可分為Map-Reduce和典型Master-Worker兩種略有區(qū)別的分布式計(jì)算架構(gòu).而在這2種不同分布式計(jì)算架構(gòu)下的數(shù)據(jù)洗牌編碼方案也不盡相同.因此，在第2.1和2.2節(jié)，將分別對(duì)基于Map-Reduce和典型Master-Worker的數(shù)據(jù)洗牌編碼計(jì)算方案進(jìn)行介紹和分析.

2.1 基于Map-Reduce的數(shù)據(jù)洗牌編碼計(jì)算

MapReduce是一種編程范式，可以并行處理海量數(shù)據(jù)集.在MapReduce架構(gòu)中，主節(jié)點(diǎn)不參與運(yùn)算，且不存儲(chǔ)數(shù)據(jù)，只為各工作節(jié)點(diǎn)協(xié)調(diào)分配不同的輸入數(shù)據(jù).更具體地說，在MapReduce中整個(gè)計(jì)算被分解為“Map”，“Shuffle”和“Reduce”3個(gè)階段.在Map階段，工作節(jié)點(diǎn)根據(jù)設(shè)計(jì)的Map函數(shù)使用輸入數(shù)據(jù)來計(jì)算中間值的一部分；在Shuffle階段，工作節(jié)點(diǎn)相互交換一組中間值；在Reduce階段，工作節(jié)點(diǎn)計(jì)算并輸出最終結(jié)果.針對(duì)Map-Reduce架構(gòu)，研究人員通過將子數(shù)據(jù)集映射到多個(gè)工作節(jié)點(diǎn)，并仔細(xì)設(shè)計(jì)放置策略，以創(chuàng)建編碼機(jī)會(huì).編碼計(jì)算利用該機(jī)會(huì)將各工作節(jié)點(diǎn)計(jì)算的中間值進(jìn)行異或編碼，然后將編碼信息廣播給其他工作節(jié)點(diǎn)，以此降低通信負(fù)載.

2.1.1 通用數(shù)據(jù)洗牌編碼方案

針對(duì)Map-Reduce架構(gòu)，Li等人[1]提出了編碼分布式計(jì)算(coded distributed computing, CDC)方案，并在后續(xù)工作中將CDC方案擴(kuò)展到無線分布式計(jì)算系統(tǒng)[9]、多級(jí)數(shù)據(jù)流[10]和TeraSort排序算法[61]等.這里結(jié)合圖2所示計(jì)算用例概述CDC方案的基本思路.

Fig. 2 Data shuffling between general scheme and CDC圖2 一般方案和CDC方案數(shù)據(jù)洗牌對(duì)比

假設(shè)客戶端需從6個(gè)輸入文件中計(jì)算3個(gè)輸出函數(shù)，分別用圓形、正方形和三角形表示，計(jì)算任務(wù)由節(jié)點(diǎn)N1，N2和N3協(xié)同完成.每個(gè)節(jié)點(diǎn)計(jì)算唯一的輸出函數(shù)，例如N1計(jì)算圓形函數(shù)，N2計(jì)算方形函數(shù)，N3計(jì)算三角形函數(shù).

在計(jì)算上不加冗余時(shí)，如圖2(a)所示，如果每個(gè)節(jié)點(diǎn)在本地存儲(chǔ)2個(gè)輸入文件，這樣便可在本地生成6個(gè)所需的中間值中的2個(gè).因此，每個(gè)節(jié)點(diǎn)需要從其他節(jié)點(diǎn)接收另外4個(gè)中間值，產(chǎn)生的通信負(fù)載為4×3=12.

如圖2(b)所示，CDC使每個(gè)輸入文件映射到2個(gè)節(jié)點(diǎn).顯然，由于執(zhí)行了更多的本地計(jì)算任務(wù)，因此每個(gè)節(jié)點(diǎn)現(xiàn)在僅需要2個(gè)其他中間值，此時(shí)的通信負(fù)載為2×3=6.由于每個(gè)節(jié)點(diǎn)計(jì)算出了更多的中間值，因此在數(shù)據(jù)洗牌時(shí)便有了編碼的機(jī)會(huì).CDC將每個(gè)節(jié)點(diǎn)處生成的2個(gè)中間值進(jìn)行異或編碼，并多播到另外2個(gè)節(jié)點(diǎn)，此時(shí)的通信負(fù)載為3.因此，CDC產(chǎn)生的通信負(fù)載比沒有計(jì)算冗余的情況下的通信負(fù)載降低了4倍，比未編碼的數(shù)據(jù)洗牌方案低2倍.可見，這樣以計(jì)算換通信的方式可有效降低洗牌時(shí)的傳輸開銷.隨后，文獻(xiàn)[1]從數(shù)據(jù)映射、計(jì)算、數(shù)據(jù)洗牌和歸約4個(gè)階段對(duì)CDC的一般化過程進(jìn)行了形式化定義.

CDC關(guān)注的是由MapReduce驅(qū)動(dòng)的通用框架中的通信流，并且適用于任意數(shù)量的輸出結(jié)果、輸入數(shù)據(jù)文件和計(jì)算節(jié)點(diǎn)，不要求計(jì)算函數(shù)具備任何特殊性質(zhì)(如線性).

2.1.2 有領(lǐng)域知識(shí)的數(shù)據(jù)洗牌編碼方案

Li等人[9]將CDC方案推廣到無線分布式計(jì)算系統(tǒng)，設(shè)計(jì)了一種無線分布式編碼計(jì)算(coded wireless distributed computing, CWDC)的框架.CWDC由上行鏈路和下行鏈路2部分組成，每個(gè)用戶在上行鏈路發(fā)送2個(gè)中間值的異或值至接入點(diǎn)，如圖3(a)所示.然后接入點(diǎn)無需解碼任何單獨(dú)的值，只需生成接收到的消息的2個(gè)隨機(jī)線性組合C1(·,·,·)和C2(·,·,·)，并將它們廣播給用戶，即可同時(shí)滿足所有的數(shù)據(jù)請(qǐng)求，如圖3(b)所示.圖示編碼方法中上行鏈路通信負(fù)載為3，下行鏈路通信負(fù)載為2.

Fig. 3 The diagram of data shuffling in CWDC coded scheme圖3 CWDC編碼方案數(shù)據(jù)洗牌圖解

對(duì)于具有K個(gè)用戶的無線分布式計(jì)算應(yīng)用程序，假設(shè)每個(gè)工作節(jié)點(diǎn)可以存儲(chǔ)整個(gè)數(shù)據(jù)集的μ(0<μ≤1)倍，所提出的CWDC方案的通信負(fù)載為

(1)

與未編碼方案相比，CWDC可將通信負(fù)載降低μK倍，并且其通信負(fù)載是固定的和工作節(jié)點(diǎn)數(shù)量無關(guān).

許多分布式計(jì)算應(yīng)用程序包含多個(gè)MapReduce階段.例如機(jī)器學(xué)習(xí)算法[62]、數(shù)據(jù)庫SQL查詢[63-64]和數(shù)據(jù)分析[65].基于此，Li等人[10]為多階段數(shù)據(jù)流應(yīng)用程序形式化定義了分布式計(jì)算模型.其將多級(jí)數(shù)據(jù)流表示為一個(gè)分層的有向無環(huán)圖(directed acyclic graph, DAG)，在這個(gè)DAG中，每個(gè)頂點(diǎn)代表一個(gè)MapReduce類型計(jì)算，方案通過對(duì)每個(gè)頂點(diǎn)實(shí)施CDC編碼策略，有效降低通信負(fù)載.

CDC中的一個(gè)隱含假設(shè)是每個(gè)服務(wù)器對(duì)存儲(chǔ)在其內(nèi)存中的所有文件執(zhí)行所有可能的計(jì)算.然而，當(dāng)工作節(jié)點(diǎn)需要執(zhí)行計(jì)算密集型任務(wù)時(shí)，可能沒有足夠的時(shí)間來執(zhí)行所有計(jì)算.針對(duì)這種情況，Ezzeldin等人[11]在CDC方案的基礎(chǔ)上提出了一種分割編碼計(jì)算(spilt coded distributed computing, S-CDC)方案.作者通過給定節(jié)點(diǎn)的計(jì)算能力閾值，從而得出相關(guān)通信負(fù)載的下限，并基于CDC提出一種啟發(fā)式方案，以達(dá)到該通信下限.

在文獻(xiàn)[61]中，作者將CDC的思路應(yīng)用于Tera-Sort排序算法，并設(shè)計(jì)了一種名為CodedTeraSort的新分布式排序算法，該算法在數(shù)據(jù)中施加結(jié)構(gòu)化冗余，以在數(shù)據(jù)洗牌階段創(chuàng)造有效的編碼機(jī)會(huì).作者通過實(shí)驗(yàn)評(píng)估了CodedTeraSort算法在Amazon EC2集群上的性能，與傳統(tǒng)的TeraSort相比，Coded-TeraSort速率高1.97～3.39倍.

2.1.3 線性假設(shè)下的數(shù)據(jù)洗牌編碼方案

在沒有進(jìn)一步假設(shè)的情況下，CDC[1]實(shí)現(xiàn)了最優(yōu)的計(jì)算和通信負(fù)載之間的平衡.然而，工作節(jié)點(diǎn)計(jì)算的函數(shù)通常有一些結(jié)構(gòu)，利用這些結(jié)構(gòu)可以進(jìn)一步降低通信負(fù)載.

Fig. 4 The diagram of data shuffling in CCDC圖4 CCDC編碼方案數(shù)據(jù)洗牌圖解

在Reduce階段是線性聚合的假設(shè)下，Li等人[14]將壓縮技術(shù)和CDC相結(jié)合提出了一種壓縮編碼分布式計(jì)算(compressed coded distributed computing, CCDC)方案.考慮如圖4所示的分布式計(jì)算場(chǎng)景，假設(shè)最終計(jì)算結(jié)果是計(jì)算各中間值之和，則可以在發(fā)送節(jié)點(diǎn)上預(yù)先組合相同函數(shù)的中間值以減少通信.

例如，節(jié)點(diǎn)1將兩對(duì)中間值相加以生成2個(gè)分組，然后將每個(gè)分組(正方形和三角形)分割為2段，并取各自的一段逐位進(jìn)行異或，以生成大小為中間值一半的編碼數(shù)據(jù).最后，節(jié)點(diǎn)1將該編碼數(shù)據(jù)多播到節(jié)點(diǎn)2和3.節(jié)點(diǎn)2和3處執(zhí)行類似的操作.

最后，每個(gè)節(jié)點(diǎn)可以利用本地已有的中間值來解碼獲得所需的數(shù)據(jù).該編碼方案可用于需在最后階段對(duì)中間結(jié)果線性聚合的分布式機(jī)器學(xué)習(xí)中.

Horii等人[66]指出在Map階段計(jì)算的中間值可以看作是2中的向量.假設(shè)工作節(jié)點(diǎn)發(fā)送的向量數(shù)為r，由這些向量構(gòu)造的線性子空間的維數(shù)可能小于r.例如，在計(jì)算大量文檔中的單詞數(shù)時(shí)，工作節(jié)點(diǎn)計(jì)算的許多中間值是相同的，并且中間值的一些線性組合也是相同的.Horii等人基于這個(gè)觀點(diǎn)和假設(shè)，在編碼時(shí)讓工作節(jié)點(diǎn)發(fā)送中間值的線性子空間的基和線性組合系數(shù)，從而進(jìn)一步降低通信負(fù)載.

2.2 基于典型Master-Worker的數(shù)據(jù)洗牌編碼計(jì)算

與Map-Reduce架構(gòu)不同，在典型Master-Worker計(jì)算框架中，主節(jié)點(diǎn)可以訪問整個(gè)數(shù)據(jù)庫，并且只有主節(jié)點(diǎn)可以發(fā)送數(shù)據(jù)，而各工作節(jié)點(diǎn)之間無法進(jìn)行通信.主節(jié)點(diǎn)在每次迭代中將整個(gè)數(shù)據(jù)集排列劃分為多個(gè)子數(shù)據(jù)集，并將每個(gè)子數(shù)據(jù)集傳輸?shù)较鄳?yīng)的工作節(jié)點(diǎn)，以便工作節(jié)點(diǎn)執(zhí)行本地計(jì)算任務(wù).工作節(jié)點(diǎn)在完成計(jì)算后將結(jié)果返回給主節(jié)點(diǎn).典型Master-Worker架構(gòu)下的編碼計(jì)算方案可分為數(shù)據(jù)洗牌和存儲(chǔ)更新2個(gè)階段.在數(shù)據(jù)洗牌階段，主節(jié)點(diǎn)將整體數(shù)據(jù)分為大小相同的子數(shù)據(jù)集，并將子數(shù)據(jù)集的編碼信息廣播發(fā)送給工作節(jié)點(diǎn)，每個(gè)工作節(jié)點(diǎn)從主節(jié)點(diǎn)廣播的編碼信息和本地存儲(chǔ)的數(shù)據(jù)中恢復(fù)出下次迭代所需的數(shù)據(jù).在存儲(chǔ)更新階段，每個(gè)工作節(jié)點(diǎn)存儲(chǔ)新分配的數(shù)據(jù)單元并更新存儲(chǔ)結(jié)構(gòu)以實(shí)現(xiàn)下次迭代的數(shù)據(jù)洗牌.值得注意的是，在編碼計(jì)算方案中工作節(jié)點(diǎn)需額外存儲(chǔ)一些關(guān)于其他數(shù)據(jù)單元的信息.編碼計(jì)算將此類附加數(shù)據(jù)進(jìn)行仔細(xì)設(shè)計(jì)，以幫助在下次迭代時(shí)從編碼信息中解碼所需數(shù)據(jù).

Lee等人[2]首次提出了典型Master-Worker分布式計(jì)算架構(gòu)下的編碼數(shù)據(jù)洗牌方案，旨在提高分布式機(jī)器學(xué)習(xí)算法的訓(xùn)練速率.假設(shè)數(shù)據(jù)集一共有q個(gè)數(shù)據(jù)行，工作節(jié)點(diǎn)數(shù)為n，每次迭代時(shí)將數(shù)據(jù)集隨機(jī)均勻的分配給各個(gè)工作節(jié)點(diǎn)，則每個(gè)工作節(jié)點(diǎn)需要處理q/n個(gè)數(shù)據(jù)行.假設(shè)每個(gè)工作節(jié)點(diǎn)的內(nèi)存大小為s(s>q/n)個(gè)數(shù)據(jù)行，由此可知工作節(jié)點(diǎn)在每次算法迭代時(shí)除了存儲(chǔ)計(jì)算任務(wù)所需的q/n個(gè)數(shù)據(jù)行外，還有額外s-q/n個(gè)數(shù)據(jù)行的存儲(chǔ)空間.文獻(xiàn)[2]充分利用這部分存儲(chǔ)空間，讓每個(gè)工作節(jié)點(diǎn)從剩余的數(shù)據(jù)行中隨機(jī)均勻的選擇s-q/n個(gè)數(shù)據(jù)行進(jìn)行存儲(chǔ)，形成“側(cè)信息”.在數(shù)據(jù)洗牌時(shí)，主節(jié)點(diǎn)利用異或編碼的方式將數(shù)據(jù)集編碼，并將編碼信息廣播至各工作節(jié)點(diǎn).各工作節(jié)點(diǎn)利用“側(cè)信息”完成解碼，獲取下次迭代所需數(shù)據(jù).Lee等人通過實(shí)驗(yàn)表明在n=50，q=1 000，s/q=0.1時(shí)，用于數(shù)據(jù)洗牌的通信開銷減少了81%.因此，在緩存的存儲(chǔ)開銷非常低的情況下，與未編碼方案相比可以顯著地降低分布式系統(tǒng)的通信開銷.

在給定一組數(shù)(K，N，S)(K為節(jié)點(diǎn)數(shù)，N為文件總數(shù)，S為每個(gè)節(jié)點(diǎn)的存儲(chǔ)大小)的情況下，Attia等人[67-68]刻畫了每個(gè)工作節(jié)點(diǎn)存儲(chǔ)容量與最大通信負(fù)載之間的關(guān)系.具體來說，在文獻(xiàn)[67]中，針對(duì)工作節(jié)點(diǎn)數(shù)K={2，3}的情況，Attia等人將最大通信負(fù)載描述為一個(gè)關(guān)于可用存儲(chǔ)的函數(shù).在文獻(xiàn)[68]中，Attia等考慮了無多余存儲(chǔ)的情況(即，S=N/K)，表明即使對(duì)于最小存儲(chǔ)值，編碼機(jī)會(huì)仍然存在.然而，該方案的參數(shù)不能取任意值.

隨后，Attia等人[13]在編碼緩存方案[69-70]的啟發(fā)下，提出了一種新穎的編碼數(shù)據(jù)洗牌方案，該方案基于一種保持存儲(chǔ)結(jié)構(gòu)不變的存儲(chǔ)/更新過程，稱為“結(jié)構(gòu)不變的放置和更新(structural invariant placement and update, SIP/SIU)”.

SIP/SIU和文獻(xiàn)[2]類似，工作節(jié)點(diǎn)除了存儲(chǔ)必要的處理數(shù)據(jù)外，需額外存儲(chǔ)一些附加數(shù)據(jù)，如圖5所示.和文獻(xiàn)[2]中隨機(jī)存儲(chǔ)分配不同，SIP/SIU以一種確定性和系統(tǒng)化的存儲(chǔ)更新策略創(chuàng)造了更多的編碼機(jī)會(huì).

Fig. 5 Storage of work nodes in SIP/SIU圖5 SIP/SIU方案中工作節(jié)點(diǎn)的存儲(chǔ)布局

(2)

Fig. 6 Storage of work nodes and the processes of storage update in [71]圖6 文獻(xiàn)[71]中工作節(jié)點(diǎn)存儲(chǔ)布局及更新過程

Attia等人通過數(shù)值模擬實(shí)驗(yàn)表明，對(duì)于具有較大存儲(chǔ)容量工作節(jié)點(diǎn)的分布式計(jì)算系統(tǒng)，文獻(xiàn)[13]要優(yōu)于文獻(xiàn)[2]中的編碼方案，并且具有較低的計(jì)算復(fù)雜度.

Elmahdy等人[71]基于SIP/SIU方案提出了一種不同的編碼洗牌方案，并證明了當(dāng)文件數(shù)等于工作節(jié)點(diǎn)數(shù)時(shí)，其編碼數(shù)據(jù)洗牌方案是最優(yōu)的.以K=4(w1,w2,w3,w4)個(gè)工作節(jié)點(diǎn)的分布式計(jì)算系統(tǒng)為例，簡(jiǎn)要說明該方案.設(shè)有4個(gè)輸入文件N=4，分別命名為A,B,C,D，每個(gè)工作節(jié)點(diǎn)的內(nèi)存大小為S=2個(gè)文件.不失一般性，假設(shè)w1,w2,w3,w4在第t次迭代時(shí)正在處理的文件分別為A,B,C,D.

(3)

由分析可知，每次迭代時(shí)主節(jié)點(diǎn)需發(fā)送3個(gè)子消息，假設(shè)每個(gè)子消息的大小為1/3，則文獻(xiàn)[71]所提出方案的通信負(fù)載為1.在相同的內(nèi)存布局策略下，非編碼洗牌方案需發(fā)送8個(gè)子消息，最終的通信負(fù)載為8/3.因此，在該場(chǎng)景下，與非編碼洗牌方案相比，Elmahdy等人所提出的編碼洗牌方案可節(jié)省約62%的通信負(fù)載.

“好”的數(shù)據(jù)洗牌方案需要緩存的數(shù)據(jù)在各工作節(jié)點(diǎn)之間和算法迭代過程中具有足夠的差異[72-74]，受這一想法的激勵(lì)，Li等人[15]提出了一種受約束的柔韌性索引編碼數(shù)據(jù)洗牌方案，該方案在通信成本和計(jì)算性能之間取得了平衡.

為了達(dá)到該目的，Li等人在索引編碼方案的基礎(chǔ)上做了2項(xiàng)修改：1)添加一條約束，即一條消息最多可以發(fā)送給c個(gè)工作節(jié)點(diǎn)，以確保只有一小部分工作節(jié)點(diǎn)可以緩存同一條消息.該約束旨在降低工作節(jié)點(diǎn)間消息的相關(guān)性，確保工作節(jié)點(diǎn)間緩存內(nèi)容的差異足夠大.2)設(shè)計(jì)了一個(gè)分層結(jié)構(gòu)，即將消息分成組，在迭代過程中，每個(gè)工作節(jié)點(diǎn)只緩存特定的消息.該修改旨在降低迭代過程中消息的相關(guān)性，以確保迭代過程中各工作節(jié)點(diǎn)緩存內(nèi)容的差異足夠大.通過在一個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，與基于索引編碼的替換式隨機(jī)洗牌方案[2]相比，文獻(xiàn)[15]提出的方案平均能減少87%的傳輸消耗.

2.3 小 結(jié)

本節(jié)我們總結(jié)了Master-Worker架構(gòu)下2種不同分布式計(jì)算框架中優(yōu)化通信負(fù)載的編碼計(jì)算方案.首先我們對(duì)此類方案進(jìn)行總結(jié)和回顧，如表3所示:

Table 3 Summary and Review of Coded Computing Schemes for Communication Bottleneck表3 面向通信瓶頸的編碼計(jì)算方案總結(jié)與回顧

在Map-Reduce架構(gòu)下的編碼計(jì)算方案通過將輸入數(shù)據(jù)映射到多個(gè)工作節(jié)點(diǎn)，并精心設(shè)計(jì)分配策略，從而創(chuàng)造編碼機(jī)會(huì).而在不注入計(jì)算冗余的情況下，工作節(jié)點(diǎn)交換中間值時(shí)，由于沒有解碼所需的信息，所以不能對(duì)中間值進(jìn)行編碼.通過注入冗余，CDC[1]，CodedTeraSort[61]可以將中間值進(jìn)行異或編碼；CWDC[9]可以在無線分布式網(wǎng)絡(luò)上下行鏈路分別將中間值異或編碼和線性組合編碼；CCDC[14]在Reduce函數(shù)是線性相關(guān)的假設(shè)下，可以對(duì)中間值進(jìn)行壓縮，然后異或編碼；文獻(xiàn)[66]則在中間值具有線性相關(guān)性假設(shè)下，可以只交換編碼信息的線性子空間的基和線性組合系數(shù)，但其在編碼階段需要更多的計(jì)算開銷；文獻(xiàn)[11-12]則分別是CDC方案在多級(jí)數(shù)據(jù)流應(yīng)用和異構(gòu)分布式系統(tǒng)下的推廣，其考慮了更多的約束條件，但編碼思想和方式與CDC方案相同.

與Map-Reduce架構(gòu)在數(shù)據(jù)洗牌階段傳輸計(jì)算結(jié)果信息不同，在典型的Master-Worker架構(gòu)中數(shù)據(jù)洗牌階段需傳輸原始數(shù)據(jù).對(duì)此類方案分析可知，典型Master-Worker架構(gòu)中工作節(jié)點(diǎn)存儲(chǔ)計(jì)算任務(wù)所需的數(shù)據(jù)外，還需存儲(chǔ)一些“冗余數(shù)據(jù)”.正是因?yàn)橐肓舜鎯?chǔ)冗余，所以數(shù)據(jù)洗牌階段才有編碼機(jī)會(huì).因此典型Master-Worker架構(gòu)中編碼洗牌方案的通信負(fù)載和各節(jié)點(diǎn)多余存儲(chǔ)空間大小相關(guān).一個(gè)極端的情況是，當(dāng)所有的工作節(jié)點(diǎn)都有足夠的存儲(chǔ)空間來存儲(chǔ)整個(gè)數(shù)據(jù)集時(shí)，數(shù)據(jù)洗牌階段不需要通信.而另一個(gè)極端情況，當(dāng)所有工作節(jié)點(diǎn)的存儲(chǔ)空間剛好足以存儲(chǔ)任務(wù)所需的數(shù)據(jù)時(shí)(稱為無多余存儲(chǔ)空間的情況)，則通信量將達(dá)到最大.文獻(xiàn)[2,13,71]考慮了無替換的數(shù)據(jù)洗牌，即附加數(shù)據(jù)用于提高通信效率，而不用于計(jì)算.然而，當(dāng)額外的存儲(chǔ)數(shù)據(jù)用于計(jì)算時(shí)，可以獲得潛在的計(jì)算增益.例如，為了訓(xùn)練分類器模型，額外存儲(chǔ)的數(shù)據(jù)樣本也有助于模型訓(xùn)練.

通過對(duì)面向通信瓶頸的編碼計(jì)算方案的分析可知，編碼計(jì)算可以有效降低數(shù)據(jù)洗牌階段的通信負(fù)載.然而，通信負(fù)載的降低通常以更大的計(jì)算負(fù)載和更大的存儲(chǔ)為代價(jià).因此，需要權(quán)衡計(jì)算-存儲(chǔ)-通信三者之間的關(guān)系，才能更好地評(píng)估方案的性能.

3 面向計(jì)算延遲的編碼計(jì)算

面向計(jì)算延遲的編碼計(jì)算方案的核心思想是通過使用編碼技術(shù)，創(chuàng)建任務(wù)冗余，即在更多的工作節(jié)點(diǎn)上分配計(jì)算任務(wù)，使得主節(jié)點(diǎn)在不接收掉隊(duì)節(jié)點(diǎn)結(jié)果的情況下依然可以恢復(fù)最終結(jié)果.在面向計(jì)算延遲的編碼計(jì)算方案中，一個(gè)重要的性能指標(biāo)是恢復(fù)閾值，它是指在最壞情況下，主節(jié)點(diǎn)解碼最終結(jié)果需要等待的工作節(jié)點(diǎn)的數(shù)量[2].一般來說恢復(fù)閾值越小，完成最終任務(wù)需等待完成計(jì)算的工作節(jié)點(diǎn)的個(gè)數(shù)越少，計(jì)算延遲越短.面向計(jì)算延遲的編碼計(jì)算方案的目標(biāo)是降低恢復(fù)閾值，以便通過等待較少的工作節(jié)點(diǎn)來恢復(fù)最終結(jié)果，從而減少計(jì)算延遲.

為了降低不同分布式計(jì)算任務(wù)的計(jì)算延遲，可以利用具體運(yùn)算的代數(shù)結(jié)構(gòu)來設(shè)計(jì)編碼方案.在隨后章節(jié)，本文將介紹分析當(dāng)前編碼計(jì)算方案在不同計(jì)算任務(wù)中的應(yīng)用.除此之外，本文還將簡(jiǎn)單討論研究人員在異構(gòu)場(chǎng)景和利用掉隊(duì)節(jié)點(diǎn)結(jié)果等方面所提出的編碼計(jì)算方案.

3.1 面向矩陣乘法運(yùn)算的編碼計(jì)算

3.1.1 矩陣-向量乘法

分布式矩陣-向量乘法是線性變換的組成部分，是機(jī)器學(xué)習(xí)和信號(hào)處理應(yīng)用中的一個(gè)重要步驟.為方便方案描述，首先定義分布式計(jì)算矩陣-向量乘法系統(tǒng)，該系統(tǒng)具有1個(gè)主節(jié)點(diǎn)和P個(gè)工作節(jié)點(diǎn)，其目標(biāo)是分布式計(jì)算大小為m×n的矩陣A和n×1的向量x的積：b=Ax.如無特殊說明外，本節(jié)編碼計(jì)算方案的計(jì)算場(chǎng)景和目標(biāo)遵循該定義.我們將對(duì)不同的編碼方案進(jìn)行簡(jiǎn)要介紹和分析.

1) MDS編碼方案.與簡(jiǎn)單的將同一個(gè)計(jì)算任務(wù)分配給多個(gè)工作節(jié)點(diǎn)(重復(fù)編碼)不同，Lee等人[2]利用MDS碼來克服矩陣-向量乘法中的計(jì)算延遲問題.基于MDS碼的方案的編碼策略是首先將矩陣A按列劃分為k個(gè)子矩陣，每個(gè)子矩陣的大小為m×n/k.隨后使用(P,k)MDS碼對(duì)k個(gè)子矩陣進(jìn)行編碼，從而生成P個(gè)編碼子矩陣.隨后將編碼子矩陣發(fā)送至工作節(jié)點(diǎn)，工作節(jié)點(diǎn)計(jì)算編碼子矩陣與向量x的積，并返回主節(jié)點(diǎn).則主節(jié)點(diǎn)可以根據(jù)最快的k個(gè)計(jì)算節(jié)點(diǎn)恢復(fù)出最終結(jié)果b.如1.3節(jié)圖1(b)所示，為一個(gè)使用(3,2)MDS碼的編碼計(jì)算方案實(shí)例.

2) Short-Dot.在基于重復(fù)編碼或者M(jìn)DS碼的編碼計(jì)算方案中，每個(gè)工作節(jié)點(diǎn)需計(jì)算長(zhǎng)度為n的點(diǎn)積，而Dutta等人[16]認(rèn)為通過縮短點(diǎn)積的長(zhǎng)度，可以減少工作節(jié)點(diǎn)的計(jì)算時(shí)間.因此Dutta等人提出了一種“短點(diǎn)積”(short-dot)的編碼計(jì)算方案,該方案通過對(duì)子矩陣施加稀疏性以使工作節(jié)點(diǎn)計(jì)算較短的點(diǎn)積.然而，工作節(jié)點(diǎn)計(jì)算點(diǎn)積的長(zhǎng)度越短，該方案的恢復(fù)閾值越高.

(4)

由式(4)可知，系數(shù)組成的矩陣為上三角矩陣，由于主對(duì)角線中的元素是非0的，所以它是可逆的.因此可以通過求系數(shù)矩陣的逆來恢復(fù)最終結(jié)果.利用對(duì)角線結(jié)構(gòu)，s-對(duì)角線編碼方案不僅降低了計(jì)算負(fù)載，并且可以實(shí)現(xiàn)和文獻(xiàn)[2]相同的恢復(fù)閾值.

4) 無碼率編碼.LT碼[75]是一類用于從有限的源符號(hào)集生成無限多個(gè)編碼符號(hào)的糾刪碼.Mallick等人[18]通過將矩陣A的m行視為源符號(hào)，將LT碼用于矩陣-向量乘法.該方案首先根據(jù)Robust Soliton度分布選擇參數(shù)d，隨后從A中隨機(jī)均勻的選擇d個(gè)數(shù)據(jù)行并將它們隨機(jī)相加生成編碼行.即d決定了每個(gè)編碼行中的原始數(shù)據(jù)行的數(shù)量.原數(shù)據(jù)行與編碼數(shù)據(jù)行之間的映射對(duì)于成功解碼至關(guān)重要，因此，此映射需存儲(chǔ)在主節(jié)點(diǎn)上.

假設(shè)對(duì)m個(gè)原始數(shù)據(jù)行進(jìn)行編碼生成了αm個(gè)編碼行，則主節(jié)點(diǎn)將αm個(gè)編碼行平均分配給P個(gè)工作節(jié)點(diǎn).工作節(jié)點(diǎn)計(jì)算編碼行和向量x的乘積，并將結(jié)果返回給主節(jié)點(diǎn).如果一個(gè)工作節(jié)點(diǎn)在主節(jié)點(diǎn)能夠解碼b之前完成了分配給它的所有向量積，則它將保持空閑狀態(tài)，主節(jié)點(diǎn)繼續(xù)從其他工作節(jié)點(diǎn)收集更多的行向量積.一旦主節(jié)點(diǎn)獲得了足夠的結(jié)果可以解碼b=Ax，則它將向所有工作節(jié)點(diǎn)發(fā)送完成信號(hào)以停止計(jì)算.和其他方案相比，無碼率編碼方案可以實(shí)現(xiàn)理想的負(fù)載平衡并且具有較低的解碼復(fù)雜度.

3.1.2 矩陣-矩陣乘法

矩陣乘法是許多數(shù)據(jù)分析應(yīng)用程序中關(guān)鍵操作之一.此類應(yīng)用程序需要處理TB級(jí)甚至PB級(jí)的數(shù)據(jù)，這需要大量計(jì)算和存儲(chǔ)資源，而單臺(tái)計(jì)算機(jī)通常無法滿足.因此，在大型分布式系統(tǒng)上部署矩陣乘法計(jì)算任務(wù)已經(jīng)引起了廣泛的研究[76-77].

本文首先定義分布式矩陣乘法計(jì)算場(chǎng)景.該分布式計(jì)算系統(tǒng)有一個(gè)主節(jié)點(diǎn)和N個(gè)工作節(jié)點(diǎn)(w1,w2,…,wN)組成，其目標(biāo)是計(jì)算大矩陣乘法C=ATB.其中A∈r×q，B∈r×s.為了分布式計(jì)算該矩陣乘法，首先將2個(gè)輸入矩陣分別(任意)劃分為p×m和p×n個(gè)子矩陣塊，其中同一輸入矩陣內(nèi)的所有子矩陣大小相等.然后將A,B中每個(gè)子矩陣分配給各工作節(jié)點(diǎn)，工作節(jié)點(diǎn)完成計(jì)算任務(wù)后，將計(jì)算結(jié)果返回給主節(jié)點(diǎn).主節(jié)點(diǎn)恢復(fù)最終結(jié)果輸出C=ATB.如無特殊說明外，本節(jié)編碼計(jì)算方案的計(jì)算場(chǎng)景和目標(biāo)遵循該定義.我們將對(duì)不同的編碼方案進(jìn)行簡(jiǎn)要介紹和分析.

2) 乘積碼.隨后Lee等人基于乘積碼[78]，在文獻(xiàn)[19]中提出了另一種新穎的編碼矩陣乘法方案，該方案較1D-MDS編碼方案具有更低的恢復(fù)閾值.乘積碼是用小編碼塊作為構(gòu)建塊構(gòu)建較大編碼塊的一種方法.以N=9，m=n=2，p=1為例，簡(jiǎn)要說明乘積碼的編碼解碼過程.由于m=n=2，因此有：

(5)

(6)

Fig. 7 An example of computing tasks assignment圖7 計(jì)算任務(wù)分配示例

介紹一類以多項(xiàng)式碼為基礎(chǔ)的編碼計(jì)算方案[20-22]，這類方案的共同特征是為每個(gè)工作節(jié)點(diǎn)分配不同的隨機(jī)數(shù)，并使用該隨機(jī)數(shù)對(duì)輸入矩陣進(jìn)行編碼，從而使得最后解碼過程可視為多項(xiàng)式插值問題，不同之處在于各方案對(duì)輸入矩陣的切割方式不同.基于多項(xiàng)式碼的編碼計(jì)算方案的主要優(yōu)點(diǎn)是可實(shí)現(xiàn)最佳恢復(fù)閾值，且恢復(fù)閾值不隨工作節(jié)點(diǎn)的數(shù)量的變化而變化.

3) 多項(xiàng)式碼.為了尋找最佳恢復(fù)閾值，Yu等人[20]提出了一種基于多項(xiàng)式碼的編碼計(jì)算方案，該方案的恢復(fù)閾值與工作節(jié)點(diǎn)數(shù)量無關(guān)，且遠(yuǎn)小于MDS碼和乘積碼方案中的恢復(fù)閾值.為構(gòu)造多項(xiàng)式編碼計(jì)算方案，Yu等人首先將輸入矩陣A和B沿垂直方向分別劃分為m和n個(gè)子矩陣，即A=(A0,A1,…,Am-1)，B=(B0,B1,…,Bn-1).隨后隨機(jī)分配給每個(gè)工作節(jié)點(diǎn)wi一個(gè)互不相同的數(shù)，記為xi∈q(q為一個(gè)足夠大的有限域).對(duì)于給定的參數(shù)α，β∈，Yu等人定義如下(α,β)-多項(xiàng)式碼：對(duì)?i∈{0,1,…,N-1}，計(jì)算:

(7)

(8)

(9)

(10)

4) MatDot.由文獻(xiàn)[20]可知，當(dāng)m=n時(shí)，多項(xiàng)式碼方案的恢復(fù)閾值為m2.針對(duì)m=n的情況，F(xiàn)ahim等人[21]提出了一種恢復(fù)閾值更低的編碼計(jì)算方案，稱為“MatDot”.MatDot假設(shè)矩陣A和B都為P×P的方陣，并將兩矩陣分別在垂直和水平方向劃分為m個(gè)大小相等子矩陣.其編碼思想和多項(xiàng)式編碼[20]相似，在m=n時(shí)，MatDot方案的恢復(fù)閾值為KMatDot=2m-1，其遠(yuǎn)遠(yuǎn)小于多項(xiàng)式編碼的恢復(fù)閾值m2.

5) PolyDot.雖然MatDot的恢復(fù)閾值比多項(xiàng)式碼方案[20]低，但在通信成本方面，MatDot中每個(gè)工作節(jié)點(diǎn)的通信成本為O(N2)，要比多項(xiàng)式碼方案的通信成本O(N2/m2)高.因此Fahim等人[21]針對(duì)矩陣A和B都是方陣的情況，在MatDot的基礎(chǔ)上提出了一種名為“PolyDot”的編碼方案.該方案權(quán)衡了恢復(fù)閾值和通信成本之間的關(guān)系，是MatDot和多項(xiàng)式碼[20]方案的折中.一般而言，PolyDot的恢復(fù)閾值為KPolyDot=t2(2s-1)(st=m)，通信成本為O(N2/t2).

6) 糾纏多項(xiàng)式碼.與只允許將矩陣按列劃分的多項(xiàng)式碼方案不同，Yu等人[22]在多項(xiàng)式碼方案的基礎(chǔ)上提出了一種名為糾纏多項(xiàng)式碼的編碼計(jì)算方案.該方案允許對(duì)輸入矩陣進(jìn)行任意劃分.在糾纏多項(xiàng)式編碼方案中，矩陣A和B分別被分割為p×m和p×n個(gè)子矩陣塊，其中同一矩陣內(nèi)的所有子矩陣大小相等.換句話說，多項(xiàng)式碼方案[20]是p=1的特殊情況.

通過選擇參數(shù)p，m和n不同的值，糾纏多項(xiàng)式碼可以實(shí)現(xiàn)系統(tǒng)資源的不同利用，從而平衡存儲(chǔ)和通信成本.該方案的恢復(fù)閾值為KEntangled polynomial=pmn+p-1.此外，糾纏多項(xiàng)式碼啟發(fā)了通用多項(xiàng)式計(jì)算[48]、安全/私有計(jì)算[79]和區(qū)塊鏈系統(tǒng)[80]中編碼計(jì)算方案的發(fā)展.

7) 稀疏編碼.大規(guī)模機(jī)器學(xué)習(xí)中許多問題都表現(xiàn)出極大規(guī)模的稀疏性，編碼方案可能會(huì)破壞這種稀疏結(jié)構(gòu)，并且導(dǎo)致更高的計(jì)算開銷.Wang等人[23]通過實(shí)驗(yàn)證明，在稀疏矩陣乘法中，多項(xiàng)式編碼方案的最終完成時(shí)間與未編碼方案相比顯著增加.針對(duì)稀疏矩陣乘法問題，Wang等人[23]提出了一種“稀疏編碼”方案，其在編碼過程中充分利用了稀疏矩陣的特性，其恢復(fù)閾值可以以較高的概率達(dá)到mn，并且可以降低工作節(jié)點(diǎn)計(jì)算量.實(shí)驗(yàn)結(jié)果表明，與未編碼方案、MDS碼[2]、乘積碼[19]、多項(xiàng)式編碼[20]和LT碼[81]相比，在不同稀疏矩陣乘法中，稀疏編碼方案都具有較快的計(jì)算速度，且對(duì)真實(shí)數(shù)據(jù)集的影響更為明顯.

我們?cè)诒?中對(duì)編碼計(jì)算方案的恢復(fù)閾值進(jìn)行了總結(jié)和對(duì)比.其中工作節(jié)點(diǎn)個(gè)數(shù)為N，輸入矩陣A,B分別被劃分為p×m和p×n個(gè)子矩陣塊.

Table 4 Summary of Recovery Threshold in Coded Computing Schemes for Matrix-matrix Multiplication表4 矩陣-矩陣乘法編碼計(jì)算方案恢復(fù)閾值總結(jié)

3.2 面向機(jī)器學(xué)習(xí)典型運(yùn)算的編碼計(jì)算

3.2.1 梯度下降算法編碼方案

Tandon等人[24]首次提出了梯度編碼(gradient coding, GC)這一概念，通過有效利用工作節(jié)點(diǎn)額外的計(jì)算和存儲(chǔ)，使得主節(jié)點(diǎn)能夠容忍部分隨機(jī)掉隊(duì)節(jié)點(diǎn).基于GC思想有一系列研究方案[24-28]，這些方案的共同特征是對(duì)梯度進(jìn)行編碼.具體來說，對(duì)于一個(gè)由n個(gè)工作節(jié)點(diǎn)組成的分布式系統(tǒng)，GC的核心思想是首先將訓(xùn)練數(shù)據(jù)集劃分n個(gè)不同的批次，隨后將r(1≤r≤n)個(gè)數(shù)據(jù)批分配給每個(gè)工作節(jié)點(diǎn)，接下來工作節(jié)點(diǎn)根據(jù)分配的數(shù)據(jù)集計(jì)算出r個(gè)部分梯度，并返回r個(gè)梯度的線性組合.這些線性組合使得主節(jié)點(diǎn)可以從任意n-r+1個(gè)工作節(jié)點(diǎn)的結(jié)果中恢復(fù)出全梯度(即，所有部分梯度的和).換句話說，基于GC的編碼方案的恢復(fù)閾值為K=n-r+1.

基于這種思想Tandon等人在文獻(xiàn)[24]中構(gòu)造了2種梯度編碼方案：1)部分重復(fù)編碼(fractional repetition coding, FRC);2)循環(huán)重復(fù)編碼(cyclic repetition coding, CRC).分別對(duì)2種方案作簡(jiǎn)要介紹.

1) FRC.假設(shè)系統(tǒng)中有s個(gè)掉隊(duì)節(jié)點(diǎn)，該方案首先將n個(gè)工作節(jié)點(diǎn)平均分為(s+1)個(gè)組，則每組有(n/s+1)個(gè)工作節(jié)點(diǎn).隨后將訓(xùn)練數(shù)據(jù)均等劃分為n個(gè)數(shù)據(jù)批，并分配給每個(gè)工作節(jié)點(diǎn)r=(s+1)個(gè)不相交的數(shù)據(jù)批，所有小組彼此互為副本.完成計(jì)算后，每個(gè)工作節(jié)點(diǎn)將其部分梯度的總和傳輸給工作節(jié)點(diǎn).然而，這種構(gòu)造只在n為s+1的倍數(shù)時(shí)適用.

2) CRC.與FRC構(gòu)造不同，CRC編碼方案不需要n被(s+1)整除.在CRC中，不是分配不相交的數(shù)據(jù)批，而是考慮將(s+1)個(gè)數(shù)據(jù)批循環(huán)分配給工作節(jié)點(diǎn).如圖8所示，為n=3，s=1的數(shù)據(jù)分配示例.假設(shè)每個(gè)數(shù)據(jù)批對(duì)應(yīng)的梯度向量分別為g1,g2,g3，各個(gè)工作節(jié)點(diǎn)分別發(fā)送梯度的線性組合，例如g1/2+g2,g2-g3,g1/2+g3.主節(jié)點(diǎn)可以從任意2個(gè)向量中恢復(fù)g1+g2+g3:

(11)

Fig. 8 Example of CRC when n=3,s=1圖8 n=3,s=1 CRC編碼示例

特別地，文獻(xiàn)[24]通過構(gòu)造一個(gè)隨機(jī)編碼矩陣，從而指定數(shù)據(jù)分配以及局部梯度的線性組合的系數(shù).以圖8為例，構(gòu)造的編碼矩陣B應(yīng)為

B中每一行的非零項(xiàng)的索引決定了分配給每個(gè)工作節(jié)點(diǎn)的數(shù)據(jù)批次，而每一行的值是每個(gè)工作節(jié)點(diǎn)對(duì)梯度進(jìn)行線性組合編碼時(shí)的系數(shù).在此基礎(chǔ)上文獻(xiàn)[26-27]分別使用循環(huán)(n,n-s)MDS碼[82]和Reed-Solomon碼[83]構(gòu)造了相同功能的編碼矩陣，并達(dá)到了相同的性能，兩者的恢復(fù)閾值都為K=n-r+1.

3) BCC編碼方案.BCC方案[27]的核心思想是在主節(jié)點(diǎn)處獲得部分梯度的“覆蓋率”.簡(jiǎn)單來說，將訓(xùn)練樣本分成若干批，每個(gè)工作節(jié)點(diǎn)獨(dú)立地隨機(jī)選擇其中一個(gè)數(shù)據(jù)批進(jìn)行梯度計(jì)算，隨后工作節(jié)點(diǎn)將計(jì)算的部分梯度的和返回給主節(jié)點(diǎn).如果主節(jié)點(diǎn)之前已經(jīng)接收到同一數(shù)據(jù)批的梯度，那么主節(jié)點(diǎn)將丟棄該消息，否則保留該消息.在接收到所有數(shù)據(jù)批的處理結(jié)果之前，主節(jié)點(diǎn)一直收集消息.最后，主節(jié)點(diǎn)通過簡(jiǎn)單地計(jì)算保留的消息的總和恢復(fù)出最終結(jié)果.

4) 通信-恢復(fù)閾值平衡方案.除了恢復(fù)閾值外，通信成本也是影響分布式梯度下降算法的重要因素之一.然而上述文獻(xiàn)的重點(diǎn)在于實(shí)現(xiàn)最佳恢復(fù)閾值，并沒有考慮通信成本的問題.Ye等人[28]通過將梯度記為一個(gè)l維矢量，并對(duì)其中的元素進(jìn)行線性編碼，從而用更大的恢復(fù)閾值來換取每個(gè)工作節(jié)點(diǎn)更少的通信量.

雖然文獻(xiàn)[28]同時(shí)權(quán)衡了恢復(fù)閾值和通信開銷，但該方案存在解碼復(fù)雜度高和數(shù)值穩(wěn)定性差的問題.為了恢復(fù)梯度和，主節(jié)點(diǎn)需要計(jì)算一個(gè)大小為n-s(n為總節(jié)點(diǎn)數(shù)，s為掉隊(duì)節(jié)點(diǎn)數(shù))的矩陣的逆矩陣，這導(dǎo)致文獻(xiàn)[28]的解碼復(fù)雜度為O(n3).Kadhe等人[84]針對(duì)該問題，設(shè)計(jì)一個(gè)允許使用任意線性代碼來實(shí)現(xiàn)編解碼功能的系統(tǒng)框架.該框架使用FRC[24]方案在工作節(jié)點(diǎn)之間分配訓(xùn)練數(shù)據(jù).當(dāng)在這個(gè)框架中使用特定的碼時(shí)，它的塊長(zhǎng)度決定了計(jì)算負(fù)載、維度決定了通信開銷、最小距離決定了恢復(fù)閾值.文獻(xiàn)[84]作者使用MSD碼在Amazon EC2上評(píng)估了該框架的性能，與文獻(xiàn)[28]相比，其平均迭代時(shí)間減少了16%.

6) AGC.與針對(duì)固定數(shù)目的掉隊(duì)節(jié)點(diǎn)方案不同，Cao等人[87]提出了一種具有靈活容忍度的自適應(yīng)梯度編碼(adaptive gradient coding, AGC)方案.通過讓工作節(jié)點(diǎn)按輪次向主節(jié)點(diǎn)發(fā)送信號(hào)，該方案在計(jì)算負(fù)載，通信開銷和恢復(fù)閾值之間實(shí)現(xiàn)了最佳折中.在AGC中，假如系統(tǒng)中沒有掉隊(duì)節(jié)點(diǎn)，則主節(jié)點(diǎn)在接收到所有工作節(jié)點(diǎn)在第一輪返回的編碼梯度后即可解碼獲得總梯度；假如系統(tǒng)中有掉隊(duì)節(jié)點(diǎn)，則正常工作節(jié)點(diǎn)需要繼續(xù)返回編碼梯度，直至主節(jié)點(diǎn)可以解碼總梯度.因此，該方案適用于掉隊(duì)節(jié)點(diǎn)數(shù)量未知并且隨著算法迭代而變化的實(shí)際應(yīng)用.表5對(duì)編碼梯度下降方案進(jìn)行了分類，并總結(jié)了各方案的恢復(fù)閾值.

Table 5 Classification and Summary of Coded Computing Schemes for Gradient表5 編碼梯度下降方案分類和總結(jié)

3.2.2 卷積計(jì)算和傅里葉變換

1) 卷積計(jì)算.卷積運(yùn)算在數(shù)學(xué)、物理、統(tǒng)計(jì)和信號(hào)處理中具有廣泛的應(yīng)用.特別是對(duì)于卷積神經(jīng)網(wǎng)絡(luò)來說，卷積常被用于過濾或提取特征.Dutta等人[30]針對(duì)受掉隊(duì)節(jié)點(diǎn)影響的分布式卷積計(jì)算系統(tǒng)，提出了一種新穎的編碼卷積策略.該編碼策略首先將輸入向量分割為長(zhǎng)度一定的短向量，并使用MDS碼對(duì)預(yù)先指定的向量進(jìn)行編碼，從而可以在目標(biāo)時(shí)間內(nèi)快速可靠地完成計(jì)算.

2) 離散傅里葉變換.離散傅里葉變換是包括信號(hào)處理，數(shù)據(jù)分析和機(jī)器學(xué)習(xí)算法等在內(nèi)的許多應(yīng)用程序的基礎(chǔ)操作之一.Yu等人[31]為了減少分布式離散傅里葉變換算法的計(jì)算延遲，提出了一種編碼傅里葉變換方案.該方案利用離散傅里葉變換的遞歸結(jié)構(gòu)，首先將其分解為多個(gè)短向量上的離散傅里葉變換操作，其次利用傅里葉變換的線性特性，對(duì)輸入數(shù)據(jù)進(jìn)行線性編碼，使工作節(jié)點(diǎn)的輸出具有一定的MDS碼特性，從而減少分布式計(jì)算的計(jì)算延遲.

3.2.3 非線性計(jì)算

由于神經(jīng)網(wǎng)絡(luò)的某些層，如激活層是非線性的，所以算法的整體計(jì)算是非線性的.然而，本文討論的編碼計(jì)算方案并不適用于具有非線性計(jì)算的神經(jīng)網(wǎng)絡(luò).但這些網(wǎng)絡(luò)的性能也受到掉隊(duì)節(jié)點(diǎn)的限制.Dutra等人[88]提出的一種用于矩陣-向量乘法的Generalized PolyDot編碼方案，是可以擴(kuò)展到深度神經(jīng)網(wǎng)絡(luò)(deep neural network, DNN)的方法之一.Generalized PolyDot通過對(duì)DNN中每一層的線性運(yùn)算進(jìn)行編碼，從而允許每一層的訓(xùn)練中出現(xiàn)錯(cuò)誤.換句話說，在錯(cuò)誤量不超過最大錯(cuò)誤容忍度的情況下，解碼仍然可以正確執(zhí)行.Hadidi等人[89]指出編碼技術(shù)可以有效降低IoT系統(tǒng)中不同神經(jīng)網(wǎng)絡(luò)架構(gòu)如AlexNet[90]中的計(jì)算延遲.但是，這種統(tǒng)一編碼DNN的策略可能不適用于其他具有大量非線性函數(shù)的神經(jīng)網(wǎng)絡(luò).現(xiàn)有的編碼計(jì)算方法側(cè)重于手工設(shè)計(jì)新的編碼方法，大多都不適合預(yù)測(cè)服務(wù)系統(tǒng).

因此，Kosaian等人[32]在CNN和多層感知器的基礎(chǔ)上，提出了一種用來學(xué)習(xí)編碼和解碼功能的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)和訓(xùn)練方法.在沒有掉隊(duì)節(jié)點(diǎn)的情況下，解碼函數(shù)返回的預(yù)測(cè)結(jié)果與其他預(yù)測(cè)服務(wù)系統(tǒng)的結(jié)果相同.當(dāng)出現(xiàn)掉隊(duì)節(jié)點(diǎn)時(shí)，解碼函數(shù)的輸出是對(duì)緩慢或失敗預(yù)測(cè)的近似重建.通過使用ResNet-18分類器在數(shù)據(jù)集MNIST，F(xiàn)ashion-MNIST和CIFAR-10上進(jìn)行實(shí)驗(yàn)，結(jié)果顯示該方案重建不可用,輸出結(jié)果的正確率分別為95.71%，82.77%和60.74%.

3.3 其他面向計(jì)算延遲的編碼計(jì)算方案

就適用場(chǎng)景而言，第3.1～3.2節(jié)所介紹的編碼計(jì)算方案中工作節(jié)點(diǎn)皆是同構(gòu)的，而分布式計(jì)算中另一個(gè)常見特性是工作節(jié)點(diǎn)的異構(gòu)性.因此，研究如何減少異構(gòu)分布式計(jì)算場(chǎng)景下的計(jì)算延遲也是非常必要的.

1) 異構(gòu)場(chǎng)景下編碼計(jì)算方案.為了更好地處理異構(gòu)分布式計(jì)算系統(tǒng)中的掉隊(duì)節(jié)點(diǎn)，必須考慮設(shè)計(jì)有效的負(fù)載分配策略，以最大程度地減少總體作業(yè)執(zhí)行時(shí)間.在給定計(jì)算時(shí)間參數(shù)，即每個(gè)工作節(jié)點(diǎn)計(jì)算時(shí)間服從一個(gè)移位的指數(shù)分布時(shí)，異構(gòu)編碼矩陣乘法(heterogeneous coded matrix multiplication, HCMM)算法[33]解決了最優(yōu)負(fù)載分配問題.HCMM方案利用編碼技術(shù)和計(jì)算負(fù)載分配策略，最大程度地減少了平均計(jì)算時(shí)間.仿真結(jié)果表明，相比于未編碼方案，未編碼負(fù)載平衡方案和統(tǒng)一的負(fù)載分配編碼方案，HCMM分別將平均計(jì)算時(shí)間分別減少了71%，53%和39%.

雖然HCMM顯著降低了計(jì)算延遲，但其解碼復(fù)雜度很高.在實(shí)際的分布式計(jì)算系統(tǒng)中，某些處理節(jié)點(diǎn)具有相同的計(jì)算能力分布，因此可以將它們組合在一起，形成一個(gè)群.通過利用這種群結(jié)構(gòu)和不同群之間的異構(gòu)性[34-35]，并結(jié)合最優(yōu)負(fù)載分配策略，不僅可以實(shí)現(xiàn)接近基于MDS碼的編碼方案的最佳計(jì)算時(shí)間，而且可以降低解碼復(fù)雜度.

除了工作節(jié)點(diǎn)的異構(gòu)能力之外，工作節(jié)點(diǎn)的可用資源也可能隨時(shí)間而變化.為了最大化工作節(jié)點(diǎn)的資源利用率，研究人員提出了適應(yīng)工作節(jié)點(diǎn)時(shí)變特性的動(dòng)態(tài)負(fù)載分配算法[36-38].Keshtkarjahromi等人[36]提出了一種編碼協(xié)同計(jì)算協(xié)議(coded cooperative computation protocol, C3P).在C3P中，主節(jié)點(diǎn)基于工作節(jié)點(diǎn)的響應(yīng)來確定編碼數(shù)據(jù)包的傳輸間隔.對(duì)于不能在給定的傳輸間隔內(nèi)完成任務(wù)的工作節(jié)點(diǎn)，它們等待下一個(gè)編碼數(shù)據(jù)包的時(shí)間更長(zhǎng).與不考慮工作節(jié)點(diǎn)動(dòng)態(tài)資源異構(gòu)性的HCMM[33]相比，C3P協(xié)議的計(jì)算延遲降低了30%.

為了避免網(wǎng)絡(luò)中掉隊(duì)節(jié)點(diǎn)造成的延遲，大多數(shù)編碼計(jì)算方案都將掉隊(duì)節(jié)點(diǎn)視為“糾刪節(jié)點(diǎn)”，這意味著它們的計(jì)算結(jié)果將被完全忽略.然而很少有工作節(jié)點(diǎn)是完全不活動(dòng)的，因此，掉隊(duì)節(jié)點(diǎn)，特別是非持久性掉隊(duì)節(jié)點(diǎn)所完成的計(jì)算結(jié)果是不可忽略的，需要更好地利用[91].

2) 利用掉隊(duì)節(jié)點(diǎn)的編碼計(jì)算方案.為了利用這些掉隊(duì)節(jié)點(diǎn)的計(jì)算能力，Ozfatura等人[39]使用了多信息通信(multi-message communication, MMC)，其允許工作節(jié)點(diǎn)在完成分配任務(wù)的一部分時(shí)傳輸其計(jì)算結(jié)果.Ozfatura等人將MMC和拉格朗日編碼計(jì)算方案[48]相結(jié)合，以最大程度地縮短作業(yè)執(zhí)行時(shí)間，但由于工作節(jié)點(diǎn)傳輸?shù)街鞴?jié)點(diǎn)的消息數(shù)量增加而導(dǎo)致通信負(fù)載增加.Kiani等人[40]將分配給工作節(jié)點(diǎn)的任務(wù)進(jìn)一步分為較小的部分，并且允許工作節(jié)點(diǎn)之間交流其各自計(jì)算結(jié)果，這使得掉隊(duì)節(jié)點(diǎn)所做的工作可以被充分利用.

Ferdinand等人[41]提出一種分層編碼計(jì)算方案，以利用所有工作節(jié)點(diǎn)的計(jì)算結(jié)果.在該方案中，每個(gè)工作節(jié)點(diǎn)將分配的計(jì)算任務(wù)按層劃分為多個(gè)子計(jì)算，然后按順序進(jìn)行處理，即在下一層計(jì)算開始之前，需要將已完成層的子計(jì)算的結(jié)果傳輸?shù)街鞴?jié)點(diǎn).Ferdinand等人使用MDS碼對(duì)每層任務(wù)進(jìn)行編碼，以使工作節(jié)點(diǎn)完成每層任務(wù)的計(jì)算時(shí)間大致相同.隨后該分層編碼計(jì)算方案被Kiani等人[42]擴(kuò)展到分布式矩陣-矩陣乘法和矩陣-向量乘法中.對(duì)于這2種類型的乘法，Kiani等人通過實(shí)驗(yàn)表明，雖然解碼時(shí)間有所減少，但是分層編碼的計(jì)算時(shí)間要比文獻(xiàn)[39]中的方案長(zhǎng).

雖然編碼計(jì)算方案可以降低通信負(fù)載并減少作業(yè)執(zhí)行時(shí)間，但未編碼的計(jì)算方案具有其自身的優(yōu)勢(shì)，即不需解碼并允許部分梯度更新.為了結(jié)合2種方案的優(yōu)點(diǎn)，Ozfatura等人[43]提出了編碼部分梯度計(jì)算(coded partial gradient computation, CPGC)方案.因?yàn)槊總€(gè)工作節(jié)點(diǎn)都有很高的概率完成第一次分配的任務(wù)，所以CPGC首先分配給工作節(jié)點(diǎn)未編碼的子矩陣，在工作節(jié)點(diǎn)完成計(jì)算后，再分配給其編碼子矩陣.主節(jié)點(diǎn)能夠使用一部分工作節(jié)點(diǎn)的全部計(jì)算結(jié)果和掉隊(duì)節(jié)點(diǎn)的部分計(jì)算結(jié)果來更新梯度參數(shù)，從而減少任務(wù)執(zhí)行的平均時(shí)間.

3.4 小 結(jié)

本節(jié)我們探討編碼技術(shù)在不同分布式計(jì)算任務(wù)中的應(yīng)用.首先對(duì)3.3節(jié)方案進(jìn)行總結(jié)回顧，如表6所示：

Table 6 Summary and Review of Coded Computing Schemes for Computing Delay表6 面向計(jì)算延遲的編碼計(jì)算方案總結(jié)與回顧

續(xù)表6

在矩陣-向量乘法任務(wù)中，研究人員不僅考慮如何使得恢復(fù)閾值最小，而且考慮了如何降低工作節(jié)點(diǎn)處的計(jì)算負(fù)載，以從整體上降低計(jì)算時(shí)間.特別地，無碼率編碼[18]可以有效利用掉隊(duì)節(jié)點(diǎn)所做的工作，但該方案工作節(jié)點(diǎn)和主節(jié)點(diǎn)通信輪次增高，帶來較大的通信開銷.在矩陣-矩陣乘法中，現(xiàn)有研究方案都先將輸入矩陣劃分為較小的子矩陣，然后對(duì)子矩陣進(jìn)行編碼，生成編碼矩陣.乘積碼[19]使用MDS碼在2個(gè)維度上對(duì)矩陣進(jìn)行編碼，多項(xiàng)式碼[20]、MatDot[21]、PolyDot[21]、糾纏多項(xiàng)式碼[22]則使用隨機(jī)數(shù)對(duì)子矩陣進(jìn)行編碼，只不過在矩陣分割形式上有所不同.文獻(xiàn)[20-22]解碼最終結(jié)果的方法都可看成多項(xiàng)式插值問題.但這些方案都未考慮矩陣的稀疏性，因此研究人員提出了稀疏碼方案[23]，在計(jì)算速度上較其他方案有較大優(yōu)勢(shì).梯度下降編碼方案則大致可分為2類:1)基于GC的編碼方案[24-27]，這些方案中工作節(jié)點(diǎn)返回局部梯度的線性組合；2)對(duì)數(shù)據(jù)進(jìn)行編碼的方案，雖然該方案的恢復(fù)閾值比GC編碼方案低，但其對(duì)數(shù)據(jù)進(jìn)行編碼帶來了額外的計(jì)算開銷.

雖然大多數(shù)的研究都集中在編碼的設(shè)計(jì)上，但是譯碼復(fù)雜度和工作節(jié)點(diǎn)的計(jì)算負(fù)載也會(huì)對(duì)計(jì)算時(shí)間產(chǎn)生很大的影響.因此面向計(jì)算延遲的編碼計(jì)算方案不應(yīng)僅以降低恢復(fù)閾值為目標(biāo)，而應(yīng)權(quán)衡恢復(fù)閾值，計(jì)算負(fù)載和譯碼復(fù)雜度三者之間的關(guān)系，從而使整體計(jì)算時(shí)間最短.除了Reed-Solomon碼[81]和LDPC碼[85]，更有效的低復(fù)雜度解碼方式需要進(jìn)一步探索.

4 面向安全隱私的編碼計(jì)算

在分布式計(jì)算系統(tǒng)中，好奇的工作節(jié)點(diǎn)可能串通起來以獲取原始數(shù)據(jù)的信息，而受到拜占庭攻擊的惡意工作節(jié)點(diǎn)可能故意提供錯(cuò)誤的結(jié)果[92]，從而誤導(dǎo)最終結(jié)果.抗惡意節(jié)點(diǎn)的編碼計(jì)算方案往往通過設(shè)計(jì)具有糾錯(cuò)能力的解碼方式以定位惡意節(jié)點(diǎn)，從而獲取正確結(jié)果.防隱私泄露的編碼計(jì)算方案則通過引入一個(gè)隨機(jī)均勻矩陣對(duì)輸入數(shù)據(jù)進(jìn)行編碼，從而達(dá)到掩藏真實(shí)數(shù)據(jù)的目的.

面向安全隱私的編碼計(jì)算方案的目標(biāo)是通過利用編碼技術(shù)，在系統(tǒng)中存在M個(gè)惡意節(jié)點(diǎn)和T個(gè)共謀節(jié)點(diǎn)時(shí)，依然可以獲得正確結(jié)果，并且不泄露原始數(shù)據(jù)的任何信息.我們將分別從抗惡意節(jié)點(diǎn)和防隱私泄露2方面對(duì)當(dāng)前編碼計(jì)算方案進(jìn)行分析.

4.1 抗惡意節(jié)點(diǎn)的編碼計(jì)算

在分布式計(jì)算的應(yīng)用場(chǎng)景中，如戰(zhàn)場(chǎng)物聯(lián)網(wǎng)[93]、聯(lián)邦學(xué)習(xí)[94]等，工作節(jié)點(diǎn)的計(jì)算可能是不可信的.因此，一個(gè)重要的問題是是否能夠在拜占庭敵手的存在下可靠地執(zhí)行分布式計(jì)算，并且該問題由來已久[95].最近，編碼技術(shù)被應(yīng)用到分布式計(jì)算系統(tǒng)中，以抵抗分布式計(jì)算系統(tǒng)中的拜占庭攻擊問題.

1) DRACO.在分布式梯度下降算法中，Chen等人分別利用FRC和CRC[24]對(duì)數(shù)據(jù)進(jìn)行編碼(具體編碼方法見4.3節(jié))，并針對(duì)2種不同的編碼方法，設(shè)計(jì)了2種不同的解碼方案.

具體來說，利用FRC對(duì)數(shù)據(jù)進(jìn)行編碼時(shí)，DRACO[44]讓每一組中的節(jié)點(diǎn)來計(jì)算相同的梯度的和.為了解碼同一組中的計(jì)算節(jié)點(diǎn)返回的輸出，主節(jié)點(diǎn)使用多數(shù)投票算法來選擇其中一個(gè)值.這保證了只要每組中少于一半的節(jié)點(diǎn)是惡意的，主節(jié)點(diǎn)將選擇到正確的結(jié)果.由此，主節(jié)點(diǎn)可以獲得所有組的正確的結(jié)果.利用CRC對(duì)數(shù)據(jù)進(jìn)行編碼時(shí)，DRACO利用離散傅里葉逆變換矩陣構(gòu)造一個(gè)函數(shù)φ(·).函數(shù)φ(·)可以利用文件分配矩陣來計(jì)算惡意工作節(jié)點(diǎn)的索引.因此，DRACO可以利用非惡意節(jié)點(diǎn)返回的值來解碼最終結(jié)果.仿真結(jié)果表明，DRACO算法在MNIST數(shù)據(jù)集上實(shí)現(xiàn)90%的測(cè)試精度時(shí)，比中值聚合方案[96]快3倍以上.隨后，Rajput等人[97]使用梯度濾波器進(jìn)一步提高了DRACO的計(jì)算效率.

2) 響應(yīng)冗余.Gupta等人[45]提出“響應(yīng)冗余”的概念，并利用隨機(jī)檢測(cè)的方法來提高系統(tǒng)的工作效率.其核心思想是讓工作節(jié)點(diǎn)響應(yīng)2次，且在每次響應(yīng)中，為同一個(gè)工作節(jié)點(diǎn)分配不同的子數(shù)據(jù)集.通過對(duì)比2次響應(yīng)的結(jié)果，主節(jié)點(diǎn)可以確定系統(tǒng)中惡意節(jié)點(diǎn)的索引.

然而，引入響應(yīng)冗余使得工作節(jié)點(diǎn)的計(jì)算成本比DRACO[44]高2倍.為了降低計(jì)算成本，Gupta等人提出了隨機(jī)方案，即主節(jié)點(diǎn)隨機(jī)選擇中間迭代的結(jié)果進(jìn)行檢測(cè)，或者，在每一次迭代中，主節(jié)點(diǎn)以概率p(0

4) LCC.針對(duì)任意多元多項(xiàng)式的計(jì)算任務(wù)，Yu等人[48]提出一種拉格朗日編碼計(jì)算方案，該方案對(duì)輸入數(shù)據(jù)進(jìn)行編碼，不僅可以降低計(jì)算延遲，而且可以抵抗惡意節(jié)點(diǎn)的攻擊，同時(shí)保護(hù)數(shù)據(jù)的隱私.

考慮一個(gè)具有N個(gè)工作節(jié)點(diǎn)的分布式計(jì)算系統(tǒng)，其目標(biāo)是對(duì)大型數(shù)據(jù)集X=(X1,X2,…,XK)中每一個(gè)Xi，計(jì)算f(Xi)(f是給定的階為deg(f)的多元多項(xiàng)式).如果通過利用合適的編碼方法可以在系統(tǒng)中存在S個(gè)掉隊(duì)節(jié)點(diǎn)，A個(gè)惡意節(jié)點(diǎn)，T個(gè)合謀節(jié)點(diǎn)時(shí)仍然獲得正確結(jié)果且不暴露數(shù)據(jù)隱私，則認(rèn)為該方案可以實(shí)現(xiàn)三元組(S,A,T).

如果N≥(K+T-1)deg(f)+S+2A+1，則LCC可以實(shí)現(xiàn)三元組(S,A,T).該結(jié)果的意義在于，增加一個(gè)工作節(jié)點(diǎn)(即N增加1)，LCC可以使掉隊(duì)節(jié)點(diǎn)的彈性增加1，或者使惡意節(jié)點(diǎn)的魯棒性提高1/2，同時(shí)保持?jǐn)?shù)據(jù)的隱私.

(12)

LCC可以應(yīng)用于計(jì)算任務(wù)是多元多項(xiàng)式的任何計(jì)算場(chǎng)景，因此涵蓋了機(jī)器學(xué)習(xí)中許多計(jì)算任務(wù)，例如，線性計(jì)算、雙線性計(jì)算、一般張量代數(shù)和梯度下降.

4.2 防隱私泄露的編碼計(jì)算

在分布式計(jì)算模型中，要計(jì)算的輸入數(shù)據(jù)可能包含大量敏感信息，如個(gè)人位置信息和醫(yī)療信息.但是主節(jié)點(diǎn)有時(shí)需要利用可疑但有用的工作節(jié)點(diǎn).因此保護(hù)輸入數(shù)據(jù)的敏感信息不被泄露變得至關(guān)重要.

4.2.1 面向多項(xiàng)式運(yùn)算的隱私編碼方案

作為L(zhǎng)CC的擴(kuò)展，So等人[49]提出了一種快速且具有隱私保護(hù)功能的分布式機(jī)器學(xué)習(xí)框架——CodedPrivateML.該框架在每一輪訓(xùn)練中分2步秘密共享數(shù)據(jù)集和模型參數(shù).首先，采用隨機(jī)量化方法將數(shù)據(jù)集和每輪的權(quán)重向量轉(zhuǎn)換為有限域.然后，CodedPrivateML使用LCC編碼技術(shù)將量化值進(jìn)行編碼，并將編碼數(shù)據(jù)分發(fā)給各工作節(jié)點(diǎn)，以保證數(shù)據(jù)隱私.CodedPrivateML面臨的挑戰(zhàn)是：LCC只能用于多項(xiàng)式求值形式的計(jì)算.因此，CodedPrivateML利用多項(xiàng)式逼近來處理涉及到sigmoid函數(shù)時(shí)的非線性計(jì)算，從而可以對(duì)LCC編碼的數(shù)據(jù)進(jìn)行Logistic回歸.在Amazon EC2集群上的實(shí)驗(yàn)表明：CodedPrivateML比基于BGW[51]的安全多方計(jì)算方法快34倍，并且可以保護(hù)數(shù)據(jù)的隱私.

針對(duì)梯度類型的計(jì)算，Yu等人[60]提出了一種新穎的編碼計(jì)算方案，稱為“調(diào)和編碼”，該方案適用于任何類型的梯度計(jì)算，同時(shí)可以保護(hù)輸入數(shù)據(jù)的隱私.和LCC不同的是，調(diào)和編碼使用一個(gè)隨機(jī)變量Z來構(gòu)造具有遞歸結(jié)構(gòu)的中間值P，然后使用P對(duì)數(shù)據(jù)進(jìn)行編碼.由于Z是隨機(jī)的，因此原始數(shù)據(jù)被掩藏，數(shù)據(jù)隱私得到保護(hù).又由于中間值P的特殊結(jié)構(gòu)，所以使得該方案相比于Shamir秘密共享方案[98]和LCC[48]方案，在計(jì)算梯度型函數(shù)時(shí)需要更少的工作節(jié)點(diǎn).表7總結(jié)了3種方案在保護(hù)數(shù)據(jù)隱私時(shí)所需的最少工作節(jié)點(diǎn)數(shù).

Table 7 Comparison of the Minimum Number of Working Nodes表7 最少工作節(jié)點(diǎn)數(shù)對(duì)比

利用多項(xiàng)式碼[20]可以有效降低分布式計(jì)算系統(tǒng)中的計(jì)算延遲，且恢復(fù)閾值與工作節(jié)點(diǎn)的數(shù)量無關(guān).在此基礎(chǔ)上，Nodehi等人[50]將多項(xiàng)式碼與BGW方案[51]結(jié)合在一起，提出了一種多項(xiàng)式共享方案.在該方案中，數(shù)據(jù)源自外部資源，因此必須對(duì)工作節(jié)點(diǎn)和主節(jié)點(diǎn)同時(shí)保持私有.與BGW方案不同，Nodehi等人使用多項(xiàng)式碼對(duì)數(shù)據(jù)集進(jìn)行編碼.文獻(xiàn)[50]可用于執(zhí)行加法、乘法和多項(xiàng)式函數(shù)等多種計(jì)算過程，同時(shí)可以減少完成任務(wù)所需的工作節(jié)點(diǎn)數(shù).

在文獻(xiàn)[50]中，執(zhí)行計(jì)算的數(shù)據(jù)集被分成多個(gè)子數(shù)據(jù)集，每個(gè)子數(shù)據(jù)集被編碼并分配給工作節(jié)點(diǎn).在這種情況下，較快完成任務(wù)的工作節(jié)點(diǎn)將在等待掉隊(duì)節(jié)點(diǎn)時(shí)處于空閑狀態(tài).為了進(jìn)一步減少計(jì)算延遲，Kim等人[99]利用計(jì)算冗余提出了一種私有異步多項(xiàng)式編碼方案，該方案將一個(gè)計(jì)算任務(wù)分成幾個(gè)相對(duì)較小的子任務(wù)，并將子任務(wù)分配給每個(gè)工作節(jié)點(diǎn).除了保留多項(xiàng)式共享方案的隱私保護(hù)特性外，該方案有2個(gè)優(yōu)點(diǎn)：1)計(jì)算能力有限的掉隊(duì)節(jié)點(diǎn)可以成功地完成較小的子任務(wù)；2)計(jì)算速度較快的工作節(jié)點(diǎn)被分配更多的任務(wù)，在整個(gè)任務(wù)計(jì)算期間持續(xù)工作，從而減少了整個(gè)任務(wù)的執(zhí)行時(shí)間.

然而，文獻(xiàn)[50，99]主要利用多項(xiàng)式碼來保護(hù)數(shù)據(jù)隱私，這在某些方面是有限制的，例如，它只允許將矩陣按列劃分.因此，Nodehi等人[100]利用糾纏多項(xiàng)式碼[22]提出了一種糾纏多項(xiàng)式碼共享方案，該方案作為多項(xiàng)式共享的擴(kuò)展，進(jìn)一步減少了數(shù)據(jù)共享階段的限制，從而在滿足隱私約束的同時(shí)減少執(zhí)行相同計(jì)算任務(wù)所需的工作節(jié)點(diǎn)的數(shù)量.

4.2.2 面向矩陣乘法運(yùn)算的隱私編碼方案

針對(duì)矩陣乘法的特點(diǎn)研究人員考慮了2種隱私情況：

1) 單邊隱私.輸入數(shù)據(jù)中只有一個(gè)是私有的，另一個(gè)輸入對(duì)工作節(jié)點(diǎn)是公開的.

2) 雙邊隱私.2個(gè)輸入數(shù)據(jù)都是私有的，工作節(jié)點(diǎn)無法獲得所有輸入的有關(guān)信息.

分別對(duì)2種隱私情況下的編碼計(jì)算方案進(jìn)行介紹和分析.

單邊隱私.Bitar等人[52-53]提出使用階梯碼替換線性秘密共享方案[101]來對(duì)數(shù)據(jù)進(jìn)行編碼.作為說明，考慮一個(gè)有3個(gè)工作節(jié)點(diǎn)的分布式計(jì)算場(chǎng)景，其目標(biāo)是分布式計(jì)算矩陣-向量乘法Ax，并保護(hù)輸入數(shù)據(jù)A的隱私(單邊隱私).為保護(hù)數(shù)據(jù)隱私，主節(jié)點(diǎn)生成一個(gè)與A具有相同維數(shù)的隨機(jī)矩陣R.當(dāng)使用線性秘密共享方案時(shí)，數(shù)據(jù)和隨機(jī)矩陣不被分割，作為一個(gè)整體進(jìn)行編碼和傳輸，如表8所示:

Table 8 Transmission Contents of Two Different Schemes表8 2種不同共享方案的傳輸內(nèi)容

因此，主節(jié)點(diǎn)必須等待其中任意2個(gè)工作節(jié)點(diǎn)的完整結(jié)果，才能解碼最終結(jié)果，如Ax=S2x-S1x.當(dāng)使用階梯碼時(shí)，數(shù)據(jù)和隨機(jī)矩陣在傳輸給工作節(jié)點(diǎn)之前被分割成子矩陣.隨后主節(jié)點(diǎn)發(fā)送給工作節(jié)點(diǎn)2組編碼數(shù)據(jù)，如表8所示.因此，每個(gè)工作節(jié)點(diǎn)有2個(gè)子任務(wù).每個(gè)工作節(jié)點(diǎn)按順序執(zhí)行計(jì)算任務(wù)，并將計(jì)算結(jié)果返回給主節(jié)點(diǎn).當(dāng)工作節(jié)點(diǎn)完成了足夠多的子任務(wù)后，主節(jié)點(diǎn)可以通知工作節(jié)點(diǎn)停止計(jì)算.例如，當(dāng)主節(jié)點(diǎn)接收到所有工作節(jié)點(diǎn)的第一個(gè)子任務(wù)的計(jì)算結(jié)果，或者主節(jié)點(diǎn)接收到任意2個(gè)工作節(jié)點(diǎn)的所有任務(wù)的結(jié)果時(shí)，可以從中解碼獲得最終的結(jié)果.在有4個(gè)工作節(jié)點(diǎn)的分布式計(jì)算場(chǎng)景下，Bitar等人在Amazon EC2集群上進(jìn)行實(shí)驗(yàn)，結(jié)果表明使用階梯碼的平均等待時(shí)間比線性秘密共享方案減少了59%.

Bitar等人[54]考慮到戰(zhàn)場(chǎng)物聯(lián)網(wǎng)(internet of battlefield things, IoBT)應(yīng)用和設(shè)備的隱私要求，以及戰(zhàn)場(chǎng)邊緣設(shè)備資源的異構(gòu)和時(shí)變性，提出了一種私密無速率自適應(yīng)(private and rateless adaptive coded computation, PRAC)編碼計(jì)算方案.和階梯碼相同，PRAC也引入隨機(jī)矩陣來掩藏原始數(shù)據(jù)，但不同的是PRAC考慮了工作節(jié)點(diǎn)的異構(gòu)性，使用噴泉碼[81]對(duì)數(shù)據(jù)進(jìn)行編碼，并根據(jù)工作節(jié)點(diǎn)的響應(yīng)情況，動(dòng)態(tài)地生成和分配隨機(jī)矩陣和編碼數(shù)據(jù).

雙邊隱私.Chang等人[55]首次考慮了矩陣乘法中雙邊隱私的情況，并設(shè)計(jì)了一個(gè)可行性方案.具體來說，輸入矩陣被分割成子矩陣并用隨機(jī)矩陣編碼.以工作節(jié)點(diǎn)數(shù)為8、共謀節(jié)點(diǎn)數(shù)為1，來說明文獻(xiàn)[55]的編碼過程.

主節(jié)點(diǎn)首先將輸入矩陣A，B進(jìn)行劃分

(13)

其中,A1,A2∈m/2×n，B1,B2∈n×p/2.然后，分別為A,B各生成一個(gè)隨機(jī)矩陣KA∈m/2×n,KB∈n×p/2.主節(jié)點(diǎn)為每個(gè)工作節(jié)點(diǎn)i選擇不同的參數(shù)xi，生成編碼數(shù)據(jù)為

(14)

(15)

h(x)=A1B1+A2B1x+KAB1x2+A1B2x3+A2B2x4+(KAB2+A1KB)x5+A2KBx6+KAKBx7.

(16)

由式(16)可知，多項(xiàng)式h(x)中4項(xiàng)A1B1,A2B1x,A1B2x,A2B2x的系數(shù)可組成最終結(jié)果.因此，主節(jié)點(diǎn)可以采取多項(xiàng)式插值法確定該多項(xiàng)式，從而獲得所需的系數(shù).

在該編碼思想的基礎(chǔ)上，Kakar等人[56]針對(duì)雙邊隱私提出了一種新的任意矩陣劃分下的對(duì)齊秘密共享方案，以優(yōu)化下載比率和恢復(fù)閾值.與文獻(xiàn)[55]將2個(gè)輸入矩陣劃分為相同數(shù)量的子矩陣不同，Kakar等人[56]將輸入矩陣劃分為不同數(shù)量的子矩陣.與文獻(xiàn)[55]相比，文獻(xiàn)[56]在下載比率、可容忍共謀服務(wù)器數(shù)量和計(jì)算復(fù)雜度等方面都有所改進(jìn).

受多項(xiàng)式碼[20]的啟發(fā)，Yang等人[57]將多項(xiàng)式碼擴(kuò)展到保護(hù)雙邊隱私的矩陣乘法中.和文獻(xiàn)[55-56]不同，該方案僅需為每個(gè)輸入矩陣生成1個(gè)隨機(jī)矩陣便可完成編碼.主節(jié)點(diǎn)的解碼過程與多項(xiàng)式碼方案相似，都可視為多項(xiàng)式插值問題.和文獻(xiàn)[56]相比，該方案的編碼復(fù)雜度要低，并且在下載比率相似的情況下，可實(shí)現(xiàn)更低的恢復(fù)閾值.

4.3 小 結(jié)

本節(jié)我們討論了編碼計(jì)算在分布式計(jì)算系統(tǒng)中對(duì)抗惡意節(jié)點(diǎn)以及保護(hù)數(shù)據(jù)隱私方面的應(yīng)用和研究.首先我們對(duì)4.1～4.2節(jié)方案進(jìn)行總結(jié)和回顧，如表9所示.

抗惡意節(jié)點(diǎn)的編碼計(jì)算方案往往通過設(shè)計(jì)具有糾錯(cuò)能力的解碼方式以獲取正確結(jié)果.DRACO[44]采用文獻(xiàn)[24]中FRC和CRC兩種編碼方式，但在解碼階段分別引入了多數(shù)投票算法和檢測(cè)函數(shù).Gupta等人[45]采用基于GC的編碼方式對(duì)梯度進(jìn)行編碼，但解碼階段則引入響應(yīng)冗余，用以檢測(cè)惡意節(jié)點(diǎn).Data等人[46]在編碼階段設(shè)計(jì)具有錯(cuò)誤校正能力的編碼矩陣，利用該矩陣對(duì)輸入數(shù)據(jù)進(jìn)行編碼，以在解碼階段可以對(duì)惡意節(jié)點(diǎn)進(jìn)行定位.LCC[48]通過構(gòu)造多項(xiàng)式的方式對(duì)數(shù)據(jù)進(jìn)行編碼，并在解碼階段利用具有糾錯(cuò)能力的Reed-Solomon解碼器進(jìn)行解碼.防隱私泄露的編碼計(jì)算方案在對(duì)數(shù)據(jù)進(jìn)行編碼時(shí)，額外引入一個(gè)隨機(jī)矩陣，以此對(duì)原數(shù)據(jù)進(jìn)行掩藏.特別是，針對(duì)矩陣乘法任務(wù)，本節(jié)討論了單、雙邊隱私2種情況.一般來說，利用特定運(yùn)算的代數(shù)結(jié)構(gòu)，例如卷積任務(wù)或梯度計(jì)算，實(shí)現(xiàn)編碼和解碼的方案通常表現(xiàn)更高效.

Table 9 Summary and Review of Coded Computing Schemes for Security and Privacy表9 面向安全和隱私的編碼計(jì)算方案總結(jié)和回顧

6 研究展望

目前，關(guān)于編碼計(jì)算在學(xué)術(shù)界的研究才剛剛起步，存在許多問題需要解決，提供一系列研究機(jī)遇，本文從3個(gè)方面對(duì)未來可能的研究方向進(jìn)行闡述.

1) 通信與計(jì)算的松耦合.在將編碼應(yīng)用于數(shù)據(jù)洗牌的相關(guān)工作中，通信和計(jì)算是松耦合的.即，其只關(guān)心通信目標(biāo)：主節(jié)點(diǎn)希望以最小的通信負(fù)載使得每個(gè)工作節(jié)點(diǎn)都能獲得執(zhí)行計(jì)算任務(wù)所需要的數(shù)據(jù).為了實(shí)現(xiàn)最小化通信負(fù)載，往往需要計(jì)算節(jié)點(diǎn)額外存儲(chǔ)大量數(shù)據(jù)(存儲(chǔ)冗余)，而這些冗余數(shù)據(jù)只幫助傳輸并不用于計(jì)算[15].

未來一個(gè)可能的工作方向是提高通信與計(jì)算的耦合性.如果多余的存儲(chǔ)數(shù)據(jù)用于計(jì)算，則可以獲得潛在的計(jì)算增益.例如，在訓(xùn)練一個(gè)分類器模型時(shí)，多余的數(shù)據(jù)樣本也有助于模型訓(xùn)練.設(shè)計(jì)一個(gè)計(jì)算和通信耦合度較高的方案，并研究其中通信與計(jì)算兩者之間的折中是必要的.

2) 掉隊(duì)節(jié)點(diǎn)的利用和通信負(fù)載的平衡.雖然掉隊(duì)節(jié)點(diǎn)的運(yùn)行速度比平均速度慢，但其完成的計(jì)算結(jié)果對(duì)仍然有助于實(shí)現(xiàn)最終計(jì)算任務(wù).例如，在文獻(xiàn)[58]中，為了使線性逆求解器在截止期約束下的均方誤差最小，掉隊(duì)節(jié)點(diǎn)的結(jié)果被視為軟誤差.然而，當(dāng)前利用掉隊(duì)節(jié)點(diǎn)計(jì)算結(jié)果的方案中，往往需要執(zhí)行更多的通信輪次.而高通信成本是分布式計(jì)算系統(tǒng)的另一個(gè)瓶頸.未來一個(gè)可能的研究方向是在利用掉隊(duì)節(jié)點(diǎn)的計(jì)算結(jié)果時(shí)，探索使主節(jié)點(diǎn)和工作節(jié)點(diǎn)之間通信成本最小化的優(yōu)化方法.

3) 安全隱私中的異構(gòu).由于掉隊(duì)節(jié)點(diǎn)是分布式計(jì)算中的一個(gè)基本問題，因此面向計(jì)算延遲的編碼計(jì)算方案考慮了異構(gòu)場(chǎng)景.然而，在編碼計(jì)算相關(guān)工作中，其他方面的異構(gòu)網(wǎng)絡(luò)問題還沒有得到充分的研究[57].例如，工作節(jié)點(diǎn)可能有不同程度的聲譽(yù)[102].保護(hù)數(shù)據(jù)隱私的手段可以只針對(duì)新工作節(jié)點(diǎn)或聲譽(yù)低的工作節(jié)點(diǎn)進(jìn)行，而對(duì)于受信任的工作節(jié)點(diǎn)則可能不需要.因此，未來一個(gè)可能的研究方向是考慮工作節(jié)點(diǎn)在聲譽(yù)上的異構(gòu)性，從而采取不同的隱私保護(hù)策略，以此降低可信節(jié)點(diǎn)的計(jì)算復(fù)雜度.

7 結(jié)束語

幾十年來，編碼理論在抗噪聲方面的作用得以深入研究，并被廣泛應(yīng)用于多種場(chǎng)景中，成為日?；A(chǔ)設(shè)施(如智能手機(jī)、筆記本電腦、WiFi和蜂窩系統(tǒng)等)的一部分.編碼計(jì)算將編碼理論和分布式計(jì)算系統(tǒng)相結(jié)合，旨在通過注入計(jì)算冗余創(chuàng)造編碼機(jī)會(huì)，實(shí)現(xiàn)降低通信成本、提高計(jì)算速度和保護(hù)數(shù)據(jù)安全等目標(biāo).本文通過區(qū)分研究目標(biāo)將已有編碼計(jì)算方案分為3類，對(duì)相應(yīng)范疇下的研究現(xiàn)狀進(jìn)行了詳細(xì)闡述，對(duì)比分析了典型方案，總結(jié)歸納了編碼計(jì)算面臨的挑戰(zhàn)及研究方向，預(yù)期為分布式計(jì)算的研究人員帶來啟發(fā)和參考.

作者貢獻(xiàn)聲明：蔡志平是本項(xiàng)目的構(gòu)思者及負(fù)責(zé)人，指導(dǎo)論文寫作;周桐慶對(duì)本文關(guān)鍵性理論和知識(shí)性內(nèi)容進(jìn)行批評(píng)性審閱;鄭騰飛是綜述的主要撰寫人;吳虹佳完成相關(guān)資料的收集和分析.周桐慶和蔡志平貢獻(xiàn)等同，同為本文通信作者.