基于XGBoost 的四分屏繪制系統負載平衡算法

賈文娟

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

0 引言

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

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

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

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

本文提出一個基于機器學習的四分屏繪制系統負載平衡算法。基本思想是將繪制任務在屏幕空間劃分為四個可獨立完成且負載量相當的子任務來實現負載平衡。關鍵在于建立一個機器學習模型，對繪制幀在特定的子屏幕下的負載進行準確且高效的預測。本文將負載預測問題抽象為機器學習中的回歸問題，同時考慮到復雜場景中的繪制參數較多所帶來的一系列問題，選擇XGBoost 算法作為學習和預測負載的機器學習模型。

1 相關工作

在并行繪制系統中，根據負載的分配方式在運行時是否改變，可將負載平衡策略分為靜態和動態兩類。

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

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

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

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

2 繪制系統的負載平衡算法

2.1 傳統四分屏負載平衡算法

（1）靜態均分負載平衡算法

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

（2）基于幀間相關性的動態負載平衡算法

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

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

2.2 基于XGBoost的四分屏負載平衡算法

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

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

T 表示葉子節點的個數，w 表示節點的數值。γ 作為葉子節點的系數使XGBoost 在優化目標函數的同時相當于做了預剪枝。λ 作為w 平方模的系數也是要起到防止過擬合的作用。

3 數據集

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

圖1 Deferred Shading算法場景圖

圖2 繪制節點切分方式

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

4 實驗

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

表1 繪制參數定義

表2 算法均方誤差對比

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

圖3 算法測試集對比曲線

XGBoost 算法相比于基于幀間相關性原理的動態負載平衡算法的優勢在于能夠根據當前幀的繪制參數預測下一幀的負載大小，以用于判斷負載是否失衡。實驗結果證實了XGBoost 具有更高的預測精確度。機器學習算法預測性能優勢相比于傳統算法依然具有很好的工程應用價值。

5 結語

本文針對基于交互的實時應用，提出了基于XGBoost 的四分屏并行繪制系統的負載平衡算法，主要是學習繪制幀的參數與負載之間的非線性對應關系，從而基于學習模型對負載的預測對繪制任務進行比較平衡的分配，最終實現負載平衡。繪制時間的預測準確性直接影響負載是否平衡。本文提出一種基于XGBoost 的機器學習模型，針對四分屏并行繪制系統的繪制參數進行了繪制時間預測。與傳統的基于幀間相關性原理的動態負載平衡算法的繪制時間進行了對比實驗，實驗表明基于XGBoost 算法的預測性能較好。綜上所述，基于XGBoost 的機器學習算法能夠幫助并行繪制系統進行負載調節，以獲得較優的繪制性能。