0
| 本文作者： 蔣寶尚 | 2020-06-13 16:39 |
近期，星云Clustar首席科學(xué)家胡水海，以“GPU在聯(lián)邦機器學(xué)習(xí)中的探索”為題，全面詳盡地講解了目前解決聯(lián)邦學(xué)習(xí)的性能與效率問題，以及解決思路。
在報告中胡水海提到，聯(lián)邦學(xué)習(xí)的模型訓(xùn)練過程，很難繞開同態(tài)計算和密文傳輸，二者對算力和網(wǎng)絡(luò)都有嚴苛的要求，星云Clustar也因此選擇從GPU加速同態(tài)運算，以及高速網(wǎng)絡(luò)助力密文傳輸效力的角度切入，來改善聯(lián)邦學(xué)習(xí)的計算速度。
以下是胡水海的演講全文：
目前在AI領(lǐng)域面臨的一個很重大的問題，其實是數(shù)據(jù)孤島問題。在企業(yè)層面，大部分公司在開發(fā)自己的AI模型的時候，其實并不缺少算法和應(yīng)用場景，也不缺少優(yōu)秀的人才，其所面臨的最大問題是數(shù)據(jù)不足的問題。
每個企業(yè)都有一些自己的數(shù)據(jù)，但是這些數(shù)據(jù)彼此之間是相互割裂的，也沒有一種方法將每個企業(yè)的數(shù)據(jù)高效地連通起來，所以一些小企業(yè)會面臨數(shù)據(jù)不足以及大企業(yè)數(shù)據(jù)壟斷問題。
另一方面，無論國內(nèi)，還是國外，對數(shù)據(jù)隱私的保護都已經(jīng)被重視了起來。其實，從2012年開始，國外歐盟已經(jīng)在逐步起草一些法律法規(guī)來保護數(shù)據(jù)安全以及用戶隱私，2018年5月份生效的GDPR更是將用戶數(shù)據(jù)安全提升到了另一個高度。
另外，在今年1月份，美國加州也出臺了相關(guān)法案，明確規(guī)定數(shù)據(jù)歸用戶所有。這些數(shù)據(jù)隱私保護的趨勢都在表明：企業(yè)已經(jīng)無法以明文的方式交換其擁有的數(shù)據(jù)。
而對于國內(nèi)，從2009年開始也在逐步出臺很多保護數(shù)據(jù)安全以及用戶隱私的法案?？偟膩砜矗瑖鴥?nèi)的數(shù)據(jù)法規(guī)政策有兩大趨勢，首先是對數(shù)據(jù)安全的保護事實上變得越來越嚴格，這直接體現(xiàn)為去年一些大數(shù)據(jù)公司在共享數(shù)據(jù)的時候，因為行為不當(dāng)，受到了很嚴厲的法律懲罰。
另外一方面是對數(shù)據(jù)安全的保護變得越來越全面，在各個領(lǐng)域各個維度都出臺了非常多的法律法規(guī)來保護數(shù)據(jù)隱私。所以，在上述背景下，解決數(shù)據(jù)孤島問題其實就變得更加困難。但是聯(lián)邦學(xué)習(xí)的出現(xiàn)為安全合規(guī)地連接數(shù)據(jù)孤島，提供了一種非常有前景的方法。聯(lián)邦學(xué)習(xí)是一項數(shù)據(jù)不出本地，就可完成機器學(xué)習(xí)多方協(xié)作建立模型的技術(shù)。換句話說這種數(shù)據(jù)不出本地的聯(lián)合建模技術(shù)，正是解決國內(nèi)企業(yè)數(shù)據(jù)孤島現(xiàn)狀的“良藥”。
聯(lián)邦學(xué)習(xí)有很多的優(yōu)點，首先能保證數(shù)據(jù)隔離，保證數(shù)據(jù)不會泄露到外部；其次聯(lián)邦學(xué)習(xí)有無損的性質(zhì)，保證聯(lián)合建模的效果等同于直接用所有的數(shù)據(jù)進行建模的效果；再者，在聯(lián)邦學(xué)習(xí)里所有數(shù)據(jù)參與方的地位都是對等的；最后，聯(lián)邦學(xué)習(xí)能保證參與方共同獲益，有助于打破數(shù)據(jù)巨頭的壟斷地位。聯(lián)邦學(xué)習(xí)之所以能實現(xiàn)這些神奇的效果，其中有一項關(guān)鍵技術(shù)就是同態(tài)加密計算。
同態(tài)加密是一種特殊的非對稱加密系統(tǒng)，一般加密后的密文是一段無法操作的二進制數(shù)，除非解密，不然不能對其進行計算或其他操作。而同態(tài)加密好的密文仍然能進行計算，得到仍然是加密的結(jié)果。
最重要的是對密文進行的計算，解密后跟對明文進行計算后的結(jié)果相同。這個特性可以讓參與者進行數(shù)據(jù)運算，但無需知道參與計算的密文內(nèi)容。同態(tài)計算的應(yīng)用范圍非常廣，但是有一個顯著的缺陷，就是性能太低，具體有多低后面會分析，不過有一種折中的方式勉強能被接受，那就是部分同態(tài)加密。部分同態(tài)加密分為加法同態(tài)和乘法同態(tài)。
比如Paillier算法是加法同態(tài)，只支持密文跟密文相加。而著名的RSA算法則是乘法同態(tài)，支持密文跟密文相乘。具體的原理就不詳細展開了，大家可以參考相關(guān)論文。值得一提的是，同態(tài)加密雖然能夠讓聯(lián)邦學(xué)習(xí)保護用戶隱私，但它其實也為聯(lián)邦學(xué)習(xí)帶來了很大的技術(shù)挑戰(zhàn)，這一點從與傳統(tǒng)機器學(xué)習(xí)方法的對比中能夠清晰看到。
首先，傳統(tǒng)機器學(xué)習(xí)一般使用的是32-bit的基本運算，這些基本運算一般都有芯片指令的直接支持，而聯(lián)邦學(xué)習(xí)中的Paillier/RSA算法依賴的是1024或2048-bit 甚至更長的大整數(shù)運算，且這些運算是模冪、模乘等復(fù)雜運算；其次，在分布式計算時，傳統(tǒng)機器學(xué)習(xí)參數(shù)聚合使用內(nèi)網(wǎng)傳輸，而聯(lián)邦學(xué)習(xí)因為涉及不同的參與方，這些參與方可能位于不同的城市，所以聯(lián)邦學(xué)習(xí)是使用廣域網(wǎng)進行傳輸。
另一方面，從數(shù)據(jù)傳輸?shù)慕嵌葋砜?，?lián)邦學(xué)習(xí)對運算位數(shù)多要求1024或2048-bit ，所以傳輸密文數(shù)據(jù)體積比傳統(tǒng)機器學(xué)習(xí)增加幾十倍；因為聯(lián)邦學(xué)習(xí)要求多次迭代，所以數(shù)據(jù)傳輸?shù)拇螖?shù)也是傳統(tǒng)機器學(xué)習(xí)的幾倍。
總的算起來，如上圖所示，聯(lián)邦學(xué)習(xí)的部分同態(tài)計算的計算量是明文計算量上百倍，聯(lián)邦學(xué)習(xí)的數(shù)據(jù)傳輸總量也比傳統(tǒng)機器學(xué)習(xí)大100到1000倍。如果使用全同態(tài)的話，其計算量會是明文計算的上萬倍。也正是基于這個原因，當(dāng)前的聯(lián)邦學(xué)習(xí)解決方案多采用部分同態(tài)加密。面臨計算和傳輸方面的挑戰(zhàn)，我們做了許多有價值的技術(shù)探索。
第一個探索是使用GPU來加速聯(lián)邦學(xué)習(xí)計算。如上圖，我們首先進行四個觀察方向的可行性分析，第一個觀察數(shù)據(jù)加解密及密態(tài)計算，不同數(shù)據(jù)的計算其實并不存在很大的關(guān)聯(lián)性，因此計算是高度并行的。而GPU正好適合加速高度并行的計算任務(wù)。
第二個觀察是聯(lián)邦學(xué)習(xí)很多計算公式其實本身并不復(fù)雜，但重復(fù)執(zhí)行次數(shù)巨大。舉例而言，聯(lián)邦學(xué)習(xí)需要經(jīng)常運行 A的B次方這種冪計算，而A和B往往是1024比特甚至更長的數(shù)字。所以，即使是簡單的公式，但是重復(fù)運算的次數(shù)非常多，而GPU正好適合加速這種重復(fù)的輕量級計算。
第三個觀察是在聯(lián)邦學(xué)習(xí)里，數(shù)據(jù)IO時間占比非常少，可能不到計算時間的0.1%，這說明聯(lián)邦學(xué)習(xí)符合計算密集型的任務(wù)，而GPU適合加速計算密集型任務(wù)。第四個觀察是聯(lián)邦學(xué)習(xí)里訓(xùn)練模型的數(shù)據(jù)通常是以批量形式的產(chǎn)生為主，符合大數(shù)據(jù)的特征，而GPU正好適合加速海量數(shù)據(jù)的批量計算。
上述四個觀察雖然確定了GPU能夠加速聯(lián)邦計算的方向，但同時也提出了三個挑戰(zhàn)。第一個挑戰(zhàn)是聯(lián)邦學(xué)習(xí)計算需要做2048-bit大整數(shù)運算，而GPU流處理器不直接支持大整數(shù)運算；第二個挑戰(zhàn)是聯(lián)邦學(xué)習(xí)計算涉及大量的模冪運算，而GPU做除法或者模冪運算的代價非常大；第三個挑戰(zhàn)是聯(lián)邦學(xué)習(xí)計算需要緩存大量中間計算結(jié)果，而由于成本和能耗的限制，GPU顯存非常有限。
針對三個挑戰(zhàn)，我們提出了三個解決方案。第一個方案是基于分治思想做元素級并行。如圖所示，以計算大整數(shù)乘法a*b為例，首先我們將N比特位長的大整數(shù)a和b分解成高位和低位兩部分，分解之后其a和b以及a*b的表達式如圖。仔細觀察a*b的表達式，發(fā)現(xiàn)四個子項的計算不存在數(shù)據(jù)關(guān)聯(lián)性，可以并行計算。
基于這個思想，我們可以通過遞歸的方式將大整數(shù)乘法分解成很多可并行計算的小整數(shù)乘法，這樣GPU就能發(fā)揮并行計算的優(yōu)勢完成大整數(shù)乘法的快速計算。不僅如此，對于聯(lián)邦學(xué)習(xí)涉及的其他大整數(shù)運算，也可以做類似的元素級并行。
第二個解決方案是用平方乘算法+蒙哥馬利算法解決GPU做模冪運算代價大的問題。其核心是如何高效計算模冪運算ab mod c ，其中a,b,c均為N比特大整數(shù)。對于這個問題，最容易想到的樸素算法是先計算ab的值，然后將計算結(jié)果對c取模。但這樣會使問題計算復(fù)雜度高達O(2^N)，并且中間的乘積結(jié)果很大。我們采用的方法是通過平方乘算法進行優(yōu)化。平方乘算法主要基于的觀察是：我們要計算a^K，并不一定需要將a自乘k次，而是可以先計算出a^k/2的值，然后求平方。
以此類推，我們只需要 logk 次的乘法運算就可以得到ak的值。根據(jù)這個思想，我們可以將b表示為2進制數(shù)，然后通過O(N)次乘法以及取模運算得到計算結(jié)果。這類方法的優(yōu)點是將復(fù)雜度降低到O(N)并且中間計算結(jié)果的大小不超過c。
缺點是需要做2N次取模運算，對GPU來說，做取模運算的時間代價很高。為了解決這個問題，我們引入了蒙哥馬利模乘算法來高效完成第3步中的模乘計算。蒙哥馬利算法的優(yōu)點能夠讓復(fù)雜度下降到O(N)，中間結(jié)果大小不超過c，完全避免了取模/除法運算，從而大大加快了運算速度。
對于第三個挑戰(zhàn)，如何減少中間計算結(jié)果，我們給出的解決方案是通過中國剩余定理。中國剩余定理是數(shù)論領(lǐng)域的一個著名定理，說的是給定一組兩兩互質(zhì)的整數(shù)n1,n2,…,nk和任意一組整數(shù)a1,a2,…,ak，那么通過這兩組數(shù)構(gòu)造的下面這個同余方程組一定有解，并且解一定同余于N。
那么怎么使用呢？首先定義mp跟mq這兩個子項，并依據(jù)這兩個子項構(gòu)造一個滿足中國剩余定理的同余方程組。如上圖所示，并用CRT(mp,mq)來表示這個同余方程組的解?？梢宰C明解密計算公式等價于同余方程組的解mod pq，所以可以通過計算這個新的表達式來求解m的值。根據(jù)上面三個計算表達式，會有兩個觀察結(jié)論。首先，三部分的中間計算結(jié)果都不超過N比特，因此減小了中間計算結(jié)果。此外，計算公式從2N比特數(shù)的模冪運算簡化成N比特數(shù)的模冪運算，計算量大幅減小。
最后看一下GPU加速聯(lián)邦學(xué)習(xí)的初步評測結(jié)果。我們主要評測了四種運算：同態(tài)加密、同態(tài)解密、密態(tài)乘法和密態(tài)加法在三種優(yōu)化下的加速比。對比的baseline是14核2.2Ghz的服務(wù)器級CPU，而使用的CPU代碼是高度優(yōu)化的。
結(jié)果如上圖：對于比較復(fù)雜的同態(tài)加密和解密，在經(jīng)過三種優(yōu)化手段后，GPU為聯(lián)邦學(xué)習(xí)帶來了差不多6倍的加速比。對于計算相對簡單的密態(tài)乘法和密態(tài)加法，GPU為聯(lián)邦學(xué)習(xí)分別帶來了30倍以上和400倍以上的加速比。
上面講的是如何應(yīng)對聯(lián)邦學(xué)習(xí)計算方面的挑戰(zhàn)，那么在傳輸方面，即在加速聯(lián)邦學(xué)習(xí)跨機構(gòu)跨區(qū)域通信方面，主要考慮聯(lián)邦學(xué)習(xí)通信的兩大場景：場景一是數(shù)據(jù)中心內(nèi)部不同機構(gòu)間通信（主要是云服務(wù)器），場景二是不同機構(gòu)的數(shù)據(jù)中心跨區(qū)域通信（地理位置不同）。
其中，數(shù)據(jù)中心內(nèi)通信場景的主要挑戰(zhàn)是高速網(wǎng)絡(luò)時代如何加速聯(lián)邦學(xué)習(xí)通信；而跨區(qū)域通信場景的主要挑戰(zhàn)是如何在高延遲、高丟包率網(wǎng)絡(luò)環(huán)境下加速聯(lián)邦學(xué)習(xí)通信。針對場景一帶來的挑戰(zhàn)，我們采用的解決方案是通過RDMA網(wǎng)絡(luò)技術(shù)優(yōu)化兩點間通信，然后通過動態(tài)參數(shù)聚合模型優(yōu)化多點間通信來解決。
在這里也提一下數(shù)據(jù)傳輸?shù)谋尘埃F(xiàn)在正處在數(shù)據(jù)中心高速網(wǎng)絡(luò)時代，如上圖所示，數(shù)據(jù)中心網(wǎng)絡(luò)帶寬近年來高速增長，100G，200G網(wǎng)絡(luò)對于大規(guī)模商用數(shù)據(jù)中心來說，已經(jīng)非常普遍。當(dāng)然，網(wǎng)絡(luò)帶寬的高速增長也對通信帶來了巨大挑戰(zhàn)！10-100倍的帶寬增長帶來了三個問題，第一，收發(fā)兩端相同時間需要處理10-100x的網(wǎng)絡(luò)數(shù)據(jù)包，第二，網(wǎng)絡(luò)突發(fā)流量現(xiàn)象變得更加嚴重，第三，網(wǎng)絡(luò)流完成時間大大減少意味著擁塞控制需要更快響應(yīng)。
傳統(tǒng)的TCP網(wǎng)絡(luò)由于存在CPU負載高、端處理延遲大以及吞吐量瓶頸等幾個問題，不太適用于高速網(wǎng)絡(luò)。所以在高速網(wǎng)絡(luò)下，RDMA取代TCP已經(jīng)成為了一個趨勢。具體表現(xiàn)在：通過內(nèi)核旁路以及將傳輸層卸載到網(wǎng)卡硬件上，RDMA能實現(xiàn)高吞吐、低時延、低CPU負載的兩點間通信，非常適合用于加速聯(lián)邦學(xué)習(xí)數(shù)據(jù)中心內(nèi)的通信。
但是要將RDMA應(yīng)用于聯(lián)邦學(xué)習(xí)數(shù)據(jù)中心內(nèi)通信，我們還需要解決GPU跟RDMA網(wǎng)卡之間高效協(xié)作的問題。我們注意到GPU與RDMA網(wǎng)卡之間的通信存在從GPU到內(nèi)存以及從內(nèi)存到網(wǎng)卡的多次數(shù)據(jù)拷貝。這會增大傳輸延遲, 降低吞吐量和浪費CPU。
為了解決這一問題，我們在聯(lián)邦學(xué)習(xí)通信中引入了英偉達的GPU-Direct-RDMA 技術(shù)，實現(xiàn)了GPU和RDMA網(wǎng)卡之間的直接數(shù)據(jù)拷貝。一方面通信吞吐量從20G提升到了100G，另一方面也將傳輸延遲最多降低了1000倍。
最后我們評估了GRDMA能為聯(lián)邦學(xué)習(xí)帶來性能提升的程度，對于AlexNet和VGG16兩種模型，分別測試了他們在TCP和GRDMA兩種網(wǎng)絡(luò)下的訓(xùn)練效率。初步的測試結(jié)果如上圖顯示，使用GRDMA分別帶來了超過60%和超過50%的訓(xùn)練性能提升。
關(guān)于優(yōu)化聯(lián)邦學(xué)習(xí)多點間通信，Parameter Server和Ring Allreduce是目前使用最廣泛的兩種參數(shù)聚合模型。但他們都分別有一些缺點。ParameterServer的問題是存在多個worker節(jié)點給單個server節(jié)點發(fā)送參數(shù)的多對一通信方式。在超售網(wǎng)絡(luò)下，這種通信方式的性能會因為鏈路擁塞而大幅度下降。Ring Allreduce的問題是存在一個很長的通信依賴鏈。一旦某一跳發(fā)生阻塞，RingAllreduce 的長依賴鏈會使整個聚合任務(wù)停滯。
對于跨區(qū)域通信場景問題，首先有以下幾點觀察，第一，隨著物理距離增加，跨區(qū)域通信時間在聯(lián)邦學(xué)習(xí)中的時間占比越來越大；第二，跨區(qū)域主干網(wǎng)具有高延遲、高丟包率等特征，丟包偵測與丟包恢復(fù)代價很大；第三，機器學(xué)習(xí)模型訓(xùn)練可以容忍一定的丟包率，即我們通過實驗發(fā)現(xiàn)，當(dāng)丟包率小于15%時，即使不做丟包恢復(fù)，模型收斂所需要的輪次并不會變多。另外我們還發(fā)現(xiàn)，當(dāng)丟包率低于15%時，不做丟包重傳能顯著減少模型訓(xùn)練時間。
那么為什么機器學(xué)習(xí)模型訓(xùn)練可以容忍部分丟包呢？原因是目前模型訓(xùn)練大多采用隨機梯度下降(SGD)方式通過多輪迭代進行，丟失一部分數(shù)據(jù)不影響訓(xùn)練算法找到模型收斂點。如圖所示，藍線是不丟包的情況下模型訓(xùn)練的收斂路徑，而在有丟包的情況下，隨機梯度下降能讓模型訓(xùn)練選擇另外一條路徑達到收斂點。
基于上述觀察，我們設(shè)計了一個機器學(xué)習(xí)專用的網(wǎng)絡(luò)傳輸協(xié)議 --- MLT。核心思想是：在不影響模型收斂的前提下，允許一定的丟包，不做重傳，從而降低跨區(qū)域通信時間。將MLT跟傳統(tǒng)的TCP以及UDP進行對比可以發(fā)現(xiàn)，TCP可以看作是做百分百丟包重傳的可靠傳輸，UDP可以看作是百分百丟包不重傳的不可靠傳輸，而MLT位于兩者之間，是根據(jù)機器學(xué)習(xí)訓(xùn)練的特點，選擇重傳一部分丟失的數(shù)據(jù)包，使丟包率控制在不影響模型收斂的范圍內(nèi)，并通過避免不必要的丟包重傳來降低聯(lián)邦學(xué)習(xí)的通信時間。
具體到實驗評測如上圖，MLT可以通過減少不必要的丟包重傳，能夠大幅縮短聯(lián)邦學(xué)習(xí)模型訓(xùn)練的時間。
雷鋒網(wǎng)、雷鋒網(wǎng)、雷鋒網(wǎng)
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
