一種用于圖形渲染的高性能SpMV專用加速器結(jié)構(gòu)

鄧軍勇，馬青青

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

1 引 言

稀疏矩陣向量乘法(Sparse Matrix-Vector multiplication，SpMV)在科學(xué)計(jì)算中有廣泛應(yīng)用[1]，例如圖形渲染中涉及的幾何變換、投影變換、視口變換等需要大量的稀疏矩陣向量運(yùn)算.目前，圖形渲染中的SpMV運(yùn)算仍存在并行度較差，資源占用較多，訪問(wèn)開(kāi)銷(xiāo)較大的問(wèn)題.因此，如何實(shí)現(xiàn)SpMV高性能計(jì)算成為了圖形處理器設(shè)計(jì)中的關(guān)鍵性問(wèn)題之一.

目前的SpMV優(yōu)化方法有很多，Liu等[2]在CSR(Compressed Sparse Row)格式的基礎(chǔ)上提出了CSR5格式，對(duì)于只有數(shù)十次迭代的求解器之類的實(shí)際應(yīng)用，CSR5格式由于格式轉(zhuǎn)換的開(kāi)銷(xiāo)較低而更加實(shí)用.Merrill等[3]提出了一種“基于合并”的CSR格式并行方法，此方法可提供高性能，而無(wú)需格式轉(zhuǎn)換或擴(kuò)充，而且基本上不受行長(zhǎng)異質(zhì)性的影響.Grigoras等[4]設(shè)計(jì)了一種非零壓縮算法，該算法可以減少冗余非零值，從而在不降低計(jì)算效率的情況下利用備用FPGA資源來(lái)克服基于FPGA的SpMV實(shí)現(xiàn)中的存儲(chǔ)器帶寬限制.Han等[5]提出了一種高效節(jié)能推理引擎(EIE)，EIE以CSC(Compressed Sparse Column)的變體格式按列存儲(chǔ)稀疏矩陣使運(yùn)算變得簡(jiǎn)單，但是，其預(yù)處理開(kāi)銷(xiāo)較大，且由于每個(gè)PE在特定列中可能具有不同數(shù)量的非零元素，因此，此運(yùn)算過(guò)程可能會(huì)遇到負(fù)載不平衡的情況.

楊等[6]在現(xiàn)有的BRC(Blocked Row-Column)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上提出了BRCP(Blocked Row-Column Plus)存儲(chǔ)格式，采用了不同的二維分塊策略，根據(jù)稀疏矩陣的特性自適應(yīng)地調(diào)節(jié)分塊參數(shù)，實(shí)現(xiàn)了SpMV在GPU上的并行性.程等[7]提出一種稀疏矩陣的存儲(chǔ)格式HEC(Hybrid ELL and CSR)，該存儲(chǔ)格式由ELL(ELLPACK)與CSR格式混合而成，可提高稀疏矩陣的存儲(chǔ)效率，減少SpMV的運(yùn)算時(shí)間.鄧等[8]提出一種用于圖計(jì)算的稀疏矩陣壓縮方法，每個(gè)稀疏列經(jīng)預(yù)處理電路獨(dú)立壓縮成CSCI格式，其中包括列標(biāo)識(shí)數(shù)據(jù)對(duì)和非零元素?cái)?shù)據(jù)對(duì)，此壓縮方法可以提高圖計(jì)算的并行性和能效.Xie等[9]提出一種稱為CVR(Compressed Vectorization-oriented sparse Row) 的SpMV表示形式，CVR可以同時(shí)處理輸入矩陣中的多行以提高緩存效率，此方法對(duì)SpMV的稀疏性和不規(guī)則性不敏感，有較小的預(yù)處理開(kāi)銷(xiāo)，具有更低的緩存未命中率，同時(shí)CVR的控制較復(fù)雜，相關(guān)控制參數(shù)超過(guò)30個(gè).

針對(duì)SpMV高性能計(jì)算，現(xiàn)有的研究?jī)?yōu)化方法都從一定程度上解決了資源占用較多，并行度較差的問(wèn)題.但是，由于預(yù)處理開(kāi)銷(xiāo)、訪問(wèn)開(kāi)銷(xiāo)較大和數(shù)據(jù)相關(guān)性，要做到同時(shí)兼顧并行度和資源占用率還是有一定難度的.于是，本文充分利用數(shù)據(jù)的并行性，基于矩陣列向量的線性組合，設(shè)計(jì)了一種用于圖形渲染的高性能SpMV專用加速器結(jié)構(gòu)，并將傳統(tǒng)矩陣運(yùn)算結(jié)構(gòu)、EIE運(yùn)算結(jié)構(gòu)與本文所設(shè)計(jì)的運(yùn)算結(jié)構(gòu)做對(duì)比，以測(cè)試其應(yīng)用于圖形渲染的變換操作時(shí)的優(yōu)化效果.

2 研究背景

2.1 圖形渲染中的變換操作

圖形渲染中包含了大量的變換操作，如幾何變換、投影變換、視口變換等[10].幾何變換通常指模型變換或視圖變換(二者合稱模型視圖變換)，完成場(chǎng)景對(duì)象由模型坐標(biāo)系向視覺(jué)坐標(biāo)系的轉(zhuǎn)換.幾何變換包括平移、旋轉(zhuǎn)、縮放變換，假設(shè)頂點(diǎn)坐標(biāo)為p=(px，py，pz，1)，則平移變換過(guò)程如式(1)所示：

p′=T(t)·pT=(px+tx，py+ty，pz+tz，1)

(1)

由公式(1)可以看出平移變換矩陣如式(2)所示：

(2)

旋轉(zhuǎn)變換根據(jù)坐標(biāo)軸不同分為繞x軸、y軸、z軸的旋轉(zhuǎn)，假設(shè)旋轉(zhuǎn)角度為φ，則繞x軸的旋轉(zhuǎn)變換矩陣如式(3)所示.

(3)

縮放變換矩陣如式(4)所示，當(dāng)某個(gè)參數(shù)大于1.0，則沿對(duì)應(yīng)的坐標(biāo)軸拉伸物體；小于1.0，則收縮物體.

(4)

根據(jù)投影中心與投影平面之間距離的不同，投影可分為透視投影和正射投影.其中透視投影變換可看作是兩個(gè)基本變換，即世界坐標(biāo)系到視點(diǎn)坐標(biāo)系的變換和視點(diǎn)坐標(biāo)系到屏幕坐標(biāo)系的變換[11]，透視投影變換矩陣如式(5)所示：

(5)

視口是指經(jīng)過(guò)幾何變換后的物體顯示于屏幕窗口內(nèi)的指定區(qū)域，在圖形渲染流程中經(jīng)視口變換可以得到窗口坐標(biāo)，窗口坐標(biāo)顯示了屏幕中的像素相對(duì)于窗口左下角的位置[10]，視口變換矩陣如式(6)所示：

(6)

不管是幾何變換還是投影變換和視口變換，其核心計(jì)算都是SpMV，而圖形渲染中存在著大量的幾何變換、投影變換和視口變換等，但由于SpMV運(yùn)算時(shí)數(shù)據(jù)之間存在的相關(guān)性和不規(guī)則的內(nèi)存訪問(wèn)引發(fā)的內(nèi)存開(kāi)銷(xiāo)，使其性能大大降低.因此，SpMV性能的優(yōu)化，將成為圖形渲染性能優(yōu)化的關(guān)鍵.

2.2 現(xiàn)有矩陣向量運(yùn)算結(jié)構(gòu)

現(xiàn)有的矩陣向量運(yùn)算結(jié)構(gòu)有很多，如前文中提到的CSR5、CVR、EIE等，本文將選擇傳統(tǒng)矩陣向量運(yùn)算結(jié)構(gòu)和EIE運(yùn)算結(jié)構(gòu)與本文所設(shè)計(jì)的運(yùn)算結(jié)構(gòu)做對(duì)比，以測(cè)試其優(yōu)化效果.

2.2.1 傳統(tǒng)矩陣向量運(yùn)算結(jié)構(gòu)

對(duì)于傳統(tǒng)的矩陣向量乘法，其運(yùn)算方式如式(7)所示，矩陣的每一行分別與向量做乘法和加法運(yùn)算，得到最終的結(jié)果向量.該算法都是串行計(jì)算，效率很低，本文在此算法的基礎(chǔ)上，尋找到了一些在計(jì)算時(shí)沒(méi)有相關(guān)性的數(shù)據(jù)，使算法能夠并行運(yùn)算，從而提高矩陣向量運(yùn)算的效率.

(7)

2.2.2 EIE運(yùn)算結(jié)構(gòu)

壓縮稀疏行(CSR)是存儲(chǔ)稀疏矩陣的最常用格式[12]，與其類似的還有壓縮稀疏列(CSC)格式.文獻(xiàn)[5]中提出的一種高效節(jié)能推理引擎(EIE)對(duì)壓縮的網(wǎng)絡(luò)模型進(jìn)行推理，并通過(guò)權(quán)重共享來(lái)加速稀疏矩陣向量乘法.EIE以壓縮稀疏列(CSC)的變體格式存儲(chǔ)編碼稀疏權(quán)重矩陣W，通過(guò)在多個(gè)處理元素(PE)上交織矩陣W的行來(lái)并行化矩陣矢量計(jì)算，每個(gè)PE都有自己的v，x和p數(shù)組.此結(jié)構(gòu)通過(guò)掃描矢量a來(lái)找到非零值aj并將aj及其索引j廣播到所有PE，然后每個(gè)PE將aj乘以其對(duì)應(yīng)Wj中的非零元素，并在累加器中累加各部分的和，最后輸出激活向量b的每個(gè)元素.表1顯示了EIE中PE0對(duì)應(yīng)的CSC表示形式

表1 PE0對(duì)應(yīng)的CSC表示形式Table 1 CSC representation of PE0

.

以CSC格式按列存儲(chǔ)稀疏矩陣使運(yùn)算變得簡(jiǎn)單，只需將每個(gè)非零激活值乘以其對(duì)應(yīng)列中的所有非零元素即可.但是，其預(yù)處理開(kāi)銷(xiāo)較大，且由于每個(gè)PE在特定列中可能具有不同數(shù)量的非零元素，因此，此運(yùn)算過(guò)程可能會(huì)遇到負(fù)載不平衡的情況.

3 基于矩陣列向量線性組合的加速器結(jié)構(gòu)

本文基于線性代數(shù)關(guān)于矩陣列向量的線性組合思想，提出了一種用于圖形渲染的高性能SpMV專用加速器結(jié)構(gòu).該結(jié)構(gòu)充分利用數(shù)據(jù)的并行性，提升了矩陣向量相乘的運(yùn)算速度，由于圖形渲染中存在大量的SpMV運(yùn)算，因此該結(jié)構(gòu)將會(huì)使圖形渲染的效率大大提高.

3.1 算法思想

并行計(jì)算可以提高SpMV的運(yùn)算效率，想要實(shí)現(xiàn)并行計(jì)算就要挖掘矩陣向量運(yùn)算過(guò)程中存在的數(shù)據(jù)并行性，即運(yùn)算可以同時(shí)進(jìn)行而不存在數(shù)據(jù)相關(guān).矩陣向量相乘的數(shù)學(xué)運(yùn)算方式——矩陣列向量的線性組合為此提供了思路，其運(yùn)算方式如式(8)所示：矩陣M可以分為4個(gè)列向量，向量v中的每一個(gè)元素與其對(duì)應(yīng)列相乘，最后相乘的結(jié)果再相加得出最后的結(jié)果向量.此算法充分利用了數(shù)據(jù)的并行性，使大量的乘法和加法操作可以同時(shí)進(jìn)行，也可以減少數(shù)據(jù)的不規(guī)則訪問(wèn).

(8)

3.2 加速器結(jié)構(gòu)

圖1是根據(jù)矩陣列向量的線性組合思想所設(shè)計(jì)的SpMV專用加速器結(jié)構(gòu)，主要包括控制器、乘法器、加法器和寄存器.A0、A1、A2、A3寄存器分別存儲(chǔ)4×4矩陣A的4列，B0、B1、B2、B3寄存器分別存儲(chǔ)4×1向量B的4個(gè)元素，控制器每隔一拍向寄存器組傳輸矩陣A的一列和向量B的一個(gè)元素，對(duì)應(yīng)的列和元素相乘得出中間向量，分別寄存在T0、T1、T2、T3寄存器中，4個(gè)中間向量?jī)蓛上嗉臃謩e寄存在S0和S1寄存器中，S0和S1中向量相加即得出最終的結(jié)果向量.

圖1 矩陣列向量的線性組合運(yùn)算結(jié)構(gòu)圖Fig.1 Structure of linear combination of matrix column vectors

此加速器使矩陣的4列能夠并行計(jì)算，整體采用流水線結(jié)構(gòu)，能夠大幅度提升矩陣向量運(yùn)算的速度，并且每一列只和向量中的一個(gè)元素進(jìn)行運(yùn)算，大大減少了向量中元素的訪問(wèn)量和訪問(wèn)不規(guī)則問(wèn)題.

3.3 算法應(yīng)用

本設(shè)計(jì)不僅實(shí)現(xiàn)了基于矩陣列向量線性組合的加速器結(jié)構(gòu)，還將傳統(tǒng)矩陣向量運(yùn)算結(jié)構(gòu)和EIE運(yùn)算結(jié)構(gòu)用verilog實(shí)現(xiàn)，并且這3種運(yùn)算結(jié)構(gòu)都采用4×4的矩陣規(guī)格和4×1的向量規(guī)格，便于比較.由2.1節(jié)我們可以知道圖形渲染中變換操作的核心計(jì)算是SpMV，提升SpMV的運(yùn)算性能對(duì)于提升圖形渲染的運(yùn)算性能具有很大的意義.因此，我們將幾何變換中的平移、旋轉(zhuǎn)、縮放變換及投影變換和視口變換的矩陣格式都應(yīng)用于上述3種運(yùn)算結(jié)構(gòu)，矩陣格式如式(2)-式(6)所示，以比較在面對(duì)不同的矩陣格式時(shí)，哪一種運(yùn)算結(jié)構(gòu)的性能更佳.

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

4.1 驗(yàn)證策略

為驗(yàn)證運(yùn)算結(jié)構(gòu)的正確性，本文使用modelsim仿真工具對(duì)用verilog實(shí)現(xiàn)的3種運(yùn)算結(jié)構(gòu)及其在3種圖形渲染變換操作上的應(yīng)用算法進(jìn)行基本功能驗(yàn)證，查看經(jīng)3種變換操作得到的視覺(jué)坐標(biāo)、屏幕坐標(biāo)、窗口坐標(biāo)是否正確.為驗(yàn)證運(yùn)算結(jié)構(gòu)的性能，本文使用Xilinx公司的綜合工具ISE，在XC6VLX550T開(kāi)發(fā)板上進(jìn)行綜合，查看3種運(yùn)算結(jié)構(gòu)及其應(yīng)用在3種變換操作時(shí)的運(yùn)算性能和資源占用情況等.

4.2 實(shí)驗(yàn)結(jié)果

不管是哪一種運(yùn)算結(jié)構(gòu)都存在大量的乘法和加法運(yùn)算，因此，乘法和加法必然成為了運(yùn)算過(guò)程中的瓶頸.為優(yōu)化運(yùn)算結(jié)構(gòu)的性能，運(yùn)算中的乘法和加法操作都調(diào)用乘法器和加法器IP核來(lái)實(shí)現(xiàn).經(jīng)modelsim仿真驗(yàn)證，本文設(shè)計(jì)的SpMV專用加速器結(jié)構(gòu)在輸入數(shù)據(jù)后經(jīng)過(guò)16個(gè)時(shí)鐘周期，輸出了正確的坐標(biāo)向量，傳統(tǒng)運(yùn)算結(jié)構(gòu)和EIE運(yùn)算結(jié)構(gòu)分別經(jīng)過(guò)15和22個(gè)時(shí)鐘周期得到正確的坐標(biāo)向量，將3種運(yùn)算結(jié)構(gòu)應(yīng)用于3種圖形渲染變換操作后也都得出了正確的坐標(biāo)向量.

4.3 性能分析

將本文提出的SpMV專用加速器結(jié)構(gòu)與傳統(tǒng)運(yùn)算結(jié)構(gòu)和文獻(xiàn)[5]中的EIE運(yùn)算結(jié)構(gòu)都用verilog實(shí)現(xiàn)，綜合后得出的速度和資源占用情況對(duì)比如表2所示.可以看出，在相同的

表2 3種運(yùn)算結(jié)構(gòu)的速度和資源占用情況對(duì)比Table 2 Comparison of speed and resource occupation of three computing structures

FPGA上，本文設(shè)計(jì)的基于矩陣列向量線性組合的加速器結(jié)構(gòu)與傳統(tǒng)運(yùn)算結(jié)構(gòu)相比，速度能夠提高28%，資源占用率減少約48%；與文獻(xiàn)[5]中的EIE運(yùn)算結(jié)構(gòu)相比，速度能夠提高37%，資源占用率減少約18%.

實(shí)現(xiàn)了上述3種運(yùn)算結(jié)構(gòu)后，將幾何變換中的平移、旋轉(zhuǎn)、縮放變換及投影變換和視口變換的矩陣格式都應(yīng)用于3種運(yùn)算結(jié)構(gòu)，經(jīng)仿真驗(yàn)證功能正確后進(jìn)行綜合，3種幾何變換的應(yīng)用經(jīng)ISE綜合后的速度和資源占用情況分別如表3、表4、表5所示，投影變換和視口變換的應(yīng)用經(jīng)ISE綜合后的速度和資源占用情況分別如表6、表7所示.

表3 應(yīng)用于旋轉(zhuǎn)變換的速度和資源占用情況對(duì)比Table 3 Comparison of speed and resource occupation applied to rotation transformation

表4 應(yīng)用于縮放變換的速度和資源占用情況對(duì)比Table 4 Comparison of speed and resource occupation applied to scaling transformation

表5 應(yīng)用于平移變換的速度和資源占用情況對(duì)比Table 5 Comparison of speed and resource occupation applied to translation transformation

表6 應(yīng)用于投影變換的速度和資源占用情況對(duì)比Table 6 Comparison of speed and resource occupation applied to projection transformation

表7 應(yīng)用于視口變換的速度和資源占用情況對(duì)比Table 7 Comparison of speed and resource occupation applied to viewport transformation

從表中可以看出，應(yīng)用于圖形渲染的變換操作后，本文設(shè)計(jì)的基于矩陣列向量線性組合的加速器結(jié)構(gòu)與傳統(tǒng)運(yùn)算結(jié)構(gòu)相比，速度依舊能夠提高28%，與文獻(xiàn)[5]中的EIE運(yùn)算結(jié)構(gòu)相比，速度平均能夠提高30%.應(yīng)用于旋轉(zhuǎn)變換后，本文設(shè)計(jì)的基于矩陣列向量線性組合的加速器結(jié)構(gòu)與傳統(tǒng)運(yùn)算結(jié)構(gòu)相比，資源占用率減少約46%，與EIE運(yùn)算結(jié)構(gòu)相比，資源占用率減少約60%；應(yīng)用于縮放變換后，本文設(shè)計(jì)的基于矩陣列向量線性組合的加速器結(jié)構(gòu)與傳統(tǒng)運(yùn)算結(jié)構(gòu)和EIE運(yùn)算結(jié)構(gòu)相比，資源占用率分別減少約43%、52%；應(yīng)用于平移變換后，資源占用率分別減少約47%、58%；應(yīng)用于投影變換后，資源占用率分別減少約48%、52%；應(yīng)用于視口變換后，資源占用率分別減少約46%、58%.

由此可以看出，不管是哪一種變換的應(yīng)用，本文設(shè)計(jì)的SpMV專用加速器結(jié)構(gòu)在運(yùn)算時(shí)的速度和資源占用都優(yōu)于傳統(tǒng)運(yùn)算結(jié)構(gòu)和EIE運(yùn)算結(jié)構(gòu).

5 結(jié) 語(yǔ)

本文針對(duì)圖形渲染中SpMV計(jì)算量大，并行度較差，資源占用較多，訪問(wèn)開(kāi)銷(xiāo)較大的問(wèn)題，從硬件實(shí)現(xiàn)角度出發(fā)，充分挖掘了數(shù)據(jù)的并行性，運(yùn)用線性代數(shù)關(guān)于矩陣列向量的線性組合思想，設(shè)計(jì)了一種用于圖形渲染的高性能SpMV專用加速器結(jié)構(gòu).此加速器整體采用流水線結(jié)構(gòu)，使大量的乘法和加法操作可以同時(shí)進(jìn)行，大幅度提升了矩陣向量運(yùn)算的速度，也可以減少數(shù)據(jù)的不規(guī)則訪問(wèn).實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)矩陣運(yùn)算結(jié)構(gòu)、文獻(xiàn)[5]中的EIE運(yùn)算結(jié)構(gòu)相比，本文設(shè)計(jì)的加速器結(jié)構(gòu)在應(yīng)用于圖形渲染的變換操作時(shí)運(yùn)算速度較快，資源占用率較低，在用于圖形渲染的高性能SpMV運(yùn)算方面具有一定的優(yōu)勢(shì).