李 釗,鄭 紅

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

多處理部件并行優(yōu)化方法研究

李 釗,鄭 紅

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

針對(duì)多處理單元(PE)并行優(yōu)化中運(yùn)行時(shí)間和資源消耗隨PE數(shù)量變化而增加的問題,分析多PE并行中運(yùn)行時(shí)間和資源消耗隨PE數(shù)量的變化規(guī)律,建立基于運(yùn)行時(shí)間和資源消耗的優(yōu)化目標(biāo)函數(shù),并從理論上證明優(yōu)化目標(biāo)函數(shù)最小值的存在性和唯一性,提出基于運(yùn)行時(shí)間與資源消耗的多PE并行優(yōu)化方法。該優(yōu)化方法可在最小資源消耗的情況下實(shí)現(xiàn)運(yùn)行時(shí)間的最優(yōu)化。利用灰度共生矩陣和單精度浮點(diǎn)矩陣乘法的多PE優(yōu)化方法進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,多PE并行的優(yōu)化方法實(shí)現(xiàn)了運(yùn)行時(shí)間和資源消耗的優(yōu)化,在運(yùn)行時(shí)間上該方法比已有方法最高快6.79倍,在運(yùn)行時(shí)間和資源消耗的綜合對(duì)比上該方法最高為已有方法的3.3倍,能夠?qū)崿F(xiàn)基于運(yùn)行時(shí)間和資源消耗的優(yōu)化。

多處理單元并行;優(yōu)化方法;運(yùn)行時(shí)間;資源消耗;灰度共生矩陣;單精度浮點(diǎn)矩陣乘法

1 概述

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

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

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

2 多PE并行運(yùn)行時(shí)間和資源消耗的優(yōu)化

本文以現(xiàn)場(chǎng)可編程邏輯門陣列(Field Programmable Gate Array,FPGA)為例對(duì)多PE的運(yùn)行時(shí)間和資源消耗影響因素及規(guī)律進(jìn)行分析,在FPGA內(nèi)PE由加法器、乘法器、累加器和比較器等基本功能邏輯單元構(gòu)成。

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

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

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

圖1 α,Tslice與Sslice的關(guān)系

2.2 多PE并行運(yùn)行時(shí)間影響因素

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

圖2 布線長(zhǎng)度和CLB數(shù)量的關(guān)系

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

FPGA內(nèi)部具有短線、長(zhǎng)線和全局互聯(lián)線等布線資源,在布局布線過程中,一個(gè)PE占用的資源會(huì)集中在一個(gè)區(qū)域,PE中會(huì)消耗較多的短線資源以實(shí)現(xiàn)基本邏輯單元之間的互連。為便于計(jì)算,設(shè)Lengthbetween_PIPs為短線長(zhǎng)度,與Lbetween_PIPs和Linside_PIPs都可從相應(yīng)FPGA文檔中得到。

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

2.3 優(yōu)化目標(biāo)函數(shù)

由式(1)和式(7)可得,隨著PE數(shù)量的增加整個(gè)系統(tǒng)的運(yùn)行時(shí)間會(huì)越來越小,但是由于受到布線延時(shí)的影響,當(dāng)PE數(shù)量增加到一定程度后,系統(tǒng)的運(yùn)行時(shí)間減小的趨勢(shì)會(huì)減弱,而資源消耗會(huì)隨著PE個(gè)數(shù)P的增加呈線性增長(zhǎng)。要想得到較好運(yùn)行時(shí)間需要較大的資源消耗,運(yùn)行時(shí)間和資源消耗之間是相互矛盾的,需對(duì)兩者進(jìn)行優(yōu)化設(shè)計(jì)。

因?yàn)檫\(yùn)行時(shí)間和資源消耗具有不同的量綱,兩者之間沒有一個(gè)統(tǒng)一的度量標(biāo)準(zhǔn),難以直接對(duì)其進(jìn)行優(yōu)化,所以需要對(duì)運(yùn)行時(shí)間和資源消耗進(jìn)行無量綱化處理,無量綱化公式如式(8)所示,其中,fmin(x)、fmax(x)分別表示f(x)在自變量變化范圍內(nèi)的最小值和最大值。

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

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

因?yàn)長(zhǎng)′(P)和T′slice(P)的值越小系統(tǒng)的整體性能就越優(yōu),所以U(P)的最小值點(diǎn)即為系統(tǒng)整體性能的最優(yōu)點(diǎn)。

現(xiàn)對(duì)U(P)最小值的存在性和唯一性進(jìn)行證明。

證明:

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

1)因?yàn)長(zhǎng)′(P)和T′slice(P)在閉區(qū)間[Pmin,Pmax]上為連續(xù)函數(shù),所以U(P)=L′(P)+T′slice(P)在閉區(qū)間[Pmin,Pmax]上連續(xù),則由有界性定理得{U(P)|P∈[Pmin,Pmax]}有界。

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

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

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

3 多PE并行優(yōu)化方法驗(yàn)證

根據(jù)灰度共生矩陣和單精度浮點(diǎn)矩陣乘法計(jì)算的特點(diǎn),設(shè)計(jì)多個(gè)PE并行結(jié)構(gòu),利用本文提出的方法對(duì)灰度共生矩陣和單精度浮點(diǎn)矩陣乘法的PE并行結(jié)構(gòu)進(jìn)行優(yōu)化,實(shí)現(xiàn)運(yùn)行時(shí)間和資源消耗的優(yōu)化。

3.1 灰度共生矩陣的優(yōu)化

灰度共生矩陣是研究圖像紋理特征的一個(gè)有效手段,并廣泛應(yīng)用于生物醫(yī)學(xué)[7-8]、目標(biāo)檢測(cè)[9-10]、質(zhì)量控制[11]和遙感圖像分析[12]等領(lǐng)域。

3.1.1 灰度共生矩陣PE的設(shè)計(jì)

計(jì)算灰度共生矩陣的PE如圖3所示[13]。因?yàn)槊總€(gè)像素對(duì)的計(jì)算都是相互獨(dú)立的,從并行計(jì)算的角度考慮,可設(shè)計(jì)多個(gè)PE并行完成灰度共生矩陣的計(jì)算。

圖3 灰度共生矩陣的PE結(jié)構(gòu)

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

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

資源消耗隨PE的個(gè)數(shù)P的變化趨勢(shì)如圖4所示,資源消耗會(huì)隨著PE個(gè)數(shù)P的增加呈線性增長(zhǎng)。

圖4 灰度共生矩陣資源消耗隨PE個(gè)數(shù)變化趨勢(shì)

3.1.3 灰度共生矩陣運(yùn)行時(shí)間分析

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

圖5 灰度共生矩陣運(yùn)行時(shí)間隨PE個(gè)數(shù)變化趨勢(shì)

3.1.4 灰度共生矩陣運(yùn)行時(shí)間和資源消耗的優(yōu)化

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

圖6 灰度共生矩陣隨PE的變化趨勢(shì)

3.2 單精度浮點(diǎn)矩陣乘法的優(yōu)化

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

3.2.1 單精度浮點(diǎn)矩陣乘法PE資源消耗分析

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

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

(13)

結(jié)合式(1)可計(jì)算得到P個(gè)PE的資源消耗,資源消耗隨PE的個(gè)數(shù)P的變化趨勢(shì)如圖7所示,資源消耗會(huì)隨著PE個(gè)數(shù)P的增加呈線性增長(zhǎng)。

圖7 矩陣乘法資源消耗隨PE個(gè)數(shù)變化趨勢(shì)

3.2.2 單精度浮點(diǎn)矩陣乘法PE運(yùn)行時(shí)間分析

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

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

圖8 矩陣乘法運(yùn)行時(shí)間隨PE個(gè)數(shù)變化趨勢(shì)

3.2.3 運(yùn)行時(shí)間和資源消耗優(yōu)化分析

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

圖9 矩陣乘法隨PE的變化趨勢(shì)

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 資源消耗對(duì)比

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

表1 灰度共生矩陣資源消耗對(duì)比

表2 矩陣乘法資源消耗對(duì)比

4.2 運(yùn)行時(shí)間對(duì)比

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

圖10 灰度共生矩陣運(yùn)行時(shí)間對(duì)比

圖11 矩陣乘法運(yùn)行時(shí)間對(duì)比

4.3 運(yùn)行時(shí)間和資源消耗綜合對(duì)比

圖12是灰度共生矩陣各種方法中運(yùn)行時(shí)間和資源消耗歸一化后的綜合對(duì)比。與其他方法相比,本文方法的運(yùn)行時(shí)間和資源消耗最小,實(shí)現(xiàn)了資源消耗和性能的優(yōu)化。

圖12 灰度共生矩陣運(yùn)行時(shí)間和資源消耗的綜合對(duì)比

圖13是采用不同數(shù)量的PE計(jì)算矩陣乘法的運(yùn)行時(shí)間和資源消耗的綜合對(duì)比,利用本文提出的優(yōu)化方法設(shè)計(jì)的4PE并行的運(yùn)行時(shí)間和資源消耗最小,實(shí)現(xiàn)了資源消耗和性能的優(yōu)化。

圖13 矩陣乘法運(yùn)行時(shí)間和資源消耗的綜合對(duì)比

5 結(jié)束語

本文根據(jù)多PE并行中運(yùn)行時(shí)間和資源消耗隨PE數(shù)量變化的規(guī)律,提出了基于運(yùn)行時(shí)間與資源消耗的多PE并行優(yōu)化方法,利用本文提出的優(yōu)化方法對(duì)灰度共生矩陣和單精度浮點(diǎn)矩陣乘法進(jìn)行了優(yōu)化,并將本文提出的灰度共生矩陣并行計(jì)算方法與現(xiàn)有的灰度共生矩陣計(jì)算方法進(jìn)行對(duì)比,實(shí)驗(yàn)結(jié)果表明該優(yōu)化方法可實(shí)現(xiàn)多PE并行中運(yùn)行時(shí)間與資源消耗的優(yōu)化。

由于多PE并行以單PE為基礎(chǔ),因此單PE優(yōu)化對(duì)于系統(tǒng)整體性能的提高具有重要意義,而單PE的內(nèi)部操作之間具有相關(guān)性,這些相關(guān)性與實(shí)現(xiàn)的具體任務(wù)有關(guān),可采用流水線結(jié)構(gòu)進(jìn)行設(shè)計(jì),下一步工作需要對(duì)基于運(yùn)行時(shí)間與資源消耗的流水線優(yōu)化進(jìn)行研究。

[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].電子與信息學(xué)報(bào),2011,33(7): 1706-1712.

[13] 鄭 紅,李 釗,李 俊.灰度共生矩陣的快速實(shí)現(xiàn)和優(yōu)化方法研究[J].儀器儀表學(xué)報(bào),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

國家自然科學(xué)基金資助項(xiàng)目(60543006);博士點(diǎn)基金資助項(xiàng)目(201003259);光電信息重點(diǎn)實(shí)驗(yàn)室基金資助項(xiàng)目(9140 C150105100C1502)。

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

2013-07-01

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