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

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

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

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

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

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

0 引言

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

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

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

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

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

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

式（5）可以看成是3DCM場(chǎng)景并行繪制的時(shí)間效率函數(shù)。顯然d值越小，各個(gè)處理器總的等待時(shí)間將會(huì)達(dá)到最小?？梢钥闯?，影響并行繪制的關(guān)鍵項(xiàng)是式（5）等號(hào)右邊的第一項(xiàng)。

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

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

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

3 結(jié)論

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

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

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

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

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

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

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

［7］WILKINSON B，ALLEN M.陸鑫達(dá)，等（譯）.并行程序設(shè)計(jì)［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é)基金項(xiàng)目（41271390）;湖南省自然科學(xué)基金項(xiàng)目（12JJ9023）;湖南科技大學(xué)研究生優(yōu)培項(xiàng)目（S120036）

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