基于AVX 与OpenMP 的LIBSVM 并行优化研究∗

田林琳 刘业峰 关世杰

（沈阳工学院信息与控制学院 抚顺 113122）

1 引言

机器学习是研究如何利用计算机来模拟或实现人类的学习行为，使用学习到新知识或技能，对现有的知识结构进行重组，以不断地提高机器自身的性能［1］。它是使计算机具有获取知识并使用知识的根本途径，是人工智能的基础，机器学习已经广泛应用于人工智能的各个领域［2］。

机器学习主要分为以下两大类：

1）分类（模式识别）：要求学习系统以已知的分类知识为前提条件，通过学习来分析未知的输入模式（该模式的描述），最终确定输入模式所属的类别，如手写体识别。

2）问题求解：以给定的状态为目标，计算获得一系列动作，这些动作可以将当前状态转换为目标状态［3］。

支持向量机是一种有监督式学习的方法［4］。一般是用在机器学习的分类（模式识别）中。在解决小样本、非线性和高维模式识别问题方面，SVM显示出了许多独特的优势，所以在手写体识别、三维目标识别、人脸识别、文本图像分类等实际问题的解决过程中都能看到SVM的影子［5］。

SVM算法是典型的计算时间长的算法，它的主要过程分为训练和分类。训练过程计算开销很大，因为参数优化算法本身需要若干次迭代。SVM 的分类过程是以在训练阶段生成的模型（model）文件为基础，再加上给定的输入（新值），输出新值所对应的类别，比如针对一个4236*1024 大小model 文件和一个1024 大小的新值进行分类预测，其耗时大约在300ms 左右，这对性能要求比较高的系统，如人脸识别，手写体识别等，其性能压力非常大，所以对串行的SVM 算法进行并行加速，将会减少训练和分类的时间，加速问题的解决，有非常重要的理论意义和应用前景。

本文使用Intel AVX 指令集和OpenMP 技术对SVM中的分类过程进行并行加速，主要出于以下两个目的：1）尽管SVM 的训练过程非常耗时，但整个训练过程是离线的，可以使用如文献［5］和文献［6］所使用GPU 方法加上高性能服务器加速整个训练过程。但其分类过程是针对每个待分类向量即时处理的，尤其是针对如人脸识别等对硬件成本和性能都要求比较高的系统，采用一个满足计算要求的高性能显卡带来了较大的成本压力，如果能够充分发挥CPU 本身所具有的计算能力，并行加速SVM的分类过程，使其满足系统的性能要求，无疑是最好的。2）尽管目前多核CPU越来越普遍，但目前大部分应用都是单线程运算，并没有充分发挥多核CPU 的并行处理能力，而且Intel 早在Pentium III 中CPU 中就增加了Streaming SIMD Extensions（SSE）的指令级并行API，这些都是充分利用CPU 计算能力的利器。通过串行和并行程序的性能对比，软件人员可以更好地审视其CPU的潜在性能，便于在今后开发中进行平台选择和降成本考虑。

2 并行技术概述

2.1 AVX

AVX 是一种单指令多数据流（Single Instruction Multiple Data，SIMD）计算技术，它通过一个计算机指令对多个连续的内存数据进行并发操作。AVX指令控制16个独立的256比特ymm 寄存器［7］。单精度浮点型AVX 指令的加法运算的工作模式如图1所示，图中的两个ymm 寄存器中存放的是单精度浮点型的数据，一个ymm 寄存器可以存放8个单精度浮点型数据［8］，因此AVX单精度加法指令的计算并行度是8。

图1 单精度浮点数AVX的加法工作模式

Intel 的AVX 指令集按功能可分为六大类，它们分别对应了指令集中的算术运算、数据传输、数值比较、逻辑运算和数据类型转换等。AVX 编程可以使用AVX 汇编，也可以使用内联函数指令（intrinsics）。AVX指令使用匈牙利的命名的方法来对内联函数进行命名，命名规则为_mm256_＜opcode＞_＜suffix＞。式中＜opcode＞代表指令的功能操作符，如mul，div，add，sub，and 等，＜suffix＞代表指令的后缀，用来指示AVX 的指令是进行单精度浮点数的运算还是进行双精度浮点数的运算。如_m256_sub_ps（）代表的是对ymm 寄存器中的内容进行单精度浮点数的减法运算；而_m256_sub_pd（）则代表的是对ymm 寄存器中的内容进行双精度浮点数的减法运算［7］。

就执行效率来说，汇编语言是很高的。但是汇编语言直接和寄存器、存储器打交道，编程十分复杂，很难掌握和理解，其编程效率相对较低。AVX内联函数指令的执行效率可以和汇编指令等同，同时它的编程效率却远远大于汇编指令，因此通常在程序中调用AVX指令进行数据的并行化。

2.2 OpenMP

OpenMP 是一个支持共享存储并行设计的库，特别适宜多核CPU 上的并行程序设计，通过在C、C++或者Fortran 的源代码中加入专用的pragma 指令来指明自己的并行意图，编译器基于该指令可以自动将程序并行化［9］。

OpenMP 以线程为基础并使用fork-join（分叉-合并）形式的执行模型，如图2所示。其中fork创建线程或者唤醒已有线程；join 即多线程的会合。在fork-join 执行模型刚开始启动的时候，只有一个线程称为“主线程”存在［10］。当需要进行并行计算时，子线程被主线程创建出来执行并行任务。这时主线程和子线程并行协同工作。当并行代码执行完毕后，子线程不再继续执行，此时控制流返回到主线程中。串行部分的执行要等到并行部分完全执行结束才开始［11］。

OpenMP允许程序员将更多的精力用于并行算法的设计，而不是其具体的实现细节。OpenMP 比较适合基于数据分集的多线程程序设计。同时，OpenMP 也提供了更大的灵活性，可以很容易地适应不同配置的并行系统。线程粒度和负载均衡是传统多线程程序设计中的难题，然而，OpenMP库从程序员手中接管了这两方面工作的一部分，从而使得程序员可以更加专注于算法本身的细节，而不是如何使得代码在CPU 负载均衡和线程粒度方面进行权衡。

图2 OpenMP fork-join执行模型

3 SVM概述

3.1 SVM原理

SVM 算法Vapnik 等在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况［12］。SVM 的基本原理为假设存在训练样本{( xi，yi)}，i=1，2，…，m，可以被某个超平面w·x+b=0 没有错地分开，其中，xi ∈Rn，yi ∈{- 1，1} ，m 为样本个数，Rn为n 维实数空间。因此两个类的最近采样点直接最大距离的超平面称为最优超平面，如图3 所示，H 为最优超平面。最优超平面仅由与其距离最近的几个样本点即支持向量确定［13］。

图3 SVM原理

图3 中H 线正确的隔离了两个不同的类，同时最大化分类间隔。设样本集为（xi，yi），i=1，2，…，m，yi ∈｛-1，1｝，并满足：

该分类的间隔等于2/‖ ‖w，，其间隔最大等价于求‖ ‖w2的值最小。满足上式（1）且12‖ ‖w2最小的分类平面叫做最优分类面，H1、H2两条平行直线上的那些训练样本点称为支持向量［14］。

3.2 LIBSVM

LIBSVM 工具箱是一个非常简单而且有效的SVM 模式识别与回归软件包，是由台湾大学林智仁教授等研发的，在SVM计算方面得到了广泛的使用，具有程序执行速度快、分类效果好的特点［15］。LIBSVM中的分类预测函数，其声明如下所示：

double svm_predict（const struct svm_model*model，const struct svm_node*x）；

该函数的第一个参数是SVM 的分类模型，是通过样本训练得到的；第二个参数是待分类的特征数据，通过分类模型的运算，来判断它所对应的类别标签。

图4 LIBSVM分类算法流程

LIBSVM 分类算法流程如图4 所示，其中加载模型文件即将训练生成的模型文件加载到内存中，这个过程只在系统启动时进行一次即可。模型文件包括文件头和支持向量数据，文件头主要记录了该模型文件的基本信息，如svm 类型、核函数类型及gamma 系数以及支持向量的数量和分类数量等［16］。

生成待分类向量是指针对待识别目标（如人脸）的感兴趣区域，使用如小波变换、方向梯度直方图（Histogram of Oriented Gradient，HOG）等提取其特征，形成1024维的待分类向量［17］。

SVM 分类是将待分类向量和模型文件中记录的正负样本支持向量进行计算，最终确定分类的过程。LIBSVM 中的分类功能分为KernelFunction 和DecisionFunction两个过程，如式（2）、（3）所示。

输出分类结果是将SVM 分类的结果输出给调用者。在系统关闭时卸载SVM 模型文件，并释放其内存空间。

4 SVM分类算法的优化过程

1）修改支持向量的内存布局。LIBSVM中对于支持向量的存储采用类似稀疏矩阵的形式，如图5所示。其中每个向量是一个被称为svm_node 的节点组成的数组，svm_node 是一个结构体，分为整数index和浮点数value，其中index即黑色字体表示当前点的索引，value 代表了对应点的系数，如图6 所示。

图5 LIBSVM中支持向量的内存布局

图6 svm_node内存格式

AVX 是SIMD 指令集，只能从连续的地址空间中取值，所以第一步改造读取模型文件的过程，在读取的过程中将index 分量去掉，只留下value 值，不存在的index 其value 设置为0，根据式（2），这样即不影响计算，又满足了使用AVX 的要求，这样svm_node类型被优化为单个浮点数，而一个支持向量即为一个浮点数组。每一个支持向量和待分类向量的内存空间都用_aligned_malloc 申请，保证首地址32 字节对齐，支持向量的内存分布如图7 所示。

图7 优化后满足AVX的内存布局

2）AVX 指令集的最大优点就是一次可以处理256 比特的数据，也就是说它可以一次可以处理8个单精度浮点数（float）或者是4 个双精度浮点数（double），从而可以大大提高数据的处理速度。经过对大量样本的测试，float的数据类型可以完全满足分类结果的准确性和精度，所以本文使用单精度（float）代替双精度（double）作为向量组成元素的数据类型，这样AVX 指令的数据吞吐量加倍，大幅度提高了SVM分类功能的并行度。

3）依次使用256 位的AVX 指令_mm256_set_ps1，_mm256_sub_ps，_mm256_mul_ps，_mm256_add_ps 和_mm256_ store_ps 每 次 计 算8 个 浮 点 数，进行KernelFunction 和Decision Function 函数的指令集实现。

4）使用OpenMP 的#pragma omp parallel for 子句将AVX实现的循环体进行多线程化，图8表示在4 核心CPU 上分为4 个线程时的计算方式，即每个线程计算支持向量总数的1/4。同理，在8 核心CPU 上，该OpenMP 子句将自动使用8 个线程进行处理。

图8 OpenMP多线程后的AVX指令执行模式

5 实验

5.1 实验环境

本文以相同的待分类向量集合其中包括正样本（人脸）6089 个，负样本（非人脸）5892 个，作为算法性能测试的输入数据，分别测试了4236*1024 和3598*1024 大小的模型文件与待输入向量的分类性能。

使用的平台：

CPU：Intel i5 4590 4核4线程3.3 GHz

内存：DDR3 1600MHz 8G

编译环境：Microsoft Visual Studio.net 2013、Intel C++编译器2016

表1 并行和串行版本的性能对比（单位ms）

5.2 结果分析

本文分别对4236*1024和3598*1024大小的模型文件进行了性能测试和对比，使用并行版本计算的结果和使用串行的相比，对全部的待分类向量其分类结果完全相同。由表1中的对比数据可见：

1）经过AVX优化的SVM 分类算法速度比串行版本快大约6 倍，虽然AVX 一次可以处理8 个float，但是由于内存的读取和写入，使得最终的加速比达不到8；

2）经过OpenMP 多线程优化后的性能比单线程AVX 指令集加速的版本快大约2.5 倍，原因在于算法中的求和运算使得线程之间的并行度降低，再加上线程本身的创建和销毁时间，在4 核心的CPU上只达到了2.5倍的加速比；

3）相对于初始的LIBSVM 串行版本，AVX+OpenMP 版本快了15 倍左右，即使是4236*1024 大小的模型文件，SVM的分类速度仍然达到了实时。

6 结语

通过利用Intel AVX指令集，本文对LIBSVM中的分类算法进行了指令集并行化，并使用OpenMP在多核心CPU 上进行了多线程优化。通过对实验结果的分析，在不增加任何计算硬件的情况下，并行版本的运行效率显著提高，满足了系统的性能要求，降低了系统成本。目前，该算法的多线程并行度不是很高，对于求和运算，后续可以考虑每个线程将自己的求和结果先存到临时变量中，最后对临时变量进行求和操作。而对于OpenMP 的性能，考虑使用系统提供的原生API 进行多线程创建和销毁或者使用线程池等更加灵活的多线程实现方法，进行性能对比，选择较快的一种。随着CPU的快速发展，相信基于CPU并行化的应用范围将更加广阔。