大規(guī)模機器學習的編程技術、計算模型以及Xgboost和MXNet案例
現(xiàn)在，機器學習的趨勢從傳統(tǒng)方法中的簡單模型 + 少量數(shù)據(jù)(人工標注樣本)，到簡單模型 + 海量數(shù)據(jù)(比如基于邏輯回歸的廣告點擊率預測)，再發(fā)展到現(xiàn)在復雜模型 + 海量數(shù)據(jù)(比如深度學習 ImageNet 圖像識別，基于 DNN 的廣告點擊率預測)。
總結下在工業(yè)屆常會用到的大規(guī)模機器學習的場景：
這次分享從這 3 部分展開：
1.并行計算編程技術
- 向量化
- Openmp
- GPU
- mpi
2.并行計算模型
- BSP
- SSP
- ASP
- Parameter Server
3.并行計算案例
- Xgboost 的分布式庫 Rabit
- Mxnet 的分布式庫 ps-lite
并行計算編程技術
首選提到并行編程技術，這是大規(guī)模機器學習的工程基礎。
向量化
向量化計算是一種特殊的并行計算的方式，相比于一般程序在同一時間只執(zhí)行一個操作的方式，它可以在同一時間執(zhí)行多次操作，通常是對不同的數(shù)據(jù)執(zhí)行同樣的一個或一批指令，或者說把指令應用于一個數(shù)組 / 向量。
在 X86 體系架構的 CPU 上，主要的向量化編程技術是 SSE 和 AVX。Intel 公司的單指令多數(shù)據(jù)流式擴展(SSE，Streaming SIMD Extensions)技術能夠有效增強 CPU 浮點運算的能力。現(xiàn)住主流的編譯器 GCC 和 Visual Studio 提供了對 SSE 指令集的編程支持，從而允許用戶在 C++ 代碼中不用編寫匯編代碼就可直接使用 SSE 指令的功能。Intel SSE 指令集支持的處理器有 16 個 128 位的寄存器，每一個寄存器可以存放 4 個(32 位)單精度的浮點數(shù)。SSE 同時提供了一個指令集，其中的指令可以允許把浮點數(shù)加載到這些 128 位的寄存器之中，這些數(shù)就可以在這些寄存器中進行算術邏輯運算，然后把結果放回內(nèi)存。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 個浮點數(shù)
- p += 8;
- }
- // 合并.
- q = (const float*)&yfsSum;
- s = q[0] + q[1] + q[2] + q[3] + q[4] + q[5] + q[6] + q[7];
這是一個數(shù)組求和的加速例子。
現(xiàn)在主流編譯器 GCC 等都支持。
其次是大家最熟悉的多線程編程技術。
UNIX/Linux 中的 pthread， Windows 環(huán)境下的 WinThread。但是相對于機器學習并行來說，一方面采用多線程編程技術，開發(fā)成本較高，而且需要妥善處理同步互斥等問題;另一方面，不同平臺中使用多線程編程庫是不一樣的，這樣也會造成移植性問題。
Openmp
OpenMP 是一個支持共享存儲并行設計的庫，特別適宜多核 CPU 上的并行程序設計，它使得多線程編程的難度大大降低，是目前機器學習上多線程主流解決方案。
大家可以看看這個例子。我們很容易把傳統(tǒng)的 for 循環(huán)語句進行加速。OpenMP 也可以實現(xiàn)類似于 MapReduce 的計算范式。更詳細的大家可以參考 openmp 的官方文檔。
GPU
GPU 編程是目前很熱的并行計算方案。
這是 GPU 和 CPU 區(qū)別。
為什么 GPU 更快呢?
- CPU 主要是為串行指令而優(yōu)化，而 GPU 是為大規(guī)模并行運算而優(yōu)化。
- GPU 相對 CPU 來說，在同樣的芯片面積上，擁有更多的計算單元，這也使得 GPU 計算性能更加強大，而 CPU 則擁有更多的緩存和相關的控制部件。
- GPU 相對 CPU 來說擁有更高的帶寬。
CUDA 是目前主流的 GPU 編程。
這也是一個數(shù)組求和例子。大家可以看看 GPU 編程并不是很難，它和傳統(tǒng)程序編程區(qū)別是：
MPI
MPI 是一種多機并行解決方案，它的核心是消息的傳遞和接收，解決多級并行中的通信問題。
這是 MPI 程序執(zhí)行流程。MPI 的學習難度也是比較低的。
MPI_Init(…); 初始化環(huán)境
MPI_Comm_size(…) 獲取進程數(shù)
MPI_Comm_rank(…) 獲取進程序號
MPI_Send(…) 發(fā)送消息
MPI_Recv(…) 接收消息
MPI_Finalize() 并行結束函數(shù)
主要是這 6 個函數(shù)。
MPI 函數(shù)雖然很多，但是功能主要有兩大類：
一種是發(fā)送數(shù)據(jù)。
這種是接收數(shù)據(jù)做規(guī)約。很類似于大家常見的 MapReduce 吧。
總結一點，大家可以根據(jù)自己的硬件條件來選擇合適的并行計算解決方案。
這里要提醒一點，大家如果想 GPU 編程的話，使用 CUDA 技術化，一定要買 nvidia 的顯卡，因為其他的裝不上。
分布式機器學習系統(tǒng)需要解決的三個問題：
- 如何更好的切分成多個任務
- 如何調(diào)度子任務
- 均衡各節(jié)點的負載
并行計算模型
BSP
這是一個通用的機器學習問題建模和優(yōu)化。大規(guī)模機器學習的核心就是梯度計算的并行化。BSP 是較早的一個并行計算模型，也是當前主流的并行計算模型之一。
每一步詳細分解下。
其計算過程也比較好理解，就是計算 ->同步 ->計算 ->同步......
BSP 具有如下優(yōu)點：
- 它將處理器和路由器分開，強調(diào)了計算任務和通信任務的分開，而路由器僅僅完成點到點的消息傳遞，不提供組合、復制和廣播等功能，這樣做既掩蓋具體的互連網(wǎng)絡拓撲，又簡化了通信協(xié)議;
- 采用障礙同步的方式以硬件實現(xiàn)的全局同步是在可控的粗粒度級，從而提供了執(zhí)行緊耦合同步式并行算法的有效方式，而程序員并無過分的負擔;
BSP 模型的這些特點使它成為并行計算的主流模型之一，開源 的 Mahout, Apache Huma, Spark mllib, Google Pregel, Graphlab, xgboost 等的并行實現(xiàn)都是基于 BSP 模型的。
BSP 模型在每一輪結論之后都需要進行一次同步，這很容易造成木桶效應，由于任務的切分中每個任務計算量并不是完全均勻的，而且在復雜的分布式計算環(huán)境下，每臺機器的硬件條件也是存在差異的，這就造成了 BSP 模型每一輪迭代的效率由最慢的計算任務來決定，為了緩解這個現(xiàn)象，SSP 模型被提出來了。
SSP
SSP 模型
我們把 SSP 中每個任務過程稱為 worker，SSP 模型通過設置一個 bound 來確定同步的時機。當最快的 worker 比最慢的 worker 超過這個 bound 時所有的 work 來就行一次參數(shù)的同步。這個 bound 可以根據(jù)迭代的次數(shù)，也可以根據(jù)參數(shù)更新的差值來確定。SSP 協(xié)議的好處在于，faster worker 會遇到參數(shù)版本過于 stale 的問題，導致每一步迭代都需要網(wǎng)絡通信，從而達到了平衡計算和網(wǎng)絡通信時間開銷的效果。
SSP 模型數(shù)學上證明是可以收斂的。
原因可以這么來解釋吧，就是條條大道通羅馬。
對于機器學習程序來說，中間結果的錯誤是可以容忍的，有多條路徑都可以收斂到最優(yōu)，因此少量的錯誤可類似于隨機噪聲，但不影響最終的收斂結果。盡快每一次迭代可能存在誤差，但是經(jīng)過多輪迭代后，平均誤差趨近于零。盡管每次可能不是最優(yōu)的求解路徑，但是最終還是找到一條通往最優(yōu)解的整體路徑。盡管這條路徑不是最快的路徑，但是由于在通訊方面的優(yōu)勢，整體的求解速度相對于 BSP 來說還是更快一些，特別是在數(shù)據(jù)規(guī)模和參數(shù)規(guī)模非常大的情況下，在多機并行的環(huán)境下。
ASP
ASP 是一種完全異步的方式，相當于取消了 BSP 中的同步環(huán)節(jié)。
ASP 的運行速度更快，當然它是沒有收斂性保證的。
SSP 協(xié)議可以有效平衡計算和網(wǎng)絡通信的開銷。
對于非凸問題，BSP 和 SSP 收斂的最優(yōu)解可能不一樣。對于非凸優(yōu)化問題(比如說神經(jīng)網(wǎng)絡)，有大量局部最優(yōu)解，隨機梯度下降(可以跳出局部最優(yōu)解)比批量梯度下降效果要更好。
Parameter Server
參數(shù)服務器是近來來在分布式機器學習領域非常火的一種技術。
Parameter Server 參數(shù)服務器中比較重要的是各個計算節(jié)點的參數(shù)同步問題。
Sequential： 這里其實是 synchronous task，任務之間是有順序的，只有上一個任務完成，才能開始下一個任務，也就是同步方式;Eventual： 跟 sequential 相反，所有任務之間沒有順序，各自獨立完成自己的任務，也就是異步的形式;Bounded Delay： 這是 sequential 跟 eventual 之間的折中，當最快計算任務比最慢計算任務快于一定閾值時進行等待，也可以當計算任務對梯度的累計更新值大于一定閾值時進行等待。
總結這 4 種模式的優(yōu)缺點：
并行計算案例
Xgboost 的分布式庫 Rabit
Xgboost 是目前非常牛的一個機器學習包，其分布式做得非常好，我們現(xiàn)在來看一下。
Xgboost 的分布式實現(xiàn)由如下幾個特點：
- OpenMp 支持多核并行
- CUDA 支持 GPU 加速
- Rabit 支持分布式
其核心就是 Rabit，Xgboost 將其分布式核心功能抽象出來，Rabit 是基于 BSP 模型的，通過兩個基本原語 Broadcast 和 AllReduce 來實現(xiàn)其分布式功能。Broadcase 和 AllReduce 與 MPI 中的功能基本上一致，設計思想類似，為什么不直接使用 MPI 呢。原因就是 Rabit 在這個基礎上提供了更好的容錯處理功能，彌補了 MPI 的不足。
為什么傳統(tǒng)的 MapReduce 模型在機器學習并行化中的作用有限呢?
上圖示傳統(tǒng) MR，下圖是 XGBOOST 的并行計算過程。
Rabit 在兩個地方都做了優(yōu)化，其一每一輪迭代結束后計算結果不需要放入到存儲系統(tǒng)，而是直接保留在內(nèi)存;其二，每一輪迭代后沒有數(shù)據(jù)重新分發(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 分布式現(xiàn)實的核心，它是基于 parameter server 模型的。
Ps-lite 的使用很簡單，可以很方便對現(xiàn)有的機器學習程序進行分布式改造，Ps-lite 的核心是 KVStore，它提供一個分布式的 key-value 存儲來進行數(shù)據(jù)交換。它主要有兩個函數(shù):
- push： 將 key-value 對從一個設備 push 進存儲， 用于計算節(jié)點將更新后的參數(shù)值推送到參數(shù)服務器上。
- pull：將某個 key 上的值從存儲中 pull 出來，用于計算節(jié)點從參數(shù)服務器上獲取相關的參數(shù)值。
在下面例子中，我們將 單機梯度下降算法改成分布式梯度下降。單機梯度下降算法：
- 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 很快實現(xiàn)了分布式，特別是對 word2vec， libffm 的官方版本是多線程的，改造更簡單。
作者介紹
陳華清，美團酒店旅游事業(yè)部高級技術專家，負責美團酒店旅游的數(shù)據(jù)建設等方面的工作, 有著 10 年的搜索、數(shù)據(jù)挖掘、機器學習平臺等方向的開發(fā)經(jīng)驗，曾在阿里巴巴從事數(shù)據(jù)挖掘和在 360 從事廣告算法等方面工作。
