基于XGBoost 的四分屏繪制系統(tǒng)負(fù)載平衡算法

賈文娟

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065；四川川大智勝軟件公司，成都610065）

0 引言

隨著人工智能技術(shù)應(yīng)用越來(lái)越廣泛，3D 游戲、虛擬現(xiàn)實(shí)（Virtual Reality，VR）等基于實(shí)時(shí)交互的娛樂(lè)系統(tǒng)也隨之飛速發(fā)展起來(lái)，很多應(yīng)用能夠?qū)崟r(shí)地生成高質(zhì)量的畫面，例如3D 游戲《傳奇世界》以及VR 游戲《弓箭大師》，其真實(shí)的場(chǎng)景和流暢精致的畫面給玩家?guī)?lái)視覺(jué)享受。HTC 最新發(fā)布的穿戴式VR 設(shè)備Vive Pro[1]，分辨率為2880×1600 且具有90Hz 的刷新率，每秒高達(dá)4 億像素點(diǎn)的繪制能力。對(duì)于復(fù)雜場(chǎng)景的繪制并輸出高質(zhì)量的畫面，對(duì)計(jì)算資源提出了更高的要求，目前GPU 的計(jì)算能力仍然無(wú)法滿足對(duì)計(jì)算能力的需求。

并行繪制[2]是應(yīng)對(duì)上述問(wèn)題的一種切實(shí)可行的解決方案。它主要是將繪制總?cè)蝿?wù)劃分為若干可獨(dú)立執(zhí)行的子任務(wù)，利用多個(gè)繪制節(jié)點(diǎn)并行地對(duì)各子任務(wù)進(jìn)行繪制，然后收集所有并行繪制節(jié)點(diǎn)的繪制結(jié)果并將結(jié)果進(jìn)行拼接，形成最終的繪制結(jié)果。NVIDIA 公司提供的多個(gè)圖形處理單元（GPU）并行繪制驅(qū)動(dòng)SLI[3]和AMD 公司CrossFire[4]技術(shù)是目前兩種主流的并行繪制技術(shù)。

并行繪制系統(tǒng)中的主要問(wèn)題是負(fù)載平衡[5]，其主要是將繪制任務(wù)均勻地劃分給各繪制節(jié)點(diǎn)，以此減少用于同步各繪制節(jié)點(diǎn)的繪制結(jié)果花費(fèi)的額外開(kāi)銷，能夠保證在相同的時(shí)間內(nèi)，繪制系統(tǒng)可輸出更多的幀提高畫面質(zhì)量和資源利用率。如果負(fù)載失衡，并行繪制輸出動(dòng)畫的幀率會(huì)下降，造成卡幀等現(xiàn)象，用戶體驗(yàn)會(huì)嚴(yán)重下降。

對(duì)于復(fù)雜場(chǎng)景的并行繪制系統(tǒng)中，通常會(huì)包含很多模型和繪制算法，對(duì)任一幀的繪制，其繪制之前無(wú)法確定其繪制開(kāi)銷，所以要實(shí)現(xiàn)運(yùn)行時(shí)的負(fù)載平衡非常困難。已有的方法是通過(guò)增加負(fù)載失衡檢測(cè)，并在負(fù)載失衡后進(jìn)行補(bǔ)償操作來(lái)盡快恢復(fù)負(fù)載平衡。這種方法會(huì)帶來(lái)額外的通信開(kāi)銷，影響實(shí)時(shí)繪制系統(tǒng)的運(yùn)行效率。從本質(zhì)上講，這種“檢測(cè)+補(bǔ)償”的方法不能從根本上解決負(fù)載失衡的問(wèn)題。傳統(tǒng)的負(fù)載平衡算法中，主要是基于幀間相關(guān)性原理，雖然簡(jiǎn)單高效并可應(yīng)用于實(shí)時(shí)系統(tǒng)中，但是在交互的實(shí)時(shí)娛樂(lè)系統(tǒng)中，會(huì)造成負(fù)載的分布發(fā)生劇烈的變化，此時(shí)幀間相關(guān)性被打破，導(dǎo)致上述算法失敗。

本文提出一個(gè)基于機(jī)器學(xué)習(xí)的四分屏繪制系統(tǒng)負(fù)載平衡算法?；舅枷胧菍⒗L制任務(wù)在屏幕空間劃分為四個(gè)可獨(dú)立完成且負(fù)載量相當(dāng)?shù)淖尤蝿?wù)來(lái)實(shí)現(xiàn)負(fù)載平衡。關(guān)鍵在于建立一個(gè)機(jī)器學(xué)習(xí)模型，對(duì)繪制幀在特定的子屏幕下的負(fù)載進(jìn)行準(zhǔn)確且高效的預(yù)測(cè)。本文將負(fù)載預(yù)測(cè)問(wèn)題抽象為機(jī)器學(xué)習(xí)中的回歸問(wèn)題，同時(shí)考慮到復(fù)雜場(chǎng)景中的繪制參數(shù)較多所帶來(lái)的一系列問(wèn)題，選擇XGBoost 算法作為學(xué)習(xí)和預(yù)測(cè)負(fù)載的機(jī)器學(xué)習(xí)模型。

1 相關(guān)工作

在并行繪制系統(tǒng)中，根據(jù)負(fù)載的分配方式在運(yùn)行時(shí)是否改變，可將負(fù)載平衡策略分為靜態(tài)和動(dòng)態(tài)兩類。

靜態(tài)負(fù)載平衡算法，通過(guò)某種固定的方式對(duì)負(fù)載進(jìn)行劃分，并且在程序運(yùn)行過(guò)程中保持該劃分策略不變。例如，Liu[6]等提出的靜態(tài)負(fù)載平衡算法，該方法通過(guò)將繪制體元?jiǎng)澐譃楹芏嗉?xì)小的3D 體元塊，并且將所有體元塊按照一種固定的方式劃分給各繪制節(jié)點(diǎn)，來(lái)實(shí)現(xiàn)負(fù)載平衡。這種方法雖然簡(jiǎn)單且容易實(shí)現(xiàn)，但適應(yīng)性差。現(xiàn)在已經(jīng)基本不被使用。

動(dòng)態(tài)負(fù)載平衡算法在運(yùn)行時(shí)根據(jù)不同負(fù)載分布調(diào)整負(fù)載的劃分方式，來(lái)達(dá)到負(fù)載平衡，其良好的適應(yīng)性使其得到迅速發(fā)展并被廣泛應(yīng)用。例如，Erol[7]等提出并應(yīng)用于Equalizer[8]的CSLB 算法，是一種基于workstealing 調(diào)度策略的算法。在該算法中，并行繪制節(jié)點(diǎn)共享繪制圖形資源，當(dāng)某繪制節(jié)點(diǎn)完成自己的繪制任務(wù)以后，在任務(wù)量較多的繪制節(jié)點(diǎn)中“steal”若干任務(wù)，以此平衡各節(jié)點(diǎn)間的負(fù)載，實(shí)現(xiàn)負(fù)載平衡。這種方法會(huì)帶來(lái)額外的數(shù)據(jù)網(wǎng)絡(luò)傳輸開(kāi)銷，所以不適用于實(shí)時(shí)并行繪制系統(tǒng)中。Yin[9]等提出了基于LDM（Load Distribution Map）的動(dòng)態(tài)負(fù)載平衡算法，利用幀間相關(guān)性的思想，將生成的負(fù)載分布圖視作下一幀的負(fù)載分布，從而進(jìn)行負(fù)載劃分。上述提到的動(dòng)態(tài)負(fù)載平衡方法都是基于幀間相關(guān)性的思想，雖然簡(jiǎn)單高效，但是不適用于頻繁交互的實(shí)時(shí)系統(tǒng)中。

機(jī)器學(xué)習(xí)近年來(lái)被廣泛應(yīng)用于計(jì)算機(jī)圖形圖像中，主要解決復(fù)雜的計(jì)算過(guò)程以換取效率上的提升。文獻(xiàn)[8]使用機(jī)器學(xué)習(xí)中的線性回歸方法進(jìn)行了人臉識(shí)別，文獻(xiàn)[10,11]運(yùn)用梯度提升決策樹(shù)算法對(duì)生態(tài)問(wèn)題進(jìn)行了分析和預(yù)測(cè)。不僅如此，文獻(xiàn)[12]中支持向量機(jī)的表現(xiàn)也十分出色，在交通運(yùn)輸時(shí)間的預(yù)測(cè)更是達(dá)到了99.4%的預(yù)測(cè)精準(zhǔn)度。

近年來(lái)，有學(xué)者將XGBoost 應(yīng)用到計(jì)算機(jī)圖形圖像領(lǐng)域。例如，Ren[13]等將XGBoost 應(yīng)用到圖像分類上，可對(duì)圖像特征進(jìn)行識(shí)別。

2 繪制系統(tǒng)的負(fù)載平衡算法

2.1 傳統(tǒng)四分屏負(fù)載平衡算法

（1）靜態(tài)均分負(fù)載平衡算法

靜態(tài)的負(fù)載平衡算法中繪制任務(wù)以一種固定的方式進(jìn)行劃分，并且在程序運(yùn)行過(guò)程中保持該劃分策略不變?；舅枷胧歉鶕?jù)繪制節(jié)點(diǎn)的數(shù)量將負(fù)載進(jìn)行劃分，保證各個(gè)節(jié)點(diǎn)負(fù)載工作量盡可能接近。特點(diǎn)是簡(jiǎn)單但適應(yīng)性差并且很少被實(shí)際系統(tǒng)所采用。

（2）基于幀間相關(guān)性的動(dòng)態(tài)負(fù)載平衡算法

常見(jiàn)的一種動(dòng)態(tài)負(fù)載平衡算法主要是利用幀間相關(guān)性這一原理，評(píng)估節(jié)點(diǎn)負(fù)載大小主要是根據(jù)前一幀的繪制時(shí)間以及繪制節(jié)點(diǎn)參數(shù)。一種改進(jìn)的基于幀間相關(guān)性原理的負(fù)載平衡算法根據(jù)前一幀的平均繪制時(shí)間和當(dāng)前幀的繪制時(shí)間提出的一個(gè)時(shí)間預(yù)測(cè)模型[14]，由方程（1）所示：

其中，ti+1表示第i+1 幀的預(yù)測(cè)繪制時(shí)間，ti表示第i幀的繪制時(shí)間，Average（x,i）表示第i 幀前已繪制的前x幀的平均繪制時(shí)間，Average（x,i+1）表示第i+1 幀前已繪制的前x 幀的平均繪制時(shí)間。方程（1）的展開(kāi)式為：

2.2 基于XGBoost的四分屏負(fù)載平衡算法

Boosting 思想是運(yùn)用梯度提升的方法進(jìn)行每一輪的迭代最終組建出強(qiáng)學(xué)習(xí)器。因此，此方法導(dǎo)致了算法的運(yùn)行對(duì)運(yùn)行時(shí)間的開(kāi)銷較大，需要生成一定規(guī)模的樹(shù)后才能達(dá)到具有實(shí)用性的準(zhǔn)確率。尤其是數(shù)據(jù)集大且復(fù)雜時(shí)，運(yùn)行過(guò)多的迭代運(yùn)算使得當(dāng)前的算力是算法應(yīng)用的最大瓶頸。針對(duì)這一問(wèn)題，華盛頓大學(xué)的陳天奇博士開(kāi)發(fā)出了XGBoost（eXtreme Gradient Boosting），它是Gradient Boosting Machine 的一個(gè)實(shí)現(xiàn)，并在原有的基礎(chǔ)上加以改進(jìn)，從而極大地提升了模型訓(xùn)練速度和預(yù)測(cè)精度?？梢哉f(shuō)，XGBoost 是Gradient Boosting 的高效實(shí)現(xiàn)。

其中，yi表示第i 個(gè)樣本的標(biāo)簽真實(shí)值，i表示算法預(yù)測(cè)值。l(i-yi)表示第i 個(gè)樣本的預(yù)測(cè)誤差。表示k 個(gè)樹(shù)的復(fù)雜度函數(shù)，復(fù)雜度越低，泛化能力越強(qiáng)。其表達(dá)式為：

T 表示葉子節(jié)點(diǎn)的個(gè)數(shù)，w 表示節(jié)點(diǎn)的數(shù)值。γ 作為葉子節(jié)點(diǎn)的系數(shù)使XGBoost 在優(yōu)化目標(biāo)函數(shù)的同時(shí)相當(dāng)于做了預(yù)剪枝。λ 作為w 平方模的系數(shù)也是要起到防止過(guò)擬合的作用。

3 數(shù)據(jù)集

本文數(shù)據(jù)集采集自四分屏并行繪制系統(tǒng)中，其選用的繪制算法為基于LLL（Light Linked Lists）[15]的靜態(tài)場(chǎng)景算法Deferred Shading，場(chǎng)景圖如圖1 所示。

圖1 Deferred Shading算法場(chǎng)景圖

圖2 繪制節(jié)點(diǎn)切分方式

為了模擬真實(shí)的應(yīng)用場(chǎng)景，本文通過(guò)隨機(jī)跳轉(zhuǎn)光源的方式模擬真實(shí)的用戶交互行為，使得繪制幀突變更加強(qiáng)烈。繪制系統(tǒng)中采集的繪制參數(shù)及其對(duì)應(yīng)的繪制時(shí)間構(gòu)成數(shù)據(jù)集，訓(xùn)練集有2,422,298 幀，測(cè)試集有286,093 幀。每幀圖像由4 個(gè)繪制節(jié)點(diǎn)并行繪制后拼接而成，屏幕切分方式如圖2 所示。每一個(gè)繪制節(jié)點(diǎn)均擁有獨(dú)立的16 個(gè)繪制參數(shù)，繪制參數(shù)含義如表1所示。

4 實(shí)驗(yàn)

本文實(shí)驗(yàn)平臺(tái)為Intel Xeon CPU E3-1231 V3@3.4GHz，32GB DDR3 內(nèi)存以及NVIDIA GeForce GTX 1080 GPU。算法基于scikit-learn 機(jī)器學(xué)習(xí)庫(kù)。算法預(yù)測(cè)均方誤差對(duì)比如表2 所示。

表1 繪制參數(shù)定義

表2 算法均方誤差對(duì)比

從表2 可以看出，在繪制幀突變較為劇烈時(shí)，基于幀間相關(guān)性原理的動(dòng)態(tài)負(fù)載平衡算法無(wú)法準(zhǔn)確預(yù)測(cè)繪制時(shí)間，相比于XGBoost 算法有較大誤差。使用XGBoost 算法根據(jù)繪制參數(shù)進(jìn)行的繪制時(shí)間預(yù)測(cè)較為準(zhǔn)確。算法的測(cè)試集對(duì)比曲線如圖3 所示。

圖3 算法測(cè)試集對(duì)比曲線

XGBoost 算法相比于基于幀間相關(guān)性原理的動(dòng)態(tài)負(fù)載平衡算法的優(yōu)勢(shì)在于能夠根據(jù)當(dāng)前幀的繪制參數(shù)預(yù)測(cè)下一幀的負(fù)載大小，以用于判斷負(fù)載是否失衡。實(shí)驗(yàn)結(jié)果證實(shí)了XGBoost 具有更高的預(yù)測(cè)精確度。機(jī)器學(xué)習(xí)算法預(yù)測(cè)性能優(yōu)勢(shì)相比于傳統(tǒng)算法依然具有很好的工程應(yīng)用價(jià)值。

5 結(jié)語(yǔ)

本文針對(duì)基于交互的實(shí)時(shí)應(yīng)用，提出了基于XGBoost 的四分屏并行繪制系統(tǒng)的負(fù)載平衡算法，主要是學(xué)習(xí)繪制幀的參數(shù)與負(fù)載之間的非線性對(duì)應(yīng)關(guān)系，從而基于學(xué)習(xí)模型對(duì)負(fù)載的預(yù)測(cè)對(duì)繪制任務(wù)進(jìn)行比較平衡的分配，最終實(shí)現(xiàn)負(fù)載平衡。繪制時(shí)間的預(yù)測(cè)準(zhǔn)確性直接影響負(fù)載是否平衡。本文提出一種基于XGBoost 的機(jī)器學(xué)習(xí)模型，針對(duì)四分屏并行繪制系統(tǒng)的繪制參數(shù)進(jìn)行了繪制時(shí)間預(yù)測(cè)。與傳統(tǒng)的基于幀間相關(guān)性原理的動(dòng)態(tài)負(fù)載平衡算法的繪制時(shí)間進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)表明基于XGBoost 算法的預(yù)測(cè)性能較好。綜上所述，基于XGBoost 的機(jī)器學(xué)習(xí)算法能夠幫助并行繪制系統(tǒng)進(jìn)行負(fù)載調(diào)節(jié)，以獲得較優(yōu)的繪制性能。