一種基于CUDA的并行SMO算法

湯斌飛, 林 超, 黃 迪

(中國石油大學(xué)(華東) a. 理學(xué)院；b. 網(wǎng)絡(luò)及教育技術(shù)中心，山東 青島 266580)

?

一種基于CUDA的并行SMO算法

湯斌飛a, 林 超b, 黃 迪a

(中國石油大學(xué)(華東) a. 理學(xué)院；b. 網(wǎng)絡(luò)及教育技術(shù)中心，山東 青島 266580)

序列最小優(yōu)化算法(Sequential Minimal Optimization，SMO)是針對支持向量機(jī)算法執(zhí)行速度慢而提出來的，它通過最小化分塊來加速算法，對不同數(shù)據(jù)集來說，其算法加速可達(dá)100x～1 000x。但是隨著數(shù)據(jù)量的增大，其算法執(zhí)行時間仍然較慢。為了加速算法，本文結(jié)合現(xiàn)代較發(fā)達(dá)的圖形處理單元(Graphics Processing Unit, GPU)計算，通過多處理器并行執(zhí)行方式，提出對算法并行化。主要的并行點(diǎn)在于確定了兩個參數(shù)α1、α2之后，求解局部最優(yōu)，從而更新所有參數(shù)的過程是天然并行的，而且SIMD形式的并行性非常符合GPU的運(yùn)算模式，通過將計算量大的參數(shù)更新部分轉(zhuǎn)移到GPU進(jìn)行計算，可以加速整個算法的運(yùn)行。實(shí)驗表明，并行算法可以達(dá)到150倍的加速效果。

SMO； CUDA； 并行SMO算法

0 引 言

SMO算法是由John C. Platt最先提出來的，其算法思想來源于Vapnik提出的“Chunking”算法[1]，通過使得分塊達(dá)到最小，來加速求解二次優(yōu)化問題[2]。另一方面并行計算由來已久，利用并行計算可以獲得更好的性價比，更好地利用電腦的硬件設(shè)備[3]，尤其是GPU的通用計算能力。硬件平常都不會滿負(fù)載工作，這在一定程度上意味著一定量的資源浪費(fèi)。為使其工作更快、更好，并行計算是一個選擇，其通過軟件的形式，改變串行程序的計算模式，在運(yùn)行正常的前提下，在同樣的硬件設(shè)備上提高了計算速率。有利用MPI編程接口實(shí)現(xiàn)的SMO算法[4]，其算法思路為把數(shù)據(jù)集分為小份，每份單獨(dú)計算完成，再進(jìn)行解的合并。也有用GPU實(shí)現(xiàn)的SVM算法，其算法思路是在GPU端計算Kernel矩陣[5]，但這不能稱為完全的并行計算[1]。

1 CUDA簡介

隨著GPU計算的高速發(fā)展，NVIDIA公司成功地抓住了通用計算的時代脈搏，它提出的CUDA C編程接口是基于NVIDIA架構(gòu)顯卡的，其通過核函數(shù)控制GPU線程進(jìn)行計算，把Block運(yùn)行快映射到SM以及把Thread運(yùn)行單元映射到SP，通過物理結(jié)構(gòu)與邏輯結(jié)構(gòu)相結(jié)合的方式，成功地把SIMD架構(gòu)程序轉(zhuǎn)移到GPU上進(jìn)行計算，通過GPU上數(shù)以千計的基本計算單元來實(shí)現(xiàn)中央處理單元(Centeral Processing Unit, CPU)多核所不能達(dá)到的計算效率[6-7]。近年來也有很多GPU計算接口相繼問世，如可以與CUDA相比肩的AMD OpenCL編程接口[8]，也有MS提出來的可以跨平臺的編程接口C++ AMP[9-10]，但是CUDA作為最基本的基于函數(shù)的編程接口，仍然受到很多編程人員的追捧。這也是因為計算本身是通過函數(shù)來體現(xiàn)的，是基于過程的，這也是CUDA成為常青樹的一個原因。為了使計算更快、更好，GPU計算是一個很好的選擇，一塊顯卡有時可以超過一臺小型服務(wù)器的計算效率，本文也是通過在GPU平臺上面實(shí)現(xiàn)了SMO并行算法來實(shí)現(xiàn)算法的加速。

2 串行SMO算法

2.1 簡 介

Sequential Minimal Optimization(SMO)算法使為了解決Support Vector Machine(SVM)運(yùn)行速率慢而最早提出來的，以解決二次規(guī)劃問題，通過最小化“分組”，使得算法達(dá)到最快。本文仍從SVM方向來引入SMO算法，并對算法進(jìn)行簡單的描述[11]。

對于數(shù)據(jù)點(diǎn)線性可分的情況，通過最大化類間距來進(jìn)行求解[12]，轉(zhuǎn)化為數(shù)學(xué)公式，即為：

s.t.yi(wxi-b)≥1, ?i

用Lagrangian乘子法進(jìn)行求解，可以化為：

s.t.αi≥0, ?i

對于數(shù)據(jù)點(diǎn)線性不可分的情況，添加懲罰因子，對線性可分的式子進(jìn)行變換即為線性不可分的情況[12]，數(shù)學(xué)公式如下所示：

s.t.yi(wxi-b)≥1-ξ, ?i

轉(zhuǎn)換到Lagrangian乘子問題即為

s.t. 0≤αi≤C,?i

代入并對原函數(shù)求導(dǎo)等于零可解得

式中：

并根據(jù)盒子原理可以推導(dǎo)出

式中：

式中：

B是邊界的集合[14-15]。

2.2 算 法

具體的算法流程如下所示。

Step1：應(yīng)用啟發(fā)式搜索算法，選擇合適α1與α2；

Step2：計算α2的上、下界H與L；

Step3：更新α2；然后更新α1；

Step4：更新所有fi；更新b；

Step5：判斷是否滿足終止條件，若是則停止；若不是則返回Step1。

3 并行SMO算法

根據(jù)對串行算法與很多數(shù)值例子的分析，可以看出算法的運(yùn)行時間絕大部分集中在Step4更新fi的操作中，為了更好地加速算法，可以對fi的更新轉(zhuǎn)移到GPU上進(jìn)行計算。

3.1 具體并行算法

Step1：算法初始化；

Step2：從CPU端傳輸數(shù)據(jù)到GPU端；

Step3：如果threadID=0，那么選擇α1和α2；并對選擇的兩個參數(shù)進(jìn)行更新操作；

Step4：對于所有 threads，更新參數(shù)fi；

Step5：如果threadID=0，更新參數(shù)b；

Step6：轉(zhuǎn)到Step3，除非達(dá)到終止條件。

3.2 并行程序優(yōu)化

(1) 考慮到Step4中更新fi的操作，其沒有數(shù)據(jù)依賴關(guān)系，對其并行計算可以獲得很好的加速效果，考慮到x1，x2，Δα1，Δα2，y1，y2等參數(shù)是每個計算進(jìn)程所共用的，結(jié)合CUDA編程架構(gòu)中的Shared Memory，可以一次性讀入這些數(shù)據(jù)，然后Block內(nèi)線程共用，這樣可以獲得更少的Global Memory與線程之間的數(shù)據(jù)交換，可以達(dá)到更好的計算效率[7]。

(2) Step3中參數(shù)的選取工作放到GPU端進(jìn)行計算，是因為如果其在CPU端計算的話，需要GPU在更新完參數(shù)fi后，把相應(yīng)更新后的參數(shù)傳回到CPU端，考慮到異構(gòu)平臺數(shù)據(jù)交換的高額代價，平衡CPU單線程計算與GPU單線程計算，把參數(shù)α1和α2的選擇工作放到GPU端完成是合理的。

(3) 考慮到利用啟發(fā)式搜索來選擇α1和α2兩個參數(shù)，這個過程分為兩個過程，第一步是選擇任意一個違反KKT條件的點(diǎn)，不妨即為α1，然后在所有數(shù)據(jù)點(diǎn)中，搜索使得E1-E2模最大的點(diǎn)，記為α2，然后對兩者進(jìn)行更新操作。整個過程是求最大化的過程，其過程也可并行化，把數(shù)據(jù)分塊，每個塊先求得局部最大值，然后合并之后求得全局最大值。

并行算法的流程如圖1所示。

圖1 并行算法程序流程圖

4 數(shù)值實(shí)驗

(1) 實(shí)驗環(huán)境采用HP Z400工作站，顯卡是另外配置的，為Nvidia Geforce GTX650。詳細(xì)參數(shù)配置如下：

操作系統(tǒng)Windows 7， 64 b，內(nèi)存大小4GB，編程環(huán)境Visual Studio 2012，CPU：Intel(R) Xeon(R) W3520@ 2.67GHz，4核，GPU：顯卡型號：Nvidia GeForce GTX650，顯存大小：1GB，GDDR5，顯卡帶寬：86.4 GB/s，核心頻率：1 111 MHz，內(nèi)存頻率：1 350 MHz，SM 數(shù)目：12，SP 數(shù)目：384。

(2) 實(shí)驗數(shù)據(jù)選擇隨機(jī)生成的數(shù)據(jù)來進(jìn)行測試，我們選擇在超平面wT·x≥51*Dim時數(shù)據(jù)點(diǎn)為正類，以wT·x≤49*Dim時數(shù)據(jù)點(diǎn)為負(fù)類，生成數(shù)據(jù)滿足xi∈[0,100];?i。

(3) 運(yùn)行參數(shù)選擇，Block的大小為256，線性排列。Grid的大小為N/Blocksize；選擇N為Blocksize的整數(shù)倍，以數(shù)據(jù)點(diǎn)個數(shù)和數(shù)據(jù)點(diǎn)維數(shù)為變換參數(shù)，可以得到運(yùn)行結(jié)果如表1所示。

表1 數(shù)據(jù)運(yùn)行結(jié)果

由表1的前4行可以看出，隨著數(shù)據(jù)數(shù)目的增大，加速效果更加明顯，這是由于隨著記錄數(shù)目的增大，GPU可以越來越達(dá)到滿負(fù)載運(yùn)行，由開始的分析我們知道，串行程序執(zhí)行過程中，90%以上的時間用來執(zhí)行fi的更新操作，在本例中，這步驟的更新操作在O(1)的時間即可完成，所以加速效果非常明顯。當(dāng)隨著數(shù)據(jù)量的增大，GPU滿負(fù)載之后，加速比逐漸達(dá)到一個上限，考慮到GPU內(nèi)SP數(shù)目為394，其不會超過這個數(shù)值[7]。

由表2中第2、5、6行可以看出，隨著數(shù)據(jù)維數(shù)的增大，加速比也是逐步增大的，這是由于串行程序執(zhí)行過程中頻繁讀取數(shù)據(jù)，維數(shù)的增大對串行程序影響較大[15]；相比之下，GPU并行執(zhí)行時間雖然也是有時間的增加，但是增加幅度較小，這是由于GPU訪存過程充分利用了共享顯存，它可以很顯著地降低顯存的讀取時間，從而使得算法達(dá)到一個很好的加速效果。

5 結(jié) 語

在GPU計算平臺下，利用CUDA編程接口，通過把SMO算法并行化，，可以達(dá)到一個很可觀的加速效果。由于顯卡是自己重新配置的計算專用顯卡，此加速比會顯示的高，但是不能否認(rèn)GPU通用計算的高效性，尤其是面對這種SIMD計算模式時，更是顯示出GPU計算的魅力。SMO算法在求解二次規(guī)劃問題中是非常重要的算法，通過把其并行化算法實(shí)現(xiàn)也使得自己對問題認(rèn)識的更加深刻。

[1] Cortes C, Vapnik V. Support-vector networks[J]. Machine learning, 1995, 20(3): 273-297.

[2] Platt J. Fast training of support vector machines using sequential minimal optimization[J]. Advances in Kernel Methods—support vector Learning, 1999, 3.

[3] 多核系列教材編寫組.多核程序設(shè)計[M]. 北京：清華大學(xué)出版社, 2007,9.

[4] Cao L J, Keerthi S S, Ong C J,etal. Parallel sequential minimal optimization for the training of support vector machines[J]. IEEE Transactions on Neural Networks, 2006, 17(4): 1039-1049.

[5] 朱齊丹,張 智,邢卓異. 支持向量機(jī)改進(jìn)序列最小優(yōu)化學(xué)習(xí)算法[J]. 哈爾濱工程大學(xué)學(xué)報,2007(2): 183-188.

[6] http://en.wikipedia.org/wiki/CUDA.

[7] 張舒, 褚艷利. GPU高性能運(yùn)算之CUDA[M]. 北京：中國水利水電出版社, 2009.

[8] http://en.wikipedia.org/wiki/Opencl.

[9] http://msdn.microsoft.com/en-us/library/bb524831(v=VS.85).aspx.

[10] C++ AMP: Language and Programming Model Version 1.0[M]. Microsoft Corporation. 2012,8.

[11] Vapnik V. Estimation of Dependences Based on Empirical Data[M]. Springer-Verlag, 1982.

[12] Vapnik V. The Nature of Statistical Learning Theory[M]. Springer-Verlag, 1995.

[13] Lee C, Jang M G. Fast training of structured SVM using fixed-threshold sequential minimal optimization[J]. ETRI Journal, 2009, 31(2): 121-128.

[14] Joachims T. Making large scale SVM learning practical[R]. Universit?t Dortmund, 1999.

[15] Zhang H R, Han Z Z. An improved sequential minimal optimization learning algorithm for regression support vector machine[J]. Journal of Software, 2003, 14(12): 2006-2013.

An Improved Parallel SMO Algorithm Based on CUDA

TANGBin-feia,LINChaob，HUANGDia

(a. College of Science; b. Network and Technology Educational Center，China University of Petroleum, Qingdao 266580, China)

The Sequential Minimal Optimization algorithm is presented to solve the time consuming problem in support vector machine training. This algorithm is accelerating the original algorithm by making the “chunking” minimal. For different datasets, this algorithm can reach 100x～1 000x speedup. But the performance of this algorithm is also bad with the dataset increasing. GPU computing is very popular nowadays. To accelerate this algorithm, this article proposes the parallel algorithm based on the SIMD model. The main point is to identify the two argumentsα1andα2. After solving local optimum, thereby updating all parameters is a naturally parallel process. And the form of SIMD parallelism is consistent with GPU computing model. By computationally intensive part of the transfer parameter update calculations to the GPU, the algorithm can be accelerated. Experiments show that the parallel algorithm can reach 150x speedup.

SMO; CUDA; parallel SMO algorithm

2015-12-01

湯斌飛(1990-)，男，江蘇江陰人，研究生在讀，研究方向是數(shù)值計算。

Tel.：18506488138，0532-86983413；E-mail：tangbinfei@163.com

林 超(1977-)，男，山東棲霞人，碩士，工程師，研究方向：計算機(jī)技術(shù)、算法分析與設(shè)計。

Tel.：18678933396；E-mail：linchao@upc.edu.cn

TP 391

A

1006-7167(2016)04-0140-04