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

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

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