鄧軍勇，馬青青

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

1 引 言

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

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

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

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

2 研究背景

2.1 圖形渲染中的變換操作

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

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

(1)

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

(2)

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

(3)

縮放變換矩陣如式(4)所示，當某個參數(shù)大于1.0，則沿對應的坐標軸拉伸物體；小于1.0，則收縮物體.

(4)

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

(5)

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

(6)

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

2.2 現(xiàn)有矩陣向量運算結(jié)構

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

2.2.1 傳統(tǒng)矩陣向量運算結(jié)構

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

(7)

2.2.2 EIE運算結(jié)構

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

表1 PE0對應的CSC表示形式Table 1 CSC representation of PE0

.

以CSC格式按列存儲稀疏矩陣使運算變得簡單，只需將每個非零激活值乘以其對應列中的所有非零元素即可.但是，其預處理開銷較大，且由于每個PE在特定列中可能具有不同數(shù)量的非零元素，因此，此運算過程可能會遇到負載不平衡的情況.

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

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

3.1 算法思想

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

(8)

3.2 加速器結(jié)構

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

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

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

3.3 算法應用

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

4 實驗結(jié)果及分析

4.1 驗證策略

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

4.2 實驗結(jié)果

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

4.3 性能分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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