謝曉燕，蘆守鵬，鄧軍勇，田汝佳

(1.西安郵電大學(xué) 計算機(jī)學(xué)院，陜西 西安 710061；2.西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 710061)

0 引 言

近年來，隨著對移動電子設(shè)備上視頻和圖像質(zhì)量以及游戲效果的要求越來越高，導(dǎo)致對處理器性能的需求也逐步增加。由于傳統(tǒng)的移動CPU并不擅長處理圖形數(shù)據(jù)，為提高系統(tǒng)的整體性能，移動GPU(mobile graphics processing unit)應(yīng)運而生。而在圖形渲染流水線中，模型視圖變換是重要的處理環(huán)節(jié)，用來實現(xiàn)對屏幕中的物體進(jìn)行平移、旋轉(zhuǎn)和縮放的處理。由于模型視圖變換的本質(zhì)是實現(xiàn)矩陣的乘法，相比于使用串行的方式實現(xiàn)矩陣乘法，高效率的并行算法更能減少處理整個圖形渲染流水線系統(tǒng)的時間。

針對基于可重構(gòu)系統(tǒng)對圖形渲染流水線中各種圖形變換進(jìn)行并行計算的實現(xiàn)，國內(nèi)外學(xué)者提出了很多設(shè)計方案。文獻(xiàn)[1]在可重構(gòu)系統(tǒng)上實現(xiàn)了4×4矩陣向量的乘法，并在FPGA器件上進(jìn)行了原型設(shè)計和驗證，其優(yōu)點在于可以將圖形流水線中的各種變換和渲染映射到可重構(gòu)陣列上，但是對于形流水線中的變換只是用了一個矩陣處理模塊，而對于模型視圖變換的三種矩陣只能相繼串行處理，不能同時輸出三種矩陣的輸出結(jié)果。文獻(xiàn)[2]利用了FPGA硬件電路專門針對模型視圖變換中縮放矩陣的執(zhí)行過程進(jìn)行映射，其使用六個乘法器以并行的方式對矩陣乘法進(jìn)行運算，這比基于通用處理器實現(xiàn)的軟件解決方案更有速度和效率上的優(yōu)勢，但是缺點在于使用電路中固定功能的模塊處理了二維縮放矩陣，并且未對模型視圖變換中的三維平移和旋轉(zhuǎn)做處理。文獻(xiàn)[3]提出了3DAT(3D仿射變換)算法的流水線架構(gòu)，其中將模型視圖中平移、縮放、旋轉(zhuǎn)矩陣的計算過程使用并行算法映射到FPGA開發(fā)板上，相比于傳統(tǒng)算法，其算法的加速比增大，但是專用硬件模塊的功能單一，如果改變其中的算法配置，則會影響整個圖形渲染流水線的實現(xiàn)，相比于可重構(gòu)的方法，其算法架構(gòu)不夠靈活。文獻(xiàn)[4]是在多核架構(gòu)的通用處理器上對形如C=AB形式的稀疏矩陣乘法進(jìn)行并行計算，而對于圖形流水線中各種變換涉及到的都是稀疏矩陣的乘法，所以具有很好的算法啟示作用，但是通用處理器上的軟件解決方案需要高級語言和處理器驅(qū)動的支持，這無疑增加了中間層處理和編譯的時間。

綜上所述，目前設(shè)計和實現(xiàn)圖形渲染流水線中各種圖形的變換大多在FPGA上使用硬件編程實現(xiàn)。當(dāng)處理圖形變換算法的并行映射時，需要事先布局設(shè)計好電路中各個模塊的功能再用硬件描述語言對電路及接口進(jìn)行編程，最后進(jìn)行綜合仿真，如果需要修改電路中某個模塊的算法，則會影響其他模塊的功能實現(xiàn)，此時需要對電路進(jìn)行修改再重新綜合。因此這種實現(xiàn)方案會導(dǎo)致電路中的模塊功能固定，使得設(shè)計和實現(xiàn)算法的周期過長，工作量較大。

基于上述情況，在可重構(gòu)的陣列結(jié)構(gòu)上使用軟件編程的方法將模型視圖變換的任務(wù)分成三個矩陣相乘的子模塊，在任務(wù)運行的不同階段根據(jù)計算的需要分別重新配置相應(yīng)的模塊，而那些不需要重新配置的模塊則不會受到影響。而且在使用匯編語言控制硬件時，對矩陣并行計算進(jìn)行編程的過程中只涉及對寄存器和共享存儲的讀寫操作，只有在與外圍電路進(jìn)行數(shù)據(jù)交互時才涉及到電路及接口的操作，這樣就增加了系統(tǒng)的靈活性并體現(xiàn)了基于可重構(gòu)系統(tǒng)使用軟件編程的優(yōu)勢。因此在實現(xiàn)相同模型視圖變換的功能且其實現(xiàn)后的性能與硬件實現(xiàn)的性能相差不大的前提下，有必要在可重構(gòu)的陣列結(jié)構(gòu)上靈活配置PE的資源完成矩陣并行算法的映射。

1 可重構(gòu)陣列結(jié)構(gòu)

文中采用的可重構(gòu)陣列結(jié)構(gòu)[5]是由多個陣列處理器簇(processing element group，PEG)構(gòu)成，其中每個簇是由4×4個輕核處理單元(thin-core processing element，TCPE)組成。每個PE可以完成加、減運算以及與、或、非和跳轉(zhuǎn)運算。相互臨近PE之間的數(shù)據(jù)交互采用鄰接互聯(lián)的方法實現(xiàn)；不相鄰PE之間的數(shù)據(jù)交互采用共享存儲RAM(random access memory)的方法?？芍貥?gòu)PE陣列的結(jié)構(gòu)如圖1所示。

圖1 可重構(gòu)PE陣列結(jié)構(gòu)

2 模型視圖變換單元可重構(gòu)設(shè)計

2.1 模型視圖變換的原理

在模型視圖變換[6-8]的過程中，圖像中的每個新位置點都是通過對原位置點進(jìn)行矩陣計算得到的。設(shè)矩陣變換前的坐標(biāo)為(x,y,z,1)T，矩陣變換后的坐標(biāo)為(x',y',z',1)T。

(1)

縮放函數(shù)glScale(x,y,z)是指對物體沿著x,y,z軸分別進(jìn)行放大縮小，函數(shù)中的三個參數(shù)分別是沿著x,y,z軸方向的縮放系數(shù)。設(shè)矩陣縮放的比例變換因子分別用Sx，Sy，Sz表示，矩陣變換關(guān)系如式2所示。

(2)

旋轉(zhuǎn)函數(shù)glRotate(angle,x,y,z)表示模型旋轉(zhuǎn)，angle指定模型旋轉(zhuǎn)的角度，且后三個變量表示以原點(0,0,0)到點(x,y,z)的連線為軸線逆時針旋轉(zhuǎn)物體。以模型繞z軸旋轉(zhuǎn)為例，設(shè)旋轉(zhuǎn)的角度用θ表示。則矩陣變換關(guān)系描述如式3所示。而模型繞x軸和繞y軸的矩陣變換關(guān)系可同理推得。

(3)

基于上述三種變換，可以引申出圖形的復(fù)合變換，即兩種或者三種變換的疊加，實質(zhì)表現(xiàn)為變換矩陣相乘的形式。由于矩陣并不符合交換律，所以這三種變換按各種順序執(zhí)行，結(jié)果是不相同的。由于縮放變換和旋轉(zhuǎn)變換并不改變原點的位置，所以在實際應(yīng)用中，一般按照先縮放再旋轉(zhuǎn)最后平移的順序進(jìn)行，這樣才能獲得預(yù)期的變換效果。

2.2 模型視圖算法的可重構(gòu)并行化設(shè)計

由于在模型視圖算法中涉及到上述三個矩陣的計算，如果采用傳統(tǒng)的串行算法去計算矩陣，會使得多個PE進(jìn)行長時間的等待，造成處理器資源的浪費。而且在對矩陣最終元素值的計算中，并無數(shù)據(jù)的相關(guān)性，所以應(yīng)該使用并行算法提高整個算法的運行效率。此外，根據(jù)可重構(gòu)陣列結(jié)構(gòu)的特點，將模型視圖算法映射到PE陣列上時，是基于最大并行化原則分配PE資源，每個PE處理算法中的一個子任務(wù)，最后將這些子任務(wù)的數(shù)據(jù)進(jìn)行拼接處理，相比硬件電路固定的功能實現(xiàn)，可重構(gòu)的設(shè)計實現(xiàn)了靈活的算法映射。

2.2.1 數(shù)據(jù)的準(zhǔn)備

根據(jù)可重構(gòu)陣列處理器鄰接互聯(lián)[9]的機(jī)制，并通過陣列處理器外圍PE的共享寄存器將坐標(biāo)數(shù)據(jù)送入陣列處理單元。由于此并行算法需要使用兩個簇PEG00和PEG01的資源，所以數(shù)據(jù)應(yīng)根據(jù)計算的需要分別輸入到兩個簇相對應(yīng)的PE共享寄存器中。基于圖1的PE陣列結(jié)構(gòu)，在第一個簇PEG00中的圖原頂點x、y、z坐標(biāo)連續(xù)賦值給PE00的R5共享寄存器；縮放矩陣沿著x軸方向的縮放系數(shù)Sx賦值給PE10的R5共享寄存器；縮放矩陣沿著y軸方向的縮放系數(shù)Sy賦值給PE01的R6共享寄存器；縮放矩陣沿著z軸方向的縮放系數(shù)Sz賦值給PE02的R6共享寄存器。平移矩陣沿著x軸、y軸、z軸平移的數(shù)值dx,dy,dz連續(xù)賦值給PE33的R7共享寄存器。在第二個簇PEG01中的圖原頂點x、y、z坐標(biāo)連續(xù)賦值給PE30的R5共享寄存器；CORDIC算法的向量(K,0,θ)連續(xù)賦值給PE00的R5共享寄存器；平移矩陣沿著x軸、y軸、z軸平移的數(shù)值dx,dy,dz連續(xù)賦值給PE33的R7共享寄存器。

2.2.2 數(shù)據(jù)的拆分

基于上述將并行化計算過程分為四大部分，依次為數(shù)據(jù)的準(zhǔn)備、數(shù)據(jù)的拆分、平移矩陣和縮放矩陣的計算、旋轉(zhuǎn)矩陣的計算。因為在可重構(gòu)陣列處理器中，其數(shù)據(jù)位寬是32位，且待處理的頂點數(shù)據(jù)也是32位，為了避免出現(xiàn)做乘法后的溢出錯誤，需要對計算的數(shù)據(jù)進(jìn)行拆分，需要拆分的數(shù)值有x、Sx、y、Sy、z、Sz。以數(shù)值x和Sx舉例，將x拆分為高10位-xH10、中間10位-xM10和低12位-xL12，將Sx拆分為高20位-SxH20和低12位-SxL12，然后分別對每部分進(jìn)行交叉乘法操作：xH10*SxH20、xH10*SxL12、xM10*SxH20、xH10*SxL12、xL12*SxH20、xL12*SxL12，最后將每部分的計算結(jié)果通過移位加的方法拼接成正確的結(jié)果。

2015年10月，盛通印刷參股一家從事教育出版策劃和發(fā)展的公司；2016年4月發(fā)布重大資產(chǎn)重組草案，擬用4.3億元人民幣并購少兒機(jī)器人教育公司——樂博樂博，致力于4～12歲青少年思維模式及動手能力方面的教育。通過幾次參股和并購，盛通印刷悄然完成了業(yè)務(wù)的大轉(zhuǎn)型，未來的市場格局更加清晰。

2.2.3 平移矩陣和縮放矩陣的計算

由于第一個簇PEG00負(fù)責(zé)計算平移矩陣和縮放矩陣，而需要實現(xiàn)的圖形效果是這兩種矩陣相乘的復(fù)合變換，即先縮放后平移，因此在矩陣計算的過程中存在數(shù)據(jù)相關(guān)性，需要先并行計算縮放矩陣，然后再串行計算平移矩陣。

首先計算縮放矩陣，需要15個PE使用鄰接互聯(lián)或者遠(yuǎn)程訪問共享存儲的方式讀取數(shù)據(jù)再進(jìn)行拆分，然后并行計算縮放矩陣，最后將這些待拼接的計算結(jié)果分別保存在該PE的本地存儲中。由于需要對縮放后的新圖原頂點坐標(biāo)進(jìn)行平移，所以先將并行計算得到的15個待拼接結(jié)果分組保存到RAM31、RAM32、RAM23中，然后使用移位加的方法同時在上述PE中進(jìn)行拼接。以X*Sx拼接的過程為例，過程如下：(XL12*SxH20)?12，(XH20*SxM10)?24，(XH20*SxH10)?34，(XH20*SxL12)?12，(XL12*SxL12)?0，最后將這些結(jié)果在PE31中相加即可得到X*Sx的正確結(jié)果。對于Y*Sy和Z*Sz可通過PE32和PE23分別采用相同的處理方法。全部拼接后可得到3個正確結(jié)果，即旋轉(zhuǎn)后的圖原頂點坐標(biāo)，并將其轉(zhuǎn)存到RAM33中。在PE33中再使用ADD指令以串行的方式計算X*Sx+dx、Y*Sy+dy、Z*Sz+dz，此時形成縮放后平移的圖原頂點坐標(biāo)，最后將其存放到PE33的寄存器中，等待外圍電路讀取數(shù)值時調(diào)用。具體的平移變換矩陣和縮放變換矩陣的整體映射過程如圖2所示。

圖2 PEG00算法映射

2.2.4 旋轉(zhuǎn)矩陣的計算

由于第二個簇PEG01主要負(fù)責(zé)計算旋轉(zhuǎn)矩陣并且需要實現(xiàn)先旋轉(zhuǎn)后平移的圖像效果，分析可知中間存在數(shù)據(jù)相關(guān)性，所以也需要運用串行與并行相結(jié)合的方法，具體執(zhí)行過程如下：首先使用CORDIC算法[10-11]串行計算出旋轉(zhuǎn)角的正弦值和余弦值，然后將這兩個值就近存入當(dāng)前PE的RAM中，接著并行計算旋轉(zhuǎn)矩陣從而得到新的圖原頂點坐標(biāo)，最后以串行的方式對新坐標(biāo)值進(jìn)行平移。

(4)

其中，Ri、Ti、Wi是當(dāng)前迭代的變量，而Ri+1、Ti+1、Wi+1是下一輪迭代的變量。

隨著迭代次數(shù)的不斷增加，其計算精度也會不斷增加。對于N位精度的CORDIC算法，迭代次數(shù)[12]M應(yīng)該滿足式5。若N=15，可以得到M=5；若N=31，可以得到M=10。

(5)

所以基于文中提出的可重構(gòu)PE陣列結(jié)構(gòu)的位寬，CORDIC算法使用移位、加減法的優(yōu)點以及迭代算法的特點，在第二個簇PEG01中使用PE00串行計算正余弦值，在計算過程中使用10次迭代，前一次的計算結(jié)果為下一次的迭代計算做準(zhǔn)備，直到第10次計算出正弦值和余弦值。當(dāng)計算出正弦值和余弦值后，將值存入PE00的存儲器RAM00中，然后通過鄰接互聯(lián)或者遠(yuǎn)程共享存儲的方式將正弦值或余弦值存入相對應(yīng)的12個PE中，最后并行計算Xcosθ、Xsinθ、Ysinθ、Ycosθ、Zcosθ、Zsinθ的各個分量。由于需要對旋轉(zhuǎn)后的新圖原頂點坐標(biāo)進(jìn)行平移，所以先將并行計算得到的待拼接分量通過STI指令分別存到RAM31、RAM32、RAM33中，然后使用移位加的方法同時對上述各分量進(jìn)行拼接，拼接后得到6個正確的結(jié)果。

以模型繞z軸旋轉(zhuǎn)的矩陣為例，將拼接好的Xcosθ、Ysinθ、Xsinθ、Ycosθ和Z坐標(biāo)這5個數(shù)值全部轉(zhuǎn)存到RAM33中，然后在PE33中通過ADD和SUB指令就可計算出式3中旋轉(zhuǎn)矩陣的元素值，此時即可得到旋轉(zhuǎn)后的圖原頂點坐標(biāo)，最后利用RAM33中的平移數(shù)值dx，dy，dz對此圖原頂點坐標(biāo)進(jìn)行平移處理。而模型繞x軸旋轉(zhuǎn)和模型繞y軸旋轉(zhuǎn)的矩陣計算方法同理可得。最后將平移處理后的三種結(jié)果存放到PE33的寄存器中，等待外圍電路調(diào)用。旋轉(zhuǎn)矩陣的整體映射過程如圖3所示。

圖3 PEG01算法映射

3 實驗結(jié)果和分析

3.1 功能測試

為了驗證文中設(shè)計方法的可行性和正確性，將實現(xiàn)的方案接入文獻(xiàn)[13]所提的結(jié)構(gòu)中，并使用Xilinx的FPGA芯片XC6VLX760T進(jìn)行原型驗證并顯示圖像。圖像對比結(jié)果如圖4所示，上圖為FPGA平臺的輸出結(jié)果，下圖為Linux平臺的輸出結(jié)果。實驗可表明兩種平臺的輸出結(jié)果一致。

3.2 性能分析

基于所使用的串行和并行相結(jié)合的算法，需要計算采用并行方式處理矩陣的加速比，所以應(yīng)根據(jù)Amdahl定理[14-15]給出式6：

(6)

其中，f表示可被并行處理部分的比例；m表示并行處理機(jī)的數(shù)量。并設(shè)CPI(每條指令執(zhí)行需要的平均時鐘周期數(shù))為T。

圖4 輸出圖像結(jié)果對比

由于文中使用32個輕核處理單元則m=32，并使用表1的參數(shù)可得f=125T/157T≈0.79，代入式6可得加速比約為4.26。與文獻(xiàn)[1]具體的參數(shù)對比分析如表1所示。文中與文獻(xiàn)[1]都是在將4×4的矩陣變換映射到FPGA硬件平臺上，但是文獻(xiàn)[1]只針對通用矩陣，而且當(dāng)處理旋轉(zhuǎn)矩陣中的旋轉(zhuǎn)角時，只能處理特殊角度的正余弦函數(shù)，而文中可以處理任意旋轉(zhuǎn)角度的正余弦函數(shù)值，且加速比也優(yōu)于文獻(xiàn)[1]。

表1 效率對比

項目文中文獻(xiàn)[1]硬件平臺Xilinx FPGAStratixII FPGA電路結(jié)構(gòu)PE陣列結(jié)構(gòu)RISC矩陣維度4×44×4總時鐘周期157T196T可并行周期125T65T加速比4.263

文獻(xiàn)[2]僅僅是處理二維的縮放矩陣，即將3×3矩陣的算法并行映射到硬件平臺上，而文中處理的是4×4的三維多功能矩陣，電路工作頻率也高于文獻(xiàn)[2]，具體的對比參數(shù)如表2所示。

表2 性能對比

4 結(jié)束語

由于可重構(gòu)配置可以實現(xiàn)接近專用硬件系統(tǒng)的性能，還能保持通用處理器的靈活性，所以文中采用可重構(gòu)多PE的陣列結(jié)構(gòu)，設(shè)計了矩陣并行映射的方法，并在Xilinx的Virtex6系列的FPGA開發(fā)板上進(jìn)行了原型驗證。

實驗結(jié)果表明，提出的模型視圖變換單元并行化映射方法，能夠正確地將所繪制的圖形進(jìn)行平移、旋轉(zhuǎn)、縮放三種獨立的變換以及它們的復(fù)合變換，而且使用陣列結(jié)構(gòu)并行計算矩陣的過程與專用硬件實現(xiàn)性能相當(dāng)，其編程靈活性也大大提高并更加實用。