[發(fā)明專利]一種編碼分布式計算系統(tǒng)

在審

• 申請?zhí)枺?/td>: 202110873853.6
• 申請日: 2021-07-30
• 公開（公告）號: CN113836482A
• 公開（公告）日: 2021-12-24
• 發(fā)明（設(shè)計）人: 童艷荔;代明軍;王蘭
• 申請（專利權(quán)）人: 深圳大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 深圳市科吉華烽知識產(chǎn)權(quán)事務所(普通合伙) 44248
• 代理人: 胡吉科

本發(fā)明提供了一種編碼分布式計算系統(tǒng)，將類牛頓多項式碼應用于編碼分布式計算系統(tǒng)中，在計算機集群中，其中一個計算機充當主節(jié)點，其他計算機充當工作節(jié)點，在所述計算機集群中分布式地計算矩陣AB相乘，主節(jié)點把矩陣A和矩陣B分成K塊，然后執(zhí)行編碼策略，分別對矩陣A和矩陣B編碼，當主節(jié)點接收到計算速度最快的K個工作節(jié)點的計算結(jié)果后就能解碼AB。本發(fā)明的有益效果是：本發(fā)明具有較低的條件數(shù)，有效改善矩陣相乘中范德蒙矩陣解碼數(shù)值不穩(wěn)定問題，提高解碼的準確度，并且具有容錯、改善落后節(jié)點功能。

技術(shù)領(lǐng)域

本發(fā)明涉及分布式系統(tǒng)技術(shù)領(lǐng)域，尤其涉及一種編碼分布式計算系統(tǒng)。

背景技術(shù)

分布式計算是現(xiàn)代機器學習和數(shù)據(jù)分析的核心，在這些數(shù)據(jù)中，有數(shù)百萬個維度非常高的數(shù)據(jù)點正在被處理。掉隊節(jié)點的問題天然的存在于一個分布式系統(tǒng)之中，掉隊節(jié)點指的是那些因為它們的計算能力或者通信鏈路較差，而導致它們返回計算結(jié)果極大的慢于平均水平的工作節(jié)點。在“編碼計算”領(lǐng)域的許多研究都著眼于將冗余整合到分布式計算中，基于編碼啟發(fā)的策略來應對這些挑戰(zhàn)。分布式系統(tǒng)的核心思想是通過編碼來獲得(n,k)組合特性(Combination Property,CP)，即將k個原始獨立的任務編碼成n個(n≥k)，在這n個任務結(jié)果中，任意k個就可以恢復原始k個計算結(jié)果。

CDC的理論研究方向主要有三類，包括編碼矩陣與向量乘法、編碼矩陣與矩陣乘法以及CDC在機器學習中的應用。矩陣乘法(尤其是大矩陣乘法)在數(shù)據(jù)分析(挖掘)、機器學習及圖像處理等領(lǐng)域普遍存在。在應用于矩陣乘法的背景下，基于多項式的方法中，將數(shù)據(jù)進行分區(qū)，并且每個工作節(jié)點存儲這些數(shù)據(jù)分區(qū)的線性編碼組合。根據(jù)一個合適的多項式的計算結(jié)果來選擇線性組合系數(shù)，然后，節(jié)點對這些數(shù)據(jù)的編碼包進行計算，主節(jié)點聚合這些計算的輸出，通過多項式插值的解碼過程恢復整體計算，例如Reed-Solomon碼，MatDot碼等。

盡管取得了巨大的成功，但限制基于多項式的方法應用于實踐的一個主要挑戰(zhàn)是它們的數(shù)值穩(wěn)定性問題。解碼過程不可避免地涉及了多項式的插值，插值不穩(wěn)定的主要原因是插值有效地求解了變換以范德蒙(Vandermonde)矩陣為特征的線性系統(tǒng)。眾所周知，具有實值節(jié)點的Vandermonde矩陣的條件數(shù)在矩陣大小上呈指數(shù)增長，大的條件數(shù)意味著由于數(shù)值精度問題而引起的范德蒙矩陣的微小擾動可以導致奇異矩陣，從而影響解碼結(jié)果不可信甚至解碼失敗。

發(fā)明內(nèi)容

本發(fā)明旨在解決矩陣與矩陣相乘時多項式插值解碼過程數(shù)值不穩(wěn)定問題。多項式插值出現(xiàn)數(shù)值不穩(wěn)定問題主要是因為使用的插值基底是簡單的單項式。在矩陣乘法中，本發(fā)明根據(jù)牛頓多項式基底的優(yōu)點，將范德蒙的單項式基底替換為牛頓多項式，通過聯(lián)合設(shè)計編碼，構(gòu)造了一種新的類牛頓多項式碼，使用牛頓多項式來得到編碼矩陣，而不是范德蒙德矩陣。

本發(fā)明提供了一種編碼分布式計算系統(tǒng)，將類牛頓多項式碼應用于編碼分布式計算系統(tǒng)中，在計算機集群中，其中一個計算機充當主節(jié)點(Master)，其他計算機充當工作節(jié)點，在所述計算機集群中分布式地計算矩陣AB相乘，主節(jié)點(Master)把矩陣A和矩陣B分成K塊，然后執(zhí)行編碼策略，分別對矩陣A和矩陣B編碼得到和主節(jié)點把和發(fā)送給N個工作節(jié)點，N≥K，工作節(jié)點執(zhí)行然后在每個工作節(jié)點對插值不同實數(shù)，當主節(jié)點接收到計算速度最快的K個工作節(jié)點的計算結(jié)果后就能從中解碼AB。

作為本發(fā)明的進一步改進，主節(jié)點(Master)把矩陣A和矩陣B分塊，如下：

要計算的結(jié)果此時變成了A₀B₀、A₀B₁、A₁B₀、A₁B₁。

作為本發(fā)明的進一步改進，用多個工作節(jié)點計算A₀B₀、A₀B₁、A₁B₀、A₁B₁的4個結(jié)果。