大范圍3DCM場景實時并行繪制的任務劃分及策略

李 朝 奎，楊 偶，吳 柏 燕，殷 智 慧，李 擁

大范圍3DCM場景實時并行繪制的任務劃分及策略

李 朝 奎，楊 偶，吳 柏 燕，殷 智 慧，李 擁

（湖南科技大學地球空間信息科學研究中心，湖南 湘潭 411201;地理空間信息湖南省工程實驗室，湖南 湘潭 411201）

針對三維城市模型（3DCM）場景并行繪制的幾何圖元分布特性，利用動態負載平衡算法實現3DCM場景繪制任務劃分和分配。給出了負載平衡性能的一種度量權，提出一種遞歸劃分算法：即把按順序執行的任務集，根據其子任務間潛在的并行性，劃分成若干個可并發執行的任務子集，并把每個子集分配給處理機，使各處理機之間的數據通信量盡可能同步，同時兼顧各處理機之間的負載平衡，從而實現了一種新的負載平衡算法。

3DCM場景;并行繪制;任務劃分;動態負載平衡

0 引言

隨著計算機圖形技術的實用化以及近年來三維掃描和建模技術的快速發展，三維模型的數據量急劇增大，單純依賴于圖形加速卡的單機繪制技術并不能滿足大范圍3DCM場景的實時繪制要求。一般3DCM場景非常復雜，而任何硬件在單位時間內處理場景的能力總是有限的［1－3］。目前大范圍3DCM場景的數據量大大超過了計算機的內存容量，使得繪制系統無法將整個場景一次性調入，因此，處理大規模3DCM場景數據的一般方法是對場景數據進行空間劃分，將整個場景分割成多個便于管理的數據塊，并按照空間層次的形式進行組織［1］。大規模3DCM場景繪制任務的劃分與調度是將一個大規模的3DCM場景繪制任務集進行分解，并把每個分解的可并發執行的任務子集映射到不同的處理機上進行并行運算，以提高3DCM場景繪制的速度［4，5］。因為3DCM場景的繪制任務之間總有許多數據聯系，它們需要在各處理機之間進行通信，而每一處理機之間通信與同步往往制約著3DCM場景繪制的效率，因此，在場景繪制任務劃分過程中如何減少子任務之間的通信量，使得相互之間通信量多的子任務盡可能在同一處理機上運算，實現各處理機之間負載平衡等問題是3DCM場景繪制的關鍵。一般任務劃分、任務調度和負載平衡是大范圍3DCM場景的并行繪制技術急需解決的3個關鍵問題。傳統的并行繪制系統（如sort-first系統和sort-last系統）需要對整個模型空間進行劃分以及對整個屏幕的像素進行合成，這樣需要對整個三維場景數據進行處理，其通信開銷量影響整個系統的效率。大范圍3DCM場景繪制要盡量避免集中對其場景數據進行處理，利用預處理將繪制任務分配給每個進程，以提高3DCM場景繪制速度［6－8］。對此，本文提出了一種適用于3DCM場景的多任務并行圖形繪制算法，通過給出負載平衡性能的一種度量權來確定3DCM場景繪制任務劃分和分配方案，實現了一種新的負載平衡算法，即把按順序執行的任務集，根據其子任務之間潛在的并行性進行劃分，并把已劃分的可并發執行的任務子集分配給處理機，使其數據通信量盡可能同步，處理機之間盡可能達到負載平衡。

1 多任務劃分策略

3DCM場景繪制的多任務劃分算法需要考慮每個繪制任務的計算量或權，稱之為場景繪制任務的粒度，這取決于場景繪制任務本身。每一繪制任務的計算量（粒度）不能太大，粒度太大就會使劃分失去意義，無法進行并行運算;同時，每一粒度也不能太小，否則任務之間頻繁地通信會降低3DCM場景繪制的效率。一般可以將幾個計算量小的語句合并成一個任務來增大粒度或者將計算量大的語句分成若干步來減少粒度，使得3DCM場景繪制任務劃分的每一任務的粒度大致相等。下面分析多任務的劃分，設有N個繪制任務和P臺處理機，每一任務的繪制時間為ti（i＝0，1，…，N－1），則將任務分配給每一個進程之后，每臺處理機的時間數值為：

式中：Mk為分配的任務在各個進程中的內部編號。則整個并行繪制需要的時間為：

而非并行計算的總時間（繪制當前幀的各任務時間總和）為：

圖形繪制時，應使各處理器能夠滿負荷地工作，也就是希望每個處理器的處理時間與并行繪制所需的時間差為最小。為了避免正負符號的影響，需考慮時間差的平方和：

式（5）可以看成是3DCM場景并行繪制的時間效率函數。顯然d值越小，各個處理器總的等待時間將會達到最小。可以看出，影響并行繪制的關鍵項是式（5）等號右邊的第一項。

2 多任務劃分算法

為了減少圖形繪制任務之間的耦合度和通信開銷，可以將3DCM場景中的圖形繪制任務按照對象（如可以按背景繪制和幾何物體繪制）進行分類。大規模三維復雜場景中的大型背景繪制非常耗時，需要進一步對其任務進行劃分以便分配給多個進程;大規模三維復雜場景中幾何實體對象的繪制（如建筑物、窗戶等）可以分配給不同的處理器。在進行預處理時，首先將幾何物體數據和背景數據進行分離，使背景數據的運算在一個或多個效率較高的處理機上進行，而幾何物體的數據計算在其他的處理機上進行，為了任務分配策略簡單，在進行任務分配時，要使各處理機的任務量盡可能平均，這樣任務并行的通信開銷也較少;在完成任務分割后，將背景或幾何物體的計算結果按屏幕區域進行劃分，再傳送到同一臺繪制服務器進行圖形繪制合成，使多個小塊屏幕實現并行合成。

3DCM場景并行繪制任務劃分的原則是分配給各個進程的繪制任務時間數值之和盡可能相等，其算法的主要思路為：首先把3DCM場景繪制任務集合GT劃分成二個元素之間的相關性最小子任務集合GL和GR，同時使GL和GR中任務的計算量盡可能一致;然后對GL和GR進行遞歸劃分，直到遞歸深度大于等于最大遞歸深度log2P（P為處理機臺數）;通過上述劃分將得到P個任務子集，把每一任務子集分配給某一處理機。其相應的算法描述如下：

3 結論

并行繪制是快速、準確地表現三維場景以及實現大范圍復雜3DCM場景數據可視化的理想方法，該方法利用多個圖形硬件（PC集群）或圖形繪制流水線，整合單機繪制能力的和完成繪制任務。針對3DCM場景并行繪制任務的幾何圖元分布特性，利用動態負載平衡算法實現3DCM場景繪制任務劃分和分配。在按順序執行的3DCM場景繪制任務集中，根據其子任務之間存在的可能的并行性，將3DCM場景繪制任務集劃分成若干個可并發執行的任務子集，并把每個子集分配給一個處理機，使各處理機之間的數據通信量盡可能同步，同時兼顧各處理機之間負載平衡。

［1］朱慶，龔俊，杜志強，等.三維城市模型的多細節層次描述方法［J］.武漢大學學報（信息科學版），2005，30（11）：965－969.

［2］徐永志，李利軍.地形場景的并行繪制及多通道圖形輸出［J］.計算機工程，2005，31（8）：175－176.

［3］韓偉杰，李曉梅，張文.并行圖形繪制技術綜述［J］.計算機工程，2010，36（1）：221－223.

［4］彭敏峰，曾亮，李思昆.并行繪制的動態負載平衡算法研究［J］.計算機應用，2007，27（1）：166－168.

［5］高宇，吳玲達，魏迎梅.海量模型實時交互可視化技術綜述［J］.中國圖象圖形學報，2008，13（9）：1633－1639.

［6］彭浩宇，金哲凡，秦愛紅，等.復式并行流水線在基于PC集群機的并行繪制中的應用［J］.計算機輔助設計與圖形學學報，2006，18（10）：1581－1586.

［7］WILKINSON B，ALLEN M.陸鑫達，等（譯）.并行程序設計［M］.北京：機械工業出版社，2002.

［8］金哲凡.保留模式圖形并行繪制研究［D］.浙江大學，2003.

Parallel Rendering Task Partitioning and Strategy for Large Range 3DCM Scene

LI Chao－kui，YANG Ou，WU Bai－yan，YIN Zhi－hui，LI Yong
（CenterofGeospatialInformationScience，HunanUniversityofScienceandTechnology，Xiangtan411201;HunanProvinceEngineeringLaboratoryofGeospatialInformation，Xiangtan411201，China）

Aim at the geometric primitives distribution characteristics of 3D city model（3DCM）scene parallel rendering，using the dynamic load balancing algorithm，the task partitioning and distribution of 3DCM scene rendering was achieved.A metric right of load balance and a recursive partitioning algorithm were proposed，and a new load balancing algorithm which is sequentially executed the task set was achieved.According to the sub-tasks′potential parallelism，task set is divided into a number of subset of tasks which can concurrent executive task，and each subset is assigned to a processor，data communication between the processors is synchronous as possible，and taking into account the load balance between processors.

3DCM scene;parallel rendering;task partitioning;dynamical load balance

P208

A

1672－0504（2012）06－0024－04

2012－01- 14;

2012－03－15

國家自然科學基金項目（41271390）;湖南省自然科學基金項目（12JJ9023）;湖南科技大學研究生優培項目（S120036）

李朝奎（1967－），男，博士，教授，主要從事地理信息應用研究。E－mail：chkl＿hn＠163.com