面向大規(guī)模矩陣乘法的編碼計(jì)算性能研究

王 艷，王希齡，賴宏達(dá)，李念爽

（華東交通大學(xué)軟件學(xué)院，江西 南昌 330013）

互聯(lián)網(wǎng)的飛速發(fā)展和大數(shù)據(jù)處理框架的進(jìn)步推動(dòng)了大規(guī)模的機(jī)器學(xué)習(xí)部署，并促進(jìn)了分布式機(jī)器學(xué)習(xí)算法在更多領(lǐng)域中的應(yīng)用[1-5]。 為了更高效地利用大數(shù)據(jù)訓(xùn)練更準(zhǔn)確的大模型，在機(jī)器學(xué)習(xí)中引入大量矩陣乘法， 一旦采用了分布式機(jī)器學(xué)習(xí)模式，就意味著大量矩陣乘法的分布式計(jì)算。 然而，分布式集群中存在某些計(jì)算節(jié)點(diǎn)由于各種因素的影響（如節(jié)點(diǎn)失效、系統(tǒng)故障、通信瓶頸等），計(jì)算速度會(huì)以某種隨機(jī)的方式變慢，從而使分布式機(jī)器學(xué)習(xí)算法執(zhí)行時(shí)間增加，成為分布式計(jì)算系統(tǒng)的主要瓶頸[6]，這種節(jié)點(diǎn)被稱作掉隊(duì)節(jié)點(diǎn)。 目前減緩掉隊(duì)節(jié)點(diǎn)影響的方法主要是增加某種形式的“計(jì)算冗余”，例如，采用副本的方式在多個(gè)節(jié)點(diǎn)上執(zhí)行相同的計(jì)算任務(wù)[7]。 然而，最近的研究結(jié)果表明，編碼計(jì)算可以更加有效地減輕掉隊(duì)節(jié)點(diǎn)的影響[8-12]，同時(shí)相較于副本方案成本更低。

Tandon 等[13]研究了分布式系統(tǒng)中梯度計(jì)算的最優(yōu)編碼設(shè)計(jì)， 提出了一種新的編碼計(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ì)這兩種情況，提出了一種編碼方案來(lái)實(shí)現(xiàn)機(jī)器學(xué)習(xí)集群對(duì)掉隊(duì)節(jié)點(diǎn)的魯棒性。 Ye 等[14]提出了通信計(jì)算高效梯度編碼方案，它從計(jì)算負(fù)載、掉隊(duì)節(jié)點(diǎn)容忍和通信成本3 個(gè)方面描述了梯度計(jì)算的基本權(quán)衡。 Li 等[15]提出了一種MapReduce 的編碼框架，稱為“Coded MapReduce”，它在r（r∈N）個(gè)精心選擇的節(jié)點(diǎn)上分配每個(gè)任務(wù)的映射計(jì)算，以使網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)減少r 倍的通信負(fù)載。Li 等[16]將文獻(xiàn)[15]中提出的編碼思想應(yīng)用于Tera-Sort，提出了一種新的分布式排序算法“Coded Tera-Sort”， 大大提高了Hadoop MapReduce 中TeraSort基準(zhǔn)的執(zhí)行時(shí)間。 Reisizadeh 等[17]研究由各種不同性能的計(jì)算機(jī)組成的通用異構(gòu)分布式計(jì)算集群，提出了一個(gè)編碼框架， 通過(guò)交換冗余來(lái)減少計(jì)算延遲， 從而加速存在掉隊(duì)節(jié)點(diǎn)的異構(gòu)集群的分布式計(jì)算。Ferdinandn 等[18]提出了一種用于近似矩陣乘法的任意時(shí)刻編碼方案， 通過(guò)近似計(jì)算的形式來(lái)加速分布式計(jì)算。 Dutta 等[19]考慮了存在掉隊(duì)節(jié)點(diǎn)的情況下， 使用并行處理器計(jì)算兩個(gè)長(zhǎng)向量的卷積問(wèn)題， 提出了存在截止時(shí)間的卷積問(wèn)題的編碼計(jì)算方案。 Park 等[20]提出了一個(gè)由工作節(jié)點(diǎn)組成的層次計(jì)算結(jié)構(gòu)。

上述研究都是通過(guò)提出編碼方案來(lái)增加對(duì)掉隊(duì)節(jié)點(diǎn)的魯棒性，并未對(duì)各自編碼方案的性能開(kāi)銷展開(kāi)研究，本文重點(diǎn)考察了面向分布式機(jī)器學(xué)習(xí)的各編碼計(jì)算方案的任務(wù)完成時(shí)間和機(jī)器計(jì)算總時(shí)間兩類開(kāi)銷。 本文定義了面向分布式機(jī)器學(xué)習(xí)的編碼計(jì)算的兩個(gè)性能指標(biāo)：一是某個(gè)使用該編碼方案的計(jì)算任務(wù)完成時(shí)間，即完成整個(gè)計(jì)算任務(wù)所需要的時(shí)間；二是整個(gè)計(jì)算任務(wù)的機(jī)器計(jì)算總時(shí)間，即整個(gè)分布式計(jì)算系統(tǒng)中所有工作節(jié)點(diǎn)對(duì)該計(jì)算任務(wù)進(jìn)行計(jì)算的時(shí)間的總和。 通過(guò)計(jì)算由n 個(gè)工作節(jié)點(diǎn)組成的分布式系統(tǒng)中第i 個(gè)完成計(jì)算任務(wù)的節(jié)點(diǎn)的密度函數(shù)，給出工作節(jié)點(diǎn)計(jì)算任務(wù)完成時(shí)間符合均勻分布場(chǎng)景下計(jì)算任務(wù)的完成時(shí)間和機(jī)器計(jì)算總時(shí)間的表達(dá)式；對(duì)比分析了這一場(chǎng)景下3 種應(yīng)用于矩陣乘法的編碼方案的完成時(shí)間和機(jī)器計(jì)算總時(shí)間，并通過(guò)實(shí)驗(yàn)對(duì)比了指數(shù)分布場(chǎng)景下不同情況對(duì)任務(wù)完成時(shí)間與計(jì)算節(jié)點(diǎn)總計(jì)算開(kāi)銷影響， 提供了計(jì)算方案選擇的依據(jù)。

1 分布式計(jì)算開(kāi)銷示例

在機(jī)器學(xué)習(xí)算法中，我們經(jīng)常要執(zhí)行矩陣乘法的操作。 我們考慮這樣一個(gè)矩陣乘法問(wèn)題：通過(guò)輸入矩陣A 和向量X 計(jì)算出矩陣B=AX。由于工作節(jié)點(diǎn)的內(nèi)存大小有限，矩陣A 按列被分成3 個(gè)大小相等的子矩陣，即A=[A1A2A3]，計(jì)算工作分別在圖1和圖2 所示的兩個(gè)分布式計(jì)算系統(tǒng)中進(jìn)行的。

圖1 所示的分布式計(jì)算系統(tǒng)由1 個(gè)主節(jié)點(diǎn)和3個(gè)工作節(jié)點(diǎn)組成，每個(gè)工作節(jié)點(diǎn)分別預(yù)先存儲(chǔ)子矩陣A1，A2，A3中的一個(gè)，且各個(gè)節(jié)點(diǎn)存儲(chǔ)的矩陣互不相同。 主節(jié)點(diǎn)將向量X 發(fā)送給每個(gè)工作節(jié)點(diǎn)，工作節(jié)點(diǎn)Wi（i=1，2，3）將本地存儲(chǔ)的矩陣與向量X 進(jìn)行乘法運(yùn)算。 主節(jié)點(diǎn)接收到3 個(gè)工作節(jié)點(diǎn)的計(jì)算結(jié)果， 可計(jì)算出B。 假設(shè)圖1 的計(jì)算系統(tǒng)中節(jié)點(diǎn)W1，W2和W3的計(jì)算任務(wù)完成時(shí)間（T） 分別為2，6 ms和10 ms，那么第一個(gè)計(jì)算系統(tǒng)T＝10 ms，機(jī)器計(jì)算總時(shí)間C＝2+6+10=18 ms。

圖1 未編碼方案示例Fig.1 Illustration of uncoded scheme

圖2 所示的分布式計(jì)算系統(tǒng)由1 個(gè)主節(jié)點(diǎn)和5個(gè)工作節(jié)點(diǎn)組成，使用（5，3）MDS 編碼將矩陣A 分成 的3 個(gè) 子 矩 陣 編 碼 為5 個(gè) 編 碼 矩 陣A1，A2，A3，A1+A2+A3，A1+2A2+3A3，并分別預(yù)先存儲(chǔ)在5 個(gè)工作節(jié)點(diǎn)W1，W2，W3，W4，W5中。主節(jié)點(diǎn)將向量X 發(fā)送給每個(gè)工作節(jié)點(diǎn)，工作節(jié)點(diǎn)Wi（i=1，2，3，4，5）將本地存儲(chǔ)的矩陣與向量X 進(jìn)行乘法運(yùn)算，并在完成計(jì)算任務(wù)后，將結(jié)果發(fā)送回主節(jié)點(diǎn)。一旦主節(jié)點(diǎn)接收到5個(gè)計(jì)算結(jié)果中的任意3 個(gè)，其他工作節(jié)點(diǎn)就會(huì)停止工作，主節(jié)點(diǎn)就可以計(jì)算出AX。 例如，當(dāng)主節(jié)點(diǎn)接收到A1X，A3X 和（A1+A2+A3）X 時(shí)，它可以通過(guò)計(jì)算（A1+A2+A3）X-A3X－A1X 得到A2X，然后計(jì)算出AX。這一編碼方案，相較于未編碼方案必須接收到全部計(jì)算結(jié)果才能完成最終計(jì)算，能容忍2 個(gè)節(jié)點(diǎn)計(jì)算速度較慢或完全失效。

圖2 編碼方案示例Fig.2 Illustration of coding scheme

假設(shè)圖2 中5 個(gè)計(jì)算節(jié)點(diǎn)的完成時(shí)間分別為2，4，6，8，10 ms， 主節(jié)點(diǎn)在接收到任意3 個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果后就立刻通知剩余的其他2 個(gè)節(jié)點(diǎn)停止計(jì)算（根據(jù)MDS 編碼性質(zhì)，任意3 個(gè)節(jié)點(diǎn)的計(jì)算已足夠得到矩陣B），所以任務(wù)完成時(shí)間T＝6 ms，機(jī)器計(jì)算總時(shí)間C＝2+4+6+6+6=24 ms。

從上述結(jié)果可以看出， 相較于未編碼方案，雖然編碼方案的任務(wù)完成時(shí)間減少了，但是機(jī)器計(jì)算總時(shí)間比未編碼方案更高。

2 模型建立

在一個(gè)由1 個(gè)主節(jié)點(diǎn)和n 個(gè)工作節(jié)點(diǎn)組成的分布式計(jì)算系統(tǒng)中， 由于每個(gè)工作節(jié)點(diǎn)內(nèi)存有限，先將總的計(jì)算任務(wù)分成若干個(gè)大小相等的子任務(wù)，然后使用編碼技術(shù)將這些子任務(wù)編碼成n 個(gè)大小相同的編碼計(jì)算任務(wù)，發(fā)送給每個(gè)工作節(jié)點(diǎn)進(jìn)行計(jì)算，主節(jié)點(diǎn)在接收到任意k 個(gè)工作節(jié)點(diǎn)的計(jì)算結(jié)果后，即可計(jì)算出最終結(jié)果。

我們通過(guò)以下兩個(gè)性能指標(biāo)評(píng)估一個(gè)編碼方案的性能：

任務(wù)完成時(shí)間（T）：從主節(jié)點(diǎn)將子任務(wù)分配給每個(gè)工作節(jié)點(diǎn)開(kāi)始，直到主節(jié)點(diǎn)接收到足夠多的工作節(jié)點(diǎn)提交的計(jì)算結(jié)果，能夠完成整個(gè)計(jì)算任務(wù)所需要的時(shí)間；

機(jī)器計(jì)算總時(shí)間（C）：整個(gè)分布式計(jì)算系統(tǒng)中所有工作節(jié)點(diǎn)對(duì)該計(jì)算任務(wù)進(jìn)行計(jì)算的時(shí)間的總和。

假設(shè)這n 個(gè)工作節(jié)點(diǎn)的計(jì)算任務(wù)完成時(shí)間分別為t1，t2， …，tn， 記Xi為這些任務(wù)完成時(shí)間中第i個(gè)最小的完成時(shí)間

由于接收到k 個(gè)工作節(jié)點(diǎn)的計(jì)算結(jié)果后，主節(jié)點(diǎn)即可計(jì)算出最終結(jié)果，任務(wù)完成時(shí)間T 為主節(jié)點(diǎn)接收到第k 個(gè)計(jì)算結(jié)果的時(shí)間，即Xk。 此時(shí)分布式計(jì)算系統(tǒng)的計(jì)算任務(wù)就已完成，主節(jié)點(diǎn)會(huì)向所有工作節(jié)點(diǎn)發(fā)送一個(gè)停止工作的信號(hào)，未完成計(jì)算任務(wù)的（n-k）個(gè)工作節(jié)點(diǎn)也在Xk時(shí)刻停止計(jì)算，機(jī)器計(jì)算總時(shí)間C 即為式（2）所示。

由于工作節(jié)點(diǎn)在進(jìn)行計(jì)算任務(wù)時(shí)可能會(huì)由于各種原因?qū)е掠?jì)算速度相較于正常節(jié)點(diǎn)更慢或是更快，使得每個(gè)工作節(jié)點(diǎn)完成計(jì)算任務(wù)的時(shí)間可能會(huì)不同，每個(gè)工作節(jié)點(diǎn)計(jì)算任務(wù)的完成時(shí)間ti（i∈{1，2，…，n}）是一個(gè)獨(dú)立同分布的連續(xù)隨機(jī)變量，具有概率分布F 和密度函數(shù)f。 為了得到Xi的分布，因Xi小于或等于x 當(dāng)且僅當(dāng)這n 個(gè)節(jié)點(diǎn)的計(jì)算時(shí)間X1，X2，…，Xn至少有i 個(gè)小于或等于x。

3 3 種編碼方案性能的對(duì)比分析

對(duì)于給定的任何一種編碼策略，本文將完成一個(gè)計(jì)算任務(wù)所需等待的最小工作節(jié)點(diǎn)數(shù)定義為該編碼策略的恢復(fù)閾值。 也就是說(shuō)，如果任何大小不小于恢復(fù)閾值的工作節(jié)點(diǎn)子集完成了它們的工作，主節(jié)點(diǎn)就能夠計(jì)算出最終結(jié)果。 在本文中，恢復(fù)閾值可以理解為：當(dāng)主節(jié)點(diǎn)接收到這n 個(gè)工作節(jié)點(diǎn)中最快的前i 個(gè)工作節(jié)點(diǎn)的計(jì)算結(jié)果后， 即可計(jì)算出最終結(jié)果。

在計(jì)算各編碼方案的任務(wù)完成時(shí)間T 和機(jī)器計(jì)算總時(shí)間C 之前，必須要說(shuō)明的是，由于編碼方案的不同，每種編碼方案中工作節(jié)點(diǎn)的計(jì)算量是不同的，因而計(jì)算時(shí)間也不相同。 這在模型中可以體現(xiàn)為，當(dāng)工作節(jié)點(diǎn)的計(jì)算時(shí)間符合均勻分布的場(chǎng)景下，各個(gè)編碼方案的區(qū)間（a，b）會(huì)有不同。 為了方便，本文將進(jìn)行一次乘法的計(jì)算量記為1，進(jìn)行加法的計(jì)算量忽略不計(jì)， 如一個(gè)1×n 的向量與一個(gè)n×1的向量相乘的計(jì)算量為n， 而一個(gè)n×1 的向量與一個(gè)1×n 的向量相乘的計(jì)算量為n2。

為了更好的對(duì)比各個(gè)編碼方案任務(wù)完成時(shí)間T和機(jī)器計(jì)算總時(shí)間C， 還需要給這些編碼方案構(gòu)造一個(gè)相同的計(jì)算場(chǎng)景，目標(biāo)都是通過(guò)輸入矩陣A 和B 計(jì)算出H=ATB，如圖3 所示。矩陣A 的維度為Z×X，矩陣B 的維度為Z×Y，計(jì)算任務(wù)是在擁有1 個(gè)主節(jié)點(diǎn)和N 個(gè)工作節(jié)點(diǎn)的分布式系統(tǒng)中進(jìn)行。 其中，兩個(gè)輸入矩陣分別被（任意）劃分為p×m 和p×n 個(gè)子矩陣塊，每一個(gè)輸入矩陣劃分的子矩陣大小是相同的，且每個(gè)工作節(jié)點(diǎn)只能在本地存儲(chǔ)2 個(gè)子矩陣。 另外，每個(gè)編碼方案的p，m，n 的取值是不同的。

圖3 矩陣乘法問(wèn)題示例Fig.3 Example of matrix multiplication problem

目前最常用于矩陣乘法的編碼方案為： 一維MDS 編碼、乘積編碼、多項(xiàng)式編碼。本文將對(duì)這3 種編碼方案進(jìn)行介紹以及實(shí)驗(yàn)對(duì)比其性能。

3.1 一維MDS 編碼方案

一維MDS 編碼方案是Lee 等[21]對(duì)文獻(xiàn)[22]的編碼思想進(jìn)行擴(kuò)展得出的， 將MDS 碼在一個(gè)輸入矩陣中加入冗余數(shù)據(jù)這種方法稱為一維MDS 碼（1D MDS 碼）。 該編碼方案的思想是:將大矩陣乘法的問(wèn)題看作n 個(gè)小矩陣乘法的問(wèn)題，即ATB=［ATb1ATb2… ATbn］， 然后對(duì)n 個(gè)小矩陣中的每一個(gè)分別應(yīng)用MDS 編碼矩陣乘法。假設(shè)N=nk，工作節(jié)點(diǎn)被分成大小為k 的n 個(gè)組，每個(gè)組都專門(mén)計(jì)算一個(gè)ATbj。例如對(duì)于第一個(gè)組，它用于計(jì)算ATb1，該方案首先使用（k，m）MDS 編碼對(duì)矩陣A 的沿列分成的m 個(gè)大小相同的子矩陣進(jìn)行編碼， 以獲得k 個(gè)編碼矩陣，比如a1到ak，然后將aiTb1的計(jì)算分配給這組的第i 個(gè)工作節(jié)點(diǎn)，以此類推。 MDS 編碼計(jì)算的計(jì)算時(shí)間由n 個(gè)組的計(jì)算時(shí)間中的最大值決定， 每個(gè)組的計(jì)算時(shí)間由組中k 個(gè)工作節(jié)點(diǎn)中第m 個(gè)完成計(jì)算任務(wù)的工作節(jié)點(diǎn)決定。

圖4 所 示 為N=3，m=2，n=1，p=1 時(shí) 的1D MDS 編碼方案示例， 主節(jié)點(diǎn)接收到3 個(gè)工作節(jié)點(diǎn)中的任意2 個(gè)返回的計(jì)算結(jié)果后， 即可計(jì)算出矩陣H。

圖4 3 工作節(jié)點(diǎn)的1D MDS 碼示例Fig.4 Illustration of 1D MDS code with 3 work nodes

3.2 乘積碼編碼方案

圖5 9 工作節(jié)點(diǎn)的乘積碼示例Fig.5 Illustration of product code with 9 work nodes

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

多項(xiàng)式碼編碼方案是Yu 等[23]提出的一種編碼計(jì)算策略，利用編碼理論的思想來(lái)設(shè)計(jì)工作節(jié)點(diǎn)上的中間計(jì)算，以實(shí)現(xiàn)對(duì)掉隊(duì)節(jié)點(diǎn)的容忍。 該方案首先沿著列將2 個(gè)輸入矩陣分別平均分成m 和n 個(gè)大小相等的子矩陣

然后給每個(gè)工作節(jié)點(diǎn)i（i∈{0，1，…，N-1}）分配一個(gè)數(shù)字xi，同時(shí)使得所有的xi都互不相同，在工作節(jié)點(diǎn)i 本地存儲(chǔ)以下2 個(gè)編碼子矩陣

由于所設(shè)計(jì)的計(jì)算策略具有特殊的代數(shù)結(jié)構(gòu)，解碼過(guò)程可以看作是一個(gè)多項(xiàng)式插值問(wèn)題(或是一個(gè)解碼Reed-Solomon 碼的問(wèn)題)，可有效求解。這種多項(xiàng)式編碼的主要?jiǎng)?chuàng)新之處和優(yōu)點(diǎn)在于，通過(guò)精心設(shè)計(jì)編碼子矩陣的代數(shù)結(jié)構(gòu)，可以確保工作節(jié)點(diǎn)上的任何mn 個(gè)中間計(jì)算都足以在主節(jié)點(diǎn)上恢復(fù)矩陣乘法的最終乘積。 從某種意義上來(lái)說(shuō)，這是在中間計(jì)算中創(chuàng)建了一個(gè)MDS 結(jié)構(gòu)， 而不是像以前的工作那樣僅僅是對(duì)矩陣進(jìn)行編碼。

圖6 所示為N=5，m=2，n=2，p=1 時(shí)的多項(xiàng)式碼編碼方案示例，主節(jié)點(diǎn)接收到5 個(gè)工作節(jié)點(diǎn)中的任意4 個(gè)返回的計(jì)算結(jié)果后，即可計(jì)算出矩陣H。

圖6 5 工作節(jié)點(diǎn)的多項(xiàng)式碼示例Fig.6 Illustration of polynomial code with 5 work nodes

另外，在多項(xiàng)式編碼的基礎(chǔ)上，Yu 等[24]提出了糾纏多項(xiàng)式編碼方案， 實(shí)現(xiàn)了pmn+p-1 的恢復(fù)閾值；Dutta 等[25]提出了MatDot 編碼方案，實(shí)現(xiàn)了2m-1 的恢復(fù)閾值。 由于這幾種方案都是通過(guò)設(shè)計(jì)編碼子矩陣的代數(shù)結(jié)構(gòu)實(shí)現(xiàn)對(duì)掉隊(duì)節(jié)點(diǎn)的容忍，本文僅將多項(xiàng)式編碼方案與其他編碼方案進(jìn)行對(duì)比分析。

4 實(shí)驗(yàn)及結(jié)果

為了更加直觀的比較各個(gè)編碼方案的任務(wù)完成時(shí)間T 和機(jī)器計(jì)算總時(shí)間C，我們通過(guò)實(shí)驗(yàn)對(duì)3種編碼方案的性能指標(biāo)進(jìn)行了測(cè)試。

本文使用Python 語(yǔ)言實(shí)現(xiàn)了3 種編碼方案的編碼計(jì)算過(guò)程。 當(dāng)編碼參數(shù)設(shè)置為a=1，b=9，X=Y=Z=4，N=16 時(shí)， 本文分別對(duì)未編碼方案和3 種編碼方案的任務(wù)完成時(shí)間T 和機(jī)器計(jì)算總時(shí)間C 進(jìn)行了數(shù)值上的測(cè)量，實(shí)驗(yàn)結(jié)果如表1 所示。

表1 未編碼方案和3 種編碼方案的對(duì)比Tab.1 Comparison between uncoded scheme and three coding schemes

從表中結(jié)果可以看出，編碼方案與未編碼方案相比：編碼方案的任務(wù)完成時(shí)間普遍要短，這是因?yàn)槊糠N編碼方案只需等待達(dá)到其恢復(fù)閾值的工作節(jié)點(diǎn)子集完成計(jì)算任務(wù)即可得到最終結(jié)果，而不必等待所有節(jié)點(diǎn)完成計(jì)算任務(wù)；但是編碼方案的機(jī)器計(jì)算總時(shí)間普遍更長(zhǎng)， 這是因?yàn)橄噍^于未編碼方案，編碼方案使用了更多的工作節(jié)點(diǎn)來(lái)完成計(jì)算任務(wù)。 將3 種編碼方案進(jìn)行對(duì)比：乘積碼的任務(wù)完成時(shí)間和機(jī)器計(jì)算總時(shí)間相較于1D MDS 編碼方案都要短，這是由于乘積碼的恢復(fù)閾值更低；多項(xiàng)式碼在3 種編碼方案中，任務(wù)完成時(shí)間和機(jī)器計(jì)算總時(shí)間的表現(xiàn)都是最優(yōu)，這是因?yàn)樵诮o定其他參數(shù)情況下3 種編碼方案p，m，n 的取值都相同時(shí)，多項(xiàng)式碼的恢復(fù)閾值遠(yuǎn)小于另外兩種編碼方案，但是該方案額外增加了主節(jié)點(diǎn)的編解碼，是以增加主節(jié)點(diǎn)的計(jì)算時(shí)間為代價(jià)的。

4.1 編碼方案的參數(shù)選擇

選定一個(gè)合適的編碼方案之后，比如某用戶準(zhǔn)備使用多項(xiàng)式編碼計(jì)算方案對(duì)2 個(gè)大小為100×100的矩陣進(jìn)行乘法計(jì)算，若該用戶選擇將兩個(gè)輸入矩陣分別劃分為4 個(gè)大小相同的子矩陣， 即m=n=4，假設(shè)該用戶選擇在20 個(gè)工作節(jié)點(diǎn)上執(zhí)行計(jì)算任務(wù)，且在該用戶選擇的工作節(jié)點(diǎn)的工作環(huán)境下a=1，b=9，那么此時(shí)任務(wù)完成時(shí)間T=443 252 ms，機(jī)器計(jì)算總時(shí)間C=4 824 405 ms。 若是該用戶選擇將兩個(gè)輸入矩陣分別劃分為4 個(gè)大小相同的子矩陣，即m=n=5，假設(shè)該用戶選擇在29 個(gè)工作節(jié)點(diǎn)上執(zhí)行計(jì)算任務(wù)，且在該用戶選擇的工作節(jié)點(diǎn)的工作環(huán)境下a=1，b=9 ， 那么此時(shí)任務(wù)完成時(shí)間T=306 667 ms，機(jī)器計(jì)算總時(shí)間C=4 573 333 ms。 從上述例子中可以看出，不同的參數(shù)選擇會(huì)導(dǎo)致機(jī)器計(jì)算總時(shí)間C，即資源消耗的不同。 那么我們又面臨著這樣一個(gè)新的問(wèn)題：如何選擇編碼方案的參數(shù)，使得用于編碼計(jì)算任務(wù)的資源消耗最少。

將這一問(wèn)題使用數(shù)學(xué)語(yǔ)言可以描述為: 在給定工作節(jié)點(diǎn)數(shù)量N 和任務(wù)完成時(shí)間T 的限制時(shí)，如何選擇m，n，N 和其他參數(shù)的值， 使得機(jī)器計(jì)算總時(shí)間C 最小。

要研究選擇m，n，N 和其他參數(shù)的值， 使得機(jī)器計(jì)算總時(shí)間C 最小，我們首先要了解機(jī)器計(jì)算總時(shí)間C 與這些參數(shù)之間有什么關(guān)系，即參數(shù)變化時(shí)C 的變化趨勢(shì)。 另外，由于對(duì)工作節(jié)點(diǎn)數(shù)量N 和任務(wù)完成時(shí)間T 的限制可以理解為給定了N 和T 的上限，并不代表著所給工作節(jié)點(diǎn)數(shù)量N 和任務(wù)完成時(shí)間T 的值就是最終結(jié)果，我們還需要對(duì)工作節(jié)點(diǎn)數(shù)量N 和任務(wù)完成時(shí)間T 進(jìn)行研究，分析這兩個(gè)參數(shù)之間、兩個(gè)參數(shù)與機(jī)器計(jì)算總時(shí)間C 之間以及兩個(gè)參數(shù)與其他參數(shù)之間的關(guān)系。

我們首先對(duì)前文求出的3 種編碼方案的任務(wù)完成時(shí)間T 和機(jī)器計(jì)算總時(shí)間C 的表達(dá)式進(jìn)行研究。 從3 種編碼方案性能指標(biāo)的表達(dá)式中，可以很明顯地觀察到，當(dāng)其他參數(shù)保持不變時(shí)，增加Z，X，Y 的值，T 和C 都會(huì)隨之增加；增加mn 的值，T 和C都會(huì)隨之減小。 但是當(dāng)N 增加時(shí)，T 和C 的值不容易判斷，本文又對(duì)工作節(jié)點(diǎn)數(shù)N 變化的情況下3 種編碼方案的T 和C 的變化情況進(jìn)行了實(shí)驗(yàn)分析。在其他參數(shù)分別設(shè)置為a=1，b=9，X=Y=Z=100，m=n=5，p=1 時(shí)，計(jì)算出N 分別取值為30，35，40，45，50，55，60，65，70，80，90，100，120，160，200，240，280，320，360 時(shí)各編碼方案的T 和C 的值，如圖7 所示。

圖7 3 種編碼方案在不同N 取值下的T 和C 變化情況Fig.7 Changes of T and C in three coding schemes with different values of N

從圖7 中可以看出， 隨著工作節(jié)點(diǎn)數(shù)N 的增加，3 種編碼方案的機(jī)器計(jì)算總時(shí)間C 都在不斷增加，而任務(wù)完成時(shí)間T 都在不斷減小，這說(shuō)明增加更多的冗余工作節(jié)點(diǎn)，能更快的完成計(jì)算任務(wù)，但是計(jì)算任務(wù)成本開(kāi)銷也會(huì)相應(yīng)地增加。 另外，從圖中還可以看出，在C 增加到一定程度后， T 的減小會(huì)變得緩慢， 這說(shuō)明增加的冗余達(dá)到一定程度之后， 再繼續(xù)增加冗余， 成本開(kāi)銷依然會(huì)繼續(xù)增加， 但是任務(wù)完成時(shí)間卻減少的很慢甚至不再減少，此時(shí)收益很低。

當(dāng)輸入矩陣A 和B 劃分成的子矩陣數(shù)量不同，即參數(shù)m，n 不同時(shí)，我們通過(guò)實(shí)驗(yàn)對(duì)編碼方案的任務(wù)完成時(shí)間T 和機(jī)器計(jì)算總時(shí)間C 進(jìn)行了研究。 以多項(xiàng)式碼編碼方案為例，當(dāng)a=1，b=9，X=Y=Z=4 時(shí)，本文分別給出了m，n 取值不同的情況下T 和C 的變化情況，研究結(jié)果如圖8 和圖9 所示。

圖8 m 和n 值不同時(shí)多項(xiàng)式編碼框架的T 的變化情況Fig.8 Changes of T for polynomial code scheme with different values of m and n

圖9 m 和n 值不同時(shí)多項(xiàng)式編碼框架的C 的變化情況Fig.9 Changes of C for polynomial code scheme with different values of m and n

可以看出，當(dāng)m 和n 的取值越大時(shí)，編碼子矩陣就越復(fù)雜，生成編碼子矩陣以及對(duì)編碼子矩陣進(jìn)行編解碼所需要的時(shí)間也就越長(zhǎng)。 m 和n 的取值越大并不能使進(jìn)行編碼計(jì)算任務(wù)花費(fèi)的全部時(shí)間越短。

從圖9 可以看出，當(dāng)給定N 時(shí)，選擇m×n 較大的輸入矩陣劃分方案，可以得到較小的C。這是因?yàn)楫?dāng)工作節(jié)點(diǎn)的總數(shù)量保持不變時(shí)，每個(gè)工作節(jié)點(diǎn)的工作時(shí)間減少， 機(jī)器計(jì)算總時(shí)間自然也就隨之減少。 此外，當(dāng)工作節(jié)點(diǎn)數(shù)量N 與多項(xiàng)式碼的恢復(fù)閾值mn 相等時(shí)， 也就是說(shuō)在分布式計(jì)算系統(tǒng)中沒(méi)有冗余存在，此時(shí)無(wú)論N 的取值如何變化，多項(xiàng)式編碼方案的機(jī)器計(jì)算總時(shí)間C 總是相等的，這是由C的計(jì)算表達(dá)式?jīng)Q定的，這也是多項(xiàng)式編碼方案的機(jī)器計(jì)算總時(shí)間C 如圖7 變化的原因。

4.2 參數(shù)的啟發(fā)式算法

在對(duì)4.1 節(jié)實(shí)驗(yàn)結(jié)果進(jìn)行分析的基礎(chǔ)上， 本文給出了在給定T 和N 的上限時(shí)， 如何選取m，n，T的值來(lái)最小化機(jī)器計(jì)算總時(shí)間C 的啟發(fā)式算法，算法過(guò)程如下所示：

輸入：矩陣維度X，Y，Z，計(jì)算節(jié)點(diǎn)完成最快時(shí)間a，最慢時(shí)間b，給定T 和N 的上限；

輸出：計(jì)算總時(shí)間C 的預(yù)測(cè)值，及最小化C 的參數(shù)m，n 的取值，任務(wù)完成時(shí)間T 和工作節(jié)點(diǎn)數(shù)量N；

1） 根據(jù)輸入矩陣大小求出所有可用的矩陣劃分方案m 和n 的可能值；

2） 根據(jù)用戶所給的任務(wù)完成時(shí)間T 的限制選擇合適的m 和n 的取值；

3） 根據(jù)工作節(jié)點(diǎn)數(shù)量N 的上限判斷在給定T和上限內(nèi)是否能完成計(jì)算工作；

4） 若能則給出使得機(jī)器計(jì)算總時(shí)間C 最小的各項(xiàng)參數(shù)的取值。

在算法中輸入給定的任務(wù)完成時(shí)間T 和工作節(jié)點(diǎn)數(shù)量N 的上限以及需要進(jìn)行乘法計(jì)算的矩陣大小， 然后算法會(huì)輸出可以使得機(jī)器計(jì)算總時(shí)間C最小化的參數(shù)m，n 的取值，任務(wù)完成時(shí)間T 和工作節(jié)點(diǎn)數(shù)量N 的預(yù)測(cè)值以及機(jī)器計(jì)算總時(shí)間C 的預(yù)測(cè)值。

當(dāng)算法輸入為a=1，b=9，X=Y=Z=100，N=46，T=200 000 ms 時(shí)，輸出為m=2，n=20 或m=4，n=10 或m=10，n=4 或m=20，n=2，T=195 212.8 ms，C=5 660 638.3 ms。

在mn 不同取值下C 的取值如表2 所示， 可以看出算法結(jié)果的確可以輸出使得機(jī)器計(jì)算總時(shí)間C最小化的參數(shù)m，n 的取值。

表2 在mn 不同取值下C 的值Tab.2 C with different values of m×n

5 結(jié)論

1） 本文對(duì)基于分布式機(jī)器學(xué)習(xí)的編碼方案的性能開(kāi)銷進(jìn)行了研究和分析，計(jì)算出了n 個(gè)工作節(jié)點(diǎn)中第i 個(gè)完成計(jì)算任務(wù)的節(jié)點(diǎn)的密度函數(shù)，并給出了工作節(jié)點(diǎn)計(jì)算任務(wù)完成時(shí)間符合均勻分布場(chǎng)景下計(jì)算任務(wù)的任務(wù)完成時(shí)間C 和機(jī)器計(jì)算總時(shí)間T 的表達(dá)式。

2） 分析對(duì)比了3 個(gè)應(yīng)用于矩陣乘法的編碼方案與未編碼方案的任務(wù)完成時(shí)間和機(jī)器計(jì)算總時(shí)間，提供了計(jì)算方案選擇的依據(jù)。 并且在此基礎(chǔ)上，通過(guò)Python 實(shí)驗(yàn)了指數(shù)分布情況下的編碼方案并實(shí)驗(yàn)得出了其任務(wù)完成時(shí)間C 和機(jī)器計(jì)算總時(shí)間T，還在此基礎(chǔ)上進(jìn)行實(shí)驗(yàn)，對(duì)3 種編碼方案進(jìn)行比較。

3） 在此基礎(chǔ)上還對(duì)參數(shù)選擇進(jìn)行分析， 提出一個(gè)啟發(fā)式算法為參數(shù)的選擇提供參考。