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