一種基于CUDA的并行SMO算法

湯斌飛, 林 超, 黃 迪

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

?

一種基于CUDA的并行SMO算法

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

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

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

SMO； CUDA； 并行SMO算法

0 引 言

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

1 CUDA簡(jiǎn)介

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

2 串行SMO算法

2.1 簡(jiǎn) 介

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

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

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

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

s.t.αi≥0, ?i

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

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

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

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

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

式中：

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

式中：

式中：

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

2.2 算 法

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

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

Step2：計(jì)算α2的上、下界H與L；

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

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

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

3 并行SMO算法

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

3.1 具體并行算法

Step1：算法初始化；

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

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

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

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

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

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

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

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

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

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

圖1 并行算法程序流程圖

4 數(shù)值實(shí)驗(yàn)

(1) 實(shí)驗(yàn)環(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：顯卡型號(hào)：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í)驗(yàn)數(shù)據(jù)選擇隨機(jī)生成的數(shù)據(jù)來(lái)進(jìn)行測(cè)試，我們選擇在超平面wT·x≥51*Dim時(shí)數(shù)據(jù)點(diǎn)為正類(lèi)，以wT·x≤49*Dim時(shí)數(shù)據(jù)點(diǎn)為負(fù)類(lèi)，生成數(shù)據(jù)滿足xi∈[0,100];?i。

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

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

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

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

5 結(jié) 語(yǔ)

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

[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] 多核系列教材編寫(xiě)組.多核程序設(shè)計(jì)[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é)報(bào),2007(2): 183-188.

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

[7] 張舒, 褚艷利. GPU高性能運(yùn)算之CUDA[M]. 北京：中國(guó)水利水電出版社, 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ù)值計(jì)算。

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

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

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

TP 391

A

1006-7167(2016)04-0140-04