Horovod 是Uber于2017年釋出的一個易于使用的高性能的分布式訓練架構，在業界得到了廣泛應用。本系列将通過源碼分析來帶領大家了解 Horovod。系列大約有15 ～ 18 篇，本文是系列第一篇，介紹相關背景知識。
[源碼解析] 深度學習分布式訓練架構 Horovod --- (1) 基礎知識
目錄
-
- 0x00 摘要
- 0x01 分布式并行訓練
- 1.1 分布式并行訓練的必要
- 1.2 分布式訓練
- 1.3 訓練并行機制
- 1.3.1 三種機制
- 1.3.2 如何使用
- 1.4 資料并行訓練
- 0x02 通信 & 架構
- 2.1 方法和架構
- 2.2 異步 vs 同步
- 0x03 具體架構
- 3.1 MapReduce
- 3.2 參數伺服器 (PS)
- 3.3 Decentralized Network
- 0x04 All Reduce
- 4.1 參數伺服器劣勢
- 4.2 并行任務通信分類
- 4.3 MPI_AllReduce
- 0x05 ring-allreduce
- 5.1 特點
- 5.2 政策
- 5.2.1 結構
- 5.2.2 Scatter-Reduce
- 5.2.2.1 分塊
- 5.2.2.2 第一次疊代
- 5.2.2.3 全部疊代
- 5.2.3 Allgather
- 5.2.3.1 第一次疊代
- 5.2.3.2 全部疊代
- 5.2.4 Horovod 架構圖
- 5.2.5 百度思路
- 5.3 差別
- 0xEE 個人資訊
- 0xFF 參考
Horovod 是Uber于2017年釋出的一個易于使用的高性能的分布式訓練架構，在業界得到了廣泛應用。
本系列将通過源碼分析來帶領大家了解 Horovod。系列大約有15 ～ 18 篇，本文是系列第一篇，介紹相關背景知識。
我們首先要介紹下分布式并行訓練。
傳統的模型訓練中，疊代計算隻能利用目前程序所在主機上的所有硬體資源，可是單機擴充性始終有限。而目前的機器學習有如下特點：
- 樣本數量大。目前訓練資料越來越多，在大型網際網路場景下，每天的樣本量可以達到百億級别。
- 特征次元多。因為巨大樣本量導緻機器學習模型參數越來越多，特征次元可以達到千億或者萬億級别。
- 訓練性能要求高。雖然樣本量和模型參數巨大，但是業務需要我們在短期内訓練出一個優秀的模型來驗證。
- 模型實時上線。對于推薦資訊類應用，往往要求根據使用者最新行為及時調整模型進行預測。
是以，單機面對海量資料和巨大模型時是無能為力的，有必要把資料或者模型分割成為多分，在多個機器上借助不同主機上的硬體資源進行訓練加速。
本文所說的訓練，指的是利用訓練資料通過計算梯度下降的方式疊代地去優化神經網絡參數，并最終輸出網絡模型的過程。在單次模型訓練疊代中，會有如下操作：
- 首先利用資料對模型進行前向的計算。所謂的前向計算，就是将模型上一層的輸出作為下一層的輸入，并計算下一層的輸出，從輸入層一直算到輸出層為止。
- 其次會根據目标函數，我們将反向計算模型中每個參數的導數，并且結合學習率來更新模型的參數。
而并行梯度下降的基本思想便是：多個處理器分别利用自己的資料來計算梯度，最後通過聚合或其他方式來實作并行計算梯度下降以加速模型訓練過程。 比如兩個處理器分别處理一半資料計算梯度 g_1, g_2，然後把兩個梯度結果進行聚合更新，這樣就實作了并行梯度下降。
由于使用小批量算法，可以把寬度（∝W）和深度（∝D）的前向傳播和反向傳播分發到并行的處理器上，這樣深度訓練的并行機制主要有三種：
- 第一個是模型并行機制（按照網絡結構分區）。
- 通常是針對一個節點無法存下整個模型的情況下，去對圖進行拆分。
- 将模型參數進行分布式存儲。計算機上每個計算可以模組化為一個有向無環圖（DAG），頂點是計算指令，邊是資料依賴（資料流）。 "基于圖去拆分" 會根據每一層中的神經元（即四維張量中的C、H或W維）來把一張大的圖拆分成很多部分，每個部分都會在很多裝置上去計算。
- 或者可以這麼了解：深度學習的計算主要是矩陣運算，有時候矩陣非常大無法放到顯存中，就隻能把超大矩陣拆分了放到不同卡上計算。
- 模型較後部分的計算必須等前面計算完成，是以不同節點間的計算實際是串行的。但每個部分計算互不妨礙，更像是流水線結構。
- 第二個是資料并行機制（按照輸入樣本分區）。
- 更多場景下我們模型規模不大，在一張 GPU 可以容納，但是訓練資料量會比較大，這時候就采用資料并行機制。
- 具體就是在多節點上并行分割資料和訓練。
- 第三種不常用的并行機制是 流水線機制（按層分區）。
- 在深度學習中，流水線可以是指重疊的計算，即在一層和下一層之間（當資料準備就緒時）連續計算；或者根據深度劃分DNN，将層配置設定給特定處理器。
- 流水線可以看作是資料并行的一種形式，因為元素（樣本）是通過網絡并行處理的，但也可以看作是模型并行，因為流水線的長度是由DNN結構決定的。
具體可見下圖：
資料的并行往往意味着計算性能的可擴充，而模型的并行往往意味着記憶體使用的可擴充。
需要注意的是：資料并行和模型并行也并不沖突，兩者可以同時存在，而流水線機制也可以和模型并行一起混用。比如，DistBelief分布式深度學習系統結合了三種并行政策。訓練在同時複制的多個模型上訓練，每個模型副本在不同的樣本上訓練（資料并行），每個副本上，依據同一層的神經元（模型并行性）和不同層（流水線）上劃分任務，進行分布訓練。
另外也需要根據具體問題具體分析，比如現代卷積神經網絡主要由兩種層構成，他們具有不一樣的屬性和性能。
- 卷積層，占據了90% ~ 95% 的計算量，5% 的參數，但是對結果具有很大的表達能力。
- 全連接配接層，占據了 5% ~ 10% 的計算量， 95% 的參數，但是對于結果具有相對較小的表達的能力。
綜上：卷積層計算量大，所需參數系數 W 少，全連接配接層計算量小，所需參數系數 W 多。是以對于卷積層适合使用資料并行，對于全連接配接層适合使用模型并行。
我們本系列主要讨論資料并行訓練（其中的一種架構）。
資料并行訓練隻是一種邏輯架構。我們從沐神的書裡面摘錄：
假設機器上有\(k\)個GPU。給定要訓練的模型，每個GPU将獨立地維護一組完整的模型參數，盡管GPU上的參數值是相同且同步的。例如，下圖示範了在\(k=2\)時使用資料并行的訓練。一般來說，訓練過程如下：[源碼解析] 深度學習分布式訓練架構 Horovod (1) --- 基礎知識
- 在訓練的任何疊代中，給定一個随機的小批量，我們将該小批量中的樣本分成\(k\)個部分，并将它們均勻地分在多個GPU上。
- 每個GPU根據配置設定給它的小批量子集計算模型參數的損失和梯度。
- 将\(k\)個GPU中每個GPU的局部梯度聚合以獲得目前的小批量随機梯度。
- 聚合梯度被重新配置設定到每個GPU。
- 每個GPU使用這個小批量随機梯度來更新它維護的完整的模型參數集。
前面提到并行梯度下降的例子：兩個處理器分别處理一般資料計算梯度 g_1, g_2，然後把兩個梯度結果進行聚合，最後再把最新參數發給各個分布計算單元，這種訓練算法叫模型一緻性方法（consistent model methods）。這就涉及到了通信問題，即如何做聚合。
一般有兩種通信方法：Share memory 和 Message passing。
- Share memory 就是所有處理器共享同一塊記憶體，這樣通信很容易，但是同一個節點内的處理器之間才可以共享記憶體，不同節點處理器之間無法共享記憶體。
- Message passing 就是不同節點之間用消息（比如基于 TCP/IP 或者 RDMA）進行傳遞/通信，這樣容易擴充，可以進行大規模訓練。
是以我們知道，Message passing 才是解決方案，于是帶來了問題：如何協調這些節點之間的通訊。
有兩種架構：
- Client-Server 架構: 一個 server 節點協調其他節點工作，其他節點是用來執行計算任務的 worker。
- Peer-to-Peer 架構：每個節點都有鄰居，鄰居之間可以互相通信。
異步 vs 同步 是通信的另外一個側面。
在資料并行訓練之中，各個計算裝置分别根據各自獲得的batch，前向計算獲得損失，進而反向傳播計算梯度。計算好梯度後，就涉及到一個梯度同步的問題：每個 計算裝置 都有根據自己的資料計算的梯度，如何在不同GPU之間維護模型的不同副本之間的一緻性。 如果不同的模型以某種方式最終獲得不同的權重，則權重更新将變得不一緻，并且模型訓練将有所不同。
怎麼做這個同步就是設計分布式機器學習系統的一個核心問題。
分布式訓練的梯度同步政策可分為異步（asynchronous）梯度更新 和 同步（synchronous）梯度更新機制。
- 同步指的是所有的裝置都是采用相同的模型參數來訓練，等待所有裝置的mini-batch訓練完成後，收集它們的梯度然後取均值，然後執行模型的一次參數更新。
- 同步訓練相當于通過聚合很多裝置上的mini-batch形成一個很大的batch來訓練模型，Facebook就是這樣做的，但是他們發現當batch大小增加時，同時線性增加學習速率會取得不錯的效果。
- 同步訓練看起來很不錯，但是實際上需要各個裝置的計算能力要均衡，而且要求叢集的通信也要均衡。
- 因為每一輪結束時算得快的節點都需等待算得慢的節點算完，再進行下一輪疊代。類似于木桶效應，一個拖油瓶會嚴重拖慢訓練進度，是以同步訓練方式相對來說訓練速度會慢一些。這個拖油瓶一般就叫做 straggler。
- 異步訓練中，各個裝置完成一個mini-batch訓練之後，不需要等待其它節點，直接去更新模型的參數，這樣總體會訓練速度會快很多。
- 異步訓練的一個很嚴重的問題是梯度失效問題（stale gradients），剛開始所有裝置采用相同的參數來訓練，但是異步情況下，某個裝置完成一步訓練後，可能發現模型參數其實已經被其它裝置更新過了，此時這個梯度就過期了，因為現在的模型參數和訓練前采用的參數是不一樣的。由于梯度失效問題，異步訓練雖然速度快，但是可能陷入次優解（sub-optimal training performance）。
具體如下圖所示：
這兩種更新方式各有優缺點：
- 異步更新可能會更快速地完成整個梯度計算。
- 同步更新 可以更快地進行一個收斂。
選擇哪種方式取決于實際的應用場景。
接下來，我們看看幾種具體架構實作，先給出一個總體說明：
| 名稱 | 通信 | 架構 | 并行性 |
|---|---|---|---|
| MapReduce | 消息傳遞 | client-server | 批同步 |
| Parameter Server | 異步 | ||
| Decentralized | P2P | 同步或異步 |
MapReduce是Client-Server架構。以 Spark 為例看看是如何進行并行化：
- Spark Driver 就是 Server，Spark Executor 就是 Worker 節點，每一個梯度下降過程包含一個廣播、map和一個 reduce 操作。
- Server 定義了 map操作（就是具體的訓練），也可以把資訊廣播到worker節點。
- Worker 會執行 map 操作進行訓練，在此過程中，資料被分給 worker 進行計算。
- 計算結束後，worker把計算結果傳回 driver 處理，這個叫做reduce。
- 在 reduce 過程中，Server 節點對 worker 傳來的計算結果進行聚合之後，把聚合結果廣播到各個worker節點，進行下一次疊代。
Parameter server 也是一種client-server架構。和MapReduce不同在于 Parameter server 可以是異步的，MapReduce隻有等所有map都完成了才能做reduce操作。
在參數伺服器架構中，計算裝置被劃分為參數伺服器（PS）和worker。
- 參數伺服器（server）。是中心化的元件，主要是負責模型參數的存儲，平均梯度和交換更新。參數伺服器可以按照不同比例的參數伺服器和工作線程進行配置，每個參數伺服器都有着不同的配置資料。
- 工作節點（worker）。每個工作節點會負責它領域内的資料分片所對應模型參數的更新計算（比如前向和反向傳播這類計算密集的運算），同時它們又會向參數伺服器去傳遞它所計算的梯度，由參數伺服器來彙總所有的梯度，再進一步回報到所有節點。
具體步驟如下：
- 所有的參數都存儲在參數伺服器中，而 工作節點（worker） 是萬年打工仔。
- 工作節點 們隻負責計算梯度，待所有計算裝置完成梯度計算之後，把計算好的梯度發送給參數伺服器，這樣參數伺服器收到梯度之後，執行一定的計算（梯度平均等）之後，就更新其維護的參數，做到了在節點之間對梯度進行平均，利用平均梯度對模型進行更新。
- 然後參數伺服器再把更新好的新參數傳回給所有的工作節點，以對每個節點中的模型副本應用一緻化更新。
- 打工仔們會再進行下一輪的前後向計算。
邏輯如下：
+----------------------------------------------+
| Parameter Server |
| |
| |
| Compute : New P = P + Sum(Delta P ...) |
| |
| |
| Parameter 1, Parameter 2, Parameter 3 ... |
| |
| |
+--+----+----------+--+----------------+--+----+
^ | ^ | ^ |
| | | | | |
Delta P | | Delta P| | Delta P| |
+-----+ | | | | +------+
| +-----+ | | | |
| | New P | | New P +------+ |
| | | | | | New P
| v | | | |
| | v | v
+-+-----------+ +-----+--+---+ +-----+--+---+
| Worker | | Worker | | Worker |
| | | | | |
| | | | ...... | |
| Model | | Model | | Model |
+------+------+ +------+-----+ +----+-------+
^ ^ ^
| | |
| | |
+----+----+ +----+-----+ +--+-----+
| Data 1 | | Data 2 | | Data 3 |
+---------+ +----------+ +--------+
手機如下：
參數伺服器既可以用在資料并行上，也可以被用到模型并行訓練上。比如可以将模型切分為多個部分，存儲在不同的PS Server節點上，并提供友善的通路服務，這是參數伺服器的本質。
Decentralized Network 就是去中心化網絡，其特點如下：
- 去中心化網絡沒有一個中心節點，屬于 Peer-to-Peer 架構。
- 采用 message passing 進行通信，且節點隻和鄰居通信。
- 并行方式可以采用異步或者同步。
- 去中心化網絡的收斂情況取決于網絡連接配接情況：
- 連接配接越緊密，收斂性越快，當強連接配接時候，模型可以很快收斂；
- 如果不是強連接配接，它可能不收斂；
因為本系列是 Horovod，是以我們要先說說參數伺服器的劣勢，下一個系列我們再說參數伺服器優勢。
盡管參數伺服器可以提升表現，但仍然面臨幾個問題：
- 确定工作者與參數伺服器的正确比例：如果使用一個參數伺服器，它可能會成為網絡或計算瓶頸。 如果使用多個參數伺服器，則通信模式變為“All-to-All”，這可能使網絡飽和。
- 處理程式複雜性：參數伺服器的概念較多，這通常導緻陡峭的學習曲線和大量的代碼重構，壓縮了實際模組化的時間。
- 硬體成本 : 參數伺服器的引入也增加了系統的硬體成本。
人們發現，MPI_AllReduce 語義也可以很好地滿足資料并行訓練這一需要。
需要注意的是：AllReduce 既可以是去中心化，也可以是主從式的。
并行任務的通信一般可以分為 Point-to-point communication 和 Collective communication。
- P2P 這種模式隻有一個sender和一個receiver，實作起來比較簡單，比如NV GPU Direct P2P技術服務于單機多卡的單機卡間資料通信 。
- Collective communication包含多個sender和多個receiver，一般的通信原語包括 broadcast，gather,all-gather，scatter，reduce，all-reduce，reduce-scatter，all-to-all等。
AllReduce（對 m 個獨立參數 進行規約，并将規約結果傳回給所有程序）其實是最顯然和直接的分布式機器學習抽象，因為大部分算法的結構都是分布資料。在每個子集上面算出一些局部統計量，然後整合出全局統計量，并且再配置設定給各個節點去進行下一輪的疊代，這樣一個過程就是AllReduce。
- 可以把每個 Worker 看作是 MPI 概念中的一個程序，比如可以用 4 個 Worker 組成了一個組，該組由 4 個程序組成。我們在這四個程序中對梯度進行一次 MPI_AllReduce。
- 根據 MPI_AllReduce 的語義，所有參與計算的程序都有結果，是以梯度就完成了分發。隻要在初始化的時候，我們可以保證每個 Worker 的參數是一緻的，那在後續的疊代計算中，參數會一直保持一緻，因為梯度資訊是一緻的。
- AllReduce 跟 MapReduce 有類似，但後者采用的是面向通用任務處理的多階段執行任務的方式，而AllReduce則讓一個程式在必要的時候占領一台機器，并且在所有疊代的時候一直跑到底，來防止重新配置設定資源的開銷，這更加适合于機器學習的任務處理。
是以，MPI_AllReduce 的語義可以很好地解決深度學習中梯度同步的問題。但是到底能不能使用它，還是要看下層的實作對這一場景是否足夠友好。
百度提出使用新算法來平均梯度，取消 Reducer，并讓這些梯度在所有節點之間交流，這被稱為 ring-allreduce，他們使用 TensorFlow 也實作了這種算法（https://github.com/baidu-research/tensorflow-allreduce）。
Ring-Allreduce特點如下：
- Ring Allreduce 算法使用定義良好的成對消息傳遞步驟序列在一組程序之間同步狀态（在這種情況下為張量）。
- Ring-Allreduce 的命名中 Ring 意味着裝置之間的拓撲結構為一個邏輯環形，每個裝置都應該有一個左鄰和一個右鄰居，且本裝置隻會向它右鄰居發送資料，并且從它的左鄰居接受資料。
- Ring-Allreduce 的命名中的 Allreduce 則代表着沒有中心節點，架構中的每個節點都是梯度的彙總計算節點。
- 此種算法各個節點之間隻與相鄰的兩個節點通信，并不需要參數伺服器。是以，所有節點都參與計算也參與存儲，也避免産生中心化的通信瓶頸。
- 相比PS架構，Ring-Allreduce 架構是帶寬優化的，因為叢集中每個節點的帶寬都被充分利用。
- 在 ring-allreduce 算法中，每個 N 節點與其他兩個節點進行 2 * (N-1) 次通信。在這個通信過程中，一個節點發送并接收資料緩沖區傳來的塊。在第一個 N - 1 疊代中，接收的值被添加到節點緩沖區中的值。在第二個 N - 1 疊代中，接收的值代替節點緩沖區中儲存的值。百度的文章證明了這種算法是帶寬上最優的，這意味着如果緩沖區足夠大，它将最大化地利用可用的網絡。
- 在深度學習訓練過程中，計算梯度采用BP算法，其特點是後面層的梯度先被計算，而前面層的梯度慢于後面層，Ring-allreduce架構可以充分利用這個特點，在前面層梯度計算的同時進行後面層梯度的傳遞，進而進一步減少訓練時間。
- Ring架構下的同步算法将參數在通信環中依次傳遞，往往需要多步才能完成一次參數同步。在大規模訓練時會引入很大的通信開銷，并且對小尺寸張量（tensor）不夠友好。對于小尺寸張量，可以采用批量操作（batch）的方法來減小通信開銷。
綜上所述，Ring-based AllReduce 架構的網絡通訊量如果處理适當，不會随着機器增加而增加，而僅僅和模型 & 網絡帶寬有關，這針對參數伺服器是個巨大的提升。
Ring-based AllReduce 政策包括 Scatter-Reduce 和 AllGather 兩個階段。
-
首先是scatter-reduce，scatter-reduce 會逐漸交換彼此的梯度并融合，最後每個 GPU 都會包含完整融合梯度的一部分，是最終結果的一個塊。
假設環中有 N 個 worker，每個 worker 有長度相同的數組，需要将 worker 的數組進行求和。在 Scatter-Reduce 階段，每個 worker 會将數組分成 N 份資料塊，然後 worker 之間進行 N 次資料交換。在第 k 次資料交換時，第 i 個 worker 會将自己的 (i - k) % N 份資料塊發送給下一個 worker。接收到上一個 worker 的資料塊後，worker 會将其與自己對應的資料塊求和。
-
然後是allgather。GPU 會逐漸交換彼此不完整的融合梯度，最後所有 GPU 都會得到完整的最終融合梯度。
在執行完 Scatter-Reduce 後，每個 worker 的數組裡都有某個資料塊是最終求和的結果，現在需要将各資料塊的最後求和結果發送到每個 worker 上。和 Scatter-Reduce 一樣，也需要 N 次循環。在第 k 次循環時，第 i 個 worker 會将其第 (i+1-k)%N 個資料塊發送給下一個 worker 。接收到前一個 worker 的資料塊後，worker 會用接收的資料快覆寫自己對應的資料塊。進行 N 次循環後，每個 worker 就擁有了數組各資料塊的最終求和結果了。
環形結構如下，每個 GPU 應該有一個左鄰居和一個右鄰居；它隻會向其右側鄰居發送資料，并從其左側鄰居接收資料。：
scatter-reduce：會逐漸交換彼此的梯度并融合，最後每個 GPU 都會包含完整融合梯度的一部分。
為簡單起見，我們假設目标是按元素對單個大型浮點數數組的所有元素求和；系統中有 N 個 GPU，每個 GPU 都有一個相同大小的數組，在 allreduce 的最後環節，每個 GPU 都應該有一個相同大小的數組，其中包含原始數組中數字的總和。
首先，GPU 将陣列劃分為 N 個較小的塊（其中 N 是環中的 GPU 數量）。
接下來，GPU 将進行 N-1 次 scatter-reduce 疊代。
在每次疊代中，GPU 會将其一個塊發送到其右鄰居，并将從其左鄰居接收一個塊并累積到該塊中。每個 GPU 發送和接收的資料塊每次疊代都不同。第 n 個 GPU 通過發送塊 n 和接收塊 n – 1 開始，然後逐漸向後進行，每次疊代發送它在前一次疊代中接收到的塊。
在第一次疊代中，上圖中的五個 GPU 将發送和接收以下塊：
| GPU | 發送 | 收到 |
|---|---|---|
| 塊 0 | 塊 4 | |
| 1 | 塊 1 | |
| 2 | 塊 2 | |
| 3 | 塊 3 | |
| 4 |
scatter-reduce 的第一次疊代中的資料傳輸如下：
第一次發送和接收完成後，每個 GPU 都會有一個塊，該塊由兩個不同 GPU 上相同塊的總群組成。例如，第二個 GPU 上的第一個塊将是該塊中來自第二個 GPU 和第一個 GPU 的值的總和。
在後續疊代中，該過程繼續直到最後。最終每個 GPU 将有一個塊，這個塊包含所有 GPU 中該塊中所有值的總和。
下面系列圖展示了所有資料傳輸和中間結果，從第一次疊代開始，一直持續到scatter-reduce完成。
第一次疊代
第二次疊代
第三次疊代
第四次疊代
所有 scatter-reduce 傳輸後的最終狀态
在 scatter-reduce 步驟完成後，在每個 GPU 的數組中都有某一些值（每個 GPU 有一個塊）是最終值，其中包括來自所有 GPU 的貢獻。為了完成 allreduce，GPU 必須接下來交換這些塊，以便所有 GPU 都具有最終所需的值。
ring allgather 與 scatter-reduce 進行相同的處理（發送和接收的 N-1 次疊代），但是他們這次不是累積 GPU 接收的值，而隻是簡單地覆寫塊。第 n 個 GPU 開始發送第 n+1 個塊并接收第 n 個塊，然後在以後的疊代中始終發送它剛剛接收到的塊。
例如，在我們的 5-GPU 設定的第一次疊代中，GPU 将發送和接收以下塊：
| 圖形處理器 | ||
|---|---|---|
allgather 的第一次疊代中的資料傳輸如下。
第一次疊代完成後，每個 GPU 都會有最終數組的兩個塊。在接下來的疊代中，該過程繼續一直到最後，最終每個 GPU 将擁有整個數組的完全累加值。
下面系列圖展示了所有資料傳輸和中間結果，從第一次疊代開始，一直持續到全部收集完成。
Allgather 資料傳輸（疊代 1）
Allgather 資料傳輸（疊代 2）如下：
Allgather 資料傳輸（疊代 3）
Allgather 資料傳輸（疊代 4）
所有全部轉移後的最終狀态。
或者我們從百度的源碼中也可以直接看到思路，現在摘錄給大家。
具體代碼參見 https://github.com/baidu-research/tensorflow-allreduce/commit/66d5b855e90b0949e9fa5cca5599fd729a70e874#diff-3d530d590e551619acd776cfe7eaff06R517
tensorflow/contrib/mpi_collectives/ring.h
/* Perform a ring allreduce on the data. Allocate the necessary output tensor and
* store it in the output parameter.
*
* Assumes that all MPI processes are doing an allreduce of the same tensor,
* with the same dimensions.
*
* A ring allreduce is a bandwidth-optimal way to do an allreduce. To do the allreduce,
* the nodes involved are arranged in a ring:
*
* .--0--.
* / \
* 3 1
* \ /
* *--2--*
*
* Each node always sends to the next clockwise node in the ring, and receives
* from the previous one.
*
* The allreduce is done in two parts: a scatter-reduce and an allgather. In
* the scatter reduce, a reduction is done, so that each node ends up with a
* chunk of the final output tensor which has contributions from all other
* nodes. In the allgather, those chunks are distributed among all the nodes,
* so that all nodes have the entire output tensor.
*
* Both of these operations are done by dividing the input tensor into N
* evenly sized chunks (where N is the number of nodes in the ring).
*
* The scatter-reduce is done in N-1 steps. In the ith step, node j will send
* the (j - i)th chunk and receive the (j - i - 1)th chunk, adding it in to
* its existing data for that chunk. For example, in the first iteration with
* the ring depicted above, you will have the following transfers:
*
* Segment 0: Node 0 --> Node 1
* Segment 1: Node 1 --> Node 2
* Segment 2: Node 2 --> Node 3
* Segment 3: Node 3 --> Node 0
*
* In the second iteration, you'll have the following transfers:
*
* Segment 0: Node 1 --> Node 2
* Segment 1: Node 2 --> Node 3
* Segment 2: Node 3 --> Node 0
* Segment 3: Node 0 --> Node 1
*
* After this iteration, Node 2 has 3 of the four contributions to Segment 0.
* The last iteration has the following transfers:
*
* Segment 0: Node 2 --> Node 3
* Segment 1: Node 3 --> Node 0
* Segment 2: Node 0 --> Node 1
* Segment 3: Node 1 --> Node 2
*
* After this iteration, Node 3 has the fully accumulated Segment 0; Node 0
* has the fully accumulated Segment 1; and so on. The scatter-reduce is complete.
*
* Next, the allgather distributes these fully accumululated chunks across all nodes.
* Communication proceeds in the same ring, once again in N-1 steps. At the ith step,
* node j will send chunk (j - i + 1) and receive chunk (j - i). For example, at the
* first iteration, the following transfers will occur:
*
* Segment 0: Node 3 --> Node 0
* Segment 1: Node 0 --> Node 1
* Segment 2: Node 1 --> Node 2
* Segment 3: Node 2 --> Node 3
*
* After the first iteration, Node 0 will have a fully accumulated Segment 0
* (from Node 3) and Segment 1. In the next iteration, Node 0 will send its
* just-received Segment 0 onward to Node 1, and receive Segment 3 from Node 3.
* After this has continued for N - 1 iterations, all nodes will have a the fully
* accumulated tensor.
*
* Each node will do (N-1) sends for the scatter-reduce and (N-1) sends for the allgather.
* Each send will contain K / N bytes, if there are K bytes in the original tensor on every node.
* Thus, each node sends and receives 2K(N - 1)/N bytes of data, and the performance of the allreduce
* (assuming no latency in connections) is constrained by the slowest interconnect between the nodes.
*
*/
在中等規模模型情況下，all-reduce 更适合。當規模巨大時候則應該使用參數伺服器。
參數伺服器 适合的是高緯稀疏模型訓練，它利用的是次元稀疏的特點，每次 pull or push 隻更新有效的值。但是深度學習模型是典型的dense場景，embedding做的就是把稀疏變成稠密。是以這種 pull or push 的不太适合。而 網絡通信上更優化的 all-reduce 适合中等規模的深度學習。
又比如由于推薦搜尋領域模型的 Embedding 層規模龐大以及訓練資料樣本長度不固定等原因，導緻容易出現顯存不足和卡間同步時間耗費等問題，是以 all-reduce 架構很少被用于搜尋推薦領域。
至此，背景知識已經介紹完畢，下一篇我們開始介紹 Horovod 的使用。