基于sor-andn的三維城市場景并行繪制性能分析

基于sor-andn的三維城市場景并行繪制性能分析

1并行繪制系統(tǒng)三維數(shù)字城市系統(tǒng)的構(gòu)建是數(shù)字地球的重要組成部分。隨著城市的快速擴(kuò)張和空間數(shù)據(jù)獲取手段的不斷進(jìn)步,三維城市模型的數(shù)據(jù)量呈現(xiàn)出指數(shù)級增加的趨勢,使得單臺消費級PC的實時繪制能力和內(nèi)存管理能力愈來愈難以滿足三維數(shù)字城市的需求。鑒此,一是從數(shù)據(jù)本身入手,建立三維城市模型的多級分辨率表達(dá),減少實時繪制系統(tǒng)的負(fù)載;二是通過軟硬件方法,直接對渲染過程進(jìn)行加速,而并行繪制因為可擴(kuò)展性高、相對易實現(xiàn),是研究重點之一。Molnar根據(jù)并行繪制系統(tǒng)中,圖元判斷在渲染流水線中的時機(jī),將其分為3類:Sort-First、SortMiddle和Sort-Last。其中,Sort-First特別適合多機(jī)分布式實現(xiàn),以及超高分辨率的顯示,并且在理論上能以類線性的代價實現(xiàn)規(guī)模擴(kuò)展,因而獲得了廣泛的關(guān)注和大量的應(yīng)用。也有一些研究者設(shè)計了混合體系結(jié)構(gòu)的并行繪制系統(tǒng),如文獻(xiàn),其本質(zhì)是一個分層的復(fù)合系統(tǒng),上層采用Sort-First結(jié)構(gòu),對Sort-First中每個子任務(wù)再采用Sort-Last進(jìn)行分解。而大規(guī)模復(fù)雜城市場景多應(yīng)用在超大屏幕展覽,且場景深度復(fù)雜度高,若采用Sort-Last系統(tǒng)可能造成圖像合成時間長,網(wǎng)絡(luò)傳輸量大等問題,因此,多采用Sort-First方式進(jìn)行并行繪制。當(dāng)前對Sort-First系統(tǒng)的研究多集中在任務(wù)劃分及負(fù)載平衡方面,鮮見一些對并行繪制系統(tǒng)性能的定量分析研究工作,并且多針對某一特殊架構(gòu),缺少對Sort-First系統(tǒng)中各系統(tǒng)參數(shù)對性能的影響和加速比的定量分析,難以從節(jié)點配置和任務(wù)劃分兩個方面達(dá)到對系統(tǒng)性能的最優(yōu)化。2首先，并行塊系統(tǒng)及其性能分析2.1并行結(jié)構(gòu)及模型構(gòu)建為了獲得更高性能的計算能力,并行系統(tǒng)對數(shù)據(jù)或者功能進(jìn)行分解,充分發(fā)揮多個節(jié)點的計算能力,分別稱為數(shù)據(jù)并行和時間并行。Sort-First并行繪制系統(tǒng)在圖像空間對任務(wù)進(jìn)行劃分,屬于一種數(shù)據(jù)并行系統(tǒng),其圖元歸屬判斷發(fā)生在進(jìn)入渲染管線之前。如圖1,圖像空間被劃分成若干個不重疊的2D子區(qū)域,每一個或多個子區(qū)域?qū)?yīng)一個繪制節(jié)點,分布在子區(qū)域內(nèi)的所有圖元會被送入相應(yīng)節(jié)點的渲染管線,在管線末端,各節(jié)點將繪制結(jié)果以圖像的形式發(fā)送到最終繪制通道所在節(jié)點完成一幀的顯示?；赟ort-First的并行繪制系統(tǒng)對渲染管線的介入較淺,相對于其他兩種并行結(jié)構(gòu),其主要優(yōu)點有:網(wǎng)絡(luò)傳輸量低;每個節(jié)點執(zhí)行完整的渲染管線,利于分布式實現(xiàn);合成方法簡單;良好的可擴(kuò)展性。由于圖元在屏幕空間的分布具有隨機(jī)性,節(jié)點之間的負(fù)載均衡是Sort-First需要解決的主要問題之一。本文采用一種時間反饋的動態(tài)負(fù)載平衡技術(shù),利用幀間圖元分布的相似性,參考前一幀的繪制時間,作為當(dāng)前幀中繪制任務(wù)劃分的依據(jù)。針對PC集群中網(wǎng)絡(luò)傳輸較慢的特點,本文對文獻(xiàn)中方法做了一定優(yōu)化,將繪制時間與傳輸時間的和作為任務(wù)劃分依據(jù)。在城市場景中,場景的深度復(fù)雜性高,圖元在屏幕上分布密度大,對2D子區(qū)域進(jìn)行的動態(tài)擴(kuò)張或收縮調(diào)整,能帶來圖元負(fù)載數(shù)量顯著的變化,使各節(jié)點的繪制時間趨于一致,所以,此方法在復(fù)雜城市場景繪制中能取得較好效果。2.2性能分析：sort-1行系統(tǒng)2.2.1并行加速比sn對于一個并行計算系統(tǒng)來說,加速比和并行效率都是非常重要的性能指標(biāo),其中最常用的性能評價指標(biāo)就是加速比。假設(shè)一個串行系統(tǒng)完成一幀的繪制所用時間為T(1),而N個節(jié)點構(gòu)成并行繪制系統(tǒng)繪制同樣一幀所用時間為T(N),則加速比S(N)定義為:阿姆達(dá)爾(Amdahl)定律將并行系統(tǒng)中執(zhí)行任務(wù)的時間T(N)分為2個部分,T(P)為系統(tǒng)中可并行部分所花費的時間,T(1)-T(P)為串行部分所花費的時間,將式(1)改寫為:當(dāng)參與并行的節(jié)點數(shù)不斷增加,可并行部分所花費的時間越來越少:可見,并行系統(tǒng)中,能達(dá)到的最高理論加速比取決于可并行部分在整個任務(wù)中的比例。2.2.2繪制時間的約束對于三維城市場景的繪制,每秒的繪制幀數(shù)(FPS)是衡量一個可視化系統(tǒng)的通用性能指標(biāo),在繪制場景內(nèi)容不變的情況下,對FPS的衡量可以轉(zhuǎn)換為繪制一幀所需要的時間,在單節(jié)點的串行繪制系統(tǒng)中,繪制一幀所需時間為:式(4)中,TG和TR分別表示幾何變換和光柵化2個階段所用時間。式(3)是阿姆達(dá)爾定律所表達(dá)的一種理想情況,在Sort-First并行繪制系統(tǒng)中,幾何變換和光柵化都具有數(shù)據(jù)可并行性,然而對數(shù)據(jù)的分解,必然會帶來其他額外的執(zhí)行時間,主要有網(wǎng)絡(luò)傳輸時間(Tw)、從顯存到內(nèi)存的回讀時間(TB)、圖像合成時間(TA)。因此,在有N個節(jié)點參與繪制的SortFirst并行繪制系統(tǒng)中,一幀的繪制時間T(N)可約束為:由于Sort-First系統(tǒng)在每個繪制節(jié)點保留了比較完整的渲染管線,可以記TEi=TGi+TRi+TBi,在以下的討論中以TEi代替繪制時間。而Sort-First架構(gòu)有著合成方法簡單的優(yōu)點,圖像的合成是一個簡單的拼接過程,所以,TA系統(tǒng)性能的影響可忽略不計,式(5)可改寫為:從式(1)可得出,加速比S(N)由每個節(jié)點的繪制時間和圖像傳輸時間決定,從而影響Sort-First并行繪制系統(tǒng)性能的主要因素有:節(jié)點繪制性能、繪制任務(wù)劃分方式、網(wǎng)絡(luò)傳輸速度,以及目標(biāo)顯示顏色深度和分辨率。3繪制節(jié)點的總負(fù)載平衡各個節(jié)點負(fù)載的均衡是Sort-First系統(tǒng)性能達(dá)到最優(yōu)的必要條件,文獻(xiàn)中采用了一種基于繪制時間反饋的動態(tài)負(fù)載平衡方法。由于每個節(jié)點的計算性能可能存在差異,即使建立一個每個節(jié)點硬件配置都是均等的計算集群,也會因多任務(wù)操作系統(tǒng)分配資源的不確定性,導(dǎo)致每個節(jié)點的繪制性能會上下波動,繪制時間難以事先計算,因此,我們通過計算前一幀的繪制時間作為當(dāng)前幀的參考繪制時間,并以此預(yù)測屏幕空間中圖元的分布情況。由直觀判斷可知,節(jié)點中TEi>Twi是該節(jié)點能提高系統(tǒng)加速比的必要條件,該方法使用TUi作為任務(wù)劃分的權(quán)值依據(jù),用有N個葉節(jié)點的二叉樹將屏幕劃分成N個不重疊的二維區(qū)域,將TUi以ms為單位,加權(quán)換算成屏幕空間中以像元無單位二維區(qū)域。本文考慮到PC集群所在的局域網(wǎng)傳輸速度較慢,以及三維城市場景的繪制負(fù)載量較大,使用繪制時間與傳輸時間的和TOi作為衡量該繪制節(jié)點負(fù)載的指標(biāo)。用TOi作為負(fù)載平衡中時空轉(zhuǎn)換的依據(jù),在理想的均衡狀態(tài)下,每個節(jié)點的TOi相等,記為,由于在一幀繪制中,系統(tǒng)中各節(jié)點的總負(fù)載量是一定的,所以,每個節(jié)點的TOi達(dá)到均衡也是整個并行繪制系統(tǒng)達(dá)到理論最高加速比的必要條件,此時,從而,Sort-First并行繪制系統(tǒng)的加速比可以描述為:同繪制時間TEi相比,從繪制節(jié)點至目標(biāo)顯示節(jié)點的網(wǎng)絡(luò)傳輸時間Twi受到傳輸數(shù)據(jù)量及網(wǎng)絡(luò)傳輸速度(記為Li字節(jié)/秒)影響,記顯示總像元為P,顏色深度為D字節(jié),其中,節(jié)點i對應(yīng)視口的像元數(shù)為Pi,則傳輸數(shù)據(jù)量由Pi及D決定:從上節(jié)可知,欲實現(xiàn)負(fù)載平衡,使系統(tǒng)加速比達(dá)到最高值的條件是每個節(jié)點的TEi+Twi相等。在實際系統(tǒng)構(gòu)建中,為了提高性能,應(yīng)用程序所在計算機(jī)往往也是繪制節(jié)點之一,與其他繪制節(jié)點不同的是,該節(jié)點的繪制結(jié)果圖像可直接用來拼接顯示,而不需要網(wǎng)絡(luò)傳輸。為了方便討論,不失一般性記該節(jié)點的繪制時間為TE1,傳輸時間Tw1=0。場景中三角面片在屏幕均勻分布的理想情況下,TE1主要受P1,即主節(jié)點繪制區(qū)域占屏幕像元的比重影響。為了獲得最高理論加速比,本文考慮并行系統(tǒng)中最理想的情況,除第一個繪制節(jié)點(即應(yīng)用程序所在節(jié)點)外,每個節(jié)點的繪制時間TEi和傳輸Twi在每個節(jié)點的值相等,據(jù)式(7)可限定每個節(jié)點的Pi和Li也相等(i≠1)。因為對節(jié)點的繪制時間TEi中包含了從顯存到內(nèi)存的回讀時間,所以,在任務(wù)均等劃分的理想情況下,記目標(biāo)顯示分辨率為P,網(wǎng)絡(luò)總帶寬為L字節(jié)/秒,則在負(fù)載平衡的情況下:由此得到N個節(jié)點構(gòu)成的集群系統(tǒng)中,并行繪制的加速比理論最高值為式(15)右端部分,對于一個可視化系統(tǒng)而言,決定T(1)的影響因素較多,且隨著場景復(fù)雜度及可視部分?jǐn)?shù)據(jù)量而波動,但是,式(15)中顯示分辨率和顏色深度往往是不變的常數(shù),而網(wǎng)絡(luò)帶寬在網(wǎng)絡(luò)環(huán)境建設(shè)好之后也相對固定,所以,我們記常數(shù)C=DL,得到加速比S(N)理論最大值為:由式(16)可看出,在繪制場景不變的情況下,如果TE1增大,意味著P1在增大,即T(1)N+(P-P1)*C在減小,反之亦然,因此,我們得到系統(tǒng)加速比S(N)達(dá)到最大值的一個必要條件:從式(17)可看出,如果T(1)或者N很小,都可能導(dǎo)致等式不成立,由此可見,基于Sort-First的并行繪制系統(tǒng)不同于普通計算密集型的并行計算,在節(jié)點數(shù)較少,以及單臺計算機(jī)繪制負(fù)載較小的情況下,并行繪制的加速比可能會小于1,同樣從式(16)可看出,當(dāng)繪制節(jié)點數(shù)不斷增加時,其帶來的收益并非線性增長,因此,合理配置并行資源對并行繪制系統(tǒng)的性能有著重要的影響。4實驗結(jié)果及分析本節(jié)通過南京市總統(tǒng)府地區(qū)的三維場景并行繪制實驗來驗證上文的分析,并對比分析文獻(xiàn)中的負(fù)載平衡策略與本文方法的性能差異。實驗采用4臺硬件配置如表1的PC機(jī),網(wǎng)絡(luò)環(huán)境為百兆交換機(jī)局域網(wǎng),軟件環(huán)境為Windows764位旗艦版,VisualStudio2010,以O(shè)SG為渲染引擎,模型中共含有8438340個頂點,2812780個三角面片。本實驗實現(xiàn)的是一個動態(tài)漫游系統(tǒng),而在漫游過程中由于磁盤I/O可能會引起FPS的抖動,對I/O相關(guān)的性能影響分析超出了本文的研究范圍,因此,為避免屏幕內(nèi)圖元數(shù)量,以及景深的不同和磁盤I/O對測量結(jié)果的影響,同次實驗中采用相同的位置及視角。顯然當(dāng)視點和視角變化時,實驗結(jié)論依然成立。在自適應(yīng)的負(fù)載平衡實驗中,由于任務(wù)劃分和分配處于一個動態(tài)平衡的狀態(tài),性能及反饋參數(shù)會不斷波動,因此,本文采用連續(xù)繪制2000幀的平均值作為測量結(jié)果。使用不同節(jié)點數(shù),采用單臺PC繪制、以及本文優(yōu)化的動態(tài)負(fù)載均衡方法,分別對實驗場景進(jìn)行繪制(圖2)。實驗中繪制窗口分辨率設(shè)置為720×480,顏色深度為24bit(3Byte)(FPS統(tǒng)計值結(jié)果如表2),因此,一幀圖像的像元數(shù)P為345600,百兆局域網(wǎng)的理論傳輸速度為12MB/s,實測中傳輸速度值大約為10.16MB/s,從而上節(jié)中的常數(shù)C大約為2.82×10-7,統(tǒng)計式(16)中各項的值,結(jié)果如表3所示。從表2可看出,本文以傳輸時間和繪制時間之和,作為性能反饋的依據(jù),相對文獻(xiàn)中的方法,更加全面地考慮了對系統(tǒng)總體性能產(chǎn)生影響的因素,使性能有一定程度的提高。在實際場景中,三角面片在屏幕的分布可能發(fā)生嚴(yán)重傾斜。據(jù)表3的數(shù)據(jù),式(17)所描述的等式并不能完全成立,而會因任務(wù)分配的波動導(dǎo)致主節(jié)點的繪制時間稍長。當(dāng)節(jié)點數(shù)增加,系統(tǒng)整體性能提高時,主節(jié)點所繪制的結(jié)果占屏幕的百分比越來越低,這與式(16)所反映的規(guī)律一致。5并行繪制系統(tǒng)配置優(yōu)化本文分析了基于Sort-First的繪制系統(tǒng)的并行機(jī)制,研究了系統(tǒng)中各項參數(shù)對系統(tǒng)性能的影響,改進(jìn)了文獻(xiàn)提出的負(fù)載平衡策略,嘗試量化分析系統(tǒng)加速比的最高理論值,并給出其成立的一個必要條件。通過一個復(fù)雜城市場景的并行繪制實驗分析,結(jié)果表明,并行繪制系統(tǒng)的配置對性能的提高有著重要的影響,當(dāng)系統(tǒng)負(fù)載較小時,增加節(jié)點甚至可能降低性能,而當(dāng)節(jié)點數(shù)不斷增加,其帶來的收益也并非呈線性增長。本研究為基于SortFirst的并行繪制系統(tǒng)的配