李 濤, 喬 虹, 黃虎才

(西安郵電大學 電子工程學院， 陜西 西安 710121)

基于PAAG的圖像處理算法并行化設計

李 濤, 喬 虹, 黃虎才

(西安郵電大學 電子工程學院， 陜西 西安 710121)

針對圖形處理中的Gamma校正算法和平均濾波算法，在多態(tài)并行陣列機上進行并行化設計。該設計利用多線程調度模式將算法中不相關程序分為多個線程相互填充，減少線程的阻塞等待時間，最后將多線程程序映射到陣列機上實現(xiàn)算法的并行化。仿真結果表明，Gamma校正算法在單線程下運行消耗時間是多線程的3.5倍，平均濾波算法在單線程下運行消耗時間是多線程的2.2倍。

多態(tài)陣列機；并行計算；圖像處理算法

在大規(guī)模并行計算領域，以圖形處理器(Graphic Processing Unit，GPU)為代表[1-2]的眾核處理器的研發(fā)逐漸成為主流。作為一種新型的體系結構，眾核處理器具有計算單元復雜度低、計算單元功耗低以及計算單元密集、性價比高等鮮明的特點，與多核處理器相比，眾核處理器的計算量吞吐量遠高于多核處理器[3]。用單個芯片上的成千上萬簡單處理核的并行計算能力來獲得高效能的計算，成為計算機體系結構研究的熱點[4]。

處理器中并行計算[5]的常用方法有數(shù)據(jù)級并行(Data Level Parallelism，DLP)[6]、指令級并行(Instruction Level Parallelism，ILP)[7]和線程級并行(Thread Level Parallelism，TLP)[8]。而迅速發(fā)展起來的Gamma校正和平均濾波等圖像處理算法具有非常強大的并行處理特征，使得該類算法被廣泛應用于處理器的并行計算研究中。

數(shù)據(jù)級并行[9]和指令級并行[10]都是單線程運行模式，通過使用較多的硬件資源來提高處理效率，存在硬件資源利用率較低的問題。本文針對數(shù)據(jù)級并行和指令級并行的缺點，提出了一種在PAAG架構上實現(xiàn)Gamma校正算法和平均濾波算法線程級并行的方法。以PAAG多態(tài)陣列處理器為硬件平臺，進行線程級并行設計，挖掘圖像處理領域中的大規(guī)模并行計算能力，從時空滿載的角度來使計算任務最大并行化，以利用眾核上的硬件資源，減少眾核處理器上硬件資源的浪費，以此解決目前眾多眾核處理器中資源利用率不高的問題。并借助仿真分析，將線程級并行的理論數(shù)據(jù)與實驗數(shù)據(jù)進行對比。

1 PAAG多態(tài)陣列處理器結構

PAAG由多個簇構成，每個簇為一個規(guī)則的二維陣列，一個基本簇由一個4行4列的陣列，共16個處理單元(Processing Element, PE)以及控制這些處理單元的行控制器(Row Controller)、列控制器(Column Controller)和共享存儲組成[11]。PE包含1個算術邏輯運算器、1個路由器、1個PE控制器、4個鄰接通信共享存儲、1個本地數(shù)據(jù)存儲和1個本地指令存儲。PAAG目前的設計可以支持多達1024個PE。PAAG支持單指令多數(shù)據(jù)流結構和多指令多數(shù)據(jù)流結構的并行編程方式，并且能夠結合數(shù)據(jù)并行，線程并行和操作并行等多種并行計算模式。

線程級并行是指應用層多個任務甚至多個輕量級任務(線程)之間的互不相關較為明顯，可以很自然的實現(xiàn)并行處理。

2 PAAG中線程并行方式的性能分析

在PAAG陣列處理器中，每個PE可以用來進行單個線程的計算，也可以進行多個線程的計算。在單線程執(zhí)行模式與多線程執(zhí)行模式下完成同一個算法，執(zhí)行時間可能有很大不同。每個圖像的像素處理指令分為復雜指令(稱為長周期指令)和簡單指令(稱為短周期指令)，長指令的周期一般是簡單指令的周期若干倍。定義以下符號。

Nshort：程序中短周期指令數(shù)。

Nlong：程序中長周期指令數(shù)。

Tshort：程序執(zhí)行短周期指令的時間。

Tlong：程序執(zhí)行長周期指令的時間。

N：所要處理的像素個數(shù)。

SUMs：單線程模式下單個PE對N個像素的處理所需時間。

SUMm：在多線程執(zhí)行模式下的PE中所消耗的時間。

C：C=Tl/Ts，表示長周期指令與短周期指令執(zhí)行時間的比例系數(shù)。

則短周期指令運行的時間為

Ts=Tshort×Nshort,

(1)

長周期指令執(zhí)行的時間為

Tl=Tlong×Nlong,

(2)

即有

SUMs=(Ts+Tl)×N。

(3)

根據(jù)式(1)和式(2)得到C的值為

(4)

則SUMm可表示為

(5)

(6)

其中常數(shù)8表示PAAG中PE的線程數(shù)。

3 圖像處理算法的線程級并行設計

在PE的單線程執(zhí)行模式中，對1 024×1 024個像素的圖像進行處理，在集成1 024個單線程PE的PAAG中，每個PE處理一行像素點進行運算。假設單線程模式下處理一幅圖像所消耗的時間為Time1。

在PE的多個線程執(zhí)行模式中，讓每個PE同時注入滿載數(shù)量的線程，即在PAAG中為8個線程，與單線程PE執(zhí)行模式一樣，每個PE處理一行像素，將一行像素的處理分配給每個線程，于是每個線程處理128個像素，并且PE中的8個線程所執(zhí)行的代碼完全一致，相互獨立。假設多線程模式下處理一幅圖像所消耗的時間為Time2。

3.1 Gamma校正

Gamma校正[12]是指在不改變圖像大小、幾何形狀以及局部結構的情況下，對像素值進行的一個映射。每個新的像素值完全依賴于相同位置的舊的像素值，而與其他位置像素值無關，尤其與其相鄰的任何像素無關。校正后的像素值p′可表示為

其中p表示原始的像素值，σ表示校正系數(shù)，pmax表示所有原始像素值中最大的像素值，pow表示指數(shù)操作，round表示取整操作。

LA 0x100,pmax

DIVF 0x101, 0x50, 0x100

POW 0x102, 0x101,σ

MULTF 0x50, 0x102, 0x100

其中存在兩個長周期的操作，分別為除法操作DIVF和指數(shù)操作POW，這兩個操作需要的時鐘數(shù)為其他操作的幾倍。從數(shù)據(jù)依賴關系角度考慮，在上述程序中，DIVF指令的執(zhí)行依賴于LA指令的執(zhí)行結果，即DIV指令的源操作數(shù)0x100是LA指令的目的操作數(shù)；POW指令的執(zhí)行依賴于DIV指令的執(zhí)行結果，即POW指令中的源操作數(shù)0x101是DIV指令的目的操作數(shù)；MULTF指令的執(zhí)行依賴于POW指令的執(zhí)行結果，即MULTF指令的源操作數(shù)0x102為POW指令的目的操作數(shù)。數(shù)據(jù)的此種依賴關系導致了在同一線程中，指令中的除法操作和指數(shù)操作指令阻塞了后續(xù)指令的運行?，F(xiàn)假設LA指令和DIVF指令之間所引起的阻塞時間為Tb0，DIVF指令和POW指令之間所引起的阻塞時間為Tb1，POW指令和MULTF指令之間所引起的阻塞時間為Tb2，那么一個像素的Gamma操作將導致Tb時鐘的阻塞等待時間，其中Tb為Tb0、Tb1和Tb2之和，如圖1的時間軸上半部分所示。

圖1 Gamma校正代碼單線程(上半部分)與多線程(下半部分)執(zhí)行時序

在PAAG的多線程PE執(zhí)行模式中，根據(jù)Gamma校正算法中線程獨立執(zhí)行的特性，通過引入新的線程，將新線程中的有效指令來填充阻塞等待時間，減少PE中線程的等待時間。如圖1所示，在單線程PE中，T1～T8為阻塞等待時間，而在多線程PE中(圖1中時間軸的下半部分)，每個線程在發(fā)射多周期指令后，立即進行線程的切換。當完成7個線程的相繼切換后，此時已經(jīng)到達T7時刻，而此時線程0已經(jīng)完成了對第一個像素的除法操作，此時重新調度線程0進入執(zhí)行，繼續(xù)完成指數(shù)操作POW運算。與浮點除法的調度相類似，線程1～線程7順序地被重新調度執(zhí)行。

在圖像的Gamma校正運算中，PE通過引入多線程調度執(zhí)行的方式使其PE在每個時鐘均進行有效指令的發(fā)射，從而使PE空閑比例減少，達到滿載狀態(tài)，PE中多個線程的執(zhí)行均為有效執(zhí)行，這就充分利用了線程并行執(zhí)行的特性，發(fā)揮了陣列機指令級并行計算能力。此時由圖1可知，單線程消耗時間Time1接近3.5倍多線程消耗時間Time2。也就是說，利用PE的多線程的合理調度，可以大幅度提高PE的利用率。

3.2 平均濾波器

平均濾波[13]就是把每個像素的新亮度值替換為其相鄰元素的亮度的平均值。像素的新亮度值可表示為

其中I(u,v)表示像素的原亮度值，通過疊加像素周圍的8個亮度值和本身的亮度值，取平均值即為新亮度值。

如圖2所示，假設I(u,v)表示4號像素，對其進行平均濾波計算時，需要提取0～8號像素亮度值進行求和，之后再進行一次除法操作。

圖2 平均濾波圖形表示

使用匯編代碼實現(xiàn)上述算法，具體代碼如下。

ADD sum, pixel0, pixel1

ADD sum1, pixel2, pixel3

ADD sum2, pixel5, pixel6

ADD sum3, pixel7, pixel8

ADD sum, sum, sum1

ADD sum1, sum2, sum3

ADD sum, sum, sum1

ADD sum, sum, pixel4

DIV newpixel, sum, 9

在平均濾波運算過程中，每個新生成像素的值由原始圖像數(shù)據(jù)的像素及其周圍8個像素所決定，采用靜態(tài)數(shù)據(jù)固定加載映射的方法，平均濾波器所具有的并行性與圖像的Gamma校正運算相一致。

由平均濾波算法的代碼可知，完成一個像素的平均濾波需要執(zhí)行一條除法操作，在PAAG中，除法操作DIV為多周期運算指令，為了彌補長延時操作所帶來的損失，每個線程在進行除法運算時，每個PE將會進行線程的切換，將其他線程調入執(zhí)行。如圖3所示，線程0在執(zhí)行完成ADD操作后，直接發(fā)射DIV操作，線程0被切換出去，線程1被切換至執(zhí)行狀態(tài)，由于PAAG中的除法操作沒有進行流水，線程1在執(zhí)行完成ADD操作后，將線程2切換到執(zhí)行狀態(tài)，在線程2執(zhí)行ADD操作結束后，線程0中的DIV操作執(zhí)行結束，線程1被調入執(zhí)行發(fā)射DIV操作后，線程3被切換至執(zhí)行狀態(tài)，發(fā)射ADD操作指令。當線程4中的DIV操作發(fā)射時，也就是到達T4時刻，線程0已執(zhí)行結束。縱觀8個線程的執(zhí)行過程，長延時除法操作最終由于線程的切換調度執(zhí)行，其阻塞時間被消除。此時，每個PE在數(shù)據(jù)滿載的情況下即可獲得最大的指令級并行度?？梢钥闯鰡尉€程PE執(zhí)行模式下所消耗的時間Time1接近等于多線程消耗時間Time2的2.2倍。

圖3 平均濾波器程序的單線程(上半部)和多線程(下半部)執(zhí)行時序

4 實驗結果

將Gamma校正算法和平均濾波算法的單線程模式和多線程模式映射在PAAG多態(tài)陣列處理器中，統(tǒng)計每種模式的具體執(zhí)行時間。根據(jù)式(1)～式(6)，結合PAAG多態(tài)陣列處理器特性，分別取短周期操作指令執(zhí)行時間Tshort= 2，長周期指令Tlong= 23，得到圖像處理算法執(zhí)行的仿真結果如圖4和圖5所示。

從圖4可以看出，Gamma校正程序完成相同個數(shù)的像素處理時，單線程PE執(zhí)行模式下所消耗的時間約等于多線程PE執(zhí)行模式下所消耗時間的3.5倍；圖5可以看出，平均濾波程序完成相同個數(shù)的像素處理時，單線程PE所消耗的時間約等于多線程消耗時間的2.2倍?？梢缘贸?，多線程處理速度高于單線程處理速度，執(zhí)行效能優(yōu)于單線程模式。另外，PE中多個線程的有效執(zhí)行，使得PE空閑比例減少，達到滿載狀態(tài)，提高了PE的利用率。因此，合理使用PAAG多態(tài)陣列處理器的多線程并行，能夠提高硬件資源的利用率。

圖4 Gamma校正程序的多線程和單線程模式仿真結果

圖5 平均濾波算法多線程和單線程模式仿真結果

5 結束語

以圖像處理算法中的Gamma校正和平均濾波為例，通過分析推導出PAAG陣列處理器中單個PE在兩種不同執(zhí)行模式下的性能統(tǒng)計計算公式，利用單線程執(zhí)行模式和多線程執(zhí)行模式結合算法的指令執(zhí)行特征進行了詳細的分析，實現(xiàn)了Gamma校正和平均濾波算法的線程級并行化計算,并利用實驗數(shù)據(jù)結果驗證了理論分析結果。仿真結果表明，利用PAAG基本處理單元PE的多線程執(zhí)行模式，在PAAG上進行圖像處理將能獲得性能的提升，并改善了由于阻塞等待所帶來的較低硬件資源利用率的情況。

[1] 韓俊剛，劉有耀，張曉.圖形處理器的歷史現(xiàn)狀和發(fā)展趨勢[J].西安郵電學院學報，2011,16(3):61-64.

[2] Diaz J, Munoz-Caro C, Nino A. A Survery of Parallel Programming Models and Tools in the Multi and Many-Core Era.Parallel and Distributed Systems[J].IEEE Computer Society,2012,23(8):1369-1386.

[3] Borkar S. Thousand core chips: A Technology Perspective[J]. Design Automation Conference, 2007,19(7):746-749.

[4] Marowka， Ramat Gan. Back to Thin-Core Massively Parallel Processors[J]. IEEE Computer Society, 2011,44(12):49-54

[5] 陳國良. 并行計算:結構，算法，編程[M]. 北京：高等教育出版社，2003:23-56.

[6] Hillis D. New computer architectures and their relationship to physics or why CS is no good[J].International Journal of Theoretical Physics,1982, 21(3/4):255-262.

[7] Hennessey J, Patterson D. Computer architecture: A quantitative approach[M].4th Ed. San Francisco: Morgan Kauffmann,2006:33-39.

[8] Quinn MJ. Parallel programming in C with MPI and OpenMP[M]. NY: McGraw-Hill,2004:103-120.

[9] 韓俊剛,姚靜,李濤，等.多態(tài)并行機上的3D圖形渲染[J].西安郵電大學學報,2015,20(2):1-6.

[10] 李濤,孫健.基于PAAG的OpenVX核心庫函數(shù)并行化實現(xiàn)[J].西安郵電大學學報,2015,20(2):7-10.

[11] 李濤,肖靈芝.面向圖形和圖像處理的輕核陣列機結構[J]. 西安郵電學院學報, 2012, 17(3): 41-47.

[12] Lindholm E, Nickllls J, Oberman S, et al. NVIDIA Tesla: a unified graphics and computing architecture[J]. IEEE Micro, 2008, 28(2):39-55.

[13] KhronosGroup.OpenVX[EB/OL].(2013-11-19)[2014-11-12]. http://cn.khronos.org/openvx.

[責任編輯:祝劍]

Research of image processing parallelization on PAAG

LI Tao, QIAO Hong, HUANG Hucai

(School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

A parallel implementation method is presented in this paper for Gamma correction and average filtering algorithm of image processing on Polymorphic Array Architecture for Graphics and image processing (PAAG). The multi-thread scheduling mode is used to divide irrelevant programs into multiple threads and to fill each other to reduce blocked waiting times of single thread. Thus, the multi-thread program is mapped to array implements parallelization of Gamma correction and average filtering algorithm. Simulation results show that Gamma correction consumes 3.5 times running time under single-thread mode than that under multi-thread mode, and that the average filtering algorithm 2.2 times.

polymorphic array processor, parallel computing, image processing

2014-12-01

國家自然科學基金重大項目(61136002)

李濤(1954-)，男，博士，教授，從事計算機體系結構，計算機圖形學研究。E-mail:litao@xupt.edu.cn 喬虹(1988-)，女，碩士研究生，研究方向為圖形圖像與視頻處理。E-mail:404910814@qq.com

10.13682/j.issn.2095-6533.2015.03.004

TN492

A

2095-6533(2015)03-0029-05