[[191977]]

現在，機器學習的趨勢從傳統(tǒng)方法中的簡單模型 + 少量數據(人工標注樣本)，到簡單模型 + 海量數據(比如基于邏輯回歸的廣告點擊率預測)，再發(fā)展到現在復雜模型 + 海量數據(比如深度學習 ImageNet 圖像識別，基于 DNN 的廣告點擊率預測)。

總結下在工業(yè)屆常會用到的大規(guī)模機器學習的場景：

這次分享從這 3 部分展開：

1.并行計算編程技術

• 向量化
• Openmp
• GPU
• mpi

2.并行計算模型

• BSP
• SSP
• ASP
• Parameter Server

3.并行計算案例

• Xgboost 的分布式庫 Rabit
• Mxnet 的分布式庫 ps-lite

并行計算編程技術

首選提到并行編程技術，這是大規(guī)模機器學習的工程基礎。

向量化

向量化計算是一種特殊的并行計算的方式，相比于一般程序在同一時間只執(zhí)行一個操作的方式，它可以在同一時間執(zhí)行多次操作，通常是對不同的數據執(zhí)行同樣的一個或一批指令，或者說把指令應用于一個數組 / 向量。

在 X86 體系架構的 CPU 上，主要的向量化編程技術是 SSE 和 AVX。Intel 公司的單指令多數據流式擴展(SSE，Streaming SIMD Extensions)技術能夠有效增強 CPU 浮點運算的能力。現住主流的編譯器 GCC 和 Visual Studio 提供了對 SSE 指令集的編程支持，從而允許用戶在 C++ 代碼中不用編寫匯編代碼就可直接使用 SSE 指令的功能。Intel SSE 指令集支持的處理器有 16 個 128 位的寄存器，每一個寄存器可以存放 4 個(32 位)單精度的浮點數。SSE 同時提供了一個指令集，其中的指令可以允許把浮點數加載到這些 128 位的寄存器之中，這些數就可以在這些寄存器中進行算術邏輯運算，然后把結果放回內存。AVX 與 SSE 類似，AVX 將所有 16 個 128 寄存器擴充為 256 位寄存器，從而支持 256 位的矢量計算，理想狀態(tài)下，浮點性能 AVX 最高能達到 SSE 的 2 倍水平。移動設備上廣泛采用的 ARM 架構，ARM 向量指令 Neon 提供 16 個長度位 128 位的向量寄存器。

簡單點說：SSE 指令集的加速比為 4 倍，AVX 可以獲取 8 倍加速比。

使用也很簡單。

AVX 指令集編程示例：

for(i=0; i<cntBlock; ++i) 
   { 
       // [AVX] 加載 
       yfsLoad = _mm256_load_ps(p);  
       // [AVX] 單精浮點緊縮加法 
       yfsSum = _mm256_add_ps(yfsSum, yfsLoad);     
       //AVX 指令一次可以處理 8 個浮點數 
       p += 8; 
   } 
   // 合并. 
   q = (const float*)&yfsSum; 
   s = q[0] + q[1] + q[2] + q[3] + q[4] + q[5] + q[6] + q[7]; 

這是一個數組求和的加速例子。

現在主流編譯器 GCC 等都支持。

其次是大家最熟悉的多線程編程技術。

UNIX/Linux 中的 pthread， Windows 環(huán)境下的 WinThread。但是相對于機器學習并行來說，一方面采用多線程編程技術，開發(fā)成本較高，而且需要妥善處理同步互斥等問題;另一方面，不同平臺中使用多線程編程庫是不一樣的，這樣也會造成移植性問題。

Openmp

OpenMP 是一個支持共享存儲并行設計的庫，特別適宜多核 CPU 上的并行程序設計，它使得多線程編程的難度大大降低，是目前機器學習上多線程主流解決方案。

大家可以看看這個例子。我們很容易把傳統(tǒng)的 for 循環(huán)語句進行加速。OpenMP 也可以實現類似于 MapReduce 的計算范式。更詳細的大家可以參考 openmp 的官方文檔。

GPU

GPU 編程是目前很熱的并行計算方案。

這是 GPU 和 CPU 區(qū)別。

為什么 GPU 更快呢?

• CPU 主要是為串行指令而優(yōu)化，而 GPU 是為大規(guī)模并行運算而優(yōu)化。
• GPU 相對 CPU 來說，在同樣的芯片面積上，擁有更多的計算單元，這也使得 GPU 計算性能更加強大，而 CPU 則擁有更多的緩存和相關的控制部件。
• GPU 相對 CPU 來說擁有更高的帶寬。

CUDA 是目前主流的 GPU 編程。

這也是一個數組求和例子。大家可以看看 GPU 編程并不是很難，它和傳統(tǒng)程序編程區(qū)別是：

MPI

MPI 是一種多機并行解決方案，它的核心是消息的傳遞和接收，解決多級并行中的通信問題。

這是 MPI 程序執(zhí)行流程。MPI 的學習難度也是比較低的。

MPI_Init(…); 初始化環(huán)境

MPI_Comm_size(…) 獲取進程數

MPI_Comm_rank(…) 獲取進程序號

MPI_Send(…) 發(fā)送消息

MPI_Recv(…) 接收消息

MPI_Finalize() 并行結束函數

主要是這 6 個函數。

MPI 函數雖然很多，但是功能主要有兩大類：

一種是發(fā)送數據。

這種是接收數據做規(guī)約。很類似于大家常見的 MapReduce 吧。

總結一點，大家可以根據自己的硬件條件來選擇合適的并行計算解決方案。

這里要提醒一點，大家如果想 GPU 編程的話，使用 CUDA 技術化，一定要買 nvidia 的顯卡，因為其他的裝不上。

分布式機器學習系統(tǒng)需要解決的三個問題：

1. 如何更好的切分成多個任務
2. 如何調度子任務
3. 均衡各節(jié)點的負載

并行計算模型

BSP

這是一個通用的機器學習問題建模和優(yōu)化。大規(guī)模機器學習的核心就是梯度計算的并行化。BSP 是較早的一個并行計算模型，也是當前主流的并行計算模型之一。

每一步詳細分解下。

其計算過程也比較好理解，就是計算 ->同步 ->計算 ->同步......

BSP 具有如下優(yōu)點：

1. 它將處理器和路由器分開，強調了計算任務和通信任務的分開，而路由器僅僅完成點到點的消息傳遞，不提供組合、復制和廣播等功能，這樣做既掩蓋具體的互連網絡拓撲，又簡化了通信協議;
2. 采用障礙同步的方式以硬件實現的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔;

BSP 模型的這些特點使它成為并行計算的主流模型之一，開源 的 Mahout, Apache Huma, Spark mllib, Google Pregel, Graphlab, xgboost 等的并行實現都是基于 BSP 模型的。

BSP 模型在每一輪結論之后都需要進行一次同步，這很容易造成木桶效應，由于任務的切分中每個任務計算量并不是完全均勻的，而且在復雜的分布式計算環(huán)境下，每臺機器的硬件條件也是存在差異的，這就造成了 BSP 模型每一輪迭代的效率由最慢的計算任務來決定，為了緩解這個現象，SSP 模型被提出來了。

SSP

SSP 模型

我們把 SSP 中每個任務過程稱為 worker，SSP 模型通過設置一個 bound 來確定同步的時機。當最快的 worker 比最慢的 worker 超過這個 bound 時所有的 work 來就行一次參數的同步。這個 bound 可以根據迭代的次數，也可以根據參數更新的差值來確定。SSP 協議的好處在于，faster worker 會遇到參數版本過于 stale 的問題，導致每一步迭代都需要網絡通信，從而達到了平衡計算和網絡通信時間開銷的效果。

SSP 模型數學上證明是可以收斂的。

原因可以這么來解釋吧，就是條條大道通羅馬。

對于機器學習程序來說，中間結果的錯誤是可以容忍的，有多條路徑都可以收斂到最優(yōu)，因此少量的錯誤可類似于隨機噪聲，但不影響最終的收斂結果。盡快每一次迭代可能存在誤差，但是經過多輪迭代后，平均誤差趨近于零。盡管每次可能不是最優(yōu)的求解路徑，但是最終還是找到一條通往最優(yōu)解的整體路徑。盡管這條路徑不是最快的路徑，但是由于在通訊方面的優(yōu)勢，整體的求解速度相對于 BSP 來說還是更快一些，特別是在數據規(guī)模和參數規(guī)模非常大的情況下，在多機并行的環(huán)境下。

ASP

ASP 是一種完全異步的方式，相當于取消了 BSP 中的同步環(huán)節(jié)。

ASP 的運行速度更快，當然它是沒有收斂性保證的。

SSP 協議可以有效平衡計算和網絡通信的開銷。

對于非凸問題，BSP 和 SSP 收斂的最優(yōu)解可能不一樣。對于非凸優(yōu)化問題(比如說神經網絡)，有大量局部最優(yōu)解，隨機梯度下降(可以跳出局部最優(yōu)解)比批量梯度下降效果要更好。

Parameter Server

參數服務器是近來來在分布式機器學習領域非常火的一種技術。

Parameter Server 參數服務器中比較重要的是各個計算節(jié)點的參數同步問題。

Sequential： 這里其實是 synchronous task，任務之間是有順序的，只有上一個任務完成，才能開始下一個任務，也就是同步方式;Eventual： 跟 sequential 相反，所有任務之間沒有順序，各自獨立完成自己的任務，也就是異步的形式;Bounded Delay： 這是 sequential 跟 eventual 之間的折中，當最快計算任務比最慢計算任務快于一定閾值時進行等待，也可以當計算任務對梯度的累計更新值大于一定閾值時進行等待。

總結這 4 種模式的優(yōu)缺點：

并行計算案例

Xgboost 的分布式庫 Rabit

Xgboost 是目前非常牛的一個機器學習包，其分布式做得非常好，我們現在來看一下。

Xgboost 的分布式實現由如下幾個特點：

• OpenMp 支持多核并行
• CUDA 支持 GPU 加速
• Rabit 支持分布式

其核心就是 Rabit，Xgboost 將其分布式核心功能抽象出來，Rabit 是基于 BSP 模型的，通過兩個基本原語 Broadcast 和 AllReduce 來實現其分布式功能。Broadcase 和 AllReduce 與 MPI 中的功能基本上一致，設計思想類似，為什么不直接使用 MPI 呢。原因就是 Rabit 在這個基礎上提供了更好的容錯處理功能，彌補了 MPI 的不足。

為什么傳統(tǒng)的 MapReduce 模型在機器學習并行化中的作用有限呢?

上圖示傳統(tǒng) MR，下圖是 XGBOOST 的并行計算過程。

Rabit 在兩個地方都做了優(yōu)化，其一每一輪迭代結束后計算結果不需要放入到存儲系統(tǒng)，而是直接保留在內存;其二，每一輪迭代后沒有數據重新分發(fā)的過程，直接進行下一輪迭代，這使得計算效率大大提升。

Xgboost 的 Rabit 對分布式操作的封裝非常的好，可以很方便移植到其他系統(tǒng)中去。我們可以基于 Rabit 來開發(fā)我們的分布式機器學習程序。

#include <rabit/rabit.h> 
 Allreduce<op::Sum>(&a[0], N); 
 rabit::Broadcast(&s, 0);  

Rabit 提供了兩個最基本的操作 Allreduce， Broadcast 可以很方便進行程序開發(fā)。

MXNet 的分布式庫 ps-lite

最后我們來提提 mxnet。

ps-lite 是 mxnet 分布式現實的核心，它是基于 parameter server 模型的。

Ps-lite 的使用很簡單，可以很方便對現有的機器學習程序進行分布式改造，Ps-lite 的核心是 KVStore，它提供一個分布式的 key-value 存儲來進行數據交換。它主要有兩個函數:

• push： 將 key-value 對從一個設備 push 進存儲， 用于計算節(jié)點將更新后的參數值推送到參數服務器上。
• pull：將某個 key 上的值從存儲中 pull 出來，用于計算節(jié)點從參數服務器上獲取相關的參數值。

在下面例子中，我們將 單機梯度下降算法改成分布式梯度下降。單機梯度下降算法：

for (int i = 0; i < max_iter; ++i) { 
   network.forward(); 
 
   network.backward(); 
   network.weight -= eta * network.gradient 
}  

基于 ps-lite 的成分布式梯度下降：

KVStore kvstore("myps "); 
kvstore.set_updater([](NDArray weight, NDArray gradient) { 
    weight -= eta * gradient; 
  }); 
for (int i = 0; i < max_iter; ++i) { 
   kvstore.pull(network.weight); 
   network.forward(); 
   network.backward(); 
   kvstore.push(network.gradient); 
}  

這是 ps-lite 分布式改造最常見的一個例子。

我們可以很方便利用開源這些分布式框架來構建我們的分布式應用，比如在工作中，我就基于 ps-lite 對 word2vec， libffm 很快實現了分布式，特別是對 word2vec， libffm 的官方版本是多線程的，改造更簡單。

作者介紹

陳華清，美團酒店旅游事業(yè)部高級技術專家，負責美團酒店旅游的數據建設等方面的工作, 有著 10 年的搜索、數據挖掘、機器學習平臺等方向的開發(fā)經驗，曾在阿里巴巴從事數據挖掘和在 360 從事廣告算法等方面工作。