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