[發明專利]集群渲染環境中基于PKDT樹的動態反饋負載均衡方法

有效

• 申請號: 201310018156.8
• 申請日: 2013-01-17
• 公開（公告）號: CN103077088A
• 公開（公告）日: 2013-05-01
• 發明（設計）人: 張勤飛;趙磊;魯東明;任艷姣;陸勝;李偉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06T15/00
• 代理公司: 杭州天勤知識產權代理有限公司 33224
• 代理人: 胡紅娟

技術領域

本發明涉及集群渲染領域，具體涉及一種集群渲染環境中基于PKDT樹的動態反饋負載均衡方法。

背景技術

目前，高真實感渲染在很多領域已經有了越來越多的應用，例如在電影特效的制作，真實感場景的展示等方面都有重要應用。

高真實感渲染需要極高的計算能量，如果對渲染速度也有較高要求，那么單機的渲染能力已經無法滿足，二需要使用集群技術。

負載均衡問題是影響集群渲染系統整體性能的重要因素之一。集群渲染系統中，由于不同渲染節點間處理能力上的差異或者任務分配的不均勻，會出現不同渲染節點任務完成時間不一致的情況，這樣完成時間早的節點只能閑置等待處理時間慢的渲染節點，從而造成了集群渲染系統資源的浪費。

目前解決負載不均衡問題的方法從大類上來說有兩種，一是靜態平衡方法；二是動態平衡方法。

靜態平衡方法通過對整個集群渲染系統中各個渲染節點的計算能力進行估算，然后在初始化階段就將任務分配好，一旦分配就不再改變。這種方法局限性非常大，首先，通常難以準確估算渲染節點的計算能力以及網絡環境等；其次，由于每個渲染節點的計算環境、網絡環境一直處于不斷的變化之中，這些渲染節點的計算能力以及網絡傳輸能力也是不停地變化的，因此，這種方法通常難以取得好的效果。

動態平衡方法是目前流行的方法，目前有很多這一類算法，像Diffustion方法，，Median-cut算法Master-slave方法等，但是仍沒有成熟的動態負載平衡方法能夠用于集群渲染環境中按屏幕空間劃分的方式。

PKDT(Prediction?KD?Tree)即預測KD樹，它記錄了當前屏幕空間的一種任務劃分，PKDT樹的每個葉子節點對應著屏幕空間中的一個像素子塊。PKDT樹基于如下理論前提：前幀和后幀之間的同一像素子塊存在時空連續性，即某一子塊的下一幀渲染所需的時間跟上一幀非常接近，所以能夠利用上一幀記錄的時間作為預估值。

發明內容

本發明提供了一種集群渲染環境中基于PKDT樹的動態反饋負載均衡方法，集群渲染系統的服務器將每幀渲染任務按屏幕空間進行任務劃分，并將劃分后的子任務在各渲染機器節點中進行動態平衡分配，充分挖掘集群渲染系統的最佳渲染能力。

一種集群渲染環境中基于PKDT樹的動態反饋負載均衡方法，包括如下步驟：

(1)針對需要渲染的三維模型，服務器將渲染任務劃分成若干子任務，將這些子任務預指定給每個渲染機器節點，并逐個進行傳送；

(2)每個渲染機器節點執行完一個子任務后，向服務器返回渲染結果圖像，并申請下一個子任務；

(3)服務器節點記錄每個渲染機器節點完成每個子任務的時間以及每個渲染機器節點完成的子任務的數量，并依據該記錄結果將未完成的子任務在渲染機器節點之間進行動態平衡分配，直至完成該幀渲染任務。

集群渲染系統的服務器節點將渲染任務依據屏幕空間劃分為若干子任務，并將子任務預先指定給每個渲染機器節點，每個渲染機器節點即集群渲染系統中的某臺機器，預先指定時，遵循每臺渲染機器完成預先指定的子任務的時間盡可能一樣的原則，最后，每次向渲染機器傳送一個子任務，服務器節點記錄每臺渲染機器完成每個子任務的時間，并依據該記錄結果將未完成的子任務在各臺渲染機器之間進行新的預先指定。

在新的預先指定過程中，首先對未完成的子任務進行重新劃分以及將重新劃分后的所有子任務在不同的渲染機器節點(機器)之間進行新的預先指定。

作為優選，所述步驟(1)中服務器節點向渲染機器節點預先指定子任務之前，根據每個子任務中(需要渲染的像素的數量)預估每個子任務的計算量。優選地，所述步驟(1)中劃分渲染任務時，每個子任務的計算量相同。也即每個子任務需要渲染的像素的數量相同。

作為優選，所述步驟(1)中子任務數目是渲染節點數目的整數倍。便于在渲染機器節點中平均分配子任務，使每個渲染機器節點在相同的時間內完成渲染任務。

作為優選，所述步驟(1)中將需要渲染的三維模型投影到屏幕空間，對于屏幕空間的像素，若與三維模型相對應的幾何點落到該像素，則該像素即為需要渲染的像素。

作為優選，所述步驟(3)中對比各個渲染機器節點完成每個子任務的時間，優先向完成時間短的渲染機器節點傳送下一個子任務。也即渲染速度快的渲染機器節點將完成較多的渲染任務，使整個集群渲染系統的渲染速度達到性能最高。

本發明集群渲染環境中基于PKDT樹的動態反饋負載均衡方法具有以下有益效果：