基于GPU并行計算的圖像特征提取與匹配研究?

劉小豫 李 紅

基于GPU并行計算的圖像特征提取與匹配研究?

劉小豫1李 紅2

（咸陽師范學(xué)院圖像處理研究所 咸陽 712000）

GPU高性能計算以其強勁計算能力成為圖像算法研究的首選計算平臺，在實際的應(yīng)用研究中往往將視頻分析工作負載分布到CPU和GPU中執(zhí)行，論文針對圖像特征提取的應(yīng)用提出一種從視頻流數(shù)據(jù)中提取特征性能的性能預(yù)測模型。該模型實現(xiàn)CPU-GPU混合計算系統(tǒng)的總執(zhí)行時間評價，并確定最佳工作負載比率以及如何針對給定工作負載使用CPU內(nèi)核。通過實驗分析，確認提出的方法可以提高三種典型工作負載分布的加速：CPU只有GPU，或CPU-GPU混合計算，工作負載比為50∶50。

GPU；特征提??；性能預(yù)測；視頻流

AbstractGPU high performance computing with its strong computing ability become the preferred computing platform of im?age algorithm，in the applied research，video analysis workload is distributed to the implementation of CPU and GPU，this paper proposes a feature extraction from the video stream in the performance characteristics of the performance prediction model.The mod?el implements the total execution time evaluation of CPU-GPU hybrid computing system，and determines the best working load ratio and how to use the CPU kernel for a given workload.Through experimental analysis，it is confirmed that the proposed method can improve the acceleration of three typical work load distributions：CPU，only GPU or CPU-GPU mixed calculation，and the work load ratio is 50∶50.

Key Wordsthe GPU，feature extraction，performance prediction，the video stream

Class NumberTP393

1 引言

1.1 研究背景

高性能視頻分析是大數(shù)據(jù)處理的一個重要挑戰(zhàn)。視頻分析中的特征提取是識別真實世界對象的重要方法。其目的是編碼簡單的幾何形式，如不同方向的直線［1］。許多計算機視覺應(yīng)用如特征提取，對象跟蹤和識別已通過使用多核平臺（如CPU或GPU）來并行化，以減少執(zhí)行時間［2］。

通常，當應(yīng)用程序使用GPU系統(tǒng)運行時，僅一個線程被分配給“主機CPU核心”（即，用于執(zhí)行主機程序的CPU的核心），以便控制GPU和管理數(shù)據(jù)復(fù)制操作，剩余的CPU核心處于空閑狀態(tài)，而GPU執(zhí)行應(yīng)用程序特定的任務(wù)，這導(dǎo)致大量的CPU資源浪費。因此，重要的是找到一種有效的方法來充分利用CPU和GPU的所有可用計算資源。近年來，在文獻［3～7］介紹了多種圖像特征提取策略，并介紹同時使用多核CPU和GPU而不是單獨使用CPU或GPU來執(zhí)行特定任務(wù)的性能評價。本文提出了一種將工作負載分布到CPU和GPU兩者中的方式，其具有包括來自視頻流數(shù)據(jù)的特征提取的特性的性能預(yù)測模型。

為了在CPU和GPU中實現(xiàn)并行化特征提取和確定的最佳工作負載分布，本文考慮特征提取的兩個重要特征。首先，特征提取受到諸如數(shù)據(jù)復(fù)制時間不可忽略的并行開銷的影響，由于對于單個圖像幀的特征提取具有相對較短的執(zhí)行時間，然而，用于對象跟蹤的特征提取需要大量的幀并且在每個幀中具有數(shù)據(jù)依賴性。因此，并行化運行一個圖像幀的特征提取，以滿足視頻流處理的實時要求。此外，由于視頻流數(shù)據(jù)在靜態(tài)工作負載內(nèi)是連續(xù)的，所以靜態(tài)策略可以有效地將工作負載分布到CPU和GPU兩者中，用于特征提取而沒有復(fù)雜的調(diào)度開銷。在本文中，對于給定機器（即多核CPU和GPU組合），作者通過使用線性內(nèi)插來導(dǎo)出給定機器的性能預(yù)測模型，并且通過使用性能預(yù)測來確定最優(yōu)CPU：GPU工作負載比模型。此外，通過減少CPU和GPU的空閑時間來提高CPU-GPU混合計算的性能。

1.2 相關(guān)概念

特征提取包括平滑圖像，漸變和跟蹤每個像素的操作，并且具有兩個重要的計算特性。首先，特征提取受諸如數(shù)據(jù)復(fù)制時間的并行開銷的影響，這是不可忽略的。圖1顯示了使用CPU-GPU混合計算的并行特征提取，通常，主CPU核處的單個圖像幀被劃分為兩個部分，并分別分配給“剩余CPU核”（即，用于計算工作負載的CPU的剩余核）和GPU。雖然GPU需要數(shù)據(jù)復(fù)制時間來計算工作負載，但應(yīng)當注意，對于沒有數(shù)據(jù)依賴性的許多應(yīng)用，GPU可以提供比多核CPU更好的性能。雖然GPU需要來自主機CPU核心的數(shù)據(jù)復(fù)制時間，但是在大規(guī)模的科學(xué)應(yīng)用中，計算限制問題數(shù)據(jù)復(fù)制時間是可以忽略的。然而，在特征提取中，并行開銷敏感地影響特征提取的總執(zhí)行時間，因為特征提取的每個操作（即平滑圖像，梯度和每個像素的可跟蹤性）具有相對短的執(zhí)行時間（即幾十毫秒）。

圖1 特征提取的計算特征的示例

例如，圖2表示了CPU（具有四個核）和GPU混合計算的計算特性以及數(shù)據(jù)復(fù)制時間的影響對比。一般來說，在計算限制的大規(guī)?？茖W(xué)問題中，數(shù)據(jù)復(fù)制時間是可以忽略的，如圖2（a）所示。然而，如果數(shù)據(jù)復(fù)制時間是不可忽略的，并且主機CPU核心的計算和數(shù)據(jù)復(fù)制時間的量比其余CPU核心的計算時間長得多，如圖2（b）所示，它顯著影響總執(zhí)行時間。在這種情況下，由于數(shù)據(jù)復(fù)制時間相對較大，所以剩余的CPU核具有長的空閑時間，為了減少這種空閑時間，可以將主機CPU內(nèi)核的工作負載分配給剩余的CPU內(nèi)核，如圖2（c）所示。由于三個CPU核（即，剩余的CPU核）用于額外的工作負載執(zhí)行，所以主CPU核（即核4）可以執(zhí)行數(shù)據(jù)復(fù)制而沒有任何工作負載執(zhí)行，在理想情況下，剩余CPU核心的工作負載可以重新分配到主機CPU核心（見圖2（d））。然而，如圖2（c）到圖2（d）在性能方面的改進遠小于來自圖2（b）到圖2（c）的性能改進［10～14］。

圖2 CPU-GPU混合計算演示數(shù)據(jù)復(fù)制時間的示例圖

此外，由于使用連續(xù)視頻流數(shù)據(jù)執(zhí)行特征提取，所以靜態(tài)策略可以有效地將工作負載分布到CPU和GPU中，而沒有復(fù)雜的調(diào)度開銷。在本文中，通過使用基于預(yù)實驗測試的線性插值應(yīng)用性能預(yù)測模型（即對于給定的CPU-GPU混合計算系統(tǒng)，通過測量圖像幀大小的特征提取執(zhí)行時間），然后確定最佳CPU：其他圖像幀大小的GPU工作負載率。

2 圖像特征提取和匹配策略研究

2.1 確定最佳CPU：GPU工作負載比

在本文中，作者通過使用基于預(yù)實驗測試的線性插值來預(yù)測執(zhí)行時間，然后確定最優(yōu)CPU：GPU工作負載比。為了準確預(yù)測特征提取的執(zhí)行時間，通過分析CPU和GPU的計算特性，包括到GPU的數(shù)據(jù)復(fù)制時間和來自GPU的數(shù)據(jù)復(fù)制時間。首先，對于給定的CPU-GPU混合計算系統(tǒng)，利用各種CPU：GPU工作負載比率來測量執(zhí)行時間，然后可以通過使用線性內(nèi)插來導(dǎo)出性能預(yù)測模型。例如，使用640*480的圖像測量執(zhí)行時間，然后通過使用線性內(nèi)插來導(dǎo)出性能預(yù)測模型（即，線性方程）。這些方程可以預(yù)測各種圖像幀大小的特征提取的執(zhí)行時間。此外，可以通過使用性能預(yù)測模型來確定各種圖像幀大小的特征提取的最優(yōu)CPU：GPU工作負載比。

最佳的CPU：GPU計算如式（1）所示。其中用WTOTAL表示W(wǎng)CPU和WGPU的總工作負載（即，給定圖像幀的大?。?。

混合計算的總執(zhí)行時間TCPU+GPU（WCPU+WGPU）由TCPU（WCPU）或 TGPU（WGPU）的最大執(zhí)行時間表示，如式（2）所示。

由于CPU和GPU的特征提取的執(zhí)行時間根據(jù)工作負載大小線性地增加或減少，因此通過使用線性內(nèi)插，可以利用式（3）和式（4）來表示TCPU（WCPU）和TGPU（WGPU）。 為了獲得參數(shù)α，β，γ和δ（即，線性方程的系數(shù)和常數(shù)），應(yīng)當至少一次測量CPU和GPU上的圖像幀大小的特征提取的執(zhí)行時間，然后執(zhí)行性能預(yù)測模型（即，線性方程）。注意，為了準確預(yù)測執(zhí)行時間，GPU的執(zhí)行時間應(yīng)包括數(shù)據(jù)復(fù)制時間。

當 TCPU（WCPU）大約等于TGPU（WGPU）時，混合計算TCPU+GPU（WCPU+WGPU）的性能值為最大。因此，使用上述式（3）和式（4），當 TCPU（WCPU）=TGPU（WGPU）時可以表示為式（5）。

最后，由式（6）表示最佳工作負載OWCPU和OWGPU，并且可以確定最佳CPU∶GPU工作負載比。

2.2 算法介紹

為了減少CPU和GPU的空閑時間，算法1顯示了工作負載分配方法。首先，導(dǎo)出性能預(yù)測模型，并且如步驟1和步驟2所示確定CPU∶GPU的最佳工作負荷比（參見圖2（a）或2（b））。在步驟3中，我們確定如何使用CPU內(nèi)核。如果主機CPU核心的計算量和數(shù)據(jù)復(fù)制時間遠大于剩余CPU核心的計算時間，則應(yīng)當使用式（3），（5）和（6）更新OWCPU和OWGPU（參見圖2（c））。最后，剩余CPU核心的一些工作負載被重新分配到主CPU核心中用于完成理想的工作負載分配（參見圖2（d））。也就是說，算法中將管理不可忽略的數(shù)據(jù)復(fù)制時間的主機CPU核心與其余的CPU核心區(qū)別對待。相反，如果數(shù)據(jù)復(fù)制時間可忽略（即，步驟3中的（2），則利用由步驟2計算的OWCPU和OWGPU來執(zhí)行CPU-GPU混合計算。

算法1 工作負載分配方法

步驟1：為GPU和CPU構(gòu)建不同的模型（Model）

（1）執(zhí)行CPU計算（采用主CPU和剩余CPU核）；

（2）計算獲得參數(shù)α，β，γ和δ；

步驟2：計算獲得OWCPU和OWGPU

步驟3：確定使用CPU核的順序

（1）IF（OWCPU/n）+data copy time＞（OWCPU/（n-1））

使用剩余的CPU核執(zhí)行計算（即采用n-1個核

根據(jù)式（3）、（5）和（6）更新CPU的性能預(yù)測模型

更新OWCPU和OWGPU

給主CPU核分配（OWCPU/（n-1））-TGPU（WGPU）

根據(jù)OWCPU和OWGPU執(zhí)行混合計算

（2）ELSE

使用CPU和主CPU核執(zhí)行計算（共n個核）

根據(jù)OWCPU和OWGPU執(zhí)行混合計算

3 實驗

為了驗證所提出的方法的優(yōu)勢，本文使用In?tel Core i5-3570 CPU（4核）和 GeForce GTX 660 GPU（960核）進行了實驗。實驗過程中使用120個圖像幀，圖像幀大小是1440×1080，1280×720，800×600，720×480和 640×480，此外，使用 OpenMP［8］和OpenCL［9］以CPU和GPU上并行化的特征提取。實驗過程中需要注意的是，雖然OpenMP不需要CPU內(nèi)的數(shù)據(jù)復(fù)制時間，但它不提供主機CPU內(nèi)核和其余CPU內(nèi)核之間非對稱工作負載分配的詳細操作。此外，圖2（c）到圖2（d）的性能改進遠小于來自圖2（b）到2（c）的性能改進，因此，我們將工作負載分布到CPU和GPU，如圖2（c）所示。為了獲得線性方程的參數(shù)，通過測量640×480圖像幀大小的CPU和GPU的特征提取的執(zhí)行時間，并且用于CPU（即α和β）和GPU（即γ和δ）的線性方程的參數(shù)的總結(jié)如表1所示。

表I 特征提取中性能預(yù)測模型的參數(shù)表

為了驗證性能預(yù)測模型，比較了預(yù)估的（即使用式（3）和（4））和實測的執(zhí)行時間，如圖3所示。結(jié)果表明，性能預(yù)測模型可以精確到足以估計最佳CPU-GPU的執(zhí)行時間與工作負載率比例。例如，圖像幀為1440×1080的CPU∶GPU最佳工作負載率為78%：22%。對于較大的圖像幀，由于受數(shù)據(jù)復(fù)制時間增加的影響，應(yīng)當減小GPU的最佳工作量大小以便提供更好的性能。注意，由于圖像幀為1440×1080的特征提取的順序執(zhí)行時間為760ms，我們應(yīng)該并行化特征提取以滿足視頻流處理的實時要求。

圖3 不同的CPU-GPU組合模式執(zhí)行的計算時間比較

為了詳細評估所提出的方法，將所提出的CPU-GPU混合計算方法的性能與三個典型工作負載分布（即，僅CPU，僅GPU或CPU-GPU混合計算工作負荷比為50∶50）。圖4顯示了即使對于GPU存在數(shù)據(jù)復(fù)制時間開銷，與僅CPU方法相比用于各種圖像幀大小的，僅GPU方法仍然提供更好的性能。我們還考慮了直接混合方法的性能（即使用所有四個CPU核心進行工作負載執(zhí)行和CPU-GPU計算，工作負載比為50∶50）。

圖4 工作負載分布的性能比較

然而，使用三個CPU的核心進行工作負載執(zhí)行本文所提出的算法，分別采用720×480，800×600，1280×720和1440×1080圖像幀，最終的最優(yōu)工作負載比為75∶25，77∶23，78∶22和78∶22。通過實驗結(jié)果，直接混合方法提供甚至比僅GPU方法更差的性能。結(jié)果顯示本文提出的混合計算方法執(zhí)行1440×1080圖像幀相比只有GPU的方法的性能可以提高達23%的。

4 結(jié)語

本文通過同時使用CPU和GPU有效地并行化視頻特征提取研究。使用性能預(yù)測模型估計了總執(zhí)行時間，并確定了最佳CPU∶CPU和GPU之間的GPU工作負載比率以及如何針對給定工作負載使用CPU內(nèi)核。本文作為處理主機CPU核心與剩余的CPU核心不同?；趯嶒灲Y(jié)果，本文確認所提出的方法可以提高僅CPU，僅GPU或CPU-GPU混合計算的性能，其工作負載比為50∶50。

［1］D.Tian.A Review on Image Feature Extraction and Repre?sentation Techniques［J］.International Journal of Multime?dia and Ubiquitous Engineering，2013，8（4）：385-395.

［2］M.Krulis，J.Lokoc and T.Skopal.Efficient Extraction of Feature Signatures Using Multi-GPU Architecture［M］.MMM LNCS，2013：446-456.

［3］S.Ohshima，K.Kise，T.Katagiri and T.Yuba.Parallel processing of matrix multiplication in a CPU and GPU het?erogeneous environment［M］.VECPAR LNCS，2006：305-318.

［4］C.Lee，W.Ro and J.Gaudiot.Boosting CUDA Applica?tions with CPU---GPU Hybrid Computing［M］.IEEE IN?TERACT，2012：384-404.

［5］X.Lu，B.Han，M.Hon，C.Xiong and Z.Xu：Adv.Eng［M］.Softw，2014：70-90.

［6］W.Sodsong，J.Hong，S.Chung，Y.Lim，S.Kim and B.Burgstaller.Dynamic Partitioning-based JPEG Decom?pression on Heterogeneous Multicore Architectures［M］.ACM PMAM，2014.

［7］L.Wan，K.Li，J.Liu and K.Li.A Novel CPU-GPU Coop?erative Implementation of A Parallel Two-List Algorithm for the Subset-Sum Problem［M］.ACM PMAM，2014：70-83.

［8］B.Chapman，G.Jost and R.Van.Using OpenMP：porta?ble shared memory parallel programming［M］.Cambridge MA MITPress，2008.

［9］B.Gaster，L.Howes，D.Kaeli，P.Mistry and D.Schaa：Heterogeneous Computing with OpenCL：Revised Open?CL 1.2 Edition［M］.Morgan Kaufmann，2012.

［10］S.Walsh，M.Saar，P.Bailey，and D.Lilja，Accelerat?ing geoscience and engineering system simulations on graphics hardware［J］.Computer&Geosciences 35，2009：2353-2364.

［11］D.Donno，A.Esposito，L.Tarricone，and L.Catarinuc?ci，Introduction to GPU Computing and CUDA Program?ming：A Case Study on FDTD［J］.IEEE Antennas and Propagation Magazine，2010，52（52）：116-122.

［12］P.Sattigeri，J.Thiagaraj an，K.Ramamurthy，and A.Spanias，Implementation of a fast image coding and re?trieval system using a GPU［C］//Emerging Signal Process?ing applications（ESPA），IEEEConference Publications，2012：5-8.

［13］S.Youssef，ICTEDCT-CBIR：Integrating curvelet trans?form with enhanced dominant colors extraction and tex?ture analysis for efficient content-based image retrieval［J］.Computers and Electrical Engineering 38，2012：1358-1376.

［14］M.Singha and K.Hemachandran，Content Based Image Retrieval Using Color and Texture［J］.Signal&Image Processing：An International Journal（SIPIJ），2012，3（1）：39-57.

Research on Image Feature Extraction and M atching Based on GPU Parallel Com puting

LIU Xiaoyu1LI Hong2
（Institute of Image Processing，Xianyang Normal College，Xianyang 712000）

TP393

10.3969/j.issn.1672-9722.2017.09.031

2017年3月8日，

2017年4月20日

陜西省教育廳科學(xué)研究計劃項目（編號：16JK1823）；咸陽師范學(xué)院專項科研基金項目“GPU并行計算在圖像處理中的應(yīng)用研究”（編號：15XSYK044）資助。

劉小豫，女，碩士，講師，研究方向：圖像處理、信息系統(tǒng)開發(fā)。李紅，女，副教授，研究方向：圖像處理與模式識別。