李文强，陆应通

（1.四川大学计算机学院，成都 610065；2.四川大学视觉合成图形图像技术国防重点学科实验室，成都 610065）

基于绘制时间的加权动态负载均衡算法

李文强1，陆应通2

（1.四川大学计算机学院，成都 610065；2.四川大学视觉合成图形图像技术国防重点学科实验室，成都 610065）

负载均衡是影响集群并行绘制系统整体性能的关键因素之一。由于场景数据的分布不均，在运行过程中经常出现负载失衡的现象。针对sort-first型并行绘制系统的特点，综合考虑每个绘制节点的绘制能力，使用权重因子加权绘制时间，提出了一种基于绘制时间加权的动态负载均衡算法。算法包括负载预估、任务动态划分与分配。负载预估时，使用加权后的时间估算屏幕中每个像素点的负载。任务分配阶段，根据负载分布，同时参考绘制能力，动态划分绘制任务。实验结果表明该算法能够提高系统的帧率，提高系统负载的稳定性。

并行绘制；动态负载均衡；自适应；归属判断

0 引言

超大规模场景交互式应用中，因其海量的数据与绘制实时性需求，对系统的处理能力提出了新的挑战。虽然硬件产品的更新换代使得PC的整体性能得到了较大提升，但应用的需求与单机所能提供的绘制能力之间的矛盾却日益突出。专业图形工作站虽能满足应用需求，但昂贵的价格限制了其应用范围。通过高速网络互联的PC集群实现图形的并行处理，具有较高的扩展性与性价比，能提供与专业图形设备相媲美的处理能力，满足应用需求[1]。在这种集群分布式并行绘制系统中，Molnar等人按照渲染任务划分阶段与方式[2]，将并行绘制系统的体系结构划分为sort-first[3]、sort-mid dle[4]、sort-last[5]三种基本类型，奠定了并行绘制体系结构研究的理论基础。

在三种基本的体系结构中，sort-middle由于需要专有的图形硬件支持，并没有运用到实际的系统之中。对sort-last型，图像合成与网络带宽是系统的性能瓶颈，且限制了集群的规模。sort-first则最大限度保留了图形绘制流水线的完整性，非常适合于集群并行绘制系统。但其最大的问题在于容易因场景数据分布不均出现负载失衡，造成资源浪费，降低系统性能。因此，如何解决负载失衡是并行绘制研究的首要问题。

1 相关工作

负载均衡是影响集群并行绘制系统整体性能的关键因素之一，开发高质量的负载均衡算法是提高系统运行效率的有效手段。针对sort-first型而言，负载均衡一般通过对屏幕空间的划分来实现，按照划分方式可将算法分为两大类：静态负载均衡算法与动态负载均衡算法。后者根据负载变化，动态调整任务划分，具有良好的可适应性，成为负载均衡算法的主要研究方向。

动态负载均衡算法中，按照系统负载预估策略的不同，将其分为两大类：基于几何数据预处理的负载均衡算法与基于绘制历史的负载均衡算法。前者以落在屏幕空间中几何图元的个数作为绘制负载的量化标准，通过对顶点等几何数据的矩阵变换，确定在屏幕空间的位置，从而完成负载分布的估计，如Roble算法[6]、Median-cut算法[7]、Whitman的自顶向下分解算法[8]、MAHD算法[9]等，这类算法需要处理整个场景数据，场景越大，开销越大，不适合用于超大规模的实时应用。

基于绘制历史的负载均衡算法（也称之为时空转换类算法）的理论基础是帧间连续性[10]，即：在交互式系统中，相邻两帧间场景数据、绘制开销等变化不大，可用上一帧绘制时间近似估算下一帧绘制所需时间。在估计场景负载分布时，使用绘制时间来度量负载。金哲凡在其博士论文[11]中首次提出了以时间作为负载度量的标准，开启了这类算法的研究。此后许多类似算法被相继提出，如：延期着色算法[12]、基于Q-Learning负载平衡策略[13]、二叉预测树算法[14]等。这类算法计算效率高，能达到较好的平衡效果。但无法准确估计出绘制时间，容易受软硬件环境差异与视点突变等因素的影响，对负载的评估易产生较大偏差。

结合上述算法的优缺点，本文提出了一种改进型的负载均衡算法：考虑节点计算能力对绘制时间的影响，得到一个影响因子，用上一帧的绘制时间与其相乘，用得到的结果计算每个像素的负载，并用于预估下一帧的负载；同时使用了一个具有统计意义的更新阈值来控制更新算法的执行。

2 算法概述

帧间连续性是本算法的理论前提。图1详细描述了算法的执行流程。系统在运行过程中收集上一帧图像绘制所用时间，并进行更新阈值计算，用以判断是否需要更新当前任务划分方式。满足更新条件时，根据场景负载分布特点重新划分绘制任务过程中，综合考虑各绘制节点图形处理能力不同、图像区域大小互异等因素，计算得到一个统一标准下的影响因子，用加权后的绘制时间，去评估绘制屏幕空间中每个像素所需时间。划分绘制任务时，根据节点计算能力的大小，按照“能者多劳”的原则进行分配。

2.1 影响因子计算

考虑到PC集群中不同绘制节点的图形处理能力有所不同，直接采用历史绘制时间去评估负载大小会因度量标准上的差异引入误差。例如：对于同一绘制任务而言，高配置机器绘制所需时间会小于低配置机器所需时间，所以需要引入一个统一标准来消除因硬件环境不同而产生的度量上的误差。

初始运行时让集群中所有绘制节点绘制同一场景，分别用时t1，t2，…，tn，设集群中绘制这一帧所用最长时间为tmax。绘制节点计算能力影响因子定义为：在同一绘制任务中，集群中最长绘制时间除以该节点绘制所用时间。公式（1）给出了节点i计算能力影响因子计算过程。后续处理需要用到绘制时间时，直接使用影响因子对绘制时间做归一化处理，得到一个在相同计算标准下的绘制时间值。

并非人人都有逃避的自由，乱世中为势所迫，明哲保身的人不在少数。五代时期，士人无论是在朝廷任高官还是在地方做小吏，内心有一种朝不保夕的恐惧感。在混世的风气下，他们随势可否，不为事先，唯唯诺诺，传统的人格精神失去了维系世道人心的力量，与盛唐锐意事功、开拓奋进的精神面貌相去甚远。

图1 算法处理流程

任务分配时，为了最大限度的提高资源利用率，使得绘制节点在大多数情况下都处于忙碌状态。根据节点计算能力大小按“能者多劳”的原则动态分配绘制任务。设总的绘制任务量为单位1，所有节点根据自己的计算能力得到一个所承担计算任务在总任务中所占的比值，将其定义为节点计算任务比。采用公式（2）计算，根据（2）式不难证明所有节点的计算任务比值之和为1，从而保证了集群中的绘制节点正好无重复完成所有绘制任务。

2.2 负载预估与任务划分

本文采用基于屏幕二维空间的剖分实现绘制任务的划分，每一个绘制节点需要保留的数据包括：当前区域边界、历史绘制时间CostTime、区域预估负载EstimateTime等。服务器作为系统中心控制节点，在系统运行过程中收集所有节点绘制上一帧所用时间，经过（3）归一化处理后，用其计算节点的EstimateTime域。

完成场景负载分布预估后，需要选取一种合理有效的屏幕划分方式，按照各绘制节点的计算能力分配负载。在划分的过程中，为了避免大量出现细长条形的划分方式，本算法总是沿着当前区域中较长边进行划分。设当前任务区域块Region有w行h列（设w＜h，记为R（0，h）），区域总负载为ER；R（i，j）表示Region中从第i列到第j列像素所组成的子块；负责当前任务区域的绘制节点集合为N，将N按照负载量均分成两份N1与N2，并尽可能满足公式（4）。

任务划分的目标就是根据绘制节点集合N1、N2找到一个k值将当前任务区域块Region分成R（0，k）和R（k+1，h），两个区域的负载分布记为ER（0，k）与ER（k+1，h），k满足公式（5）所列出的条件。

本算法总是沿着当前区域中较长边进行划分，即每次在区域长边上选取一个k值，在这个点上做垂直于该边的划分，将当前区域划分成两个相邻且不重叠的子区域。

任务划分过程可由一棵二叉树描述，图2给出了一个拥有4个绘制节点的并行绘制系统屏幕子块划分过程，其中不同颜色标识了最终的不同绘制任务。

图2 屏幕子块划分

2.3 任务更新策略

假设当前集群系统有n个绘制节点，设ti是第i个绘制节点绘制上一帧所用时间，其均值μ与方差σ12可由公式（6）计算。

为简化计算复杂度，采用文献[14]给出的调整方式，即合并小负载，分割大负载。设Ra是开销最大的绘制节点，Rb和Rc是tRb*tRc最小的相邻绘制节点。将Ra分裂为Ra1与Ra2，合并Rb与Rc为Rbc，其余划分方式不变，得到新的方差σ22。划分前与划分后两方差相减，整理得到（7）式。

系统运行过程中，服务器收集上一帧绘制所用时间，经归一化处理之后，更新绘制节点的EstimateTime的值。在每一帧分发绘制任务之前，使用未经过归一化处理的绘制时间计算更新控制阈值Threshold。如果Threshold＞0，则认为系统处于不均衡状态，需要调整任务划分方式；否则，仍然按照上一帧的划分方式分配任务。

图3 相同节点绘制时间对比

3 实验及分析

本文算法的验证在实验室并行绘制集群的基础[15]下完成，采用6台Intel Xeon E3-1230V2 3.30GHz，16G内存，4块NVIDA GeForce GTX980和2块NVIDA GeForceGTX670图形加速卡，6块InfiniBand MCX353A-TCBT网卡，一台Mellanox IS5022交换机。对同一场景在相同视点变换条件下分别与静态负载均衡算法和未加权的动态负载均衡算法比较。

负载均衡实验所使用的动态场景包含12个dragon模型。为准确评价本算法性能，我们将其与静态负载均衡算法相对比，两组试实验中所使用的测试场景、视点信息、相机参数完全一致。图3给出了静态负载均衡算法与动态负载均衡算法运行过程中同一绘制节点在连续30帧里的绘制开销对比。

图3可以看出，同一绘制节点在相同条件下运行场景时，每帧绘制所需时间相差较大。这是因为静态算法运行过程中不改变绘制区域的大小，而落入该区域的图元数目随视点改变而变化，造成绘制时间时高时低。动态算法会根据上一帧负载调整下一帧绘制区域，因此绘制开销相对平缓。

为定量分析系统负载性能，使用变量负载系数factorLB=tmin/tCost，其中tcost表示集群系统绘制某一帧所用时间，tmin表示首先完成该帧绘制任务的绘制节点所用时间。factorLB可反映系统绘制负载分配状况，factorLB值越接近1表明系统负载均衡性能越好。图4给出了连续15帧里系统使用静态算法与动态算法的factorLB柱状图。

从图4可以看出，动态算法的factorLB值相对于静态算法较大，且更加接近于1。这些特点表明本文的负载均衡算法提高了系统的负载性能。

图4 factorLB柱状图

为验证加权动态算法的优势，各绘制节点使用了不同的显卡（绘制节点的性能主要由显卡性能决定）。图5给出了三种算法在运行过程中某段时间系统帧率对比。

图5 系统帧率对比

并行绘制系统实际绘制速度取决于集群中运行最慢的绘制节点。在动态场景中视点信息不断发生改变，落入视域范围内的场景数据也随之改变，场景数据在屏幕空间中的分布也不断变化。静态算法在系统运行前就确定屏幕划分方式，运行过程中不再改变，而各子区域的数据有时分布较为均匀，有时相差较大，导致帧率时高时低，波动较大。动态负载均衡算法在运行过程中，根据上一帧绘制负载的分布状况，通过调整绘制节点绘制区域，确定下一帧各绘制节点的绘制任务，能够适应场景负载的变化，所以绘制帧率较高，曲线也相对平缓。但未加权的动态均衡算法与加权动态均衡算法相比，由于绘制节点性能各异，使得前者的帧率明显低于后者的帧率。图5也印证了这一现象，实验结果显示，使用加权动态算法，系统帧率维持在19～22帧，而相同条件下未加权动态算法帧率维持在17～19帧，静态算法帧率维持在11～16帧。

产生上述特点的原因有：第一、静态负载均衡算法在运行过程中任务划分方式不再改变，在某些视点条件下将高负载分配给高配置机器，反之亦然，故运行时出现较大的波动性。第二、动态负载均衡算法在运行过程中动态根据负载调整任务划分，故受视点变化影响较小。第三、未加权动态负载均衡算法虽动态划分任务，但在负载预估与任务分配时，未考虑机器硬件绘制能力的差异，从而引入了较大误差，在某些视点下使得低配置机器承担了较高负载的绘制任务。本文提出的算法使用绘制能力对绘制时间加权，并应用到负载预估与任务分配中，使得各绘制节点合理的承担了绘制任务，故帧率相对于前者有所提高。第四、两种动态负载均衡算法均出现一定的波动性，其根本原因在于他们都是一种负载失衡补救策略，当帧间连续性失效时，负载预估将不再准确，系统需要一定时间来调整。

4 结语

负载均衡是并行绘制系统中影响性能的最为关键问题，本文提出的基于绘制时间加权的动态负载均衡算法的处理思路为：考虑绘制节点的绘制能力，得到一个因子去归一化处理绘制时间；计算屏幕空间像素点负载时，考虑区域大小的影响，并使用加权后的时间去估算；分配绘制任务时，根据绘制能力大小，按比例分配任务；并采用方差这一更新阈值控制任务划分更新算法的执行。最后通过对比实验证明了本文所提算法的正确、有效性，并给出了理论上的分析说明。

在本文基础上，后续的一个潜在可改进方向：考虑帧间连续性失效的情况下，通过学习的手段，在对大量历史运行数据的研究下，找到各种输入与负载之间的关系，从而在知道视点的情况下，可更加精确地估算系统负载，以期达到更好的平衡效果。

[1]刘真,石教英,彭浩宇,等.基于PC集群并行图形绘制系统综述[J].系统仿真学报,2006(z1):70-72.

[2]Steven Molnar,Michael Cox,David Ellsworth,and Henry Fuchs.A Sorting Classification of Parallel Rendering[J].Computer Graphics and Applications,IEEE,14(4):23-32,1994.

[3]E Bethel,Greg Humphreys,Brian Paul,J Dean Brederson.Sort-First,Distributed Memory Parallel Visualization and Rendering[C].In Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics,page 7.IEEE Computer Society, 2003.

[4]Erik Ordentlich,Craig M Wittenbrink.Systems and Methods for Compressing Rasterization Setup Data Within a Sort Middle Graphics Architecture:U.S.Patent,6995769[B2],2006.

[5]Kenneth Moreland,Brian Wylie,Constantine Pavlakos.Sort-Last Parallel Rendering for Viewing Extremely Large Data Sets on Tile Displays[C].In Proceedings of IEEE 2001 Symposium on Parallel and Large-Data Visualization and Graphic,pages 85-92.IEEE Press,2001.

[6]Douglas R Roble.A Load Balanced Parallel Scanline Z-Buffer Algorithm for the Ipsc Hypercube[C].In Proceedings of Pixim,Volume 88,pages 177-192,1988.

[7]Daniel S Whelan.Animac:A Multiprocessor Architecture for Real-Time Computer Animation，1985.

[8]Scott Whitman.Dynamic Load Balancing for Parallel Polygon Rendering[J].Computer Graphics and Applications,IEEE,14(4):41-48, 1994.

[9]Carl Mueller.The Sort-First Rendering Architecture for High-Performance Graphics[C].In Proceedings of the 1995 Symposium on Interactive 3D Graphics,pages 75-ff.ACM,1995.

[10]彭浩宇.基于PC集群机的并行图形绘制系统研究[D].杭州:浙江大学图书馆,2006.

[11]金哲凡.保留模式图形并行绘制研究[D].杭州：浙江大学，2003.

[12]常辉,雷小永,戴树岭.基于动态负载平衡的sort-first绘制集群[J].北京航空航天大学学报,2010(4):447-450.

[13]Sina Meraji,Wei Zhang,Carl Tropper.A Multi-State Q-Learning Approach for the Dynamic Load Balancing of Time Warp[C].In Proceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation,pages 142-149.IEEE Computer Society,2010.

[14]Biagio Cosenza,Gennaro Cordasco,Rosario De Chiara,et al.Load Balancing in Mesh-Like Computations Using Prediction Binary Trees[C].In Parallel and Distributed Computing,2008.ISPDC'08.International Symposium on,pages 139-146.IEEE,2008.

[15]付讯,叶庆.基于InfiniBand的集群分布式并行绘制系统设计[J].四川大学学报，2015,52(1):39-44.

Dynamic Load Balancing for Parallel Rendering System Based on Rendering Time Weighted

LI Wen-Qiang1，LU Ying-Tong2
（1.College of Computer Science，Sichuan University，Chengdu 610065；2.National Key Laboratory of Fundamental Science on Synthetic Vision，Sichuan University，Chengdu 610065）

Load balancing is one of key factors that influences the performance of the parallel rendering system.The existing algorithms usually suffer from high load imbalance during the execution because of the irregular nature of datasets.Proposes an improved load balancing algorithm based on the rendering history for sort-first parallel rendering system,which includes load estimation and render task partition.This algorithm considers the processing ability of each render node,and gets a weight factor.During the load estimation stage,uses this factor to weight the rendering time and compute the render cost of each pixels.Then according to the load distribution and rendering ability, partitioning the render task dynamically.The experimental result shows that this method can improve the frame rate,maintain the stability of the system load.

Parallel Rendering;Dynamic Load Balancing;Self-Adaptive;Belong-Determining

1007-1423（2017）08-0045-06

10.3969/j.issn.1007-1423.2017.08.010

李文强（1990-），男，四川自贡人，硕士研究生，研究方向为并行图形绘制、虚拟现实陆应通（1991-），男，广东佛山人，硕士研究生，研究方向为计算机图形学

2016-12-22

2017-03-10

国家自然科学基金（No.61472261）、国家科技支撑计划（No.2012BAH62F03）