劉云彪，陳純毅，胡小娟，邢琦瑋，楊華民

基于貪心策略的多結點并行光線跟蹤負載均衡算法

劉云彪，陳純毅，胡小娟，邢琦瑋，楊華民

(長春理工大學計算機科學技術學院，吉林 長春 130022)

為了提高利用光線跟蹤集群繪制生成高分辨率復雜場景畫面的并行度，提出基于貪心策略的多結點并行光線跟蹤負載均衡算法。首先根據GPU的并行特性將屏幕空間劃分成若干正方形圖像塊，并基于移動物體球形包圍體在屏幕空間的投影構建二值繪制時間影響度圖。然后依據時空相關性利用上一幀圖像塊耗時和二值繪制時間影響度圖建立渲染任務隊列，通過兩步負載均衡實現多渲染結點任務的動態(tài)分配。最后進行了實驗驗證和分析，結果表明該方法具有良好的負載均衡效果，在5個渲染結點的繪制效率最高能提升4.96倍。

光線跟蹤；高分辨率圖像；負載均衡；多結點繪制；貪心策略

光線跟蹤技術[1]是計算機圖形學中一個重要研究分支，目前在影視制作、虛擬現實、醫(yī)學研究、輔助設計等領域發(fā)揮重要作用[2-3]。光線跟蹤能夠呈現其他渲染方法難以實現的反射、折射和陰影等效果，并且光線跟蹤算法容易實現。然而，光線跟蹤為生成更加真實的圖像需要從視點發(fā)射千萬數量級的光線，并根據場景、光源和材質等信息決定是否繼續(xù)跟蹤光線，最終得到渲染圖像[4]。因此，光線跟蹤的耗時龐大，難以應用于復雜場景的實時繪制。

針對光線跟蹤繪制速率的提升，現存的研究大致有2個方向：①加速結構的構建；②并行執(zhí)行?？臻g加速結構能夠減少光線與幾何物體的基礎單元(三角形、球體等)在求交過程花費的時間。通過如層次包圍盒(bounding volume hierarchy，BVH)[5]、八叉樹[6]和KD樹[7]等加速結構降低了光線跟蹤算法對于硬件性能的依賴，且保證光線跟蹤渲染效果的同時減少部分繪制時間，實現簡單場景的實時繪制效果，但不能滿足復雜場景實時繪制速率的要求。由于光線追蹤發(fā)射的光線相互獨立，理論上能夠在并行處理器上同時計算出所有像素的顏色值。實際上GPU雖然具有強大的并行處理能力[8]，但仍不能實現高分辨率圖像所有像素的同時計算。在這種情況下，使用多GPU渲染是一種可行的提升渲染速度的解決方案[9-10]。

為實現光線跟蹤集群渲染復雜場景，本文提出一種基于貪心策略的多結點光線跟蹤負載均衡算法，首先構造二值繪制時間影響度圖，構造方法結合球形包圍體和空間投影算法；其次利用上一幀圖像塊的繪制時間和二值繪制時間影響度圖建立任務隊列；結合貪心策略進行第一步負載均衡，在不影響繪制效率的情況下，得到受移動物體影響的圖像塊繪制時間；最后將剩余任務再次利用貪心策略進行第二步負載均衡，提高復雜場景的繪制效率。

1 相關工作

現有的多結點并行光線跟蹤方法包括：圖像分解并行和場景幾何分解并行。圖像分解并行是每個渲染結點負責圖像的部分區(qū)域，而場景數據通常復制到每個渲染結點的內存中。場景幾何分解并行是每個渲染結點負責場景的部分數據，光線在渲染結點間傳播[11]。由于場景幾何分解并行方法存在數據一致性問題以及數據傳輸開銷大等缺點，本文采用圖像分解并行方式。多結點并行繪制中整個任務的繪制時間由耗時最長的結點決定，有負載均衡算法的渲染集群要優(yōu)于無負載均衡算法的渲染集群[12-13]，因此負載均衡算法是 一個重要的研究分支。

負載均衡[14-15]的研究有很多，張正昌等[16]提出基于warp線程優(yōu)化的動態(tài)調度策略，提高算法在BVH階段的效率，實現GPU并行優(yōu)化算法在光線跟蹤的應用，結合GPU的計算特性實現加速效果，卻未對多結點渲染方式進行研究。CHEN等[17]提出基于任務的動態(tài)負載均衡算法，利用隊列機制在多個GPU有效實現負載均衡效果，提升計算效率，但是通信頻繁。COSENZA等[18]利用連續(xù)計算階段之間的時間一致性，將網格式計算映射到處理器集群上。通過預測二叉樹劃分渲染任務到各個獨立的處理器，并且表明圖像塊的數量影響系統性能，但是僅給出繪制速率提升未對負載均衡效果進行分析。以及文獻[11]提出通過光柵化渲染方式得到像素擊中點的相關信息，估算出每個像素的耗時，最終生成預測耗時圖。然后利用KD-Tree將預測耗時圖分成多個耗時相近的渲染任務，分配到各個渲染結點進行光線跟蹤，最后采用工作竊取(work-stealing)實現負載均衡，該方法的負載均衡效果良好，但是需要設置的參數過多不利于算法的通用性。針對上述問題，本文在考慮GPU并行計算特性的同時，設計了新的負載均衡方法：一方面采取集中式負載均衡減少數據傳輸量；另一方面，通過兩階段結合貪心策略的任務分配，提高負載均衡效果。

2 算法原理與實現

2.1 算法思想概述

本文算法基于光線跟蹤框架，采用BVH加速結構，利用CPU作為控制結點實現負載均衡算法，GPU作為渲染結點執(zhí)行全局光照下場景渲染任務。負載均衡算法的核心內容可分2個部分：屏幕空間劃分和負載均衡。屏幕空間劃分，將屏幕空間劃分成若干正方形圖像塊；負載均衡，在一幀圖像塊繪制時間分配渲染任務，并提出二值繪制時間影響度圖解決快速移動物體產生的影響，通過2步負載均衡實現渲染任務的分配。算法工作流程如圖1所示。

2.2 屏幕空間劃分

屏幕空間劃分的方式對多結點并行繪制有著重要的影響，為加快繪制速率實現負載均衡效果，本文選取正方形作為屏幕空間劃分的單元。利用正方形劃分屏幕空間會存在剩余空間不足以劃分的情況，此時需要將剩余部分歸入鄰近的圖像塊。屏幕空間塊劃分過程如圖2所示。選擇正方形作為屏幕空間劃分的單元是由于正方形相對于其他相同面積圖形其對角線長度最短，圖像塊跨越多個幾何物體可能性最低。因此，圖像塊包含幾何物體的屬性盡可能一致，能減少并行光線跟蹤分支情況，降低繪制時間。

圖1 負載均衡工作流程圖

圖2 屏幕空間塊分塊示意

GPU在并行計算時，利用計算耗時與延遲(準備執(zhí)行下一條指令所需的時鐘周期數量)重疊，達到隱藏延遲的效果。所有的warp[18]調度器在延遲期間的每個時鐘周期都有指令要發(fā)出時，能夠最大化GPU的資源利用率。因此，GPU處理足夠多的并行線程能夠有效隱藏延遲，充分發(fā)揮GPU的并行計算性能以及最大化吞吐量。如圖3所示，并行線程指令運行流程。其中，表示GPU執(zhí)行warp最大的數量，H2D表示數據從主機到設備的傳輸周期，Kernel表示執(zhí)行時鐘周期，D2H表示數據從設備到主機的傳輸周期。

圖3 并行線程指令運行流程

2.3 二值繪制時間影響度圖

場景中視點或物體在一定速度范圍內移動，根據時空相關性同一圖像塊相鄰兩幀的繪制時間相近，但屏幕空間存在快速移動的物體時，同一圖像塊相鄰兩幀的繪制時間可能存在較大的差異。為有效實現負載均衡，提出二值繪制時間影響度圖。進行精細計算的時間成本過高增加負載均衡算法時間，利用簡單的二值圖(非0即1)描述移動物體對圖像塊繪制時間的影響。二值繪制時間影響度圖通過移動物體的球形包圍體在屏幕空間的投影判斷移動物體對下一幀圖像塊繪制時間的影響，其構造方式表述為

其中，C為圖像塊繪制時間產生影響的閾值；P為相交面積與圖像塊面積的比值；I為移動物體對該圖像塊的影響。如圖4所示，將球形包圍體投影到屏幕空間并且計算物體對圖像塊繪制時間的影響，其中數值1表示移動物體對圖像塊繪制時間產生了影響，而數值0則表示未產生影響。

影響繪制時間的圖像塊有2種，重新投影繪制時間產生影響的圖像塊和上一幀繪制時間受影響的圖像塊。如圖5所示，物體移動時二值繪制時間影響度圖的變化。

圖5 二值繪制時間影響度圖變化

2.4 負載均衡

負載均衡的主要目的在于實現各個渲染結點繪制時間的均衡，依據本文的屏幕空間劃分方法，繪制高分辨率的圖像時大多數圖像塊內執(zhí)行線程數量相同，但不同的圖像塊繪制幾何物體不同，繪制時間可能存在較大的差異。本文的負載均衡算法結合了貪心策略、消息隊列機制以及二值繪制時間影響度圖，通過分配到渲染結點不同數量的圖像塊，使渲染結點達到負載均衡的效果。本文將圖像塊分成繪制時間受到影響的圖像塊和未受到影響的圖像塊2類。首先控制結點創(chuàng)建渲染任務隊列0，根據二值繪制時間影響度圖將繪制時間產生影響的圖像塊順序存入隊列0，其次將剩余圖像塊根據上一幀的繪制時間(第一幀將面積作為上一幀繪制時間)按照降序存入隊列0，如圖6(a)所示，屏幕空間分成6個圖像塊，圖像塊的數字表示該圖像塊上一幀的繪制時間，*表示繪制時間產生影響的圖像塊。隨后將渲染任務隊列中的任務分配到渲染結點，由于繪制時間影響圖是描述移動物體是否對圖像塊繪制時間產生影響，無法判斷具體影響的程度，因此將繪制時間產生影響的圖像塊和部分繪制時間未受影響的圖像塊同時分配到渲染結點。繪制時間產生影響的圖像塊按數量平均分配，繪制時間未受影響的圖像塊根據貪心策略分配。利用貪心策略為渲染結點分配渲染任務隊列中的元素過程可用式(2)和式(3)表示

其中，為渲染結點的數量；為渲染耗時最小的渲染結點序號；t為結點執(zhí)行已分配任務所需的時間；為渲染任務隊列隊首圖像塊的繪制時間。即分配渲染任務隊列隊首的圖像塊到當前耗時最小的渲染結點。如圖6(b)所示執(zhí)行第1步負載均衡，計算各個渲染結點已分配未受影響圖像塊的耗時，渲染結點1和2耗時分別為0和28，耗時最少的渲染結點是1，此時控制結點分配0隊首圖像塊到1，然后渲染結點執(zhí)行控制結點分配的圖像塊并記錄其繪制時間，同時計算下一幀該圖像塊的繪制時間影響情況。當渲染結點處理完所有繪制時間受影響的圖像塊并且正在處理未受影響圖像塊時，控制結點根據返回的信息可以計算出渲染結點已分配任務的耗時，然后利用貪心策略分配剩余圖像塊到渲染結點，如圖6(c)所示，執(zhí)行第2步負載均衡，根據受影響圖像塊的繪制時間，計算出渲染結點1和2的耗時分別為30和35，然后按照負載均衡算法分配下一個圖像塊到耗時最小的渲染結點1，進行上述算法直到渲染任務隊列0為空，本文負載均衡算法的具體步驟為：

步驟1.構造渲染任務隊列0，設置繪制時間受影響圖像塊數量，閾值，設繪制時間受影響圖像塊次數為，繪制時間受影響圖像塊標志符。

步驟2.若>，圖像塊面積作為繪制時間，并且令=0。

步驟3. 根據圖像塊上一幀渲染耗時(第一幀將面積作為渲染耗時)按降序存入渲染任務隊列0，令=0。

步驟4.將隊列0前個圖像塊順序分配到渲染結點的同時利用貪心策略分配部分圖像塊到渲染結點。

步驟5.若=，執(zhí)行步驟6，否則執(zhí)行步驟7。

步驟6.根據渲染結點已分配任務的耗時，利用貪心策略分配剩余圖像塊到渲染結點。

步驟7. 接收渲染結點發(fā)送的信息，令=+1。若<=，令=1，更新結點已分配任務耗時，否則令=0。

步驟8.若下一幀該圖像塊繪制時間受影響，令=1，繪制時間用無窮大代替。

步驟9.若=1，則下一幀該圖像塊繪制時間受影響。

步驟10.若為最后一個圖像塊，算法結束，否則執(zhí)行步驟7。

圖6 負載均衡算法

2.5 數據傳輸

數據傳輸是光線跟蹤負載均衡算法的重要組成部分，影響負載均衡算法的執(zhí)行時間。為降低光線跟蹤負載均衡算法的耗時，本文采用多線程將數據傳輸時間隱藏在渲染任務執(zhí)行時間。如 圖7(a)所示，渲染結點以串行方式執(zhí)行渲染任務和數據傳輸的運行流程，整個過程的耗時等于全部指令耗時相加。如圖7(b)所示，采用多線程方式執(zhí)行渲染任務和數據傳輸，由于數據接收部分僅包括圖像塊的起始坐標、終止坐標和標志符(判斷是否更新渲染場景的相關數據)，數據接收時間可忽略不計，因此以串行方式進行數據接收和任務執(zhí)行。然后采用多線程方式將發(fā)送數據和任務執(zhí)行時間重疊，能夠有效降低負載均衡算法時間，提升繪制速率。多線程執(zhí)行渲染任務的具體步驟如下：

(1) 線程1。

步驟1.創(chuàng)建緩沖區(qū)Buffer1和Buffer2用于存儲渲染結果，創(chuàng)建線程2用于向控制結點發(fā)送渲染結果。

步驟2.接收渲染任務信息。

步驟3.當標志符為真，則更新渲染場景數據。

步驟4.執(zhí)行渲染任務，若執(zhí)行次數為奇數將渲染結果存入Buffer1，否則存入Buffer2。

步驟5.向線程2發(fā)送信號，執(zhí)行步驟2。

(2) 線程2。

步驟1.若接收到線程1的信號，則執(zhí)行步驟2。

步驟2. 若執(zhí)行次數為奇數，傳輸Buffer1的渲染結果，否則傳輸Buffer2的渲染結果。執(zhí)行步驟1。

圖7 任務運行流程

3 實驗結果與分析

3.1 實驗設備及參數設置

實驗環(huán)境由一個控制結點和多個渲染結點組成，控制結點的配置：Intel(R) Xeon(R) E3-1225 v3 @ 3.20 GHz CPU，4 GB內存和NVIDIA Quadro K600 GPU。渲染結點的配置：Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz，8 GB內存和NVIDIA Quadro P4000 GPU。使用NVIDIA CUDA SDK 10.1和NVIDIA OptiX SDK5.0.1作為開發(fā)工具。其中K600有172個CUDA核心，P4000有1 792個CUDA核心。圖像分辨率統一設置為4096×2160像素，光線最大遞歸深度設為5。實驗場景如圖8所示，其中場景1和2為靜態(tài)場景，場景3~6為動態(tài)場景。

圖8 實驗場景

3.2 負載均衡效果

本文算法的目的在于實現多渲染結點的負載均衡，為判斷負載均衡效果引入繪制時間歸一化標準差，計算方法為

表1為靜態(tài)場景在4個渲染結點時不同分塊情況下的平均歸一化標準差，其中在場景1進行2組實驗，分別是在光源數量為50和150的情況下進行不同分塊的實驗，光源位置在場景上方。場景2的實驗是在125個光源下進行，其中 25個光源在場景上方，100個光源在窗外。從 表1可以看出，場景1在150個光源下比50個光源的平均歸一化標準差大。單個像素繪制時間增加會導致圖像塊繪制時間差異變大，負載均衡效果降低。雖然場景2的繪制時間少，但是沒有50個光源下場景1的負載均衡效果好，因此決定負載均衡效果的主要因素是圖像塊繪制時間的差異。

表2是靜態(tài)場景在5個渲染結點時不同分塊下的平均歸一化標準差，可以看出圖像塊分辨率為480×480時，由于圖像塊之間繪制時間相差較大，并且總體圖像塊數量少，因此該分辨率比其他圖像塊分辨率的負載均衡效果差。隨著圖像塊分辨率的減小，圖像塊之間的繪制時間差異降低，并且可分配到單個渲染結點的圖像塊數量增加，所以平均歸一化標準差隨圖像塊數量增加而降低，能夠有效實現負載均衡效果。

對比表1和表2，若圖像塊分辨率較高，可分配到單個渲染結點圖像塊數量少，相同場景在相同分塊情況下5個渲染結點比4個渲染結點的平均歸一化標準差大。隨著圖像塊分辨率的降低，圖像塊的總體數量會增加，并且單個圖像塊繪制時間降低，不同數量結點的平均歸一化標準差越接近。因此圖像塊分辨率為384×384時，不同場景的平均歸一化標準差基本平穩(wěn)，圖像塊分辨率降低對負載均衡效果提升的收益降低。

表1 靜態(tài)場景在4個渲染結點時不同分塊情況下的平均歸一化標準差對比

表2 靜態(tài)場景在5個渲染結點時不同分塊情況下的平均歸一化標準差對比

表3以5個渲染結點繪制靜態(tài)場景，并且視點以每幀0.5°，1.0°和1.5°的速度旋轉時的平均歸一化標準差。當視點旋轉速度加快，圖像塊內物體變化的速度提升，因此圖像塊繪制時間的變化加劇，使用上一幀圖像塊繪制時間作為當前幀圖像塊繪制時間的偏差增加，所以隨著視點旋轉速度的增加，負載均衡的效果降低。從表3可以看出當視點以相同速度旋轉，圖像塊分辨率降低能夠提升負載均衡效果。對比表3中場景1和場景2，在相同圖像塊分辨率情況下視點以相同速度旋轉，場景1較場景2的平均歸一化標準差小，因此場景中存在反射現象對繪制時間的影響 更大。

表3 靜態(tài)場景在視點旋轉時不同分塊情況下的平均歸一化標準差對比

表4以5個渲染結點繪制動態(tài)場景，并且視點以每幀0.5°旋轉時不同分塊情況下的平均歸一化標準差。在相同圖像塊分辨率的情況下，場景3和場景4的平均歸一化標準差低于場景5和場景6，進一步證明場景中存在對移動物體的反射會對負載均衡效果產生影響。而場景6比場景5的平均歸一化標準差小是因為反射到移動物體區(qū)域所在圖像塊繪制時間和上一幀該圖像塊繪制時間更接近。場景3和場景4在圖像塊分辨率降低時負載均衡效果的提升比場景和場景6的提升更高，該情況的出現說明場景5和場景6會對移動物體反射。

表4 動態(tài)場景在視點旋轉時不同分塊情況下的平均歸一化標準差對比

3.3 傳輸時間

本文渲染圖像的分辨率為4096×2160，圖像共有33.75 M字節(jié)，傳輸一幀圖像需要大量的時間。因此采用多線程方式降低傳輸時間。圖像塊繪制時間大于其傳輸時間，因此利用多線程將傳輸耗時隱藏在渲染任務執(zhí)行時間內，總傳輸時間等于最后一個圖像塊的傳輸時間。多線程傳輸耗時如圖9所示，隨圖像塊數量增加數據傳輸耗時隱藏越多。能夠有效降低傳輸耗時在負載均衡算法耗時的比例，提升繪制效率。

圖9 渲染結果傳輸時間

3.4 圖像塊分辨率的選取

圖像塊數量的增加能夠提升負載均衡效果以及降低渲染結果傳輸時間，但GPU隱藏延遲時間降低，因此需要考慮圖像塊尺寸。為最大化提升渲染效率本文圖像塊尺寸利用式(5)確定，即

其中，為圖像寬度；為圖像高度；為圖像高度與圖像塊邊長的比值；為渲染結點的數量；為平均分配到渲染結點圖像塊的數量。實驗參數設置：=4096，=2160，=10。確定距離最近且大于×的值，然后通過得到圖像塊尺寸。本文在CUDA架構實現GPU并行計算，warp (由32個線程組成)是GPU執(zhí)行指令時的調度單位，若warp不足32個線程，則需要填充至32個線程。填充的線程占據一定資源但對任務沒有任何貢獻，因此保證圖像塊數量相同條件下，圖像塊邊長像素數是32的倍數，能夠減少warp線程填充情況，有利于資源的充分利用[19]。

3.5 算法對比與分析

本文與靜態(tài)和動態(tài)負載均衡算法[20]進行對比。共進行4組對比實驗，實驗參數見表5。由于對比實驗是在5個渲染結點進行，因此通過式(5)計算得到圖像塊分辨率為384×384。本文算法屬于圖像分解并行，而靜態(tài)負載均衡算法和文獻[20]算法也均屬于圖像分解并行，因此通過4組對比實驗能夠體現本文算法的性能。

表5 對比實驗參數

如圖10所示，3種負載均衡算法的對比實驗?？梢钥闯霰疚乃惴ㄔ陟o態(tài)場景和動態(tài)場景中都能有效實現負載均衡效果，并且本文算法比靜態(tài)負載均衡算法和文獻[20]的負載均衡算法的效果更好。本文算法的歸一化標準差也更加平穩(wěn)，不會出現大幅度的波動。

圖11為3種負載均衡算法渲染效率提升的對比。為減少實驗誤差，對比實驗采用50幀繪制圖像性能提升的平均值。可以看出本文算法在不同場景下的性能提升均較另外2種負載均衡算法的提升高，并且本文算法在動態(tài)場景的效率提升更明顯，能夠最大化利用計算資源。

圖10 歸一化標準差對比實驗

圖11 繪制效率提升

4 結束語

本文提出多結點并行光線跟蹤負載均衡算法。依據GPU的并行特性設計屏幕空間的劃分方法，采用正方形作為分塊單元，將屏幕空間劃分成若干正方形圖像塊。根據連續(xù)計算的時間相關性利用上一幀圖像塊的渲染耗時以及移動物體對圖像塊繪制時間影響構建渲染任務隊列，然后依據貪心策略將圖像塊隊列的渲染任務分配到渲染結點，由渲染結點執(zhí)行對應的渲染任務，實現多結點動態(tài)任務分配，并且在渲染結點采用多線程將數據傳輸時間和計算時間重疊，能夠隱藏傳輸時間，提升繪制效率。實驗結果表明本文算法具有良好的擴展性和通用性，在5個渲染結點情況下，靜態(tài)場景繪制效率能夠提升4.964 1倍，視線移動的靜態(tài)場景能夠提升4.921 9倍，視線移動的動態(tài)場景能夠提升4.835 2倍，有效實現負載均衡效果。

盡管本文算法能夠有效實現負載均衡效果，但依舊存在改進空間：①構造二值繪制時間影響圖的方法，本文采用球形包圍體投影判斷對圖像塊繪制時間的影響，在后續(xù)工作中將使用更精確且簡單的方法得到鏡面對移動物體反射的情況。②將算法進行擴展延伸，應用于路徑跟蹤中。

[1] WHITTED T. An improved illumination model for shaded display[J]. Communications of the ACM, 1980, 23(6): 343-349.

[2] 盧賀齊, 鮑鵬, 馮結青. 基于OpenCL的實時KD-Tree與動態(tài)場景光線跟蹤[J]. 計算機輔助設計與圖形學學報, 2013, 25(7): 963-973.

[3] 王妙一, 王斌, 雍俊海. GPU 上的水彩畫風格實時渲染及動畫繪制[J]. 圖學學報, 2012, 33(3): 73-80.

[4] 宋元杰, 王璐, 孟祥旭. 采用Intel集成眾核架構的并行光線追蹤加速方法[J]. 計算機輔助設計與圖形學學報, 2015, 27(12): 2313-2322.

[5] HU Y S, WANG W J, LI D, et al. Parallel BVH construction using locally density clustering[J]. IEEE Access, 2019, 7: 105827-105839.

[6] 張文勝, 解騫, 鐘瑾, 等. 基于八叉樹鄰域分析的光線跟蹤加速算法[J]. 圖學學報, 2015, 36(3): 339-344.

[7] ZHANG J, GUO H Q, HONG F, et al. Dynamic load balancing based on constrained k-d tree decomposition for parallel particle tracing[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1): 954-963.

[8] 吳恩華, 柳有權. 基于圖形處理器(GPU)的通用計算[J]. 計算機輔助設計與圖形學學報, 2004, 16(5): 601-612.

[9] CHEN M, HUANG H F. A Real-time parallel ray-tracing method based on GPU cluster[C]//2018 IEEE International Conference of Safety Produce Informatization (IICSPI). New York: IEEE Press, 2018: 327-330.

[10] 孫昭, 柳有權, 張彩榮, 等. 一種場景內容分布的交互式渲染系統[J]. 圖學學報, 2019, 40(1): 87-91.

[11] COSENZA B, DACHSBACHER C, ERRA U. GPU cost estimation for load balancing in parallel ray tracing[C]// Proceedings of the International Conference on Computer Graphics Theory and Applications. Heidelberg: Springer, 2013: 139-151.

[12] JIANG Y C. A survey of task allocation and load balancing in distributed systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(2): 585-599.

[13] 王海峰, 陳慶奎. 圖形處理器通用計算關鍵技術研究綜述[J]. 計算機學報, 2013, 36(4): 757-772.

[14] STEINER D, PAREDES E G, EILEMANN S, et al. Dynamic work packages in parallel rendering[C]// Proceedings of the 16th Eurographics Symposium on Parallel Graphics and Visualization. Goslar: Eurographics Association, 2016: 89-98.

[15] 楊際祥, 譚國真, 王榮生. 并行與分布式計算動態(tài)負載均衡策略綜述[J]. 電子學報, 2010, 38(5): 1122-1130.

[16] 張正昌, 何發(fā)智, 周毅. 基于動態(tài)任務調度的層次包圍盒構建算法[J]. 計算機輔助設計與圖形學學報, 2018, 30(3): 491-498.

[17] CHEN L, VILLA O, KRISHNAMOORTHY S, et al. Dynamic load balancing on single-and multi-GPU systems[C]//2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). New York: IEEE Press, 2010: 1-12.

[18] COSENZA B, CORDASCO G, DE CHIARA R, et al. Load balancing in mesh-like computations using prediction binary trees[C]//2008 International Symposium on Parallel and Distributed Computing. New York: IEEE Press, 2008: 139-146.

[19] ELTANTAWY A, AAMODT T M. Warp scheduling for fine-grained synchronization[C]//2018 IEEE International Symposium on High Performance Computer Architecture (HPCA). New York: IEEE Press, 2018: 375-388.

[20] YANG C Z, CHEN C Y, HU X J, et al. Dynamic load balancing algorithm based on per-pixel rendering cost estimation for parallel ray tracing on PC clusters[C]//14th Conference on Image and Graphics Technologies and Applications, IGTA 2019. Heidelberg: Springer, 2019: 591-601.

Load balancing algorithm based on greedy strategy for multi-node parallel ray tracing

LIU Yun-biao, CHEN Chun-yi, HU Xiao-juan, XING Qi-wei, YANG Hua-min

(School of Computer Science and Technology, Changchun University of Science and Technology, Changchun Jilin 130022, China)

A load-balancing algorithm based on greedy strategy for multi-node parallel ray tracing was proposed to improve the parallelism degree of applying ray tracing cluster to producing high-definition pictures of complex scenes. Firstly, according to parallel property of GPU, the screen space was divided into a number of square image blocks. Based on the projection of the spherical bounding box of moving objects on the screen, the binary rendering time influence map was constructed. Then on the basis of the spatiotemporal correlation, the rendering task queue was established by combining the time consumed by the previous image block and the binary rendering time influence map. Then the dynamic allocation of multi-rendering node tasks was realized through two-step load-balancing. Finally, the method was verified and analyzed based on experimental data. The results showed that this method presents good load-balancing effect, and the rendering efficiency can be improved by up to 4.96 times.

ray tracing; high-definition picture; load balancing; multi-node rendering; greedy strategy

TP 391

10.11996/JG.j.2095-302X.2020020237

A

2095-302X(2020)02-0237-09

2019-10-12；

2019-12-03

國家自然科學基金項目(U19A2063)；吉林省科技發(fā)展計劃(20170101005JC, 20180519012JH, 20190302113GX)；吉林省教育廳“十三五”科學技術研究項目(JJKH20200792KJ, JJKH20200799KJ)

劉云彪(1994–)，男，吉林長春人，碩士研究生。主要研究方向為三維場景建模與繪制。E-mail：LiuYunBiao@163.com

陳純毅(1981–)，男，重慶人，教授，博士，博士生導師。主要研究方向為三維場景建模與繪制等。E-mail：chenchunyi@hotmail.com