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

劉小豫 李 紅

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

劉小豫1李 紅2

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

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

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

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

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

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

1.2 相關(guān)概念

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

圖1 特征提取的計(jì)算特征的示例

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

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

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

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

2.1 確定最佳CPU：GPU工作負(fù)載比

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

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

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

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

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

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

2.2 算法介紹

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

算法1 工作負(fù)載分配方法

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

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

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

步驟2：計(jì)算獲得OWCPU和OWGPU

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

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

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

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

更新OWCPU和OWGPU

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

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

（2）ELSE

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

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

3 實(shí)驗(yàn)

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

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

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

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

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

圖4 工作負(fù)載分布的性能比較

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

4 結(jié)語

本文通過同時(shí)使用CPU和GPU有效地并行化視頻特征提取研究。使用性能預(yù)測(cè)模型估計(jì)了總執(zhí)行時(shí)間，并確定了最佳CPU∶CPU和GPU之間的GPU工作負(fù)載比率以及如何針對(duì)給定工作負(fù)載使用CPU內(nèi)核。本文作為處理主機(jī)CPU核心與剩余的CPU核心不同。基于實(shí)驗(yàn)結(jié)果，本文確認(rèn)所提出的方法可以提高僅CPU，僅GPU或CPU-GPU混合計(jì)算的性能，其工作負(fù)載比為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é)研究計(jì)劃項(xiàng)目（編號(hào)：16JK1823）；咸陽(yáng)師范學(xué)院專項(xiàng)科研基金項(xiàng)目“GPU并行計(jì)算在圖像處理中的應(yīng)用研究”（編號(hào)：15XSYK044）資助。

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