算法分析
LP-SVM在CUDA架构上的加速实现
兰远东
(惠州学院计算机科学系广东惠州516007)
皮
摘要：为了能在PC机上处理大规模数据集问题.提出了使用CUDA架构对LP-SVM的加速实现方法。该方法针对PC机内存小的缺点,对SVM的分解算法进行改编，得到求解LP-SVM的分解算法。LP-SVM分解算法每次只需要求解一个小规模的线性规划问题，避免一次性把所有训练数据部装进内存。同时把求解线性规划中比较耗时的矩阵运算，移植到CUDA上进行,提高了求解效率。实验结表明:LP-SVM算法在经过CUDA加速以后，算法的执行效单提高了10-35信
关键调：机器学习线性规划支持向量机图形处理器统一计算设备架构
文献标识码：A
文章编号：1007-9416(2014)04-0130-04
中图分类号：TP311
Abstract:In order to handle the problem of largescale data processing on PC, an acceleration method which uses the CUDA architecture to accelerate the implementation of LPSVM is proposed. Considering the limit memory of PC, the decomposition algorithm of SVM is modified to solve the LPSVM. Each time the new decomposition algorithm of only solves a smallscale linear programming problem and avoidk loading all the training data into memory The comparative timeconsuming parts of linear programming are migrated to CUDA platfom, which has greatly improved caleulation efficiency. Experimental results show that the efficiency of LpSVM algorithm has been speeded up by 10 to 35 times.
Key Words:machine learning linear programming SVM GPU CUDA
0引言
支持向量机(SupportVectorMachine，SVM)学习算法由 Vapnik叫首次提出，该学习算法建立了精确的数学模型，通常用来解决分类，回归和知识发现等问题，SVM已成功的应用在人脸识
CPU
各数据结构初始化及求初始解
获取换入变量序号得到最优解：
计算最优值，结束
获取换出变量序号
间题无解？
结束
GPU
计算单纯形子Y 计算检验数序列
取系数矩阵向量A，计算T，计算比序列
计算新基的逆矩阵B"，更新C，计算新解X
图1LP-SVM的算法流程图
表1CPU与CUDA执行时间的比较
数据集 Adult Forest KDD Ring
130
CPU (s)
210 209 1709 420
CUDA(s)
20 50 20
规模 1000 5000 8000 10000
加速比 2 10.2 34.8 21
别，文本分类和生物信息学等各个领域。标准的SVM算法需要解决个二次规划间题。因此它的计算时间复杂度为O(m2),其中m是训练数据的数量，并且运行算法还需要巨大的内存空间。
随着显卡相关技术的不断发展，图形处理器(GraphicsProxesing Unt,GPU)越来越强大，如果仅仅把显卡用于图形计算，那么显然是巨大的资源浪费。NVIDIA公司在2007年推出统一计算设备架构(Compute Unified Device Architecture, CUDA)2,使得显卡可以用于图像计算以外的目的。CUDA是一个新的基础架构,这个架构可以使用GPU来解决商业、工业以及科学方面的复杂计算问题。
本文主要探过了如何使用CUDA架构的强大计算能力来如速实现线性规划SVM(Linear ProgrammingSVM,LP-SVM)，使之
能够在PC上处理大规模的数据集。 1LP-SVM
由于LP-SVM是在标准的SVM基础上发展而来的，因此先介
40 35 30 25
加速比
20 15 10 5 0
1000
5000
8000
数据规模
图2数据规模和加速比的关系
10000