第三屆機器學習與系統會議（MLSys 2020）将于 2020 年 3 月 2 日至 4 日在美國奧斯汀會議中心舉行。MLSys 是 2018 年新成立的一個聚焦機器學習在系統、軟體、硬體等多個綜合領域中應用研究的學術會議。
随着機器學習算法和模型的不斷發展，傳統的軟硬體平台、部署環境等無法支撐機器學習的應用，這也成為了目前機器學習方法落地及大規模推廣應用的主要困難之一。目前，有關于 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 topic
https://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 将成為瓶頸。
圖 1. 群集上每個 8-GPU 伺服器中配置設定給 Cloud-X 上 40000 個多 GPU 作業的 GPU 數
此外，這些限制還會導緻連結使用不足，如圖 2 所示。
圖 2. DGX-1P 中 NCCL 與本文提出的 Blink 在 6-GPUs 上的廣播比較
通過将 GPU 之間的連結模組化為圖，前期的研究結果表明，包裝生成樹 (Packing Spanning Trees) 能夠生成從有選擇的根頂點到有向圖中的所有其他頂點的最大流。基于此研究，作者認為一對多協定（如使用根節點的生成樹進行廣播）是克服鍊路使用率不足的一個潛在有效選擇。當然，除了像廣播這樣隻轉發資料的操作之外，還需要實作像 AllReduce 這樣的通信原語，即可以被模組化為在一個方向上減少并前進（面向根的方向），然後在另一個方向廣播。
【Blink 詳解】
圖 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 從根渦生成，沿着有向連結擴充到其它渦點。通過确定滿足能力限制的最大權重樹狀圖，可以解決在廣播中确定最佳時間表的問題。
由上式，給定一個圖 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：
其中，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 可以實作最佳的資料分割。
其中，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）個根。第三階段根據每個伺服器的本地根目錄，将第二階段的結果廣播給伺服器中的所有節點。
圖 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 倍。
圖 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 的更高性能。
圖 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 數成正比。
圖 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% 幾何平均值）。
圖 8. DGX-1V 機器内的閃爍端到端訓練時間縮短（ImageNet1K）
在多伺服器的情況下，圖 9（a）顯示 Blink 比 Horovod 的 NCCL/MPI 高出 11%，與單伺服器訓練相比，Blink 在 NCCL 方面的改進有所減少。為了了解更快的互連将如何改變性能，圖 9（b）給出了一個改變跨機器帶寬的模拟結果。實驗比較了 100MB 資料的吞吐量，發現随着跨機器帶寬的增加，Blink 的設計将帶來更顯著的端到端優勢。
圖 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 topic
https://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 圖 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 架構中使用的記憶體優化，因為它們假設一次運作一個作業。将短暫區域劃分為通道并不能消除記憶體碎片，它會将通道内的碎片移動到通道級别的碎片，隻不過解決通道級别的碎片化要相對容易一些。在通道的情況下，所配置設定的記憶體在每次疊代結束時完全釋放，并在下一次疊代開始時傳回，畢竟它們是短暫的記憶體。是以，碎片整理幾乎是自動進行的，無需任何成本，也不需要額外的記憶體移動。
在進行通道記憶體配置設定的過程中，始終保持滿足下式：
其中，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 快速切換能力的例子。它是以秒為機關的記憶體配置設定活動的可視化：在作業切換時，第二個作業的疊代在第一個作業停止後立即開始。
圖 11. 使用 SRTF 運作長任務的詳細資訊。在兩個切片中，時間都是标準化的
圖 12 中實驗展示了 Salus 如何允許多個 DL 作業之間的秒粒度公平共享，而不是分鐘粒度。在這兩種情況下都考慮單一的 GPU 通道。一共包括 4 個訓練任務：googlenet_100、resnet50_25、alexnet 100 和 resnet50_50 在實驗過程中處于活動狀态，Salus 嘗試使其 GPU 時間相等。同樣，所有的切換都發生在亞秒的粒度。
圖 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 有足夠的記憶體将許多作業放在一起，計算也很可能成為此時完成任務的瓶頸。
圖 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
topic
https://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 方法。目标函數為下式：
其中，N 為裝置總數，pk≥0 表示每個裝置更新的權重。一般來說，本地優化目标衡量的是不同資料分布的本地經驗風險 Dk，例如
其中，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：
增加修正項有兩個有益效果：（1）通過使得局部的更新更加接近于初始（全局）模型來解決聯邦學習架構中不同裝置間的統計異質性問題，而不需要手動設定局部 E 的大小。（2）它允許安全地整合各個局部裝置由于系統異質性所導緻的可變數量的本地工作。完整的 FedProx 工作流程如下：
本文使用了合成資料和真實資料庫（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% 離散）的情況下收斂。
圖 14. 與 FedAvg 相比，FedProx 在異質網絡中的收斂性得到了顯著的改善
圖 15 中的實驗通過強制每個裝置運作相同數量的 epoch（E）來消除系統異質性的影響。在這個設定中，FedProx（μ=0）将簡化為 FedAvg。上面一行的圖示中，給出四個統計異質性從左到右增加的合成資料集上的訓練損失。其中，μ=0 的方法對應于 FedAvg 的實驗結果。異質性的增加會導緻更差的收斂性，但是當μ>0 時，能夠緩解這一問題。下面一行圖示顯示了四個合成資料集的相應差異性度量（梯度方差）。該度量能夠有效捕獲資料統計異質性，由實驗結果可知，該度量的趨勢與訓練損失一緻；較小的差異表示更好的收斂性。
圖 15. 資料異質性對收斂性的影響
文章小結
在這篇文章中，作者提出了 FedProx--一個解決聯邦學習固有的系統和統計異質性問題的優化架構。FedProx 允許在裝置之間局部地執行可變量的工作，并且依賴一個修正項來確定方法的穩定性。作者對一組聯邦資料集的實證評估驗證了其理論分析，并證明了 FedProx 架構可以顯著改善現實異質網絡中聯邦學習的收斂行為。
作者介紹：仵冀穎，工學博士，畢業于北京交通大學，曾分别于香港中文大學和香港科技大學擔任助理研究員和研究助理，現從事電子政務領域資訊化新技術研究工作。主要研究方向為模式識别、計算機視覺，愛好科研，希望能保持學習、不斷進步。