蔣 林，施佳琪，李遠(yuǎn)成

（西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安 710600）

（?通信作者電子郵箱s1007236623@163.com）

0 引言

隨著數(shù)字視頻技術(shù)日趨成熟和圖像圖形技術(shù)、計(jì)算機(jī)視覺技術(shù)的快速發(fā)展，三維（Three-dimensional，3D）視頻以其真實(shí)的視覺體驗(yàn)受到了人們的廣泛關(guān)注，但其龐大的數(shù)據(jù)量給視頻的傳輸和存儲(chǔ)帶來(lái)了極大的壓力。高效視頻編碼（High Efficiency Video Coding，HEVC）框架主要用于視點(diǎn)紋理圖及深度圖編碼［1］，三維高效視頻編碼（3D High Efficiency Video Coding，3D-HEVC）是將深度圖和紋理圖信息用于虛擬合成視點(diǎn)，采用多視點(diǎn)+深度圖（Multi-view Video plus Depth maps，MVD）的編碼格式，根據(jù)數(shù)據(jù)間關(guān)系，引入幀間預(yù)測(cè)技術(shù)降低視頻冗余，達(dá)到高效視頻壓縮的目的。

在3D-HEVC 中，編碼紋理圖造成的圖像失真會(huì)直接導(dǎo)致合成的虛擬視點(diǎn)失真，如果仍選用標(biāo)準(zhǔn)視頻編碼器進(jìn)行編碼，視頻就會(huì)存在失真。這時(shí)，該如何描述合成后圖像的失真程度，對(duì)選擇合適的虛擬視點(diǎn)合成（Virtual View Synthesis，VVS）方法有極大的幫助。圖像失真程度一般采用失真值描述，合成視點(diǎn)失真變化（Synthesized View Distortion Change，SVDC）算法是通過計(jì)算深度圖與紋理圖信息，獲取合成后圖像的失真值［2］，即縮短SVDC 算法的執(zhí)行時(shí)間，從而高效描述合成后圖像失真程度。

SVDC 算法以整幅圖像作為輸入，隨著圖像尺寸的增大，SVDC 算法時(shí)間復(fù)雜度會(huì)大幅增加，失真值將難以計(jì)算［3］。文獻(xiàn)［4］進(jìn)行算法分析時(shí)，發(fā)現(xiàn)在失真值計(jì)算過程中:當(dāng)視差矢量為0，失真值也等于0。根據(jù)此特點(diǎn)，采用自適應(yīng)分段跳過規(guī)則視點(diǎn)合成方法，在SVDC 算法計(jì)算過程中，降低了計(jì)算圖像失真程度的時(shí)間復(fù)雜度。

SVDC 算法以矩陣形式參與運(yùn)算，運(yùn)算步驟相對(duì)獨(dú)立，計(jì)算過程中數(shù)據(jù)依賴性低，具有較高的并行性，適合可重構(gòu)陣列處理器進(jìn)行并行計(jì)算。一種典型的可重構(gòu)陣列處理器系統(tǒng)結(jié)構(gòu)如圖1 所示，其中，圖1（a）為可重構(gòu)陣列處理器系統(tǒng)，由主處理器、全局指令存儲(chǔ)器、輸入/輸出存儲(chǔ)器、可重構(gòu)陣列處理器和接口控制器等部分組成。主處理器通過接口控制器調(diào)度可重構(gòu)陣列處理器，全局指令存儲(chǔ)器用于存儲(chǔ)可重構(gòu)陣列處理器操作和調(diào)用指令，輸入/輸出存儲(chǔ)器用于存儲(chǔ)陣列處理器需要處理的數(shù)據(jù)，可重構(gòu)陣列處理器用于完成主處理器分配的任務(wù)。

圖1 可重構(gòu)陣列處理器系統(tǒng)結(jié)構(gòu)Fig.1 Architecture of reconfigurable array processor system

與通用處理器相比，可重構(gòu)陣列處理器由主控制器和可重構(gòu)處理單元陣列組成。主控制器控制整個(gè)結(jié)構(gòu)執(zhí)行，可重構(gòu)處理單元陣列由多個(gè)處理單元（Process Element，PE）構(gòu)成，每個(gè)PE 包含算術(shù)邏輯單元（Arithmetic Logical Unit，ALU）、寄存器、存儲(chǔ)器，根據(jù)配置不同PE 可以執(zhí)行常見操作（如加法、減法、與、或、非等）。在編譯方式上，與通用編譯為單一目標(biāo)處理器的匯編指令不同，可重構(gòu)編譯通過軟硬件劃分，將劃分結(jié)果分別生成主控制器的控制碼以及配置陣列處理器上的配置信息。此外，可重構(gòu)陣列處理的執(zhí)行方式是通過主處理器將任務(wù)下發(fā)給可重構(gòu)陣列處理器執(zhí)行，采用主控制器選擇片上配置存儲(chǔ)器中的信息，將信息下發(fā)給處理簇（Process Element Group，PEG）執(zhí)行，每個(gè)簇再通過片上配置存儲(chǔ)器將存儲(chǔ)的可重構(gòu)配置信息［5］分配到PE中進(jìn)行運(yùn)算。

綜上所述，本文基于可重構(gòu)陣列結(jié)構(gòu)（基于現(xiàn)場(chǎng)可編程邏輯門陣列（Field Programmable Gate Array，F(xiàn)PGA）實(shí)現(xiàn)的BEE4 平臺(tái)），設(shè)計(jì)并實(shí)現(xiàn)了一種混合粒度SVDC 算法，以有效縮短SVDC 算法執(zhí)行時(shí)間。通過分析虛擬視點(diǎn)合成過程中深度圖與紋理圖的關(guān)系，利用失真值計(jì)算過程中圖像失真值等于像素點(diǎn)失真值累加的特點(diǎn)，發(fā)揮可重構(gòu)陣列結(jié)構(gòu)優(yōu)勢(shì)，設(shè)計(jì)并實(shí)現(xiàn)了SVDC算法并行化映射方法。

1 SVDC算法的并行性分析

SVDC算法是計(jì)算虛擬視點(diǎn)合成失真值的方法，但是隨著圖像尺寸的增大，將難以在有限時(shí)間內(nèi)計(jì)算虛擬視點(diǎn)合成失真值。因此，將SVDC 算法分為三部分:初始化、重渲染和失真值計(jì)算，其計(jì)算過程如圖2所示。

圖2 SVDC算法流程Fig.2 Flow chart of SVDC algorithm

由圖2 可以看出，SVDC 算法三部分的具體內(nèi)容如下:1）初始化部分:已編碼的深度圖像D'與已編碼紋理圖像T'。2）重渲染部分:已編碼的深度圖像D"與未編碼紋理圖像T"，分別進(jìn)行虛擬視點(diǎn)合成，用V'和V"表示，然后將原始紋理圖T與原始深度圖D合成參考視點(diǎn)V。3）失真值計(jì)算:V與V'的差值平方和SSD'和V與V"的差值平方和SSD"的差值表示為虛擬視點(diǎn)合成的失真值。

1.1 SVDC算法計(jì)算階段確定

由圖2 中SVDC 的計(jì)算過程，可得SVDC 算法主要有兩個(gè)模塊:虛擬視點(diǎn)合成和失真值計(jì)算，其計(jì)算階段劃分如圖3 所示。圖3 中:最左側(cè)為將原始圖像分割成大小是8×8 的待處理塊，通過虛擬視點(diǎn)合成獲得合成后的圖像；失真值計(jì)算獲得合成后的失真值。

圖3 SVDC算法計(jì)算階段示意圖Fig.3 Schematic diagram of SVDC algorithm calculation stages

由于SVDC 算法計(jì)算模式不同，所以，在可重構(gòu)陣列結(jié)構(gòu)處理器上，增加配置信息去映射不同的PEG。

1.2 虛擬視點(diǎn)合成并行分析

虛擬視點(diǎn)合成作為SVDC 算法的第一個(gè)模塊，包括三個(gè)部分:邊界掩模、3D warping 和空洞填充。這三個(gè)部分的輸入單位是像素塊，本文使用的像素塊大小是m×m，具體內(nèi)容如下:

1）邊界掩模:依據(jù)像素點(diǎn)的紋理圖和深度圖信息判斷物體邊界是否遮蔽以及遮蔽后的處理方法。

2）3D warping:依據(jù)深度圖信息與紋理圖信息的疊加找到合成后視點(diǎn)的映射規(guī)則。在執(zhí)行邊界掩膜和3D warping 時(shí)，需要對(duì)整塊區(qū)域進(jìn)行處理。

3）空洞填充:空洞是前景參照物遮擋到后景區(qū)域產(chǎn)生的，使得合成視頻較原景象出現(xiàn)較大的偏差，一般通過低通濾波器對(duì)深度圖進(jìn)行預(yù)處理減小空洞區(qū)域，在視點(diǎn)合成過程中需要空洞填充以保證視頻圖像的準(zhǔn)確性。

虛擬視點(diǎn)合成的三個(gè)部分，雖然在自身內(nèi)部計(jì)算時(shí)不能并行化，但在進(jìn)行虛擬視點(diǎn)合成時(shí)都相對(duì)獨(dú)立，可以采用流水線與重構(gòu)方式進(jìn)行加速計(jì)算［6］。

1.3 失真值計(jì)算并行分析

SVDC算法的第二個(gè)模塊是失真值計(jì)算，失真值計(jì)算主要分為圖像失真值計(jì)算和像素點(diǎn)失真值計(jì)算，計(jì)算已編碼區(qū)和未編碼區(qū)分別與參考圖平方和的差值，如式（1）所示。

其中:I為圖像處理塊，ΔD為I的失真值；為I的初始化紋理圖為I的重渲染紋理圖為I的參考紋理圖；()x，y為I的像素點(diǎn)坐標(biāo)。

1.3.1 圖像失真值計(jì)算分析——任務(wù)級(jí)

失真值計(jì)算的流程如圖4 所示，其中，Dx1是第一個(gè)循環(huán)讀取初始化圖像與參考圖像像素值E1、E2后，差值平方的累加值；Dx2是第二個(gè)循環(huán)讀取重渲染圖像與參考圖像像素值E3、E4后，差值平方的累加值。

圖4 失真值計(jì)算流程Fig.4 Flow chart of distortion value calculation

分析這兩個(gè)循環(huán)可得失真值計(jì)算是整個(gè)區(qū)域塊內(nèi)部中所有像素點(diǎn)失真值的累加，兩個(gè)循環(huán)中每次循環(huán)都相對(duì)獨(dú)立且具有相同的計(jì)算過程［7］，因此，失真值計(jì)算具備并行性。

1.3.2 像素點(diǎn)失真值計(jì)算分析——指令級(jí)

由1.3.1 節(jié)可知，圖像失真值計(jì)算是像素點(diǎn)失真值計(jì)算的累加。像素點(diǎn)失真值計(jì)算如圖5 所示，圖中a1、a2、a3分別是初始化紋理圖、參考紋理圖、重渲染紋理圖的像素點(diǎn)。

圖5 像素點(diǎn)失真值計(jì)算Fig.5 Calculation of pixel distortion value

整個(gè)計(jì)算過程分解為兩個(gè)部分:1）A，計(jì)算a1與a2差值平方a6的過程；2）B，計(jì)算a3與a2差值平方a7的過程。將A、B 兩部分的結(jié)果相減得到最終結(jié)果，可得像素點(diǎn)的失真值，兩部分計(jì)算過程一致，數(shù)據(jù)依賴性低，具有并行性［8］。

綜上所述，SVDC 算法的優(yōu)化主要分為兩個(gè)部分:1）虛擬視點(diǎn)合成部分采用流水線方式加速；2）失真值計(jì)算部分采用兩級(jí)（任務(wù)級(jí)、指令級(jí)）劃分加速。

2 混合粒度劃分方法

首先，提出了混合粒度劃分方法的基本思想。然后，根據(jù)SVDC 算法的特點(diǎn)，對(duì)虛擬視點(diǎn)合成部分，設(shè)計(jì)流水線劃分策略縮短虛擬視點(diǎn)合成部分時(shí)間；對(duì)失真值計(jì)算部分，比較像素點(diǎn)以及計(jì)算過程對(duì)其執(zhí)行時(shí)間的加速程度。最后，選擇合適的方法縮短SVDC 算法的執(zhí)行時(shí)間，并給出SVDC 算法的重構(gòu)配置信息。

2.1 混合粒度劃分的基本思想

混合粒度劃分為兩個(gè)部分:虛擬視點(diǎn)合成和失真值計(jì)算。虛擬視點(diǎn)合成采用流水線作業(yè)的方式加速。失真值計(jì)算采用兩級(jí)劃分加速:任務(wù)級(jí)——像素塊與像素點(diǎn)的依賴關(guān)系；指令級(jí)——像素點(diǎn)內(nèi)部計(jì)算過程中的依賴關(guān)系。

混合粒度劃分方法，通過虛擬視點(diǎn)合成得到合成圖像，計(jì)算失真值。并行化過程使用addparallel 方法實(shí)現(xiàn)。通過判斷singal狀態(tài)選擇并行或同步處理，若為false 則表示計(jì)算未結(jié)束需要同步等待；反之，需要并行計(jì)算，其具體計(jì)算步驟如下。

其中，通過VVS 方法實(shí)現(xiàn)虛擬視點(diǎn)合成，失真值計(jì)算過程中，通過imagedivide方法實(shí)現(xiàn)任務(wù)級(jí)劃分策略，即將像素塊均勻分配給指定數(shù)目的處理單元運(yùn)算；通過get_Set_SVDC 方法實(shí)現(xiàn)指令級(jí)劃分策略，將任務(wù)級(jí)劃分的結(jié)果作為輸入，對(duì)每個(gè)結(jié)果采用指令級(jí)方法，獲取失真值，將失真值結(jié)果累加，即可獲得圖像的失真情況。

2.2 虛擬視點(diǎn)合成劃分

根據(jù)1.2 節(jié)分析可知，虛擬視點(diǎn)合成分為邊界掩模、3D warping 和空洞填充三個(gè)部分。由于這三個(gè)部分各自不能并行，所以使用如圖6所示的流水線方式進(jìn)行加速。

圖6 虛擬視點(diǎn)合成時(shí)空間流水線作業(yè)Fig.6 Spatio-temporal pipelining of virtual view synthesis

圖6 中，將深度圖和紋理圖像素塊通過邊界掩模、3D warping 和空洞填充這三個(gè)部分進(jìn)行虛擬視點(diǎn)合成。當(dāng)?shù)谝粋€(gè)像素塊邊界掩膜完成后，第二個(gè)像素塊開始邊界掩膜。因此，采用流水線方式能夠縮短虛擬視點(diǎn)合成階段的執(zhí)行時(shí)間。虛擬視點(diǎn)合成采用流水線方式加速的設(shè)計(jì)方法，以邊界掩膜為例，具體算法如下。

其中addparallel（“boder”，1）詢問處理單元是否處于freedom狀態(tài)，對(duì)于繁忙狀態(tài)則需要等待，進(jìn)行線程同步；反之，直接運(yùn)算。3D warping和空洞填充使用相同的判斷方法。

2.3 失真值計(jì)算基礎(chǔ)劃分方法性能對(duì)比

根據(jù)1.3 節(jié)對(duì)失真值計(jì)算的分析可得兩類劃分策略:1）按照任務(wù)級(jí)劃分，如1.3.1 節(jié)所述，將像素塊中像素點(diǎn)單獨(dú)計(jì)算，累加求和；2）按照指令級(jí)劃分，如1.3.2 節(jié)所述，使用兩個(gè)處理單元計(jì)算初始化失真和重渲染失真結(jié)果，兩者相減，累加求和。兩種劃分方法的性能對(duì)比如表1所示。

表1 SVDC失真值計(jì)算方法性能對(duì)比Tab.1 Performance comparison of SVDC distortion value calculation methods

一方面，從表1 中的數(shù)據(jù)中可得，當(dāng)處理問題規(guī)模不同（像素塊大小不同）時(shí)，劃分方法的計(jì)算性能提升也不同。問題規(guī)模較大時(shí)，任務(wù)級(jí)劃分方法的性能提升較好；而指令級(jí)劃分方法對(duì)單一點(diǎn)有更好的性能提升。

另一方面，分析表1 中的數(shù)據(jù)可知，任務(wù)級(jí)劃分方法能合理使用有限的資源，指令級(jí)劃分對(duì)單一點(diǎn)加速性能更好。但是從1.3 節(jié)可知，圖像的失真值是像素點(diǎn)失真值的累加，然而指令級(jí)劃分是對(duì)像素點(diǎn)失真值計(jì)算的優(yōu)化。所以，在不考慮處理單元數(shù)目時(shí)，將任務(wù)級(jí)和指令級(jí)劃分方法混合能夠得到更優(yōu)的性能［9］。而處理單元數(shù)目有限時(shí)，任務(wù)級(jí)劃分方法能夠得到更好的性能提升。

2.4 像素塊-像素點(diǎn)劃分（任務(wù)級(jí)）

在像素塊-像素點(diǎn)劃分中，由失真值計(jì)算式（1）分析可得，像素塊內(nèi)失真值等于像素點(diǎn)失真值的累加。對(duì)失真值計(jì)算分析可得，圖像失真值等于像素塊失真值之和，即圖像的失真值等于像素點(diǎn)失真值的累加，由此提出任務(wù)級(jí)方法［10］。

如圖7 所示，以4 個(gè)PE 為例，首先PE00 讀取的是初始化紋理圖St、重渲染紋理圖、參考紋理圖Stf中的第0號(hào)像素值，而PE01、PE02、PE03 分別讀取的是三幅圖中第1、2、3 號(hào)像素值。然后讀取4×當(dāng)前PE 已讀取像素點(diǎn)數(shù)（如:a為PE00 已讀取像素點(diǎn)數(shù)），最后將計(jì)算結(jié)果在PE03處累加得到失真值。

圖7 像素塊-像素點(diǎn)劃分框圖Fig.7 Block diagram of pixel block-pixel point division

像素塊-像素點(diǎn)劃分方法是將像素塊均勻分配到每個(gè)處理單元計(jì)算失真值，具體算法如下。

通過計(jì)算像素點(diǎn)與處理單元的模值，即通過i取process_num模分配像素點(diǎn)到對(duì)應(yīng)的處理單元計(jì)算失真值，并將分配后的點(diǎn)寫入process_point_set中進(jìn)行失真值計(jì)算。

2.5 像素點(diǎn)-計(jì)算過程劃分（指令級(jí)）

像素點(diǎn)-計(jì)算過程劃分是將每個(gè)像素點(diǎn)失真值計(jì)算過程進(jìn)行劃分。由1.3 節(jié)對(duì)失真值計(jì)算的分析可得每一個(gè)像素點(diǎn)都具有相同的計(jì)算過程，可以并行化。因此，將失真值計(jì)算的式（1）分解為式（2），整個(gè)計(jì)算式分為三個(gè)部分。

式（2）中，前半部分是初始化像素點(diǎn)差值的平方，后半部分是重渲染像素點(diǎn)差值的平方。該方法能保證負(fù)載上的均衡，提升整體計(jì)算性能［11］，像素點(diǎn)內(nèi)部計(jì)算過程的任務(wù)執(zhí)行如圖8所示。圖8中，S1代表計(jì)算初始化像素與參考圖像素點(diǎn)差值的平方，S2代表計(jì)算重渲染像素與參考圖差值的平方，將兩者的計(jì)算結(jié)果通過PE30相減，得到失真值。

圖8 像素點(diǎn)-計(jì)算過程劃分框圖Fig.8 Block diagram of pixel-calculation division

像素點(diǎn)-計(jì)算過程的劃分中，通過addparallel 方法將計(jì)算初始化和重渲染像素點(diǎn)差值平方進(jìn)行并行化處理。通過addparallel（“ST1”，1）、addparallel（“ST2”，2）判斷計(jì)算完成情況，如果完成，則將結(jié)果相減得到最終失真值；反之等待，具體步驟如下。

2.6 重構(gòu)信息配置

重構(gòu)配置信息執(zhí)行示意圖如圖9 所示。首先，通過分析SVDC 算法與可重構(gòu)陣列結(jié)構(gòu)的關(guān)系得到SVDC 算法的配置信息:虛擬視點(diǎn)合成和失真值計(jì)算。然后，將配置信息載入到片上配置存儲(chǔ)器，在可重構(gòu)計(jì)算陣列執(zhí)行時(shí)，載入PEG［12-13］。最后，PEG00 載入虛擬視點(diǎn)合成配置信息后重復(fù)執(zhí)行Nt次虛擬視點(diǎn)合成，將每次計(jì)算結(jié)果寫入PEG01，PEG01重復(fù)執(zhí)行Nt次失真值計(jì)算，并將每次計(jì)算結(jié)果累加，求得圖像失真值。

圖9 可重構(gòu)配置信息執(zhí)行示意圖Fig.9 Schematic diagram of reconfigurable configuration information execution

3 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證混合粒度劃分方法的計(jì)算性能，本文基于Beecube 公司BEE4 型號(hào)的FPGA 開發(fā)板進(jìn)行實(shí)驗(yàn)?？芍貥?gòu)陣列處理器結(jié)構(gòu)是由1 024個(gè)PE鄰接互連成的動(dòng)態(tài)可編程可重構(gòu)陣列結(jié)構(gòu)。該陣列結(jié)構(gòu)包含64個(gè)簇，每個(gè)簇包含16個(gè)PE，每個(gè)PE 包含大小為512×32 的指令存儲(chǔ)單元、大小為512×16 的數(shù)據(jù)存儲(chǔ)單元、12 個(gè)本地寄存器（R1～R7，R12～R15）和4個(gè)共享寄存器（RE、RS、RW、RN），各個(gè)PE 之間通過4 個(gè)共享寄存器進(jìn)行數(shù)據(jù)交互。每個(gè)PE 采用load/store 模式的精簡(jiǎn)指令集計(jì)算機(jī)（Reduced Instruction Set Computer，RISC）架構(gòu)，按照取指、譯碼、執(zhí)行、寫返回4 級(jí)流水線結(jié)構(gòu)進(jìn)行執(zhí)行整個(gè)過程。

3.1 實(shí)驗(yàn)方案

為了驗(yàn)證混合粒度劃分方法在陣列結(jié)構(gòu)上的適用性，本文將以3D-HEVC 的參考模型HTM 作為參照［14］。依據(jù)可重構(gòu)陣列結(jié)構(gòu)的設(shè)計(jì)原理，在Questasim 10.1d 仿真平臺(tái)上進(jìn)行實(shí)驗(yàn)，時(shí)鐘周期為20 ns，讀取數(shù)據(jù)仿真時(shí)間為200 ns，合并數(shù)據(jù)仿真時(shí)間為134 ns。

針對(duì)大小為8×8 的編碼單元進(jìn)行仿真。測(cè)試用例分別為Balloons（1024×768）、GTFly（1920×1088）、PoznanStreet（1920×1088）、UndoDancer（1920×1088），測(cè)試用例的視點(diǎn)為雙視點(diǎn)，分別對(duì)應(yīng)兩對(duì)深度序列。首先，采用共享存儲(chǔ)并行編程（Open Multi-Processing，OpenMP）工具在SVDC 算法可并行的代碼段中添加標(biāo)記［15］。然后，使用底層虛擬機(jī)（Low Level Virtual Machine，LLVM）并行編譯器執(zhí)行SVDC 算法的代碼。最后，由于SVDC 算法中失真值計(jì)算部分的并行性較高，采用像素點(diǎn)劃分和本文劃分的方法，分別驗(yàn)證處理單元數(shù)目和像素塊大小對(duì)失真值計(jì)算的加速性能。

3.1.1 SVDC算法性能仿真

四個(gè)測(cè)試序列分別采用上述四類方法（本文方法、OpenMP、LLVM 和HTM），針對(duì)四個(gè)處理單元，像素塊大小為8×8 的執(zhí)行時(shí)間對(duì)比如圖10 所示。根據(jù)阿姆達(dá)爾定律可得混合粒度劃分方法的加速比約為2.11。

圖10 不同平臺(tái)上SVDC算法執(zhí)行時(shí)間對(duì)比Fig.10 Comparison of SVDC algorithm execution time on different platforms

LLVM 與OpenMP 并行編程方法，都是采用顯式并行策略:一方面通過操作系統(tǒng)進(jìn)行調(diào)度會(huì)額外增加調(diào)度開銷；另一方面采取保守方式挖掘算法并行性。本文方法是在可重構(gòu)結(jié)構(gòu)的基礎(chǔ)上挖掘多粒度并行性，減少了額外開銷，具有更好的并行性能。

針對(duì)不同的視頻圖像，經(jīng)計(jì)算可得，本文方法與LLVM 并行編譯方法相比計(jì)算性能提升了18.56%，與OpenMP 編程模型相比計(jì)算性能提升了21.93%。這也表明混合粒度劃分方法對(duì)于SVDC算法性能提升更優(yōu)，尤其序列2更為明顯。

3.1.2 失真值計(jì)算性能仿真

由第1.3 節(jié)分析可得，失真值計(jì)算部分更適合并行執(zhí)行。分析2.3 節(jié)可知，當(dāng)處理單元有限時(shí)，任務(wù)級(jí)劃分方法會(huì)獲得更優(yōu)的加速性能。而當(dāng)處理單元數(shù)目足夠時(shí)，本文方法的性能更優(yōu)。

因此，實(shí)驗(yàn)對(duì)序列2 分別通過PE 數(shù)目（2、4、8、16、32、64、128）和像素塊大小（1×1、2×2、4×4、8×8）這兩個(gè)因素，設(shè)計(jì)分別使用任務(wù)級(jí)劃分方法與本文的混合粒度劃分方法，分析這兩種方法對(duì)失真值計(jì)算部分加速性能的影響，結(jié)果如圖11所示。

由圖11 可以看出，在像素塊大小一致、處理單元數(shù)目大于像素塊大小時(shí)，本文劃分方法相較像素點(diǎn)劃分方法，加速性能有顯著的提升，并且隨著像素塊擴(kuò)大，本文劃分方法在PE數(shù)目足夠時(shí)，加速性能的提升依舊顯著。

3.2 混合粒度劃分方法性能分析

混合粒度劃分方法分為兩步:1）將像素塊分解為若干像素點(diǎn)失真值計(jì)算的累加；2）將像素點(diǎn)內(nèi)部失真值計(jì)算過程分解為A、B 兩個(gè)過程。對(duì)混合粒度方法進(jìn)行理論分析，得到混合粒度劃分方法執(zhí)行時(shí)間，進(jìn)行實(shí)驗(yàn)驗(yàn)證。

假設(shè)原圖為On1×n2，使用的像素塊為Gm×m，則需要處理塊的數(shù)目block_num=

首先，對(duì)虛擬視點(diǎn)合成而言，假設(shè)T1、T2、T3分別為虛擬視點(diǎn)合成的三個(gè)部分邊界掩膜、3D warping 和空洞填充的執(zhí)行時(shí)間。那么，虛擬視點(diǎn)合成串行算法的時(shí)間TVVS=T1+T2+T3。而采用流水線方式進(jìn)行計(jì)算，結(jié)合2.2 節(jié)視點(diǎn)合成流水線時(shí)空?qǐng)D和相應(yīng)的算法，得出并行算法的執(zhí)行時(shí)間TVVSp=max｛T1，T2，T3｝。

其次，對(duì)失真值計(jì)算而言，設(shè)Cm×m中每個(gè)元素為像素塊中每個(gè)點(diǎn)失真值計(jì)算的時(shí)間，則串行時(shí)間TSSD=C11+C12+…+Cmm。而對(duì)于混合粒度方法中的失真值計(jì)算，包括將像素塊劃分為均勻等分的像素點(diǎn)集劃分?jǐn)?shù)量num=m2/S。

根據(jù)像素點(diǎn)-計(jì)算過程的劃分，設(shè)Cc1、Cc2分別為像素點(diǎn)的SSD'與SSD"計(jì)算時(shí)間，則每個(gè)像素點(diǎn)失真值計(jì)算的時(shí)間Tc=2×max｛Cc1，Cc2｝+t1。

因此，失真值計(jì)算并行執(zhí)行時(shí)間TSSDp=num×（Tc）+m2×t2。

其中，S為可使用的核數(shù)，t1為處理單元數(shù)據(jù)合并時(shí)間，t2為像素點(diǎn)失真值累加時(shí)間。

最后，經(jīng)理論推算本文方法的加速比為:

由上述分析可得，本文方法對(duì)于SVDC 算法的性能提升體現(xiàn)在:1）虛擬視點(diǎn)合成采用流水線方式加速；2）失真值計(jì)算采用任務(wù)級(jí)+指令級(jí)進(jìn)行加速。本文方法進(jìn)一步提升了算法性能的主要因素是處理器數(shù)目與問題規(guī)模的關(guān)系，只有選擇合適的處理器數(shù)目，才能有效縮短算法的執(zhí)行時(shí)間。

4 結(jié)語(yǔ)

SVDC算法是虛擬視點(diǎn)合成中的關(guān)鍵環(huán)節(jié)，而算法的執(zhí)行效率對(duì)圖像視點(diǎn)合成質(zhì)量非常重要。因此，本文提出了一種在可重構(gòu)結(jié)構(gòu)下基于混合粒度的SVDC 算法并行化方法。該方法將算法原有的三個(gè)部分（初始化、重渲染和失真值計(jì)算）轉(zhuǎn)變?yōu)閮蓚€(gè)部分:虛擬視點(diǎn)合成和失真值計(jì)算。其中，第一個(gè)部分虛擬視點(diǎn)合成采用流水線方法進(jìn)行優(yōu)化；第二個(gè)部分將失真值計(jì)算分為兩個(gè)過程:像素塊-像素點(diǎn)、像素點(diǎn)-計(jì)算過程。實(shí)驗(yàn)結(jié)果表明，在處理單元數(shù)目為4、像素塊大小為8×8時(shí)，本文劃分方法與基于LLVM 和OpenMP 的SVDC 算法相比，計(jì)算時(shí)間分別縮短了18.56%、21.93%。針對(duì)SVDC 計(jì)算過程中并行度高的失真值計(jì)算部分，通過實(shí)驗(yàn)得到當(dāng)處理單元數(shù)目為128時(shí)，失真值計(jì)算的性能可提升55.23倍。在接下來(lái)的研究中，將把硬件結(jié)構(gòu)作為側(cè)重點(diǎn)，包括循環(huán)迭代過程中免數(shù)據(jù)驗(yàn)證、增加數(shù)據(jù)傳輸帶寬等，都是提升算法性能的可行性方法。