劉鶴年

摘要：在光線跟蹤算法中，傳統(tǒng)上通過像素遞歸深度對場景進(jìn)行劃分，然后必須每一個任務(wù)分配一個GPU服務(wù)器節(jié)點服務(wù)器，但是這種靜態(tài)任務(wù)分配的算法在虛擬化環(huán)境中沒辦法實現(xiàn)對GPU資源的有效利用，而且一旦有服務(wù)器節(jié)點宕機(jī)就會導(dǎo)致場景繪制失敗。對此，提出一種基于hash思想的解決方案，有效的解決該問題。

關(guān)鍵詞：實時場景繪制；hash算法；集群

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2018）02-0127-02

在三維場景繪制領(lǐng)域中已有的負(fù)載均衡策略有PBT樹的自適應(yīng)劃分算法[1]和基于像素開銷[2]以及按像素遞歸深度對場景進(jìn)行劃分[3]的方法。但是這些方式都沒有解決集群中的宕機(jī)問題。因此本文采用hash的方式解決在三維場景繪制的過程中出現(xiàn)服務(wù)器節(jié)點宕機(jī)的情況。

1 總體框架

在任務(wù)劃分上本算法采用按像素遞歸深度[3]對場景進(jìn)行劃分，然后通過數(shù)據(jù)傳輸將劃分好的場景發(fā)送給GPU集群。本文主要研究的是GPU集群的資源調(diào)度方案。通過本算法的資源調(diào)度本文優(yōu)化了實時場景繪制的速度并解決了GPU集群中有服務(wù)器節(jié)點出現(xiàn)宕機(jī)的問題，如圖1所示。

2 算法原理

為了能夠更有效的分配GPU集群的計算節(jié)點，本算法將引入一個足夠大的Hash空間，如果hash空間太小，容易在映射時發(fā)生沖突，所以將這個用來映射的hash空間大小定為0～232。為了更好的描述本算法，可以將hash空間想象成一個首位相連的圓環(huán)。然后將服務(wù)器服務(wù)器節(jié)點也映射到同一個hash空間中。

使用A，B，C和D四臺服務(wù)器服務(wù)器節(jié)點，將服務(wù)器節(jié)點映射到hash空間中，以對應(yīng)的hash值排列。

使用MD5算法作為服務(wù)器節(jié)點的hash算法，并使用機(jī)器名作為機(jī)器IP地址作為hash輸入。

將服務(wù)器節(jié)點和繪制任務(wù)都映射到hash空間之后，繪制任務(wù)順時針方向?qū)ふ易罱姆?wù)器節(jié)點，這樣就將服務(wù)器節(jié)點和繪制任務(wù)對應(yīng)起來。

3 服務(wù)器節(jié)點宕機(jī)情況處理

當(dāng)服務(wù)器節(jié)點B出項宕機(jī)情況導(dǎo)致繪制失敗的時候，受到影響的是沿著B逆時針遍歷到下一個節(jié)點之間的繪制任務(wù)。

因此這里僅需變動任務(wù)1，將任務(wù)1重新映射到C就可以，如圖2所示。

此時并沒有進(jìn)行任務(wù)的重新劃分，任務(wù)依舊是4個，只不過將其中兩個任務(wù)分配給了同一個服務(wù)器節(jié)點。因此場景繪制不會因其中一個服務(wù)器節(jié)點的宕機(jī)而導(dǎo)致繪制失敗。

4 平衡性處理

因為實時場景的繪制的最終效果依賴?yán)L制最慢的服務(wù)器節(jié)點。為了使場景的繪制任務(wù)能夠均勻的映射到服務(wù)器節(jié)點上，引入了“虛擬服務(wù)器節(jié)點”的概念，一個服務(wù)器節(jié)點對應(yīng)多個“虛擬服務(wù)器節(jié)點”。

節(jié)點A1，A2代表了A，D1和D2代表了D，如圖3所示。

實際上任務(wù)1和任務(wù)2被分配到了A上進(jìn)行計算，任務(wù)3和任務(wù)4被分配到D上進(jìn)行了計算；

5 實驗結(jié)果

本文使用的集群是通過4臺微機(jī)進(jìn)行每臺配置為：Intel（R）Xeon（R）E3-1255v3CPU，4GB主存，NVQuadroK600GPU。編譯環(huán)境為：win1064位操作系統(tǒng)，VS2013、OptiX3.8.0、CUDA7.5。

經(jīng)過測試該算法可以很好的對任務(wù)進(jìn)行分配，而且在任務(wù)分配過程中出現(xiàn)服務(wù)器宕機(jī)的情況也可以很好的進(jìn)行處理，而且不影響任務(wù)分配的情況。

參考文獻(xiàn)

[1]任崇輝.基于GPU的高真實感集群渲染系統(tǒng)[D].杭州：浙江大學(xué)，2011.

[2]梁鮮，曲福恒，楊勇，等.基于加權(quán)處罰的K-均值優(yōu)化算法[J].長春理工大學(xué)學(xué)報：自然科學(xué)版，2015，38（4）：132-137.

[3]蔣聰，陳純毅.基于手勢的交互式三維場景并行光線跟蹤繪制研究[J].長春理工大學(xué)學(xué)報（自然科學(xué)版），2016，（2）：90-97.

[4]孔令德.計算機(jī)圖形學(xué)基礎(chǔ)教程[M].北京：清華大學(xué)出版社，2008.

[5]Alan Chalmers，Erik Reinhard.Pratical parallel rendering[M].A.K.Peters，Ltd.，2002：20-35.