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

大范圍3DCM場景實(shí)時并行繪制的任務(wù)劃分及策略

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

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

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

3DCM場景;并行繪制;任務(wù)劃分;動態(tài)負(fù)載平衡

0 引言

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

1 多任務(wù)劃分策略

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

式中：Mk為分配的任務(wù)在各個進(jìn)程中的內(nèi)部編號。則整個并行繪制需要的時間為：

而非并行計算的總時間（繪制當(dāng)前幀的各任務(wù)時間總和）為：

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

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

2 多任務(wù)劃分算法

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

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

3 結(jié)論

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

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

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

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

［4］彭敏峰，曾亮，李思昆.并行繪制的動態(tài)負(fù)載平衡算法研究［J］.計算機(jī)應(yīng)用，2007，27（1）：166－168.

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

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

［7］WILKINSON B，ALLEN M.陸鑫達(dá)，等（譯）.并行程序設(shè)計［M］.北京：機(jī)械工業(yè)出版社，2002.

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

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

LI Chao－kui，YANG Ou，WU Bai－yan，YIN Zhi－h(huán)ui，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

國家自然科學(xué)基金項目（41271390）;湖南省自然科學(xué)基金項目（12JJ9023）;湖南科技大學(xué)研究生優(yōu)培項目（S120036）

李朝奎（1967－），男，博士，教授，主要從事地理信息應(yīng)用研究。E－mail：chkl＿h(yuǎn)n＠163.com