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

賈文娟

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

靜態(tài)的負(fù)載平衡算法中繪制任務(wù)以一種固定的方式進行劃分，并且在程序運行過程中保持該劃分策略不變。基本思想是根據(jù)繪制節(jié)點的數(shù)量將負(fù)載進行劃分，保證各個節(jié)點負(fù)載工作量盡可能接近。特點是簡單但適應(yīng)性差并且很少被實際系統(tǒng)所采用。

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

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

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

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

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

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

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

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

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

圖1 Deferred Shading算法場景圖

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

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

4 實驗

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

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

表2 算法均方誤差對比

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

圖3 算法測試集對比曲線

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

5 結(jié)語

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