多處理部件并行優化方法研究

李 釗,鄭 紅

(北京航空航天大學自動化科學與電氣工程學院,北京100191)

多處理部件并行優化方法研究

李 釗,鄭 紅

(北京航空航天大學自動化科學與電氣工程學院,北京100191)

針對多處理單元(PE)并行優化中運行時間和資源消耗隨PE數量變化而增加的問題,分析多PE并行中運行時間和資源消耗隨PE數量的變化規律,建立基于運行時間和資源消耗的優化目標函數,并從理論上證明優化目標函數最小值的存在性和唯一性,提出基于運行時間與資源消耗的多PE并行優化方法。該優化方法可在最小資源消耗的情況下實現運行時間的最優化。利用灰度共生矩陣和單精度浮點矩陣乘法的多PE優化方法進行驗證。實驗結果表明,多PE并行的優化方法實現了運行時間和資源消耗的優化,在運行時間上該方法比已有方法最高快6.79倍,在運行時間和資源消耗的綜合對比上該方法最高為已有方法的3.3倍,能夠實現基于運行時間和資源消耗的優化。

多處理單元并行;優化方法;運行時間;資源消耗;灰度共生矩陣;單精度浮點矩陣乘法

1 概述

多處理單元(Processing Element,PE)是一個能實現特定功能的處理單元,在不同的硬件平臺上PE具有不同的表現形式,例如在通用并行硬件平臺上一個PE可以是一臺PC機或者工作站,在嵌入式并行硬件平臺上一個PE可以是一片微處理器芯片,也可以是芯片中的一個核或者是可編程邏輯器件中由邏輯單元組成的能實現特定功能的一個功能模塊。根據待處理算法的不同設計不同的PE,以實現特定的功能,PE與PE之間可以并行執行,以提高算法實時性。目前,設計多個PE并行的計算結構實現算法的并行計算,在信號處理和圖像處理等領域得到廣泛應用。

文獻[1]在實現一維快速傅里葉變換(one-Dimensional Fast Fourier Transform,1-D FFT)計算的基礎上,以1-D FFT計算單元為核心設計實現2-D FFT的PE,并利用多個PE并行實現二維快速傅里葉變換(two-Dimensional Fast Fourier Transform,2-D FFT)的計算,PE的數量由可使用的硬件資源決定。文獻[2]利用圖像處理算法的數據并行性,設計基于2D脈動陣列的多PE并行的計算結構,該結構可以完成圖像卷積和模板匹配等算法的計算。文獻[1-2]利用多個PE的并行執行有效減少了算法的運行時間,但是隨著PE數量的增加會消耗更多的硬件資源,而硬件資源是有限的,因此,在改善運行時間的同時,也需要降低系統的資源消耗。文獻[3]設計數量可擴展的多個PE線性陣列,實現任意維數的矩陣乘法,PE的數量由存儲器帶寬和硬件資源決定,PE內采用流水線結構設計,利用數據訪問的局部性和可重用性降低資源消耗。文獻[4]提出2種計算浮點矩陣乘法的多個PE并行的結構,算法1可實現最大程度的并行,但需要消耗較多的硬件資源和I/O帶寬,算法2對算法1進行了改進,通過減少PE的數量雖然增加了算法運行時間,但是也降低了資源消耗,提高了資源的利用率。文獻[3-4]在改善算法運行時間的同時開始用各種方法降低資源消耗,但是沒有對運行時間、資源消耗與PE數量之間的關系進行分析,未實現運行時間和資源消耗的優化設計。

隨著PE數量的增加,算法需要占用越來越多的硬件資源,并且隨著PE數量的增加,PE間的通信開銷會逐漸增加,布線延時也會隨之增加。布線延時的增加會導致運行時間的增加。由于不是設計越多的PE就會得到更好的運行性能,因此本文對PE的數量(P)與PE占用的硬件資源和運行時間等參數之間的關系進行分析,建立運行時間和資源消耗的優化目標函數,實現運行時間和資源消耗的優化。

2 多PE并行運行時間和資源消耗的優化

本文以現場可編程邏輯門陣列(Field Programmable Gate Array,FPGA)為例對多PE的運行時間和資源消耗影響因素及規律進行分析,在FPGA內PE由加法器、乘法器、累加器和比較器等基本功能邏輯單元構成。

2.1 多PE并行資源消耗影響因素

FPGA資源消耗主要包括占用基本可編程邏輯單元的數量和片上存儲空間的數量。本文對PE占用基本可編程邏輯單元的數量進行分析。以Xilinx公司Virtex系列的FPGA為例,一個基本可編程邏輯單元(Configurable Logic Block,CLB)由2個slice組成,一個算法的資源消耗最終可由slice的數量來表示。

α與Sslice的關系如圖1(a)所示,當PE中各個基本功能邏輯單元占用的slice數量即Sslice＜600時,α呈現震蕩趨勢,當Sslice≥600時,α基本保持不變。因為當PE規模較小時,一個slice中僅利用了部分查找表和觸發器,而隨著PE設計規模的增加,一個slice中更多的查找表和觸發器得到利用,因此,當PE規模較小時,PE占用slice的數量與PE的規模并不呈線性關系,只有當PE達到一定程度后,占用slice的數量與PE的規模才呈線性關系。圖1(b)為Tslice與Sslice在比例因子α作用下的關系圖,當Sslice＜600時,Tslice與Sslice呈非線性關系,當Sslice≥600時,Tslice與Sslice呈線性關系。

圖1 α,Tslice與Sslice的關系

2.2 多PE并行運行時間影響因素

FPGA設計中,可通過布線資源連接不同基本功能單元實現某一特定功能,因此運行時間LE主要由各基本功能單元的運行時間組成的邏輯器件延時Llogic和布線延時Lrouting組成,如式(2)所示。各基本功能邏輯單元的延時Llogic由其實現的功能及采用的FPGA決定。布線延時Lrouting直接由布線的長度決定,因此要計算布線延時需要先正確的估算布線的長度,布線長度可由式(3)計算得到[6]。其中,C表示CLB的數量(可通過slice數量計算得到);p表示Rent系數其值設為0.72。圖2為布線長度與CLB數量的關系曲線,隨著CLB數量增加,布線長度也隨之增加,即PE占用的資源越多就需要更多的布線資源實現邏輯單元之間的連接。

圖2 布線長度和CLB數量的關系

至此,布線延時Lrouting可由式(5)計算得到,其中,Lengthbetween_PIPs表示 2個可編程連接點(Programmable Interconnect Points,PIPs)之間的長度;Lbetween_PIPs+Linside_PIPs表示PIPs之間的延時與PIPs內部延時之和。

FPGA內部具有短線、長線和全局互聯線等布線資源,在布局布線過程中,一個PE占用的資源會集中在一個區域,PE中會消耗較多的短線資源以實現基本邏輯單元之間的互連。為便于計算,設Lengthbetween_PIPs為短線長度,與Lbetween_PIPs和Linside_PIPs都可從相應FPGA文檔中得到。

設處理的算法可分為H個并行處理的部分,采用P個PE并行對圖像算法進行處理,則待處理算法的運行時間L如式(6)所示。將式(2)、式(3)、式(5)代人到式(6)中即得到P個PE并行處理所需要的延時計算式式(7)。

2.3 優化目標函數

由式(1)和式(7)可得,隨著PE數量的增加整個系統的運行時間會越來越小,但是由于受到布線延時的影響,當PE數量增加到一定程度后,系統的運行時間減小的趨勢會減弱,而資源消耗會隨著PE個數P的增加呈線性增長。要想得到較好運行時間需要較大的資源消耗,運行時間和資源消耗之間是相互矛盾的,需對兩者進行優化設計。

因為運行時間和資源消耗具有不同的量綱,兩者之間沒有一個統一的度量標準,難以直接對其進行優化,所以需要對運行時間和資源消耗進行無量綱化處理,無量綱化公式如式(8)所示,其中,fmin(x)、fmax(x)分別表示f(x)在自變量變化范圍內的最小值和最大值。

一般P的最小值Pmin為1,此時為串行操作,P的最大值Pmax由圖像大小、FPGA硬件資源和具體的圖像處理算法決定。由式(1)和式(7)可得,P=Pmin時運行時間L取得最大值Lmax(P),資源消耗Tslice取得最小值Tslicemin(P);P=Pmax時L取得最小值Lmin(P),Tslice取得最大值Tslicemax(P)。利用式(8)可計算得到無量綱化后的運行時間L′(P)和資源消耗T′slice(P)。因為運行時間和資源消耗的優化目標都是實現目標函數的最小化,所以可直接將L′(P)與T′slice(P)相加構造新的優化目標函數U(P),即:

U(P)=L′(P)+T′slice(P) (9)

因為L′(P)和T′slice(P)的值越小系統的整體性能就越優,所以U(P)的最小值點即為系統整體性能的最優點。

現對U(P)最小值的存在性和唯一性進行證明。

證明:

(1)U(P)最小值存在性證明

1)因為L′(P)和T′slice(P)在閉區間[Pmin,Pmax]上為連續函數,所以U(P)=L′(P)+T′slice(P)在閉區間[Pmin,Pmax]上連續,則由有界性定理得{U(P)|P∈[Pmin,Pmax]}有界。

2)設M為U(P)在[Pmin,Pmax]上的下確界,即inf{U(P)|P∈[Pmin,Pmax]}=M。用反證法證明U(P)最小值存在性。

與M為U(P)在[Pmin,Pmax]上的下確界的假設相矛盾,存在Popt∈[Pmin,Pmax],使得U(Popt)=M,即函數U(P)在區間[Pmin,Pmax]內可取得最小值。

(2)U(P)最小值唯一性證明

3 多PE并行優化方法驗證

根據灰度共生矩陣和單精度浮點矩陣乘法計算的特點,設計多個PE并行結構,利用本文提出的方法對灰度共生矩陣和單精度浮點矩陣乘法的PE并行結構進行優化,實現運行時間和資源消耗的優化。

3.1 灰度共生矩陣的優化

灰度共生矩陣是研究圖像紋理特征的一個有效手段,并廣泛應用于生物醫學[7-8]、目標檢測[9-10]、質量控制[11]和遙感圖像分析[12]等領域。

3.1.1 灰度共生矩陣PE的設計

計算灰度共生矩陣的PE如圖3所示[13]。因為每個像素對的計算都是相互獨立的,從并行計算的角度考慮,可設計多個PE并行完成灰度共生矩陣的計算。

圖3 灰度共生矩陣的PE結構

3.1.2 灰度共生矩陣PE資源消耗分析

如圖3所示,一個PE中主要包含地址組合器和數據加法器2個功能模塊,并且一個PE共有3個16位定點加法器和1個16位定點乘法器等基本邏輯功能單元,其中2個16位定點加法器和1個16位定點乘法器用于實現地址組合器。加法器和乘法器占用slice的數量可用式(10)、式(11)進行計算,其中,M=max(in1(I+F),in2(I+F));I為整數部分的位寬;F為小數部分的位寬。

資源消耗隨PE的個數P的變化趨勢如圖4所示,資源消耗會隨著PE個數P的增加呈線性增長。

圖4 灰度共生矩陣資源消耗隨PE個數變化趨勢

3.1.3 灰度共生矩陣運行時間分析

通過式(7)可計算得到P個PE對64×64大小的圖像操作的運行時間,運行時間隨著PE個數P的變化趨勢如圖5所示,隨著PE數量的增加整個系統的運行時間會越來越小,但由于受到布線延時的影響,當PE數量增加到一定程度后,系統的運行時間會基本保持不變。

圖5 灰度共生矩陣運行時間隨PE個數變化趨勢

3.1.4 灰度共生矩陣運行時間和資源消耗的優化

無量綱化后的運行時間L′(P)、面積消耗T′slice(P)和U(P)隨PE的個數P的變化趨勢如圖6所示。當P=8.45時可實現面積消耗和運行時間的折衷優化。本設計中為了便于計算,要求P應能夠被N×N整除,因此,取P=8。

圖6 灰度共生矩陣隨PE的變化趨勢

3.2 單精度浮點矩陣乘法的優化

單精度浮點矩陣乘法的PE采用文獻[4]提出的第2種設計方法,一個PE包含1個32位浮點乘法器、1個32位浮點加法器和2個多路復用器等基本功能邏輯單元,其中,浮點加法器和浮點乘法器采用并行和流水線結構設計。設矩陣A、B維數為40×40,將矩陣A分成20×40的2個子模塊,將矩陣B分成40× 20的2個子模塊,實現浮點矩陣乘法的計算。

3.2.1 單精度浮點矩陣乘法PE資源消耗分析

一個PE共有1個32位浮點乘法器、1個32位浮點加法器和2個多路復用器等基本功能邏輯單元。32位浮點加法器占用slice的數量可用式(13)進行計算,其中,E表示指數位數;M表示尾數位數,也可通過ISE軟件綜合得到。32位浮點乘法器和多路復用器占用的slice數量由ISE軟件綜合得到。

Slice(add_FP)=5.40×E+11.06×M+51.20

(13)

結合式(1)可計算得到P個PE的資源消耗,資源消耗隨PE的個數P的變化趨勢如圖7所示,資源消耗會隨著PE個數P的增加呈線性增長。

圖7 矩陣乘法資源消耗隨PE個數變化趨勢

3.2.2 單精度浮點矩陣乘法PE運行時間分析

單精度浮點矩陣乘法 PE的邏輯延時Llogic如式(14)所示。布線延時Lrouting直接由布線長度決定,布線長度可由式(3)計算得到。至此,布線延時Lrouting可由式(5)計算得到。

通過式(7)可計算得到P個PE對40×40大小的單精度浮點矩陣乘法的運行時間,運行時間隨著PE的個數P的變化趨勢如圖8所示。隨著PE數量的增加整個系統的運行時間會越來越小,但由于受到布線延時的影響,當PE數量增加到一定程度后,系統的運行時間會基本保持不變。

圖8 矩陣乘法運行時間隨PE個數變化趨勢

3.2.3 運行時間和資源消耗優化分析

無量綱化后的運行時間L′(P)、面積消耗T′slice(P)和U(P)隨PE的個數P的變化趨勢如圖9所示。當P=3.42時可實現面積消耗和運行時間的折衷優化。根據文獻[4],P應能夠被20整除,因此,取P=4,即當P=4時可實現運行時間和資源消耗的優化設計。

圖9 矩陣乘法隨PE的變化趨勢

4 實驗結果與分析

為進一步驗證本文提出的方法,將本文提出的計算灰度共生矩陣的方法和計算矩陣乘法的方法在XC5VFX100T上進行實驗驗證。將灰度共生矩陣的計算方法與文獻[14-16]提出的計算灰度共生矩陣的方法分別從運行時間和資源消耗方面進行對比。因為文獻[14-16]中并行計算了d={1,2,3,4},θ= {0°,45°,90°,135°}相組合的16個灰度共生矩陣,但是在實際應用中,針對具體圖像只計算d,θ的一種組合即可,為了便于和本文方法比較只利用文獻提出的方法計算d=1,θ=0°的灰度共生矩陣,從運行時間和資源消耗方面對采用不同數量的PE實現矩陣乘法進行了對比分析。

4.1 資源消耗對比

表1為本文提出的方法與文獻[14-16]方法實現灰度共生矩陣計算的資源消耗對比。文獻中采用16個PE完成灰度共生矩陣的計算,而本文提出的方法采用了8個PE并行完成對灰度共生矩陣的計算,并且每一個PE有3個加法器和1個乘法器,每個加法器和乘法器都會占用一定的slice。本文方法消耗的 slice數最少,并且本文方法消耗的 slice registers和slice LUT的數量也是最少的。另外與文獻[14-15]相比,本文方法沒有使用外部存儲資源,對片外存儲器訪問的延時是片內存儲器的1個～2個數量級,因此,提高了系統的實時性。表2為采用不同數量的PE實現矩陣乘法的資源消耗情況,隨著PE數量的增加會消耗更多的硬件資源。

表1 灰度共生矩陣資源消耗對比

表2 矩陣乘法資源消耗對比

4.2 運行時間對比

圖10是在XC5VFX100T上計算圖像大小為64×64像素的灰度共生矩陣時各方法運行時間的對比。本文方法計算64×64像素圖像的運行時間為76 μs,比文獻[14]方法快6.79倍,比文獻[16]方法快4.75倍,比文獻[15]方法快3.80倍。圖11是在XC5VFX100T上采用不同數量的PE計算40×40像素的浮點矩陣乘法的運行時間對比,隨著PE數量的增加運行時間逐漸減少,但其減少的幅度越來越小,例如4PE并行時的運行時間比1PE時快3.72倍,而8PE并行時的運行時間為4PE并行時快1.72倍,因為隨著PE數量的增加,PE間的通信開銷會逐漸增加,布線延時也會隨之增加,布線延時的增加會導致運行時間的增加。

圖10 灰度共生矩陣運行時間對比

圖11 矩陣乘法運行時間對比

4.3 運行時間和資源消耗綜合對比

圖12是灰度共生矩陣各種方法中運行時間和資源消耗歸一化后的綜合對比。與其他方法相比,本文方法的運行時間和資源消耗最小,實現了資源消耗和性能的優化。

圖12 灰度共生矩陣運行時間和資源消耗的綜合對比

圖13是采用不同數量的PE計算矩陣乘法的運行時間和資源消耗的綜合對比,利用本文提出的優化方法設計的4PE并行的運行時間和資源消耗最小,實現了資源消耗和性能的優化。

圖13 矩陣乘法運行時間和資源消耗的綜合對比

5 結束語

本文根據多PE并行中運行時間和資源消耗隨PE數量變化的規律,提出了基于運行時間與資源消耗的多PE并行優化方法,利用本文提出的優化方法對灰度共生矩陣和單精度浮點矩陣乘法進行了優化,并將本文提出的灰度共生矩陣并行計算方法與現有的灰度共生矩陣計算方法進行對比,實驗結果表明該優化方法可實現多PE并行中運行時間與資源消耗的優化。

由于多PE并行以單PE為基礎,因此單PE優化對于系統整體性能的提高具有重要意義,而單PE的內部操作之間具有相關性,這些相關性與實現的具體任務有關,可采用流水線結構進行設計,下一步工作需要對基于運行時間與資源消耗的流水線優化進行研究。

[1] Uzun I S,Bouridance A A A.FPGA Implementations of Fast Fourier Transforms for Real-time Signal and Image Processing[J].Vision,Image and Signal Processing, 2005,152(3):283-296.

[2] Huitzil C T,Estrada M A.Real-time Image Processing with a Compact FPGA-based Systolic Architecture[J]. Real Time Imaging,2004,10(3):177-187.

[3] Dou Yong,Vassiliadis S,Kuzmanov G K,et al.64-bit Floating-point FPGA Matrix Multiplication[C]//Proc.of the 13th International Symposium on Field Programmable Gate Arrays.Monterey,USA:[s.n.],2005:86-95.

[4] Kumar V B Y,Joshi S,Patkar S B,et al.FPGA Based High Performance Double-precision Matrix Multiplication[J]. International Journal of Parallel Programming,2010,38(4):322-338.

[5] Deng Linpeng,Sobti K,Zhang Yuanrui,et al.Accurate Area,Time and PowerModelsforFPGA-based Implementation[J].Journalof SignalProcessing Systems,2011,63(1):39-50.

[6] Nayak A,Haldar M,Choudhary A,et al.Accurate Area and Delay EstimatorsforFPGAs[C]//Proc.of International Conference on Design Automation and Test in Europe.Paris,France,2002:862-869.

[7] Chai H Y,Wee L K,Swee T T,et al.Gray-level Cooccurrence Matrix Bone Fracture Detection[J]. American Journal of Applied Sciences,2011,8(1): 7-16.

[8] Hafizah W M,Supriyanto E,Yunus J.Feature Extraction ofKidney Ultrasound Images Based on Intensity Histogram and Gray Level Co-occurrence Matrix[C]// Proc.of the 6th Asia Modelling Symposium.Bali, Indonesia:[s.n.],2012:115-120.

[9] Gupta M,Bhaskar D,Bera R,et al.Target Detection of ISAR Data by Principal Component Transform on Cooccurrence Matrix[J].Pattern Recognition Letters, 2012,33(13):1682-1688.

[10] Dash A,Kanungo P,Mohanty B P.A Modified Gray Level Co-occurrence Matrix Based Thresholding for Object Background Classification [C]//Proc.of International Conference on Communication Technology and System Design.Tamil Nadu,India:[s.n.],2011: 85-91.

[11] Lu Wenbo,Jiang Weikang,Wu Haijun,et al.A Fault Diagnosis Scheme of Rolling Element Bearing Based on Near-field Acoustic Holography and Gray Level Cooccurrence Matrix[J].Journal of Sound and Vibration, 2012,331(15):3663-3674.

[12] 張紹明,何向晨,張小虎,等.高分辨率星載SAR圖像水上橋梁解譯[J].電子與信息學報,2011,33(7): 1706-1712.

[13] 鄭 紅,李 釗,李 俊.灰度共生矩陣的快速實現和優化方法研究[J].儀器儀表學報,2012,23(11): 2509-2515.

[14] Tahir M A,Bouridane A,Kurugollu F,etal.Accelerating the Computation of GLCM and Haralick Texture Features on Reconfigurable Hardware[C]//Proc.of International Conference on Image Processing.[S.l.]: IEEE Press,2004:2857-2860.

[15] Iakovidis D K,Maroulis D E,Bariamis D G.FPGA Architecture forFastParallelComputation ofCooccurrence Matrices [J]. Microprocessors and Microsystems,2007,31(2):160-165.

[16] Sieler L,Tanougast C,Bouridance A.A Scalable and Embedded FPGA Architecture for Efficient Computation of Grey Level Co-occurrence Matrices and Haralick Textures Features [J]. Microprocessors and Microsystems,2010,34(1):14-24.

編輯 顧逸斐

Research on Optimization Method of
Multiple Processing Element Parallelization

LI Zhao,ZHENG Hong
(School of Automation Science and Electrical Engineering,Beihang University,Beijing 100191,China)

The changing of run time and resource consumption with the number of the Processing Element(PE)is contrary.The rules of run time and resource consumption with the number of PE are analyzed.And the variation trend for resource consumption and run time with the number of PE is got.The optimization objective function based on run time and resource consumption is established.The existence and uniqueness of the minimum for optimization objective function are proved.The multi-PE optimization method based on run time and resource consumption is proposed.This method can realize the run time optimization with the least resource consumption.In order to validate the method,the optimal design of the calculation of the gray level co-occurrence matrix and single float matrix multiplication are proposed.Experimental results indicate that the runtime of gray level co-occurrence matrix is at most 6.79 times than the old method.The integrated result about runtime and area consumption is 3.3 times than the old method.The optimization of runtime and area consumption is implemented.

multiple Processing Element(PE)in parallel;optimization method;runtime;area consumption;gray level co-occurrence matrix;single float matrix multiplication

1000-3428(2014)09-0305-07

A

TP316

10.3969/j.issn.1000-3428.2014.09.061

國家自然科學基金資助項目(60543006);博士點基金資助項目(201003259);光電信息重點實驗室基金資助項目(9140 C150105100C1502)。

李 釗(1983-),男,博士研究生,主研方向:并行計算,嵌入式系統設計;鄭 紅,教授。

2013-07-01

2013-08-28E-mail:lizhao_buaa@126.com