罗小涛，段思羽

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

0 引言

并行绘制[7]是基于实时交互的娱乐系统，尤其是要求输出高质量连续并稳定动画的应用中常用的解决方案。负载平衡是并行绘制系统中研究的重要问题之一。负载失衡时，并行绘制系统的输出帧率突然下降，从而造成动画不连续、卡帧等现象，对用户体验造成极大的负面影响。而对于高质量实时交互娱乐系统，此类现象应该严格避免。针对并行绘制系统的负载平衡问题，现有的解决方案是增加负载失衡检测，并在负载失衡后进行补偿以尽快恢复负载平衡。例如，Erol[2]等提出并应用于Equalizer的CSLB（Cross-Segment Load Balancing）策略，属于一种 Work-Stealing策略；Labroni⁃ci[6]等针对不规则物体的光线跟踪提出的基于屏幕划分的动态负载平衡算法;Goswami[3]等针对高显示分辨率的交互式应用提出了基于多路KD-Tree的负载平衡策略等。本质上来讲，上述“检测+补偿”的方法仅能降低负载失衡对并行绘制系统的影响，并不能从根本上消除负载失衡。负载失衡，其根本原因是各并行绘制节点之间的绘制任务量不平衡，如果提前知道特定帧的绘制开销，并制定任务平衡划分的方式，是否能从根本上解决负载平衡问题？

本文基于“绘制程序的特定帧在绘制程序整个生命周期会被多次绘制”这一事实，以及结合机器学习模型能够学习过往知识并进行预测的功能，为使并行绘制系统输出连续且稳定的动画，提高绘制输出帧率，提高资源利用率，提出并实现了基于回归森林的并行绘制系统地负载平衡调度策略。实验证明，本文方法能较好的做到并行绘制任务的平衡调度，与传统方法相比，提升了并行绘制系统的性能和效率。

1 本文算法描述

1.1 回归森林算法概述

回归森林是由Leo Breiman[1]于2001年提出的组合回归器，由多棵回归树组成。该方法引入随机机制，使模型对噪声数据有很好的容忍度且不容易出现过拟合[4]。其随机性主要体现在两个地方：

（1）每一棵树在进行训练时，从原始训练集合中进行随机有放回的采样，形成和原始训练集合大小相同的训练集（Bootstrap数据集）

（2）在节点进行划分的过程中，随机的从所有的特征中选择特征子集，并从中计算得到最好的划分轴以及划分位置，对节点进行分裂。

图1所示为回归森林结构图，在预测过程中，输入预测实例，每一棵树进行二分搜索并映射到叶子节点，得到该棵树的预测值，而回归森林的预测值为所有树的预测值的平均值。

图1 回归森林结构图

1.2 并行绘制系统的负载平衡调度策略

在并行绘制系统中，负载失衡的根本原因是由于绘制任务的分配不均匀造成。如图2为并行绘制系统的框架图，由控制节点和绘制节点组成，各节点间通过网络连接。进行并行绘制的流程如下：

图2 集群并行绘制系统框架

（1）控制节点对绘制任务进行划分，并通过网络连接将子任务分发给各并行绘制节点；

（2）各并行绘制节点分别对绘制任务进行绘制，并将绘制完成的结果通过网络传回给控制节点；

（3）控制节点等待所有的绘制任务完成并接收到绘制结果，进行结果的拼接，形成并行绘制的最终结果，即图片，并显示到屏幕上。

上述流程中，控制节点将任务进行划分并同时发送给各绘制节点，负载失衡时，各节点由于绘制任务量的不同，导致将绘制结果传回给控制节点的时间不同，造成控制节点额外的等待时间，使得并行绘制系统的效率下降。对任何一个绘制程序，在进行绘制的过程中，不同帧之间的参数可能发生改变，令各帧之间可能发生改变的参数为该帧的特征 X={X1，X2，X，…，Xp}。而对任意帧，若X保持不变，则绘制该帧的计算量必然不变，因此若忽略计算机系统本身的不稳定因素，绘制完成该帧的时间为某固定值。然后对任意固定值进行等分，必然存在解Y，即对任意特定帧X，必然存在某种进行任务平衡划分的方式Y，即等式（1）成立。

本文基于“特定帧在绘制程序的生命周期中会被多次绘制”这一事实，通过离线模拟采集数据，使用回归森林进行离线学习，并保存学习得到的模型以实时对负载的划分进行预测，使用预测结果进行任务调度以达到负载平衡。基于回归森林的负载调度框架如图3所示。

图3 本文算法框架

2 实验

本文基于回归森林的负载平衡调度算法，选用的绘制算法为静态场景下基于LLL（Light Linked Lists）[8]的Deferred Shading算法，如图4。为简化回归森林模型，使用两个绘制节点进行并行绘制模拟实验，此时任务的划分方式Y为平行于计算机屏幕的竖直的划分轴，如图5。具体实验细节如下。

图4 基于LLL的Deferred Shading算法场景图

图5 任务划分方式

2.1 数据采集及模型训练

离线模拟采集的数据记为集合D={X,Y}，可分为如下两个步骤：

（1）确定各帧的特征X。本实验中，选用的绘制算法为静态场景下基于 LLL（Light Linked Lists）[8]的 De⁃ferred Shading算法。如图4所示，该算法中，各帧之间的变化因素有：①相机的摆放；②场景中各光源的位置。上述变化因素即定义为该帧的特征X。

（2）确定各帧的负载平衡划分方式Y。负载是否平衡可体现在各节点完成绘制任务所花费时间是否相当，步骤如下：

①固定X不变，等分任务；

②为消除计算机系统本身不稳定因素对绘制时间的影响，各绘制节点对特定帧X重复进行多次绘制，并保存各自多次绘制的时间；

③从④中绘制时间集合选择一个值作为完成该任务的期望值。这里，由于中值50%的溃点[5]等优势，选择中值作为期望的绘制时间。随机选择4帧，根据其绘制时间的分布选择期望时间，如图6所示，该图也证明中值更加靠近期望时间；

④判断各节点绘制时间是否相当，首先计算平均绘制时间，即式（2）。

若满足，转⑤。否则借助帧间相关性的思想进行调整，假定场景负载度在左右空间中均匀分布，以两个绘制节点举例，首先计算左右屏幕的平均宽度所需绘制时间：

判断左边屏幕的绘制时间是否达到平均时间，若满足，则划分轴向左移动，否则划分轴向右移动

⑤记录当前X，Y为一条数据实例。更新X，转①。

完成上述步骤可得到数据集D，经过简单的数据处理，输入回归森林算法进行训练，并保存得到的模型。

2.2 性能测试

上述得到的模型对两个绘制节点进行分屏并行绘制的任务划分有一定预测能力。为验证模型的性能，即本文方法的有效性，选择静态均分的任务调度以及动态的基于帧间相关性的任务调度方法进行对比。分别使用上述方法和本文方法，绘制完成1000帧，对比实验结果如表1所示。

随机选择相同的100帧，对比使用不同的方法进行任务调度，各并行绘制节点之间最大负载与最小负载之间的关系，如图7所示。

图6 各帧绘制时间的分布

表1 实验结果对比

图7 使用不同任务调度方法最大与最小负载之间的偏差

2.3 结果分析

从表1可以看出，使用本文方法的任务调度策略可使得并行绘制系统在相同的时间内输出更多的帧。从图7可以看出，本文方法调度分配的子任务之间负载偏差相差较均分、帧间相关性要小，反映了各并行绘制节点之间的负载更加平衡。而且，由于当前基于实时交互的娱乐系统复杂度分布不均且常常由于用户交互触发的特效等原因，绘制的帧率必然存在较多突变的情况，而本文方法较前两种传统方法更能适应此类应用，对保证绘制输出动画的稳定性及用户体验有保障。

3 结语

本文提出并实现了一种基于回归森林的并行绘制系统的负载平衡调度策略，并使用特定的绘制算法进行仿真模拟与评估。实验结果显示，尽管该方法每帧均会花费额外的时间用于预测，但是该方法较传统的方法对并行绘制系统的输出帧率以及资源利用率均有提升，且对任意绘制算法适用。基于大规模实时并行绘制系统的特点，抽象化任务平衡划分的方式使得回归森林具有对该抽象化的划分方式具有预测的能力，将是下一步的研究方向。

参考文献：

[1]Breiman L.Random Forests[J].Machine Learning,2001,45（1）:5-32.

[2]Erol F,Eilemann S,Pajarola R.Cross-Segment Load Balancing in Parallel Rendering[C].Eurographics Conference on Parallel Graphics and Visualization.Eurographics Association,2011:41-50.

[3]Goswami P,Erol F,MukhiR,et al.An Efficient Multi-Resolution Framework for High Quality Interactive Rendering of Massive Point Clouds Using Multi-Way KD-Trees[J].Visual Computer,2013,29（1）:69-83.

[4]Hawkins DM.The Problem of Overfitting[J].Cheminform,2004,35（19）:1.

[5]Hellerstein JM.Quantitative Data Cleaning for Large Databases[J]，2008.

[6]Labronici B B,Bentest C,Drummond LM A,et al.Dynamic Screen Division for Load Balancing the Raycasting of Irregular Data[C].IEEE International Conference on CLUSTER Computing and Workshops.IEEE,2009:1-10.

[7]Molnar S,CoxM,Ellsworth D,etal.A Sorting Classification of Parallel Rendering[J].IEEE Computer Graphics&Applications,1994,14（4）:23-32.

[8]Yang JC,Hensley J,Thibieroz N.Real-Time Concurrent Linked List Construction on the GPU[J].Computer Graphics Forum,2010,29（4）:1297-1304.