機器之心分析師網絡

作 者: 仵冀穎 編輯:Hao Wang

第三屆機器學習與系統會議(MLSys 2020)將於 2020 年 3 月 2 日至 4 日在美國奧斯汀會議中心舉行。MLSys 是 2018 年新成立的一個聚焦機器學習在系統、軟件、硬件等多個綜合領域中應用研究的學術會議。

MLSys 提前看 | 機器學習的分佈式優化方法

隨着機器學習算法和模型的不斷髮展,傳統的軟硬件平臺、部署環境等無法支撐機器學習的應用,這也成爲了目前機器學習方法落地及大規模推廣應用的主要困難之一。目前,有關於 MLSys 的研究方向包括硬件領域、軟件領域和對機器學習算法的改進三個方面,以 MLSys 2020 爲例,本屆大會的議題包括:Distributed and parallel learning algorithms (5 篇論文)、Efficient model training (8 篇論文)、Efficient inference and model serving (8 篇論文)、Model/Data Quality and Privacy (4 篇論文)、ML programming models and abstractions & ML applied to systems (5 篇論文)以及 Quantization of deep neural networks (4 篇論文)。整個會議一共錄用 34 篇論文。

在本篇提前看中,我們選擇了三篇文章進行詳細分析,以瞭解機器學習與系統(Machine Learning and Systems)領域最新的研究成果。其中,前兩篇文章屬於經典的機器學習分佈式優化方法(通信方式、內存分配方法),第三篇文章則是關於一種新的用於機器學習的具有高度系統性和設備(統計、數據)異質性的分佈式方法--聯邦學習。
Blink: Fast and Generic Collectives for Distributed ML
Efficient model training topichttps://arxiv.org/pdf/1910.04940.pdf
隨着高質量數據庫、大規模數據集的不斷髮展,深度學習模型不斷改進,在圖像分類、目標檢測、機器翻譯、語音處理等領域都獲得了很好的效果。與之同時,漫長的訓練時間卻成爲了另一個讓人頭疼的問題。在處理一些圖像分類任務時,在單個 GPU 中的訓練時間甚至需要幾天!基於多個 GPU 的數據並行訓練(Data-Parallel Training)的引入,大大緩解了大規模深度學習模型訓練耗時長的問題。在數據並行訓練中,每個 GPU 都有一個完整的模型參數副本,同時也會與其他參與訓練的 GPU 交換參數。這篇文章介紹的是 MLSys 領域中基於 GPU 的模型參數同步問題。
跨 GPU 的參數同步在大規模訓練時產生了較大開銷,對於常見 ML 模型,通信開銷可以從 50% 到 90% 不等。解決這一問題的手段主要有兩種:硬件手段—先進的多 GPU 服務器,例如 NVIDIA』s DGX-1、DGX-2 等;軟件手段,利用了 Wait-free 反向傳播技術的現代通信原語,例如 NVIDIA『s Collective Communications Library (NCCL)、百度的 Ring AllReduce 等。本文研究的是軟件手段,提出了 Blink—一個通過包裝生成樹動態生成最佳通信原語的集合通信庫。爲了處理硬件生成中的拓撲異質性問題或集羣調度程序中的分配問題,Blink 能夠動態生成給定拓撲的最佳通信原語。
【目前的問題】
即使在 NVIDIA DGX-1 這樣的快速多 GPU 服務器上運行數據並行訓練時,深度學習工作負載也會帶來很高的通信開銷。更重要的是,作者發現,即使在像 DGX-1 這樣的高性能服務器內,現有通信原語如 NCCL 或 Horovod 也會放大通信開銷,作者認爲,這主要是因爲它們無法處理拓撲異質性問題。DGX-1 中既有諸如 NVLink (20-25GB/s)的 GPU 點對點(P2P)互連,也有諸如 PCIe (8-12GB/s)的共享互連。PCIe 通過 PCIe 交換機層次結構將多個 GPU 相互連接到一臺計算機內,並連接到 CPU 和 I/O 設備。NCCL、Horovod 等通信原語基於環的模式(Ring-based Protocols)進行數據傳輸,然而,基於環的協議有結構上的限制:對於每個環,每個節點只能有一個輸入和一個輸出。基於環的模式將所有的通信節點通過首尾連接形成一個單向環,數據在環上依次傳輸。假設有 3 個 GPU,GPU0 爲信息的發送者,將信息發送給剩下的 GPU,基於環的通信原語按照環的方式將信息傳輸,即 GPU0-->GPU1-->GPU2。這種限制使得環無法適應由於調度程序分配而導致的不規則拓撲,如圖 1 所示。環的吞吐量受到帶寬最低的鏈路的限制,因此這些協議要麼將自己限制在高帶寬、同質鏈路上,要麼將吞吐量限制在環中帶寬最低的鏈路上。以 NCCL 爲例,對於一臺機器內的多 GPU 通信,NCCL 將優先使用 NVLink,而當在 NVLink 環中時,PCIe 將成爲瓶頸。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 1. 羣集上每個 8-GPU 服務器中分配給 Cloud-X 上 40000 個多 GPU 作業的 GPU 數
此外,這些限制還會導致鏈接使用不足,如圖 2 所示。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 2. DGX-1P 中 NCCL 與本文提出的 Blink 在 6-GPUs 上的廣播比較

通過將 GPU 之間的鏈接建模爲圖,前期的研究結果表明,包裝生成樹 (Packing Spanning Trees) 能夠生成從有選擇的根頂點到有向圖中的所有其他頂點的最大流。基於此研究,作者認爲一對多協議(如使用根節點的生成樹進行廣播)是克服鏈路利用率不足的一個潛在有效選擇。當然,除了像廣播這樣只轉發數據的操作之外,還需要實現像 AllReduce 這樣的通信原語,即可以被建模爲在一個方向上減少並前進(面向根的方向),然後在另一個方向廣播。
【Blink 詳解】

MLSys 提前看 | 機器學習的分佈式優化方法

圖 3. Blink 工具鏈工作流
給定拓撲,Blink 的主要方法是動態地生成適當的集合通信原語。通過引入包裝生成樹來實現高利用率,使用能夠最大化傳輸速率的算法,同時最小化所使用的樹的數量。最後,通過在雙向鏈路的每個方向上執行多對一和一對多的操作來實現像 AllReduce 這樣的多對多算法。Blink 工具鏈完整工作流見圖 3 所示。具體步驟包括 :
(1)給定深度學習任務,一旦安排並分配了一組 GPU,Blink 就能夠探測機器的拓撲結構,並通過分配的 GPU 推斷互連拓撲結構。(2)給定拓撲,將集體通信操作建模爲有向圖上的流,並計算生成樹的最大分數填充。此步驟表示爲圖 3 中的 TreeGen,此步驟輸出一組生成樹和對應於應通過它們發送多少數據的權重。
(3) CodeGen 解析生成樹並生成 CUDA 代碼。生成的代碼與 NCCL 提供的 API 匹配,並打包到共享庫 libblink.so 中。
(4)設置 LD_PRELOAD 標誌,以便在調用主程序時動態加載 Blink 實現。這確保了現有程序可以在沒有任何修改的情況下運行。
1、包裝生成樹
將從分配的資源推斷出的拓撲建模爲一個有向圖,其中每個 GPU 是頂點 V,每個鏈路(NVLink 或 PCIe)標記爲有向邊緣 E。每個有向邊緣還具有帶寬比例容量。通過找到圖中的有向生成樹或樹狀圖的最大填充可以達到最優速率。每個樹狀圖 Ti 從根渦生成,沿着有向鏈接擴展到其它渦點。通過確定滿足能力限制的最大權重樹狀圖,可以解決在廣播中確定最佳時間表的問題。

MLSys 提前看 | 機器學習的分佈式優化方法

由上式,給定一個圖 G,頂點爲 V,邊爲 E,根爲 r,生成樹爲 T1, T2, T3, ... Ti,希望找到權重 w_i,使得通過任何邊的權重樹的總和不超過特定邊的容量。
2、減小生成樹的數目(優化算法)
乘法權重更新(multiplicative weight update,MWU)是一種廣泛應用於優化、博弈論等各個領域的算法。本文使用 MWU 實現分數線性包裝問題的近似線性時間逼近。使用一個容量和一個權重來初始化每一個邊,這個權重用來標記已經使用了多少容量。運行一個迭代方法,每次迭代都會找到給定當前分配的最小權值生成樹。然後,將所選樹上的權重增加一個 ε 因子,並相應地更新圖上的權重。給定 T1, T2, T3, ... Tk,爲了最小化生成樹的數目,構造了一個整數線性規劃問題(integer linear program,ILP),每個權重被限制爲 0 或 1:

MLSys 提前看 | 機器學習的分佈式優化方法

其中,k 由 MWU 過程返回的樹的數目控制,因此比圖中的生成樹的總數小得多。
3、推廣到多對多的情況
爲了處理多對多的操作,作者利用了這樣一個事實:在這些機器中發現的所有鏈接本質上都是雙向的,因此可以創建一個無向圖,用鏈接的一個方向運行多對一原語,並相應地在另一個方向運行一對多原語。這種使用兩個無向樹的策略也與 AllReduce 操作所需的消息數下限相匹配。
AllReduce 的進程需要發送的最小消息數是 2x|(N-1)/N|。N 個頂點上的生成樹包含 N-1 條邊,並考慮了兩個方向上的樹(一個用於 Reduce,一個用於 Broadcast),類似的,本文方法同樣有 2x(N-1)條消息。
4、處理複雜通信問題
處理複雜問題重點探討的是處理複雜的 PCIe 和 NVLink 拓撲。使用 PCIe 和 NVLink 的主要挑戰來自 NVIDIA 驅動程序不允許用戶直接控制對兩個鏈路的訪問,如果檢測到 NVLinks,系統將自動啓用使用 NVLinks 的 GPU 之間的 P2P 數據傳輸。作者通過實驗發現,使用 cudaDeviceDisablePeerAccess 會禁用 NVLinks 並強制通過 PCIe 鏈路傳輸數據。然而,這仍然有一個侷限性,即不能用這兩組鏈接構造一個統一的拓撲。作者通過構造兩個獨立的樹集來解決這個問題,一個在 PCIe 鏈路上,另一個在 NVLinks 上。這種方法的難點之一是平衡在每種鏈路類型上傳輸的數據量,作者使用的方法是最小化每個傳輸所花費的最大時間,即最小化 MAX (T_pCIe, T_NVL),其中 T_pCIe 和 T_NVL 表示每條鏈路上的數據總數。定義 D_total 爲待傳輸的數據總量,T_dpa 爲調用 disable_peer_access ()的延遲,BW_PCIe 和 BW_NVL 表示爲 PCIe 和 NVLink 樹的帶寬,通過使 T_PCIe=T_NVL 可以實現最佳的數據分割。

MLSys 提前看 | 機器學習的分佈式優化方法

其中,T_dpa 由經驗性測量得到並可能根據 GPU 的數量而變化。
5、應對多服務器設置
最後,作者以 DGX-2 和多機訓練爲例,討論如何應對多服務器設置。DGX-2 由 16 個通過 NVSwitch 連接的 V100 GPU 組成;每個 GPU 通過 6x NVLink 連接到 switch。在 DGX-2 上,Blink 爲 AllReduce (reduce broadcast)生成的生成樹爲:對於 mGPU,每個 GPU 充當 1/m 個數據塊的根,每個根直接連接到(m-1)個葉節點,從而生成 m 個一跳(one-hop)樹。當訓練任務的 GPU 跨越多個服務器、通過交換機或交換機層次結構連接時,Blink 使用三相協議,如圖 4 所示。其中,第一個階段對本地生成樹上的每臺服務器進行縮減—每臺服務器中的每棵樹的根會像以前一樣聚合來自其子級的數據。第二個階段跨服務器進行 reduce 廣播(類似於 DGX-2 中的內容)–跨 n 個服務器,有 n 個單跳跨服務器樹,每個服務器的本地根連接到其他服務器上的(n-1)個根。第三階段根據每個服務器的本地根目錄,將第二階段的結果廣播給服務器中的所有節點。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 4. 用於跨服務器設置的三相 AllReduce 協議,其中 X_m,g 表示服務器 m、GPU g 上的數據分區
【實驗分析】
首先,作者給出了本文提出的包裝生成樹的理論效益。在 V100 和 P100 機器上,實驗比較了 NCCL 在給定拓撲中創建的環的數量和 Blink 打包的所有可能分配的生成樹的總重量(從 3GPU 到 8GPU)。我們使用廣播和 AllReduce 所需消息的下限(分別爲 [(N-1)/N] 和 [2x(N-1)/N])將其轉換爲廣播速率。對於 8GPU 的情況給出了 4 個環,每個環將在 8/14 的鏈路帶寬下工作,對於 4 個這樣的環,有效速率是 32/14。實驗中,近似 PCIe 環的帶寬爲 NVLink 環帶寬的一半。實驗結果如圖 5,在所有情況下包裝生成樹的速度與使用環一樣快,而在某些情況下(即環必須通過 PCIe),包裝生成樹的速度達到了環的 6 倍。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 5. DGX-1P (P100)和 DGX-1V (V100)理論加速比對,方塊圖顯示了可能的配置分佈
第二,作者給出在三種不同的硬件設置(DGX-1P,DGX-1V,DGX-2)上 NCCL 和 Blink 在廣播和 AllReduce 中的吞吐量比較的實驗結果。作者在這一組實驗中給出了一系列實驗結果以驗證 Blink 的有效性,受篇幅所限,我們不一一貼出,給出 NCCL 和 Blink 之間的廣播吞吐量比較作爲示例,該示例比較 AWS (p3.16xlarge)上 DGX-1V 上 GPU 分配引起的所有可能拓撲,使用的 GPU 數量從 3 到 8 不等。爲了使互連完全飽和,使用總數據大小爲 500MB (50MB 到 1000MB 的誤差線)進行測試。具體結果見圖 6。
與 NCCL 相比,Blink 的性能可以提高 6 倍(2 倍的幾何平均值)。在 GPU 未通過 NVLink 完全連接的情況下(例如 GPU 1、4、5、6),NCCL 無法在這些 GPU 上形成僅 NVLink 的環,從而迫使其重新使用 PCIe 進行數據傳輸。這會導致許多 NVLink 通道未使用,顯著降低吞吐量。NCCL 在 Blink 可以形成完全連接的 NVLink 環並且 Blink 只能創建一個生成樹時匹配 Blink。但是,即使在這些情況下,由於優化了分塊傳輸,Blink 仍能獲得 3-5GB/s 的更高性能。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 6. DGX-1V 上所有獨特拓撲 NCCL2 和 Blink 的廣播吞吐量比較
第三,作者討論在使用 PCIe 和 NVLink 執行混合數據傳輸時的權衡。爲簡潔起見,僅在 AWS DGX-1V 服務器上顯示 3-8 GPU 的廣播結果。實驗結果見圖 7,顯示了當 Blink 同時通過 NVLink 和 PCIe 傳輸時,僅通過 NVLink 傳輸的額外 2-5 GB/s 性能增益。從 NVLink 到 PCIe 的通信通道切換時間隨着 GPU 數量的增加而增加。對於 3 和 4 GPU 設置,與僅 NVLink 廣播相比,混合傳輸可實現約 5GB/s 的提升;對於 7 和 8 GPU,此加速僅爲約 2GB/s。這是因爲啓用和禁用對等訪問(即在 PCIe 和 NVLink 之間切換)所花費的總時間與使用的 GPU 數成正比。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 7. 混合和 NVLink 在不同 GPU 數下的廣播吞吐量比較
最後,作者給出在單個 DGX-1 和多個 DGX-1 設置上使用四個常用 DNN 的 Blink 的端到端加速結果。作者將 Blink 與 Pytorch 結合起來,並評估訓練的端到端性能增益。使用四個流行的 CNN:AlexNet、ResNet18、ResNet50 和 VGG16,並在 ImageNet-1K (ILSVRC12)數據集上訓練這些模型。對於所有模型都使用與原始論文中相同的每 GPU 小批量大小和超參數。
如圖 8 所示,在單服務器的情況下,將集合通信後端從 NCCL2 切換到 Blink,可以將端到端 DNN 訓練迭代所花費的時間最多減少 40%(6.3% 幾何平均值),並實現最多 87% 的通信時間減少(31% 幾何平均值)。

MLSys 提前看 | 機器學習的分佈式優化方法

MLSys 提前看 | 機器學習的分佈式優化方法

圖 8. DGX-1V 機器內的閃爍端到端訓練時間縮短(ImageNet1K)

在多服務器的情況下,圖 9 (a)顯示 Blink 比 Horovod 的 NCCL/MPI 高出 11%,與單服務器訓練相比,Blink 在 NCCL 方面的改進有所減少。爲了瞭解更快的互連將如何改變性能,圖 9 (b)給出了一個改變跨機器帶寬的模擬結果。實驗比較了 100MB 數據的吞吐量,發現隨着跨機器帶寬的增加,Blink 的設計將帶來更顯著的端到端優勢。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 9.Multi-DGX-1 DNN 中 Blink 訓練結果

【文章小結】
本文提出的 Blink 是一個快速通用的集體通信庫,用於加速分佈式機器學習。爲了處理在現代 GPU 硬件中普遍存在的拓撲異質性,Blink 使用動態包生成樹以最大化鏈路利用率。與目前最先進的、基於環的集體通信協議(如 NCCL2)相比,Blink 可以實現高達 8 倍的模型同步速度,並將端到端 DNN 模型訓練時間減少 40%。
Salus: Fine-Grained GPU Sharing Primitives for Deep Learning Applications
Efficient inference and model serving topichttps://arxiv.org/pdf/1902.04610v1.pdf
隨着深度學習(deep learning,DL)應用的普及,GPU 計算正變得越來越流行。然而,與傳統資源(如 CPU 或網絡)不同,現代 GPU 本身並不支持細粒度共享原語(最細的顆粒度就是整個 GPU)。因此,實現諸如分時和搶佔等公共策略的代價是非常昂貴的。更糟糕的是,當一個 DL 應用程序不能完全使用 GPU 的資源時,GPU 不能在多個應用程序之間有效地共享,從而導致 GPU 利用率低下。雖然這種訪問 GPU 的排他性簡化了硬件設計並使其變得高效,但它導致了兩個主要的低效率:首先,粗粒度、一次一個的 GPU 分配模型阻礙了 GPU 集羣管理器的調度能力;其次,並非所有的 DL 作業都能一直充分利用 GPU。此外,日益流行的 DL 模型的自動超參數調整趨勢進一步強調了提高 GPU 利用率的必要性。這種自動超參調整可以被視爲「預訓練」的過程。它通常是通過爲超參數探測並行生成許多訓練作業來完成的,其中許多作業一旦被認爲質量低劣就會被殺死。
爲了解決這些問題,這篇文章的作者提出 Salus,一種使細粒度的共享 GPU 與靈活的調度策略共存的方法。Salus 通過公開兩個 GPU 共享原語來實現這一點:快速任務切換和內存共享。前者確保可以在 GPU 上快速切換當前活動的 DL 作業,從而實現高效的時間共享和搶佔。後者通過在同一設備上打包更多的小 DL 作業來確保高利用率。DL 應用程序獨特的內存使用模式是在 Salus 中高效實現這些原語的關鍵:識別三種不同的內存使用類型,並在處理它們時應用不同的管理策略。將這兩個原語組合在一起,可以使用細粒度時空共享來實現各種解決方案。
【SALUS 詳解】
1、總體結構
Salus 被實現爲一個單一的執行服務,它整合了所有 GPU 訪問,從而支持 GPU 共享,同時避免了 GPU 上進程之間代價高昂的上下文切換。因此,任何未修改的 DL 作業都可以使用 DL 框架特定的適配器利用 Salus,如圖 10 所示。從用戶角度來說,Salus 相當於一個虛擬計算資源。而從用戶角度,框架的 API 並沒有什麼變化,無需增加新操作。
Salus 已經開源:https://github.com/SymbioticLab/Salus

MLSys 提前看 | 機器學習的分佈式優化方法

圖 10. Salus 位於 DL 框架和 DL 堆棧中的硬件之間,對用戶是透明的
當在用戶腳本中創建 DL 作業時,DL 框架中的 Salus 適配器在 Salus 中創建相應的會話(1a)。在創建過程中,DL 作業的計算圖也被轉移到 Salus。然後,會話繼續從存儲器管理器(1b)請求通道。根據系統中的當前作業,此進程可以阻塞從而會話將排隊。在作業運行過程中,無論是訓練還是推斷,迭代都由用戶腳本生成並轉發到 Salus 中的相應會話(2a)。然後,它們由迭代調度器(2b)根據其關聯的 GPU 通道進行調度,併發送給 GPU 執行。Salus 執行服務通過 DL 作業的迭代粒度調度實現 GPU 共享。
2、快速任務切換
首先,作者對於 DL 任務中內存分配的類型進行分析。

  • 模型:這些主要保存模型參數,通常由一些大的內存塊組成。由於模型大小在整個訓練過程中通常是固定的,因此模型數據很少或沒有時間變化,並且是可預測的。

  • 短暫:這些是每次迭代所需的臨時內存。這些內存通常保存中間層的輸出以及算法本身生成的臨時數據。它們只在計算期間才需要,並且在迭代之間被釋放,從而產生 DL 作業的時間內存使用模式。它們通常也是大內存分配。

  • 框架:這些通常被 DL 框架用於記賬或數據準備通道。它們經常在迭代中持續存在。

由上述分析可知,模型和框架類的內存需求在迭代過程中是一直存在的。此外,對於 DL 作業,持久內存使用率明顯低於臨時內存。有可能在 GPU 中保留多個作業的持久內存,同時仍有足夠的空間存儲任一作業的短暫內存。由此,作者得出結論:不從 GPU 中刪除持久內存就可以實現快速的作業切換。
考慮到迭代在 DL 作業中通常很短(從幾十毫秒到幾秒不等),而且粒度更細,例如在 GPU 內核級別,因此可以進一步利用 GPU 資源。但是,細粒度的調度也會給執行服務增加更多的開銷。因此,對於給定的調度粒度,需要在最大利用率和效率之間尋找最優的折衷。考慮下面的場景,給定 12GB 的 GPU 內存容量,作業 A 和作業 B 進行了兩次迭代。它們的模型內存使用量是 PA=PB=1GB,而臨時內存使用量是 EA=EB=7GB (由於框架相對較小,忽略了它的內部使用量)。內存的分配方式不是一次分配所有 8GB,而是一個作業的每個迭代以不同的增量分配。在迭代之間切換的選擇允許迴避漸進式內存分配的問題。這是因爲框架在每次迭代後都會釋放所有短暫的分配,並且模型和框架內部分配在整個迭代中保持不變。
3、內存共享
在高效作業交換的基礎上,作者設計了一種特殊的內存佈局方案 GPU 通道(Lane),實現了內存共享,從而提高了內存利用率。首先,將 GPU 內存空間分爲短暫的和持續的區域。「模型」和「框架」分配持續區域,而「短暫」則分配的是短暫的區域。短暫區域進一步劃分爲通道,通道是連續的內存空間,其中可以包含用於迭代的短暫內存分配。然而,通道又不僅僅是關於內存。實現通道內串行的迭代過程以及基於 GPU 流的通道間並行處理,其中,每條通道都可以分配給多個 DL 任務。
首先,通過實現一個能感知應用程序的箱式內存分配器 (application-aware bin-based memory allocator) 來解決這個問題,以減少內存碎片。這種方法打破了通常在 DL 框架中使用的內存優化,因爲它們假設一次運行一個作業。將短暫區域劃分爲通道並不能消除內存碎片,它會將通道內的碎片移動到通道級別的碎片,只不過解決通道級別的碎片化要相對容易一些。在通道的情況下,所分配的內存在每次迭代結束時完全釋放,並在下一次迭代開始時返回,畢竟它們是短暫的內存。因此,碎片整理幾乎是自動進行的,無需任何成本,也不需要額外的內存移動。
在進行通道內存分配的過程中,始終保持滿足下式:

MLSys 提前看 | 機器學習的分佈式優化方法

其中,Pi 和 Ei 分別是任務 i 的持久性內存(模型和框架內部)和短暫內存,Lj 表示通道 j 的通道大小,同時也被定義爲通道中所有工作的最大短暫內存使用數。C 是 GPU 的容量。Salus 通過確保所有允許的作業都分配有足夠的持久內存容量,併爲具有最大臨時內存需求的迭代保留足夠的內存,提高了內存的利用率,同時也確保了通道中至少有一個作業可以繼續。
作者也認爲:「如何組織通道分配是一個懸而未決的問題。 我們通過實驗認爲使用我們的算法非常有效,但是給定一組任務,找到最優通道數存在更多其它的可能。
4、調度策略
通過使用細粒度的 GPU 共享原語,Salus 可以將多個作業打包在一起以提高效率,優先搶佔長時間運行的作業而不是較短的作業(或基於其他優先級標準),此外,還有很多不同的調度策略值得進一步探索。在這篇文章中作者試用了簡單的調度策略,包括 PACK (目標是優化資源利用)、SRTF (最短剩餘時間優先)和 FAIR (在當前任務中平均分配資源)。
【實驗分析】
本文將 Salus 與 TensorFlow 集成進行實驗,所有的實驗都是在一臺基於 x86_64 的 Intel Xeon E5-2670 機器上進行的,帶有 2 個 NVIDIA Tesla P100 GPU。每個 GPU 都有 16GB 的片上存儲器,以及使用 Tensor-Flow v1.5.0 和 CUDA 8.0。實驗中主要基準是當今 GPU 集羣中常用的 FIFO 調度,此外還與 NVIDIA MPS 進行了比較。
首先,評估 Salus 對訓練的影響,對比方法包括 FIFO、SRTF、PACK 和 FAIR。圖 11 中實驗證明了 Salus 允許快速搶佔內存,同時又允許實現最短剩餘時間優先(SRTF)調度策略。考慮長作業任務,一個大的訓練工作已經運行了一段時間,然後用戶想快速地爲較小的網絡做一些超參數調整的測試。如果沒有 Salus,用戶只能等到大的工作完成才能開始新的測試-這是 HOL 阻塞的一個例子。而 Salus 能夠通過高效切換來實現搶佔,以運行短作業,並在稍後恢復較大的作業。圖 11 (a)中的任務爲:當作業 #1 到達時,後臺作業 #0 立即停止,Salus 切換到運行新到達的較短作業。作業 #2 比作業 #3 來得早,但由於作業 #3 較短,所以它是先安排的。最後,由於作業 #5 較短,因此作業 #4 被搶佔,並讓作業 #5 運行到完成。在該過程中,後臺作業 #0 僅在沒有其他較短作業存在時才被調度。圖 11 (b)是另一個 Salus 快速切換能力的例子。它是以秒爲單位的內存分配活動的可視化:在作業切換時,第二個作業的迭代在第一個作業停止後立即開始。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 11. 使用 SRTF 運行長任務的詳細信息。在兩個切片中,時間都是標準化的
圖 12 中實驗展示了 Salus 如何允許多個 DL 作業之間的秒粒度公平共享,而不是分鐘粒度。在這兩種情況下都考慮單一的 GPU 通道。一共包括 4 個訓練任務:googlenet_100、resnet50_25、alexnet 100 和 resnet50_50 在實驗過程中處於活動狀態,Salus 嘗試使其 GPU 時間相等。同樣,所有的切換都發生在亞秒的粒度。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 12. 使用 FAIR 的長任務內存使用情況
其次,作者對於 Salus 在超參調參情況下的性能進行了實驗。作者評估了兩組超參調參任務:resnet50_50 和 superres_128,分別用於圖像分類和圖像分辨率增強。每組任務包含 300 個作業,當 300 個作業全部完成時代表一個任務完成。使用 FIFO (在 TensorFlow 中)和 Salus 實現的最大完工時間的比較如圖 13 所示。在 resnet50_50 的情況下,Salus 有 1.07 倍的改進,而 superres_128 中 Salus 的最大完工時間改進是 2.38 倍。在 resnet50_50 中幾乎沒有什麼改進,這是因爲即使 GPU 有足夠的內存將許多作業放在一起,計算也很可能成爲此時完成任務的瓶頸。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 13. 超參調參任務情況
【文章小結】
現代 GPU 及其運行時不允許在 GPU 中共存多個進程。對於 DL 任務來說,執行一個任務過程中空閒狀態的內存無法釋放給其它作業使用,這導致了巨大的資源浪費、性能損失、效率降低以及出現線頭阻塞 (Head-of-lineblocking,HOL)。本文提出的 Salus 是一個整合的執行服務,它支持在複雜的、未修改的 DL 作業之間細粒度的 GPU 共享。
Salus 是一種嘗試,它還帶來了很多需要進一步研究解決的問題。首先,Salus 提供了一種機制,但策略問題是:在共享 GPU 上運行 DL 作業的最佳調度算法究竟是什麼?本文探討了集中簡單的調度策略,但是對於最佳調度策略的判斷依據未做討論。其次,雖然本文沒有重點介紹,但 Salus 可以擴展到同一臺機器上的多個 GPU 甚至其他加速器。最後,作者提到,他們在下一步的工作中計劃利用 RDMA 將 Salus 擴展到多臺機器上的 GPU 中。
Federated Optimization in Heterogeneous Networks
Distributed and parallel learning algorithms topichttps://arxiv.org/pdf/1812.06127.pdf
聯邦學習已經成爲了一種在遠程設備網絡中分發機器學習模型訓練的有效方法。雖然都是針對機器學習的分佈式優化,但是聯邦學習與傳統的分佈式優化方法(例如本篇文章中我們分析的前兩篇論文)有兩個關鍵的區別:高度的系統異質性和統計異質性。爲了處理異質性和解決高通信成本問題,聯邦學習採用的是局部更新和低參與度的優化方法。FedAvg 是一種著名的聯邦學習方法:在每次迭代中,FedAvg 首先在 K 個設備上執行 E 輪隨機梯度下降(SGD)階段,其中 E 是一個小的表示 Epoch 次數的常數,K 是網絡中所有設備的一小部分。然後,這些設備將其模型更新傳遞到中央服務器,並在那裏對其進行平均化處理。雖然 FedAvg 在處理異質環境問題中顯示出了其有效性,但它並沒有完全解決與異質相關的潛在挑戰。

關於聯邦學習,機器之心做過重要研究進展的梳理,感興趣的讀者可以讀一讀相關文章:打破數據孤島:聯邦學習近期重要研究進展

在存在系統異質性的情況下,基於 FedAvg 框架,各個設備並不能根據自身的資源情況完成工作量可變的工作。相反,如果在給定的時間內,設備沒有能夠在 E 輪迭代中返回局部優化的結果,FedAvg 會直接刪除該設備。這種直接刪除沒有及時反饋局部優化結果的設備(如 FedAvg)或簡單收集設備中的部分信息(如 FedProx 中修正項爲 0 的情況下)的操作都會在一定程度上增大系統的統計異質性,並且會對收斂行爲產生不利影響。爲了解決聯邦學習中的異質性問題,本文提出了 FedProx 框架。FedProx 引入了一個修正項(the proximal term)來提高整體框架的穩定性,該修正項的本質是針對局部模型中的參數和全局模型中的參數增加差異性的限制,從而爲解釋全局與部分局部信息之間的異質性提供理論依據。
【FedProx 詳解】
首先回顧一下經典的 FedAvg 方法。目標函數爲下式:

MLSys 提前看 | 機器學習的分佈式優化方法

其中,N 爲設備總數,pk≥0 表示每個設備更新的權重。一般來說,本地優化目標衡量的是不同數據分佈的本地經驗風險 Dk,例如

MLSys 提前看 | 機器學習的分佈式優化方法

其中,n_k 表示第 k 個設備上有 n_k 個樣本。一般設置爲 p_k=n_k/n,其中 n 爲全部 n_k 的總和。一般認爲 Fk(w) 爲非凸的。
爲了減少通信量,聯邦優化方法中的一種常用技術是,在每個設備上,使用基於設備數據的局部目標函數作爲全局目標函數的代理。在每次外部迭代中,選擇一個參與本次迭代的設備子集,並使用局部優化算子優化每個選定設備上的局部目標函數。然後,這些設備將其本地模型更新傳遞給中央服務器,中央服務器聚合它們並相應地更新全局模型。在這種情況下,如果能夠做到非精確地求解每個局部目標函數的最優解,就能夠保證整體的靈活性能,這也意味着必須允許根據執行的本地迭代次數(與更精確的本地解決方案相對應的附加本地迭代)調整本地計算量與通信量。從數學上表示,這是一種γ-不準確解。
FedAvg 中有一個值得注意的問題是:FedAvg 中 E 的選擇對全局目標函數的收斂性起着重要作用。一方面,E 越大就意味着存在較多的局部計算和較少的設備間通信,這能夠極大地提高全局目標函數的整體收斂速度。但是從另外一個角度分析,對於不同的(異質的)局部目標 Fk,設置較大的 E 值,卻可能導致每個設備都致力於實現其局部目標函數的最優,而不是全局目標函數的最優,這反而會影響全局目標函數的收斂甚至導致發散。
本文提出的框架 FedProx 與 FedAvg 類似,它在每一輪中選擇一個參與更新的設備子集,執行本地更新,然後對這些更新進行平均化處理以形成全局更新。然而,FedProx 做了一些簡單而關鍵的修改,使得其具有收斂性保證。
1、容忍部分工作(Tolerating partial work)
在分佈式工作的聯邦學習網絡中,不同的設備資源不同,例如硬件條件、網絡環境、電池水平等,因此不可能要求設備完成一樣多的工作。在 FedProx 中,我們通過允許基於可用系統資源的設備在本地執行可變工作量的工作來改進 FedAvg,最後聚合從各個設備發出的「部分」解決方案(與完全刪除這些設備的策略是不同的)。此時,FedProx 執行的是 (γ_k)^t-不準確解。(γ_k)^t-不準確解測量在第 t 輪時爲解決設備 k 上的局部子問題而執行的局部計算量。局部優化過程的迭代次數爲 (γ_k)^t 的近似。通過引入 (γ_k)^t-不準確解,能夠有效擴展 FedAvg 的收斂結果,從而解決與系統異質性相關的問題。
2、修正項(Proximal term)

允許聯邦學習框架具備靈活的性能的關鍵是有針對性的實現每個設備中的局部目標函數優化,這就要求必須允許設備能夠根據每次執行的本地迭代次數(與更精確的本地解決方案相對應的附加本地迭代)自動調整本地計算量與通信量。
向局部目標函數中增加一個修正項,以有效地限定可變化的局部更新的影響。特別地,不是僅僅最小化局部函數 Fk,而是令設備 k 使用它的局部優化算子來近似地最小化以下目標函數 h_k:

MLSys 提前看 | 機器學習的分佈式優化方法

增加修正項有兩個有益效果:(1)通過使得局部的更新更加接近於初始(全局)模型來解決聯邦學習框架中不同設備間的統計異質性問題,而不需要手動設置局部 E 的大小。(2)它允許安全地整合各個局部設備由於系統異質性所導致的可變數量的本地工作。完整的 FedProx 工作流程如下:

MLSys 提前看 | 機器學習的分佈式優化方法

最後,作者提到,FedProx 只是對 FedAvg 進行了很小的修改,這使得我們能夠對目前已經出現的大量的 FedAvg 方法 / 框架進行推理,將本文的改進方法與相關的方法 / 框架進行集成。特別的,也可以認爲 FedAvg 是 FedProx 的一種特殊情況,(1)μ=0 (2)局部優化使用 SGD (3)跨設備和更新輪次(即,不存在系統概念)的常數γ(對應於本地 epoch 的數量)。
【實驗分析】
本文使用了合成數據和真實數據庫(MINIST、FEMNIST、Shakespeare、Sent140)進行實驗,使用 TensorFlow,以及 SGD 作爲局部優化算子。對於每個數據集,調整 FedAvg 上的學習率(E=1 且不存在系統異質性),並對該數據集上的所有實驗使用相同的學習率。對於所有數據集上的所有實驗,將所選設備的數量設置爲 10。基於全局目標函數 f(w) 衡量最終效果。圖 14 給出在不同數據庫中關於異質網絡中收斂性的實驗結果。通過比較 FedAvg 和 FedProx (μ=0),在存在系統異質性的情況下,允許各個設備執行可變的工作量有助於整體目標函數的收斂。將 FedProx (μ=0)與 FedProx (μ>0)進行比較,證明了所增加的修正項的優點。μ>0 的 FedProx 具有更穩定的收斂性,此外能夠在存在系統異質性(50% 和 90% 離散)和不存在系統異質性(0% 離散)的情況下收斂。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 14. 與 FedAvg 相比,FedProx 在異質網絡中的收斂性得到了顯著的改善

圖 15 中的實驗通過強制每個設備運行相同數量的 epoch (E)來消除系統異質性的影響。在這個設置中,FedProx (μ=0)將簡化爲 FedAvg。上面一行的圖示中,給出四個統計異質性從左到右增加的合成數據集上的訓練損失。其中,μ=0 的方法對應於 FedAvg 的實驗結果。異質性的增加會導致更差的收斂性,但是當μ>0 時,能夠緩解這一問題。下面一行圖示顯示了四個合成數據集的相應差異性度量(梯度方差)。該度量能夠有效捕獲數據統計異質性,由實驗結果可知,該度量的趨勢與訓練損失一致;較小的差異表示更好的收斂性。

MLSys 提前看 | 機器學習的分佈式優化方法

圖 15. 數據異質性對收斂性的影響**
文章小結**

在這篇文章中,作者提出了 FedProx--一個解決聯邦學習固有的系統和統計異質性問題的優化框架。FedProx 允許在設備之間局部地執行可變量的工作,並且依賴一個修正項來確保方法的穩定性。作者對一組聯邦數據集的實證評估驗證了其理論分析,並證明了 FedProx 框架可以顯著改善現實異質網絡中聯邦學習的收斂行爲。
作者介紹:仵冀穎,工學博士,畢業於北京交通大學,曾分別於香港中文大學和香港科技大學擔任助理研究員和研究助理,現從事電子政務領域信息化新技術研究工作。主要研究方向爲模式識別、計算機視覺,愛好科研,希望能保持學習、不斷進步。
關於機器之心全球分析師網絡 Synced Global Analyst Network
機器之心全球分析師網絡是由機器之心發起的全球性人工智能專業知識共享網絡。在過去的四年裏,已有數百名來自全球各地的 AI 領域專業學生學者、工程專家、業務專家,利用自己的學業工作之餘的閒暇時間,通過線上分享、專欄解讀、知識庫構建、報告發布、評測及項目諮詢等形式與全球 AI 社區共享自己的研究思路、工程經驗及行業洞察等專業知識,並從中獲得了自身的能力成長、經驗積累及職業發展。
感興趣加入機器之心全球分析師網絡?點擊閱讀原文,提交申請。

來源鏈接:mp.weixin.qq.com