基于回歸森林的并行繪制系統(tǒng)的負(fù)載平衡策略

羅小濤，段思羽

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065；2.四川大學(xué)視覺(jué)合成圖形圖像技術(shù)國(guó)家重點(diǎn)學(xué)科實(shí)驗(yàn)室，成都610065）

0 引言

并行繪制[7]是基于實(shí)時(shí)交互的娛樂(lè)系統(tǒng)，尤其是要求輸出高質(zhì)量連續(xù)并穩(wěn)定動(dòng)畫的應(yīng)用中常用的解決方案。負(fù)載平衡是并行繪制系統(tǒng)中研究的重要問(wèn)題之一。負(fù)載失衡時(shí)，并行繪制系統(tǒng)的輸出幀率突然下降，從而造成動(dòng)畫不連續(xù)、卡幀等現(xiàn)象，對(duì)用戶體驗(yàn)造成極大的負(fù)面影響。而對(duì)于高質(zhì)量實(shí)時(shí)交互娛樂(lè)系統(tǒng)，此類現(xiàn)象應(yīng)該嚴(yán)格避免。針對(duì)并行繪制系統(tǒng)的負(fù)載平衡問(wèn)題，現(xiàn)有的解決方案是增加負(fù)載失衡檢測(cè)，并在負(fù)載失衡后進(jìn)行補(bǔ)償以盡快恢復(fù)負(fù)載平衡。例如，Erol[2]等提出并應(yīng)用于Equalizer的CSLB（Cross-Segment Load Balancing）策略，屬于一種 Work-Stealing策略；Labroni?ci[6]等針對(duì)不規(guī)則物體的光線跟蹤提出的基于屏幕劃分的動(dòng)態(tài)負(fù)載平衡算法;Goswami[3]等針對(duì)高顯示分辨率的交互式應(yīng)用提出了基于多路KD-Tree的負(fù)載平衡策略等。本質(zhì)上來(lái)講，上述“檢測(cè)+補(bǔ)償”的方法僅能降低負(fù)載失衡對(duì)并行繪制系統(tǒng)的影響，并不能從根本上消除負(fù)載失衡。負(fù)載失衡，其根本原因是各并行繪制節(jié)點(diǎn)之間的繪制任務(wù)量不平衡，如果提前知道特定幀的繪制開銷，并制定任務(wù)平衡劃分的方式，是否能從根本上解決負(fù)載平衡問(wèn)題？

本文基于“繪制程序的特定幀在繪制程序整個(gè)生命周期會(huì)被多次繪制”這一事實(shí)，以及結(jié)合機(jī)器學(xué)習(xí)模型能夠?qū)W習(xí)過(guò)往知識(shí)并進(jìn)行預(yù)測(cè)的功能，為使并行繪制系統(tǒng)輸出連續(xù)且穩(wěn)定的動(dòng)畫，提高繪制輸出幀率，提高資源利用率，提出并實(shí)現(xiàn)了基于回歸森林的并行繪制系統(tǒng)地負(fù)載平衡調(diào)度策略。實(shí)驗(yàn)證明，本文方法能較好的做到并行繪制任務(wù)的平衡調(diào)度，與傳統(tǒng)方法相比，提升了并行繪制系統(tǒng)的性能和效率。

1 本文算法描述

1.1 回歸森林算法概述

回歸森林是由Leo Breiman[1]于2001年提出的組合回歸器，由多棵回歸樹組成。該方法引入隨機(jī)機(jī)制，使模型對(duì)噪聲數(shù)據(jù)有很好的容忍度且不容易出現(xiàn)過(guò)擬合[4]。其隨機(jī)性主要體現(xiàn)在兩個(gè)地方：

（1）每一棵樹在進(jìn)行訓(xùn)練時(shí)，從原始訓(xùn)練集合中進(jìn)行隨機(jī)有放回的采樣，形成和原始訓(xùn)練集合大小相同的訓(xùn)練集（Bootstrap數(shù)據(jù)集）

（2）在節(jié)點(diǎn)進(jìn)行劃分的過(guò)程中，隨機(jī)的從所有的特征中選擇特征子集，并從中計(jì)算得到最好的劃分軸以及劃分位置，對(duì)節(jié)點(diǎn)進(jìn)行分裂。

圖1所示為回歸森林結(jié)構(gòu)圖，在預(yù)測(cè)過(guò)程中，輸入預(yù)測(cè)實(shí)例，每一棵樹進(jìn)行二分搜索并映射到葉子節(jié)點(diǎn)，得到該棵樹的預(yù)測(cè)值，而回歸森林的預(yù)測(cè)值為所有樹的預(yù)測(cè)值的平均值。

圖1 回歸森林結(jié)構(gòu)圖

1.2 并行繪制系統(tǒng)的負(fù)載平衡調(diào)度策略

在并行繪制系統(tǒng)中，負(fù)載失衡的根本原因是由于繪制任務(wù)的分配不均勻造成。如圖2為并行繪制系統(tǒng)的框架圖，由控制節(jié)點(diǎn)和繪制節(jié)點(diǎn)組成，各節(jié)點(diǎn)間通過(guò)網(wǎng)絡(luò)連接。進(jìn)行并行繪制的流程如下：

圖2 集群并行繪制系統(tǒng)框架

（1）控制節(jié)點(diǎn)對(duì)繪制任務(wù)進(jìn)行劃分，并通過(guò)網(wǎng)絡(luò)連接將子任務(wù)分發(fā)給各并行繪制節(jié)點(diǎn)；

（2）各并行繪制節(jié)點(diǎn)分別對(duì)繪制任務(wù)進(jìn)行繪制，并將繪制完成的結(jié)果通過(guò)網(wǎng)絡(luò)傳回給控制節(jié)點(diǎn)；

（3）控制節(jié)點(diǎn)等待所有的繪制任務(wù)完成并接收到繪制結(jié)果，進(jìn)行結(jié)果的拼接，形成并行繪制的最終結(jié)果，即圖片，并顯示到屏幕上。

上述流程中，控制節(jié)點(diǎn)將任務(wù)進(jìn)行劃分并同時(shí)發(fā)送給各繪制節(jié)點(diǎn)，負(fù)載失衡時(shí)，各節(jié)點(diǎn)由于繪制任務(wù)量的不同，導(dǎo)致將繪制結(jié)果傳回給控制節(jié)點(diǎn)的時(shí)間不同，造成控制節(jié)點(diǎn)額外的等待時(shí)間，使得并行繪制系統(tǒng)的效率下降。對(duì)任何一個(gè)繪制程序，在進(jìn)行繪制的過(guò)程中，不同幀之間的參數(shù)可能發(fā)生改變，令各幀之間可能發(fā)生改變的參數(shù)為該幀的特征 X={X1，X2，X，…，Xp}。而對(duì)任意幀，若X保持不變，則繪制該幀的計(jì)算量必然不變，因此若忽略計(jì)算機(jī)系統(tǒng)本身的不穩(wěn)定因素，繪制完成該幀的時(shí)間為某固定值。然后對(duì)任意固定值進(jìn)行等分，必然存在解Y，即對(duì)任意特定幀X，必然存在某種進(jìn)行任務(wù)平衡劃分的方式Y(jié)，即等式（1）成立。

本文基于“特定幀在繪制程序的生命周期中會(huì)被多次繪制”這一事實(shí)，通過(guò)離線模擬采集數(shù)據(jù)，使用回歸森林進(jìn)行離線學(xué)習(xí)，并保存學(xué)習(xí)得到的模型以實(shí)時(shí)對(duì)負(fù)載的劃分進(jìn)行預(yù)測(cè)，使用預(yù)測(cè)結(jié)果進(jìn)行任務(wù)調(diào)度以達(dá)到負(fù)載平衡?；诨貧w森林的負(fù)載調(diào)度框架如圖3所示。

圖3 本文算法框架

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

本文基于回歸森林的負(fù)載平衡調(diào)度算法，選用的繪制算法為靜態(tài)場(chǎng)景下基于LLL（Light Linked Lists）[8]的Deferred Shading算法，如圖4。為簡(jiǎn)化回歸森林模型，使用兩個(gè)繪制節(jié)點(diǎn)進(jìn)行并行繪制模擬實(shí)驗(yàn)，此時(shí)任務(wù)的劃分方式Y(jié)為平行于計(jì)算機(jī)屏幕的豎直的劃分軸，如圖5。具體實(shí)驗(yàn)細(xì)節(jié)如下。

圖4 基于LLL的Deferred Shading算法場(chǎng)景圖

圖5 任務(wù)劃分方式

2.1 數(shù)據(jù)采集及模型訓(xùn)練

離線模擬采集的數(shù)據(jù)記為集合D={X,Y}，可分為如下兩個(gè)步驟：

（1）確定各幀的特征X。本實(shí)驗(yàn)中，選用的繪制算法為靜態(tài)場(chǎng)景下基于 LLL（Light Linked Lists）[8]的 De?ferred Shading算法。如圖4所示，該算法中，各幀之間的變化因素有：①相機(jī)的擺放；②場(chǎng)景中各光源的位置。上述變化因素即定義為該幀的特征X。

（2）確定各幀的負(fù)載平衡劃分方式Y(jié)。負(fù)載是否平衡可體現(xiàn)在各節(jié)點(diǎn)完成繪制任務(wù)所花費(fèi)時(shí)間是否相當(dāng)，步驟如下：

①固定X不變，等分任務(wù)；

②為消除計(jì)算機(jī)系統(tǒng)本身不穩(wěn)定因素對(duì)繪制時(shí)間的影響，各繪制節(jié)點(diǎn)對(duì)特定幀X重復(fù)進(jìn)行多次繪制，并保存各自多次繪制的時(shí)間；

③從④中繪制時(shí)間集合選擇一個(gè)值作為完成該任務(wù)的期望值。這里，由于中值50%的潰點(diǎn)[5]等優(yōu)勢(shì)，選擇中值作為期望的繪制時(shí)間。隨機(jī)選擇4幀，根據(jù)其繪制時(shí)間的分布選擇期望時(shí)間，如圖6所示，該圖也證明中值更加靠近期望時(shí)間；

④判斷各節(jié)點(diǎn)繪制時(shí)間是否相當(dāng)，首先計(jì)算平均繪制時(shí)間，即式（2）。

若滿足，轉(zhuǎn)⑤。否則借助幀間相關(guān)性的思想進(jìn)行調(diào)整，假定場(chǎng)景負(fù)載度在左右空間中均勻分布，以兩個(gè)繪制節(jié)點(diǎn)舉例，首先計(jì)算左右屏幕的平均寬度所需繪制時(shí)間：

判斷左邊屏幕的繪制時(shí)間是否達(dá)到平均時(shí)間，若滿足，則劃分軸向左移動(dòng)，否則劃分軸向右移動(dòng)

⑤記錄當(dāng)前X，Y為一條數(shù)據(jù)實(shí)例。更新X，轉(zhuǎn)①。

完成上述步驟可得到數(shù)據(jù)集D，經(jīng)過(guò)簡(jiǎn)單的數(shù)據(jù)處理，輸入回歸森林算法進(jìn)行訓(xùn)練，并保存得到的模型。

2.2 性能測(cè)試

上述得到的模型對(duì)兩個(gè)繪制節(jié)點(diǎn)進(jìn)行分屏并行繪制的任務(wù)劃分有一定預(yù)測(cè)能力。為驗(yàn)證模型的性能，即本文方法的有效性，選擇靜態(tài)均分的任務(wù)調(diào)度以及動(dòng)態(tài)的基于幀間相關(guān)性的任務(wù)調(diào)度方法進(jìn)行對(duì)比。分別使用上述方法和本文方法，繪制完成1000幀，對(duì)比實(shí)驗(yàn)結(jié)果如表1所示。

隨機(jī)選擇相同的100幀，對(duì)比使用不同的方法進(jìn)行任務(wù)調(diào)度，各并行繪制節(jié)點(diǎn)之間最大負(fù)載與最小負(fù)載之間的關(guān)系，如圖7所示。

圖6 各幀繪制時(shí)間的分布

表1 實(shí)驗(yàn)結(jié)果對(duì)比

圖7 使用不同任務(wù)調(diào)度方法最大與最小負(fù)載之間的偏差

2.3 結(jié)果分析

從表1可以看出，使用本文方法的任務(wù)調(diào)度策略可使得并行繪制系統(tǒng)在相同的時(shí)間內(nèi)輸出更多的幀。從圖7可以看出，本文方法調(diào)度分配的子任務(wù)之間負(fù)載偏差相差較均分、幀間相關(guān)性要小，反映了各并行繪制節(jié)點(diǎn)之間的負(fù)載更加平衡。而且，由于當(dāng)前基于實(shí)時(shí)交互的娛樂(lè)系統(tǒng)復(fù)雜度分布不均且常常由于用戶交互觸發(fā)的特效等原因，繪制的幀率必然存在較多突變的情況，而本文方法較前兩種傳統(tǒng)方法更能適應(yīng)此類應(yīng)用，對(duì)保證繪制輸出動(dòng)畫的穩(wěn)定性及用戶體驗(yàn)有保障。

3 結(jié)語(yǔ)

本文提出并實(shí)現(xiàn)了一種基于回歸森林的并行繪制系統(tǒng)的負(fù)載平衡調(diào)度策略，并使用特定的繪制算法進(jìn)行仿真模擬與評(píng)估。實(shí)驗(yàn)結(jié)果顯示，盡管該方法每幀均會(huì)花費(fèi)額外的時(shí)間用于預(yù)測(cè)，但是該方法較傳統(tǒng)的方法對(duì)并行繪制系統(tǒng)的輸出幀率以及資源利用率均有提升，且對(duì)任意繪制算法適用?；诖笠?guī)模實(shí)時(shí)并行繪制系統(tǒng)的特點(diǎn)，抽象化任務(wù)平衡劃分的方式使得回歸森林具有對(duì)該抽象化的劃分方式具有預(yù)測(cè)的能力，將是下一步的研究方向。

參考文獻(xiàn)：

[1]Breiman L.Random Forests[J].Machine Learning,2001,45（1）:5-32.

[2]Erol F,Eilemann S,Pajarola R.Cross-Segment Load Balancing in Parallel Rendering[C].Eurographics Conference on Parallel Graphics and Visualization.Eurographics Association,2011:41-50.

[3]Goswami P,Erol F,MukhiR,et al.An Efficient Multi-Resolution Framework for High Quality Interactive Rendering of Massive Point Clouds Using Multi-Way KD-Trees[J].Visual Computer,2013,29（1）:69-83.

[4]Hawkins DM.The Problem of Overfitting[J].Cheminform,2004,35（19）:1.

[5]Hellerstein JM.Quantitative Data Cleaning for Large Databases[J]，2008.

[6]Labronici B B,Bentest C,Drummond LM A,et al.Dynamic Screen Division for Load Balancing the Raycasting of Irregular Data[C].IEEE International Conference on CLUSTER Computing and Workshops.IEEE,2009:1-10.

[7]Molnar S,CoxM,Ellsworth D,etal.A Sorting Classification of Parallel Rendering[J].IEEE Computer Graphics&Applications,1994,14（4）:23-32.

[8]Yang JC,Hensley J,Thibieroz N.Real-Time Concurrent Linked List Construction on the GPU[J].Computer Graphics Forum,2010,29（4）:1297-1304.