趙永柱，黎衛(wèi)東，唐 斌，梅 峰，盧文達

（1.國網(wǎng)陜西省電力公司信息通信公司，西安710065；2.計算機軟件新技術國家重點實驗室（南京大學），南京210023；3.國網(wǎng)浙江省電力有限公司，杭州310007）

0 引言

隨著互聯(lián)網(wǎng)、云計算、物聯(lián)網(wǎng)的迅猛發(fā)展，無處不在的移動設備、傳感器持續(xù)產(chǎn)生數(shù)據(jù)，數(shù)以億計用戶的互聯(lián)網(wǎng)服務時時刻刻產(chǎn)生巨量的交互，使得數(shù)據(jù)呈現(xiàn)出爆炸式增長趨勢。大規(guī)模的數(shù)據(jù)資源為大規(guī)模的機器學習和數(shù)據(jù)挖掘應用提供了物質(zhì)基礎，因此近年來涌現(xiàn)了很多大規(guī)模的機器學習模型。這些模型在語音處理、圖像處理、自然語言處理、人機對弈等領域表現(xiàn)出非凡的問題處理能力；但是大規(guī)模機器學習的訓練對計算能力和存儲容量都提出了較高的要求，單機訓練和存儲開銷太高，利用分布式計算技術來完成訓練任務已成常態(tài)。

矩陣-向量相乘，簡稱矩陣相乘，即計算y=Ax（其中，A為矩陣，x 為向量），是很多數(shù)值計算、機器學習算法中的核心計算，比如求解偏微分方程［1］、神經(jīng)網(wǎng)絡的前向后向推進［2］、計算PageRank［3］等。通過多臺機器來分布式計算矩陣相乘時，通常將矩陣A 進行分割后分配到系統(tǒng)中的各個工作節(jié)點（worker node），每個節(jié)點將子矩陣與x進行相乘后將結果交回給主節(jié)點（master node），由主節(jié)點整合出最終的計算結果。在這種方式下，主節(jié)點需要等到所有工作節(jié)點均返回計算結果后方可完成整體計算任務。

然而，大規(guī)模分布式系統(tǒng)由于資源競爭、負載均衡、網(wǎng)絡變化等諸多原因，工作節(jié)點在執(zhí)行計算任務時，其完成時間經(jīng)常難以預測且表現(xiàn)出較大波動，從而會有部分計算節(jié)點計算嚴重滯緩，其計算完成時間能超出平均水平5～10 倍，從而嚴重拖累整體計算。這樣的節(jié)點通常被稱為落后節(jié)點（straggler），產(chǎn)生的問題被稱為落后者問題［4-5］。

近年來，研究者提出采用編碼的方法能夠有效應對上述落后者問題。Lee 等首先提出基于MDS（Maximum Distance Separable）碼的編碼方案［6-7］，即將矩陣劃分成k 份，并應用碼率為k/n的MDS碼，將其編碼成n份（n為工作節(jié)點個數(shù)），每個工作節(jié)點存儲其中一份并完成計算。這種方法可以容忍nk 個落后節(jié)點。這種方法將落后節(jié)點等價于傳統(tǒng)通信中的擦除（erasure），無法利用落后節(jié)點上的部分計算結果，從而導致性能欠佳。為了能夠利用落后節(jié)點，研究者從不同的角度提出了一些可行方案［7-10］。其中，Mallick 等提出了基于噴泉碼的編碼方案［10-12］，利用噴泉碼的無碼率特性，可以將k 份子矩陣編碼成任意多的編碼子矩陣，并將這些編碼子矩陣預先存儲到工作節(jié)點上去，而工作節(jié)點則可以逐步計算并返回每個編碼子矩陣與向量x 相乘的結果；與此同時，主節(jié)點只需要接收到的部分計算結果數(shù)略多于k 即可恢復出完整計算結果。與其他方法相比，這種基于噴泉碼的方式能夠充分利用每個工作節(jié)點的計算能力，且具有線性的編譯碼復雜度。

Mallick 等的工作假設每個工作節(jié)點存儲的分片數(shù)充分多，從而保障在整體計算完成前，每個工作節(jié)點均持續(xù)進行計算［10］，但這種方式將消耗過多的存儲資源，從而導致計算成本過高。譬如，用戶以租用云計算平臺的方式進行分布式計算，成本開銷與存儲開銷密切相關。另一方面，如果工作節(jié)點存儲的編碼子矩陣數(shù)目過小，則可能導致工作節(jié)點因過早完成分配給它的計算任務而處于空閑狀態(tài)，從而延長整體計算完成時間。因此，存儲開銷與整體計算完成時間存在一定的權衡關系。

基于上述分析，本文首先對如何在保障給定期限內(nèi)大概率完成計算任務的前提下優(yōu)化工作節(jié)點的存儲開銷問題進行了建模。該問題求解面臨的難點有兩方面：一是工作節(jié)點的耗時具有隨機性；二是工作節(jié)點的異構性，即其耗時相關的參數(shù)不同。通過理論分析發(fā)現(xiàn)，在通常情況下，一定時間內(nèi)主節(jié)點接收到的計算結果個數(shù)以較大概率集中在其期望值左右，從而提出了基于期望近似的解決思路，將原問題約束條件進行了轉(zhuǎn)化。由于轉(zhuǎn)化后的問題仍是整數(shù)規(guī)劃問題，進一步地考慮了松弛，并證明松弛后的優(yōu)化問題為凸優(yōu)化問題，從而可以高效求解，并將其最優(yōu)解通過簡單的取整轉(zhuǎn)化為未松弛問題的可行解。仿真實驗結果表明，所提方法能夠在保障整體計算在期限內(nèi)大概率完成的前提下，大幅度降低總體的額外存儲開銷。

1 問題建模

1.1 系統(tǒng)模型

考慮在一典型分布式計算環(huán)境中計算y=Ax，其中，A ∈?r×m是大小為r×m 的矩陣，x ∈?m為m 維的向量。該計算環(huán)境由一個主節(jié)點（master node）及n 個工作節(jié)點構成?？紤]采用噴泉碼的方法有效應對落后者問題。具體而言，如圖1 所示，首先將矩陣A 按行分割成k 個大小相同的子矩陣(a1，a2，???，ak)（如果r 不能被k 整除，可以通過補0 完成），每個子矩陣包含r/k 行，并利用噴泉碼（如LT 碼［13］、Raptor 碼［14］）對這k 個子矩陣進行編碼，可以生成一系列（數(shù)量可以無窮多）的編碼子矩陣，其大小與這k個子矩陣保持一致。

圖1 矩陣預編碼和部署Fig.1 Matrix pre-coding and allocation

令ci為第i個工作節(jié)點放置的編碼子矩陣個數(shù)，并記這些編碼子矩陣為，則第i 個工作節(jié)點按序計算，每算完一個就將結果發(fā)送給主節(jié)點。當主節(jié)點從所有工作節(jié)點處接收到(1+ε)k 個這樣的結果時，可以通過噴泉碼的Peeling 算法［10］進行解碼，從而能夠以非常接近1 的概率恢復出(a1x，a2x，…，akx)，其中ε ＞0 是一個非常小的常數(shù)，稱之為解碼條件。整個工作流程如圖2所示。

圖2 編碼矩陣相乘的流程Fig.2 Flowchart of coded matrix multiplication

1.2 耗時模型

為刻畫任務完成時間，本文采用與文獻［10］相同的耗時模型。每個工作節(jié)點i 的耗時包含兩部分：一是啟動時延Xi，它服從參數(shù)為μi的指數(shù)分布，即Xi～exp(μi)；二是每計算并返回一個結果給主節(jié)點所需要的時間為常數(shù)τi。因此，工作節(jié)點返回Ri個計算結果所花費的時間為：

其中Ri＜ci。此外，Xi之間是獨立的。本文考慮了工作節(jié)點之間的異構性，即對于不同的i，μi和τi的取值可能不同，如圖3所示。

圖3 耗時模型與任務執(zhí)行示意圖Fig.3 Schematic diagram of time consumption model and task execution

1.3 期限感知的存儲優(yōu)化

考慮上述計算任務存在期限t*，即上述計算任務能夠以較大概率在t*時間內(nèi)完成。一種方式是每個工作節(jié)點上放置充分多的編碼子矩陣，保證每個工作節(jié)點在t*時間內(nèi)均保持計算狀態(tài)，這能使得計算完成時間最短；但這種方法帶來的存儲開銷將非常大。另一方面，如果在工作節(jié)點上部署過少的編碼子矩陣，則可能導致工作節(jié)點過早進入閑置狀態(tài)，從而延長計算完成時間?；谏鲜隹紤]，本文提出期限感知的存儲優(yōu)化問題，致力于優(yōu)化工作節(jié)點的存儲開銷，同時保障計算能以較大概率在期限t*內(nèi)完成。

令Ri(t*)表示工作節(jié)點Wi在t*時刻返回的計算結果數(shù)，它取決于啟動時延Xi，同時受限于編碼子矩陣的存儲個數(shù)ci，因此為取值不超過ci的隨機變量。因此，根據(jù)解碼條件，計算任務能在期限t*完成的充分必要條件為：

基于此，本文將期限感知的存儲優(yōu)化問題（記為問題P）建模成：

ci＞0，ci為整數(shù)

其中，限制條件表示計算任務在t*時間內(nèi)無法完成的概率不超過O(1/n)，即是1/n的無窮小量。

2 存儲優(yōu)化方案

為方便求解，首先引入如下一些自然的假設：

1）異構性受限假設：存在某常數(shù)C，使得對于任意的i和j均有，即不同工作節(jié)點的計算速度之間的比例受限。

基于上述假設可以發(fā)現(xiàn)，存在常數(shù)C'使得對于充分大的k，

此外，由于Ri(t*)之間是相互獨立的，因此，可以應用Heoffding不等式［15］得到：

其中，函數(shù)F(t)=1-eμit為Xi的分布函數(shù)。根據(jù)期望的線性性質(zhì)，有

至此，可以將期限感知的存儲優(yōu)化問題轉(zhuǎn)化為如下優(yōu)化問題（記為問題P2）：

ci＞0，ci為整數(shù)

由于上式是整數(shù)規(guī)劃問題，難以直接求解。對ci為整數(shù)的條件進行松弛，即考慮ci為非負實數(shù)的情形（記為問題P3）：

需要補充說明的是，在小規(guī)模分布式計算環(huán)境中，當n 較小，且ε′取值較小時，基于Heoffding 不等式建立的計算失敗概率上限可能會較大。因此在實際應用時，可以通過增加P3的限制條件中ε″的取值去降低計算失敗的概率。

3 仿真驗證

對于本文提出的存儲優(yōu)化方案，將從兩個角度來分析驗證：一方面，本文存儲方案是期限感知的，所以希望知道隨著任務期限放寬，在保證任務完成概率的前提下，本文方案存儲開銷的變化情況；另一方面，與其他方案進行對比，以驗證本文方案在存儲優(yōu)化方面的效果。

3.1 仿真環(huán)境

仿真實驗在Matlab R2018b工具平臺中進行，凸優(yōu)化求解工具是CVX工具包下的SDPT3求解器。仿真實驗中，有20個工作節(jié)點和1 個主節(jié)點。工作節(jié)點的參數(shù)，如任務的單位處理時間τi和異構與啟動時延參數(shù)μi，通過均勻分布采樣隨機生成，并滿足1.2 節(jié)中的假設。其中τi從［0.1，1］中隨機生成，μi從［0.012 5，0.125］中隨機生成。這些設定構成仿真實驗的拓撲信息，在一組實驗過程中不會發(fā)生改變。此外，假設數(shù)據(jù)矩陣被分成1 000份，即k取值為1 000。

3.2 存儲開銷變化趨勢

根據(jù)系統(tǒng)的拓撲信息，給定一個任務完成期限，同時設定一個存儲閾值ε″，就可以通過所提方法求得一個存儲分配方案，并依據(jù)這個方案分配計算任務。計算任務分配成功后，便能進行大量的仿真測試，可以求得本文方案的任務完成成功率。與此同時，可以仿真測得在每個節(jié)點上存儲無限量的計算任務假設下任務完成的概率，作為任務成功率的上限。可以調(diào)節(jié)存儲閾值ε″，使得本文的存儲方案成功率接近任務成功率上限，此時獲得的存儲方就是最終的優(yōu)化方案。隨機生成兩組不同的系統(tǒng)參數(shù)，針對一組不同的任務期限，每個任務期進行104次仿真測試，統(tǒng)計其任務成功率，以及優(yōu)化方案的存儲開銷（用存儲的子矩陣數(shù)目表示）。

在兩組隨機生成的環(huán)境下進行了實驗，實驗結果如圖4?？梢钥闯?，在保證較大任務成功率（接近任務成功率上限，即每個工作節(jié)點均存放充分多的編碼子矩陣）的前提下，隨著任務期限的逐漸放寬，所提方案引入的存儲開銷在迅速下降，并逐漸趨向于原始子矩陣個數(shù)。根據(jù)存儲開銷的變化趨勢，結合實際情形，本文的存儲優(yōu)化方案都可以有較好的收益：對于對任務完成時間要求高的場景，本文方案可以以不超過原始數(shù)據(jù)2 倍存儲的開銷，就達到和無限存儲接近的任務完成時間和成功率；面對對任務時間要求不高的場景，本文方案只引入了輸入矩陣數(shù)據(jù)量0.2～0.3 倍的額外存儲開銷，即可以大概率保證計算任務成功完成。同時，對比圖4（a）和（b）可以發(fā)現(xiàn)，對于不同的系統(tǒng)配置，本文方案的存儲開銷變化趨勢都是一致的。

圖4 任務完全期限延長下存儲開銷變化趨勢Fig.4 Trend of storage overhead with deadline increasing

3.3 對比實驗

該部分實驗中，選取了另外兩種預先放置策略，并在給定任務期限前提下，比較三種方案的存儲開銷變化對任務完成概率的影響。三種方案只在每個節(jié)點預先存儲子矩陣數(shù)目方面有所不同，其他方面則保持一致，即均是采用無碼率的噴泉碼編碼，逐步返回計算內(nèi)容。另外兩種對比方案如下：

1）均勻放置方案：每個工作節(jié)點放置等量的計算任務。這種方案忽視了工作節(jié)點之間的異構性。

2）比例放置方案：按照參數(shù)τi即處理速度來按比例分配總的存儲開銷。這種方案只考慮了不同工作節(jié)點計算速度上面的區(qū)別，并未考慮啟動時延方面的區(qū)別。

在一組隨機生成的環(huán)境下進行了實驗，并考慮兩個不同的任務期限100 及80。對于不同的存儲開銷，每個方案均仿真104次求得任務成功的概率，實驗結果如圖5 所示。從圖5中可以看到，隨著存儲開銷的變大，三種方案的任務完成概率均是逐步上升的，其中所提存儲優(yōu)化方案任務完成概率上升速度最快，而比例放置策略則優(yōu)于均勻放置策略。當任務大概率成功，比如概率取0.9 或者0.95 時，如圖5 所示，本文方案帶來的冗余存儲只有按比例放置方案的一半左右。此外，通過對比圖5（a）和（b）可以發(fā)現(xiàn)，在任務完成期限較小時，本文存儲優(yōu)化方案與對比方案相比，性能優(yōu)勢更為明顯。

圖5 三種存儲方案下存儲開銷與任務完成概率對比Fig.5 Storage overheads and task success rates of three storage schemes

4 結語

在考慮存儲開銷與計算完成時間之間的權衡關系的基礎上，本文對面向異構工作節(jié)點的計算期限感知的存儲優(yōu)化問題進行了建模，并基于理論分析，提出了基于期望近似的解決思路，進而通過松弛將問題轉(zhuǎn)化為凸優(yōu)化問題進行高效求解。仿真實驗結果表明，本文存儲方案與其他方案相比，能夠大幅度降低編碼帶來的額外存儲負載。由于很多實際應用中數(shù)據(jù)被建模成稀疏矩陣，因此未來還將進一步探討面向稀疏矩陣-向量相乘的高效存儲方法。