一種用于圖形渲染的高性能SpMV專用加速器結構

鄧軍勇，馬青青

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

1 引 言

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

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

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

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

2 研究背景

2.1 圖形渲染中的變換操作

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

2.2 現有矩陣向量運算結構

現有的矩陣向量運算結構有很多，如前文中提到的CSR5、CVR、EIE等，本文將選擇傳統矩陣向量運算結構和EIE運算結構與本文所設計的運算結構做對比，以測試其優化效果.

2.2.1 傳統矩陣向量運算結構

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

(7)

2.2.2 EIE運算結構

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

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

.

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

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

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

3.1 算法思想

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

(8)

3.2 加速器結構

圖1是根據矩陣列向量的線性組合思想所設計的SpMV專用加速器結構，主要包括控制器、乘法器、加法器和寄存器.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中向量相加即得出最終的結果向量.

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

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

3.3 算法應用

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

4 實驗結果及分析

4.1 驗證策略

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

4.2 實驗結果

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

4.3 性能分析

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

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

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

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

表3 應用于旋轉變換的速度和資源占用情況對比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

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

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

5 結 語

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