大范围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