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