基于陣列處理器的SVDC算法并行設計與實現

蔣 林 黎瑞金 曹 非

1(西安科技大學計算機科學與技術學院 陜西 西安 710600)

2(西安科技大學電氣與控制工程學院 陜西 西安 710600)

0 引 言

近年來3D視頻在各行各業中有著廣闊的應用場景。在基于3D-HEVC的三維視頻編碼技術中,編碼模式的選擇采用了率失真優化方法,深度圖的失真會導致合成視點的失真,所以我們可以通過測量合成視點的失真來替代深度圖的失真,保證虛擬合成視圖的質量[1]。因此,Tech等[2-4]針對深度數據的失真度量提出了應用3D-HEVC的視點合成失真變化算法。這種算法具有高級視圖算法的所有基本功能,例如像素變化、差值、空洞填充以及融合,使得編碼端可以在率失真優化過程中直接計算合成視點失真。但是,這種方法需要在編碼過程中執行基于像素級的視點合成與失真值計算操作,引起頻繁的訪存操作,導致過高的編碼復雜度以及較低的算法性能。為了解決SVDC這種數據密集型算法的計算復雜度過高的問題,Ma等[5]提出了一種通過設置三種合成視點零差異條件下提前終止SVDC計算過程的模型,但是傳統處理器串行化的計算方式仍使得SVDC算法的性能提升有限。

針對上述問題,本文基于陣列處理器的SVDC并行算法,采用分布式共享存儲結構(Unified addressing Distributed Shared Memory Structure,UaDSMS)[7]實現了多視點并行計算。充分利用了陣列處理器的并行特性進行算法映射,并根據算法的訪存特性做出優化,使得SVDC算法的性能得到較大提升。

1 陣列處理器及分布式共享存儲結構

項目組前期開發的陣列處理器由多個處理單元(Processing Element,PE)構成,該PE的結構如圖1所示[6]。每個PE分別由ALU單元、寄存器單元、左路數據選擇單元、右路數據選擇單元、fanout單元和配置單元組成。

圖1 PE結構

此陣列處理器結構由16個PE組成一個簇,采用了4×4的矩陣結構,單個PE的數據訪存位寬是16位。其中分布式共享存儲結構如圖2所示[7],此存儲結構下層為16個同樣排列結構512 bit×16 bit大小組成的RAM,中間是采用了全交換結構(Full Switching,FS)的高速訪問單元,上層為16個PE組成的簇,這種結構是一種最直接且并行度最高的高速交換單元結構。

圖2 分布式共享存儲結構

分布式共享存儲結構的主要優勢如下：1) 從邏輯上分析,整個片上存儲采用相同的編址方式。2) 從物理上分析,采用多個分布式存儲塊,實現片上存儲的并行訪問,支持簇內請求的無沖突并行訪問。

根據以上分析,我們發現具有“邏輯共享、物理分布”特性的分布式共享存儲結構所表現出的并行化設計優勢,非常適合SVDC算法數據密集的特點。

2 SVDC算法并行化設計

2.1 SVDC算法并行性分析

SVDC算法可以通過聯系合成視點失真與深度圖失真,計算當前合成視點中由于深度值變化所產生的全部失真值,從而提升深度圖編碼的率失真優化效果,并且可以同時考慮當前深度圖編碼塊周圍像素的深度值變化情況。因此,SVDC算法被定義為計算兩個合成視點的失真值之差：

(1)

圖3 SVDC算法流程

由圖3可以看出SVDC算法在計算過程中,每一次SVDC計算都要經過三個合成視點進行SSD計算,其中每一個合成視點都是由原始紋理圖幀、原始深度圖幀和重建紋理圖幀、重建深度圖幀分別求得,大量的SSD計算會出現頻繁的訪存操作。傳統處理器串行化的計算方式會使得算法的性能難以提升。針對以上的問題,本文將基于陣列處理器和分布式共享存儲結構,實現多視點SSD并行計算,通過簇內PE陣列處理器的并行執行,實現對SVDC算法的加速。

2.2 SVDC算法并行化映射

SVDC算法主要可分為虛擬視點合成以及失真值計算兩大部分。圖4是SVDC算法的陣列處理器映射結構。共調用4個簇的資源,PE00簇負責預處理,PE01簇負責3D-warping,PE11簇負責空洞填充,PE10簇負責失真值計算,下面為各個簇的工作安排。

圖4 SVDC算法映射結構圖

PE00號簇：00號簇從外部存儲設備加載相機參數并將數據暫時存入00號簇的RAM中。如圖5所示針對深度圖進行中值濾波預處理,使用01、02、03、11、12、13、21、22、23號PE,分為三步進行中值濾波。

圖5 預處理中值濾波

Step1：將從外部存儲設備加載的數據以3×3的像素塊為單位,每行從大到小排序,分別取得大、中、小三個值。

Step2：對大值行即第一列進行比較,對小值行即第三列進行比較,取其中的大值與小值。

Step3：把三行的中值與第二列相比較,再取一次中值。將小值、中值和大值進行比較與排序,獲得的中值即為該像素塊的中值。

PE01號簇：3D-warping是產生虛擬視點的核心技術,它將先提取圖像幀的深度圖信息,再根據深度圖信息,把參考紋理圖的視點信息投射至3D空間坐標,最后投射到2D空間坐標的目標視點。這種方法需要攝像機參數,其中內部相機參數用A表示,外部相機參數用R與t表示。

(2)

式中：r代表參考視點;Zr是參考視點在(ur,vr)位置的深度值,首先我們利用內部相機參數A將3D相機的坐標映射到2D空間的虛擬視點中去,再取一個參考視點的像素坐標(ur,vr),最后利用深度圖信息將像素坐標映射到世界坐標中的(Xw,Yw,Zw)位置中。

(3)

(4)

式中：v表示8比特的深度值,其中z、Znear和Zfar都被設定為正值或負值。如式(4)所示,其中(Xw,Yw,Zw)是式(2)映射到3D空間的坐標,3×3的旋轉矩陣R與3×1的平移矩陣是攝像機參數。

PE11號簇：空洞填充作為虛擬視點合成中的難點,長期以來影響著該領域的發展[9]。本文通過人工識別空洞點的方式,通過匯編指令向PE下發指令,針對空洞部分采集鄰近像素點的信息,再逐步進行空洞點的像素填充。這里共調用10個PE,首先由00號PE將數據分發至02、03、12、13、20、21、30、31號PE,然后各PE采集鄰近像素點的信息,并將其填充進空洞部分,最后各PE將結果傳送到33號PE,準備送入10號簇進行失真值計算。

PE10號簇：失真值計算,由于失真值計算涉及大量合成視點的SSD計算,存在頻繁的訪存操作以及冗余的編碼復雜度,本文利用陣列處理器及分布式共享存儲的并行設計優勢,實現了多視點SSD并行計算。

2.3 失真值計算設計與優化

失真值計算作為SVDC算法的核心步驟,頻繁的訪存操作會使得算法出現大量的數據移動。本節作者在使用單元級SSD計算映射方案實現后,通過優化訪存時序,提出了像素級SSD計算設計。

(1) 單元級SSD計算設計。以8×8像素點的圖像塊為例,具體操作如圖6所示。

圖6 單元級SSD計算

圖7 像素級SSD計算設計結構圖

這種不同于傳統處理器串行訪存特性的處理方式,完全依賴于本文所用到的陣列處理器與分布式共享存儲結構。其中單個PE對本地RAM的無阻塞訪問以及簇內無沖突的并行訪問極大地提高了運算資源利用率。使用像素級SSD計算替代單元級SSD計算,可以使失真值計算提升39.3%的時間性能。

3 實驗分析

3.1 驗證方案

為了評估本文所提出SVDC算法并行設計的性能,我們采用3D-HEVC參考軟件HTM-16.1[12]作為對比平臺。選用四個JCT-3V小組建議的標準序列作為測試用例,包括“Balloons”“Kendo”“GTFly”“PoznanStreet”進行測試,量化參數(QP)為(25,34)。本文使用基于項目組提供的DPR-CODEC結構精簡指令集經過轉碼后的二進制代碼在modelsim中進行基本功能仿真驗證。

3.2 實驗結果與性能分析

將本文實現的SVDC算法計算性能分別與文獻[4]、文獻[5]與文獻[10]的計算性能進行對比,如表1所示。其中ΔT表示本文在SVDC算法計算相比于HTM-16.1平臺中計算節省時間百分比,Δt表示并行編碼相比于串行編碼節省時間百分比,ΔS表示像素級SSD計算相比單元級SSD計算節省時間百分比。

表1 不同方法的編碼時間對比(%)

(5)

(6)

(7)

其中文獻[4]所提出的RM渲染器在編碼端將SVDC算法分為初始化、部分重渲染以及SVDC計算共三部分,通過RM渲染器在初始化后存儲中間變量并進行快速重渲染過程,大幅度降低編碼復雜度。針對深度圖編碼越復雜的測試序列,RM渲染器提升越大,與本文相比在視點合成部分有較大的編碼優勢。文獻[5]提出的零合成視差模型考慮了深度-視差映射,紋理適應和遮擋三種效果用于視點合成優化。文獻[10]提出了的視點合成優化方法,相比原方法增加了跳過零失真的較小模塊或像素行的過程。文獻[5]與文獻[10]仍著重于對視點合成部分進行優化,但是失真值計算卻依舊采用傳統的串行編碼方式。經過實驗得到如表1所示實驗數據,可以發現本文提出的SVDC算法并行化設計相比于文獻[5]與文獻[10]可以獲得更快的編碼時間,但是未能超過文獻[4]的RM渲染器模型。相較于HTM原始算法,本文的算法性能平均可以提升19.025%。

為了證明并行編碼方式的有效性,如表2所示對四個不同測試序列測試四個8×8的像素塊,分別使用串行編碼方式(單PE)以及并行編碼方式(多PE)進行失真值計算,并行編碼方式分為單元級SSD計算以及像素級SSD計算。實驗結果可知,相比于串行編碼方式,本文提出的并行編碼方式可以提升57.6%的計算性能,串/并加速比平均可以達到2.36,相比于單元級SSD計算,本文提出的像素級SSD計算優化設計可以提升39.3%的計算性能。從表2中可看出,當像素塊越復雜,像素級SSD計算的Δt就越大,這得益于像素級SSD計算設計通過重新劃分計算與訪存時序,提高了計算訪存比,減少了PE單元的空閑時間。

表2 串行編碼與并行編碼失真值計算性能分析

由于整個SVDC算法中涉及大量的SSD計算,陣列處理器以及分布式共享存儲結構可以在簇內提供16個位寬為16位的數據讀寫訪問通道,支持單個像素點的數據存取,其中單個PE擁有對本地RAM的優先訪問權,讀操作與寫操作分別可以在1與2個時鐘周期內完成,使得PE的數據訪存難度降低,可以大幅度提高SVDC計算的性能。

如圖8所示,對8×8的像素塊使用不同處理器規模進行失真值計算性能分析。實驗結果表明,當使用的PE核數增多時,算法并行度的提升將導致性能逐步提升,但是由于核數的增多、數據訪存量的增大會造成算法并行化設計愈加復雜。后續的工作中將對于如何提高PE的資源利用率以及如何設計出更高并行度的算法映射方式展開研究。

圖8 不同處理器規模下失真值計算分析

4 結 語

本文基于陣列處理器及分布式共享存儲結構,提出了一種針對SVDC算法的并行映射實現方法。首先通過加載相機參數并進行中值濾波對圖像進行預處理,其次進行3D-warping與空洞填充合成虛擬視點,最后進行失真值計算。以8×8的像素塊為單位,進行多視點SSD計算,利用一個簇的運算資源得到4個塊共計256個像素點的SVDC失真值。同時根據算法訪存特性,使用像素級SSD計算設計替換單元級SSD計算設計以提高運算資源利用率與算法性能。實驗結果表明,相比于HTM平臺,本文所采用的陣列處理器實現的SVDC算法,其時間性能平均可以提升19.025%,所設計的失真值計算并行方案的串/并加速比為2.36,相比于單元級SSD計算,像素級SSD計算優化設計可以提升39.3%的計算性能。使用不同處理器規模對8×8的像素塊進行失真值計算性能分析表明,隨著處理器核數的增多,算法計算性能會逐漸提升,但是數據訪存量的增大會造成算法并行化設計愈加復雜。后續的工作中將對于如何提高PE的資源利用率以及如何設計出更高并行度的算法映射方式展開研究。