一种基于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]，其算法思路为把数据集分为小份，每份单独计算完成，再进行解的合并。……