一種基于CUDA的并行SMO算法

湯斌飛, 林 超, 黃 迪

(中國石油大學(華東) a. 理學院；b. 網絡及教育技術中心，山東 青島 266580)

?

一種基于CUDA的并行SMO算法

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

(中國石油大學(華東) a. 理學院；b. 網絡及教育技術中心，山東 青島 266580)

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

SMO； CUDA； 并行SMO算法

0 引 言

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

1 CUDA簡介

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

2 串行SMO算法

2.1 簡 介

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

對于數據點線性可分的情況，通過最大化類間距來進行求解[12]，轉化為數學公式，即為：

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

用Lagrangian乘子法進行求解，可以化為：

s.t.αi≥0, ?i

對于數據點線性不可分的情況，添加懲罰因子，對線性可分的式子進行變換即為線性不可分的情況[12]，數學公式如下所示：

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

轉換到Lagrangian乘子問題即為

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

代入并對原函數求導等于零可解得

式中：

并根據盒子原理可以推導出

式中：

式中：

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

2.2 算 法

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

Step1：應用啟發式搜索算法，選擇合適α1與α2；

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

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

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

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

3 并行SMO算法

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

3.1 具體并行算法

Step1：算法初始化；

Step2：從CPU端傳輸數據到GPU端；

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

Step4：對于所有 threads，更新參數fi；

Step5：如果threadID=0，更新參數b；

Step6：轉到Step3，除非達到終止條件。

3.2 并行程序優化

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

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

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

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

圖1 并行算法程序流程圖

4 數值實驗

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

操作系統Windows 7， 64 b，內存大小4GB，編程環境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，內存頻率：1 350 MHz，SM 數目：12，SP 數目：384。

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

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

表1 數據運行結果

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

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

5 結 語

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

[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] 多核系列教材編寫組.多核程序設計[M]. 北京：清華大學出版社, 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]. 哈爾濱工程大學學報,2007(2): 183-188.

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

[7] 張舒, 褚艷利. GPU高性能運算之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-)，男，江蘇江陰人，研究生在讀，研究方向是數值計算。

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

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

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

TP 391

A

1006-7167(2016)04-0140-04