田林琳 劉業(yè)峰 關世杰

（沈陽工學院信息與控制學院 撫順 113122）

1 引言

機器學習是研究如何利用計算機來模擬或實現(xiàn)人類的學習行為，使用學習到新知識或技能，對現(xiàn)有的知識結構進行重組，以不斷地提高機器自身的性能［1］。它是使計算機具有獲取知識并使用知識的根本途徑，是人工智能的基礎，機器學習已經廣泛應用于人工智能的各個領域［2］。

機器學習主要分為以下兩大類：

1）分類（模式識別）：要求學習系統(tǒng)以已知的分類知識為前提條件，通過學習來分析未知的輸入模式（該模式的描述），最終確定輸入模式所屬的類別，如手寫體識別。

2）問題求解：以給定的狀態(tài)為目標，計算獲得一系列動作，這些動作可以將當前狀態(tài)轉換為目標狀態(tài)［3］。

支持向量機是一種有監(jiān)督式學習的方法［4］。一般是用在機器學習的分類（模式識別）中。在解決小樣本、非線性和高維模式識別問題方面，SVM顯示出了許多獨特的優(yōu)勢，所以在手寫體識別、三維目標識別、人臉識別、文本圖像分類等實際問題的解決過程中都能看到SVM的影子［5］。

SVM算法是典型的計算時間長的算法，它的主要過程分為訓練和分類。訓練過程計算開銷很大，因為參數(shù)優(yōu)化算法本身需要若干次迭代。SVM 的分類過程是以在訓練階段生成的模型（model）文件為基礎，再加上給定的輸入（新值），輸出新值所對應的類別，比如針對一個4236*1024 大小model 文件和一個1024 大小的新值進行分類預測，其耗時大約在300ms 左右，這對性能要求比較高的系統(tǒng)，如人臉識別，手寫體識別等，其性能壓力非常大，所以對串行的SVM 算法進行并行加速，將會減少訓練和分類的時間，加速問題的解決，有非常重要的理論意義和應用前景。

本文使用Intel AVX 指令集和OpenMP 技術對SVM中的分類過程進行并行加速，主要出于以下兩個目的：1）盡管SVM 的訓練過程非常耗時，但整個訓練過程是離線的，可以使用如文獻［5］和文獻［6］所使用GPU 方法加上高性能服務器加速整個訓練過程。但其分類過程是針對每個待分類向量即時處理的，尤其是針對如人臉識別等對硬件成本和性能都要求比較高的系統(tǒng)，采用一個滿足計算要求的高性能顯卡帶來了較大的成本壓力，如果能夠充分發(fā)揮CPU 本身所具有的計算能力，并行加速SVM的分類過程，使其滿足系統(tǒng)的性能要求，無疑是最好的。2）盡管目前多核CPU越來越普遍，但目前大部分應用都是單線程運算，并沒有充分發(fā)揮多核CPU 的并行處理能力，而且Intel 早在Pentium III 中CPU 中就增加了Streaming SIMD Extensions（SSE）的指令級并行API，這些都是充分利用CPU 計算能力的利器。通過串行和并行程序的性能對比，軟件人員可以更好地審視其CPU的潛在性能，便于在今后開發(fā)中進行平臺選擇和降成本考慮。

2 并行技術概述

2.1 AVX

AVX 是一種單指令多數(shù)據(jù)流（Single Instruction Multiple Data，SIMD）計算技術，它通過一個計算機指令對多個連續(xù)的內存數(shù)據(jù)進行并發(fā)操作。AVX指令控制16個獨立的256比特ymm 寄存器［7］。單精度浮點型AVX 指令的加法運算的工作模式如圖1所示，圖中的兩個ymm 寄存器中存放的是單精度浮點型的數(shù)據(jù)，一個ymm 寄存器可以存放8個單精度浮點型數(shù)據(jù)［8］，因此AVX單精度加法指令的計算并行度是8。

圖1 單精度浮點數(shù)AVX的加法工作模式

Intel 的AVX 指令集按功能可分為六大類，它們分別對應了指令集中的算術運算、數(shù)據(jù)傳輸、數(shù)值比較、邏輯運算和數(shù)據(jù)類型轉換等。AVX 編程可以使用AVX 匯編，也可以使用內聯(lián)函數(shù)指令（intrinsics）。AVX指令使用匈牙利的命名的方法來對內聯(lián)函數(shù)進行命名，命名規(guī)則為_mm256_＜opcode＞_＜suffix＞。式中＜opcode＞代表指令的功能操作符，如mul，div，add，sub，and 等，＜suffix＞代表指令的后綴，用來指示AVX 的指令是進行單精度浮點數(shù)的運算還是進行雙精度浮點數(shù)的運算。如_m256_sub_ps（）代表的是對ymm 寄存器中的內容進行單精度浮點數(shù)的減法運算；而_m256_sub_pd（）則代表的是對ymm 寄存器中的內容進行雙精度浮點數(shù)的減法運算［7］。

就執(zhí)行效率來說，匯編語言是很高的。但是匯編語言直接和寄存器、存儲器打交道，編程十分復雜，很難掌握和理解，其編程效率相對較低。AVX內聯(lián)函數(shù)指令的執(zhí)行效率可以和匯編指令等同，同時它的編程效率卻遠遠大于匯編指令，因此通常在程序中調用AVX指令進行數(shù)據(jù)的并行化。

2.2 OpenMP

OpenMP 是一個支持共享存儲并行設計的庫，特別適宜多核CPU 上的并行程序設計，通過在C、C++或者Fortran 的源代碼中加入專用的pragma 指令來指明自己的并行意圖，編譯器基于該指令可以自動將程序并行化［9］。

OpenMP 以線程為基礎并使用fork-join（分叉-合并）形式的執(zhí)行模型，如圖2所示。其中fork創(chuàng)建線程或者喚醒已有線程；join 即多線程的會合。在fork-join 執(zhí)行模型剛開始啟動的時候，只有一個線程稱為“主線程”存在［10］。當需要進行并行計算時，子線程被主線程創(chuàng)建出來執(zhí)行并行任務。這時主線程和子線程并行協(xié)同工作。當并行代碼執(zhí)行完畢后，子線程不再繼續(xù)執(zhí)行，此時控制流返回到主線程中。串行部分的執(zhí)行要等到并行部分完全執(zhí)行結束才開始［11］。

OpenMP允許程序員將更多的精力用于并行算法的設計，而不是其具體的實現(xiàn)細節(jié)。OpenMP 比較適合基于數(shù)據(jù)分集的多線程程序設計。同時，OpenMP 也提供了更大的靈活性，可以很容易地適應不同配置的并行系統(tǒng)。線程粒度和負載均衡是傳統(tǒng)多線程程序設計中的難題，然而，OpenMP庫從程序員手中接管了這兩方面工作的一部分，從而使得程序員可以更加專注于算法本身的細節(jié)，而不是如何使得代碼在CPU 負載均衡和線程粒度方面進行權衡。

圖2 OpenMP fork-join執(zhí)行模型

3 SVM概述

3.1 SVM原理

SVM 算法Vapnik 等在多年研究統(tǒng)計學習理論基礎上對線性分類器提出了另一種設計最佳準則。其原理也從線性可分說起，然后擴展到線性不可分的情況［12］。SVM 的基本原理為假設存在訓練樣本{( xi，yi)}，i=1，2，…，m，可以被某個超平面w·x+b=0 沒有錯地分開，其中，xi ∈Rn，yi ∈{- 1，1} ，m 為樣本個數(shù)，Rn為n 維實數(shù)空間。因此兩個類的最近采樣點直接最大距離的超平面稱為最優(yōu)超平面，如圖3 所示，H 為最優(yōu)超平面。最優(yōu)超平面僅由與其距離最近的幾個樣本點即支持向量確定［13］。

圖3 SVM原理

圖3 中H 線正確的隔離了兩個不同的類，同時最大化分類間隔。設樣本集為（xi，yi），i=1，2，…，m，yi ∈｛-1，1｝，并滿足：

該分類的間隔等于2/‖ ‖w，，其間隔最大等價于求‖ ‖w2的值最小。滿足上式（1）且12‖ ‖w2最小的分類平面叫做最優(yōu)分類面，H1、H2兩條平行直線上的那些訓練樣本點稱為支持向量［14］。

3.2 LIBSVM

LIBSVM 工具箱是一個非常簡單而且有效的SVM 模式識別與回歸軟件包，是由臺灣大學林智仁教授等研發(fā)的，在SVM計算方面得到了廣泛的使用，具有程序執(zhí)行速度快、分類效果好的特點［15］。LIBSVM中的分類預測函數(shù)，其聲明如下所示：

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

該函數(shù)的第一個參數(shù)是SVM 的分類模型，是通過樣本訓練得到的；第二個參數(shù)是待分類的特征數(shù)據(jù)，通過分類模型的運算，來判斷它所對應的類別標簽。

圖4 LIBSVM分類算法流程

LIBSVM 分類算法流程如圖4 所示，其中加載模型文件即將訓練生成的模型文件加載到內存中，這個過程只在系統(tǒng)啟動時進行一次即可。模型文件包括文件頭和支持向量數(shù)據(jù)，文件頭主要記錄了該模型文件的基本信息，如svm 類型、核函數(shù)類型及gamma 系數(shù)以及支持向量的數(shù)量和分類數(shù)量等［16］。

生成待分類向量是指針對待識別目標（如人臉）的感興趣區(qū)域，使用如小波變換、方向梯度直方圖（Histogram of Oriented Gradient，HOG）等提取其特征，形成1024維的待分類向量［17］。

SVM 分類是將待分類向量和模型文件中記錄的正負樣本支持向量進行計算，最終確定分類的過程。LIBSVM 中的分類功能分為KernelFunction 和DecisionFunction兩個過程，如式（2）、（3）所示。

輸出分類結果是將SVM 分類的結果輸出給調用者。在系統(tǒng)關閉時卸載SVM 模型文件，并釋放其內存空間。

4 SVM分類算法的優(yōu)化過程

1）修改支持向量的內存布局。LIBSVM中對于支持向量的存儲采用類似稀疏矩陣的形式，如圖5所示。其中每個向量是一個被稱為svm_node 的節(jié)點組成的數(shù)組，svm_node 是一個結構體，分為整數(shù)index和浮點數(shù)value，其中index即黑色字體表示當前點的索引，value 代表了對應點的系數(shù)，如圖6 所示。

圖5 LIBSVM中支持向量的內存布局

圖6 svm_node內存格式

AVX 是SIMD 指令集，只能從連續(xù)的地址空間中取值，所以第一步改造讀取模型文件的過程，在讀取的過程中將index 分量去掉，只留下value 值，不存在的index 其value 設置為0，根據(jù)式（2），這樣即不影響計算，又滿足了使用AVX 的要求，這樣svm_node類型被優(yōu)化為單個浮點數(shù)，而一個支持向量即為一個浮點數(shù)組。每一個支持向量和待分類向量的內存空間都用_aligned_malloc 申請，保證首地址32 字節(jié)對齊，支持向量的內存分布如圖7 所示。

圖7 優(yōu)化后滿足AVX的內存布局

2）AVX 指令集的最大優(yōu)點就是一次可以處理256 比特的數(shù)據(jù)，也就是說它可以一次可以處理8個單精度浮點數(shù)（float）或者是4 個雙精度浮點數(shù)（double），從而可以大大提高數(shù)據(jù)的處理速度。經過對大量樣本的測試，float的數(shù)據(jù)類型可以完全滿足分類結果的準確性和精度，所以本文使用單精度（float）代替雙精度（double）作為向量組成元素的數(shù)據(jù)類型，這樣AVX 指令的數(shù)據(jù)吞吐量加倍，大幅度提高了SVM分類功能的并行度。

3）依次使用256 位的AVX 指令_mm256_set_ps1，_mm256_sub_ps，_mm256_mul_ps，_mm256_add_ps 和_mm256_ store_ps 每 次 計 算8 個 浮 點 數(shù)，進行KernelFunction 和Decision Function 函數(shù)的指令集實現(xiàn)。

4）使用OpenMP 的#pragma omp parallel for 子句將AVX實現(xiàn)的循環(huán)體進行多線程化，圖8表示在4 核心CPU 上分為4 個線程時的計算方式，即每個線程計算支持向量總數(shù)的1/4。同理，在8 核心CPU 上，該OpenMP 子句將自動使用8 個線程進行處理。

圖8 OpenMP多線程后的AVX指令執(zhí)行模式

5 實驗

5.1 實驗環(huán)境

本文以相同的待分類向量集合其中包括正樣本（人臉）6089 個，負樣本（非人臉）5892 個，作為算法性能測試的輸入數(shù)據(jù)，分別測試了4236*1024 和3598*1024 大小的模型文件與待輸入向量的分類性能。

使用的平臺：

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

內存：DDR3 1600MHz 8G

編譯環(huán)境：Microsoft Visual Studio.net 2013、Intel C++編譯器2016

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

5.2 結果分析

本文分別對4236*1024和3598*1024大小的模型文件進行了性能測試和對比，使用并行版本計算的結果和使用串行的相比，對全部的待分類向量其分類結果完全相同。由表1中的對比數(shù)據(jù)可見：

1）經過AVX優(yōu)化的SVM 分類算法速度比串行版本快大約6 倍，雖然AVX 一次可以處理8 個float，但是由于內存的讀取和寫入，使得最終的加速比達不到8；

2）經過OpenMP 多線程優(yōu)化后的性能比單線程AVX 指令集加速的版本快大約2.5 倍，原因在于算法中的求和運算使得線程之間的并行度降低，再加上線程本身的創(chuàng)建和銷毀時間，在4 核心的CPU上只達到了2.5倍的加速比；

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

6 結語

通過利用Intel AVX指令集，本文對LIBSVM中的分類算法進行了指令集并行化，并使用OpenMP在多核心CPU 上進行了多線程優(yōu)化。通過對實驗結果的分析，在不增加任何計算硬件的情況下，并行版本的運行效率顯著提高，滿足了系統(tǒng)的性能要求，降低了系統(tǒng)成本。目前，該算法的多線程并行度不是很高，對于求和運算，后續(xù)可以考慮每個線程將自己的求和結果先存到臨時變量中，最后對臨時變量進行求和操作。而對于OpenMP 的性能，考慮使用系統(tǒng)提供的原生API 進行多線程創(chuàng)建和銷毀或者使用線程池等更加靈活的多線程實現(xiàn)方法，進行性能對比，選擇較快的一種。隨著CPU的快速發(fā)展，相信基于CPU并行化的應用范圍將更加廣闊。