基于XGBoost 的四分屏绘制系统负载平衡算法

贾文娟

（四川大学计算机学院，成都610065；四川川大智胜软件公司，成都610065）

0 引言

随着人工智能技术应用越来越广泛，3D 游戏、虚拟现实（Virtual Reality，VR）等基于实时交互的娱乐系统也随之飞速发展起来，很多应用能够实时地生成高质量的画面，例如3D 游戏《传奇世界》以及VR 游戏《弓箭大师》，其真实的场景和流畅精致的画面给玩家带来视觉享受。HTC 最新发布的穿戴式VR 设备Vive Pro[1]，分辨率为2880×1600 且具有90Hz 的刷新率，每秒高达4 亿像素点的绘制能力。对于复杂场景的绘制并输出高质量的画面，对计算资源提出了更高的要求，目前GPU 的计算能力仍然无法满足对计算能力的需求。

并行绘制[2]是应对上述问题的一种切实可行的解决方案。它主要是将绘制总任务划分为若干可独立执行的子任务，利用多个绘制节点并行地对各子任务进行绘制，然后收集所有并行绘制节点的绘制结果并将结果进行拼接，形成最终的绘制结果。NVIDIA 公司提供的多个图形处理单元（GPU）并行绘制驱动SLI[3]和AMD 公司CrossFire[4]技术是目前两种主流的并行绘制技术。

并行绘制系统中的主要问题是负载平衡[5]，其主要是将绘制任务均匀地划分给各绘制节点，以此减少用于同步各绘制节点的绘制结果花费的额外开销，能够保证在相同的时间内，绘制系统可输出更多的帧提高画面质量和资源利用率。如果负载失衡，并行绘制输出动画的帧率会下降，造成卡帧等现象，用户体验会严重下降。

对于复杂场景的并行绘制系统中，通常会包含很多模型和绘制算法，对任一帧的绘制，其绘制之前无法确定其绘制开销，所以要实现运行时的负载平衡非常困难。已有的方法是通过增加负载失衡检测，并在负载失衡后进行补偿操作来尽快恢复负载平衡。这种方法会带来额外的通信开销，影响实时绘制系统的运行效率。从本质上讲，这种“检测+补偿”的方法不能从根本上解决负载失衡的问题。传统的负载平衡算法中，主要是基于帧间相关性原理，虽然简单高效并可应用于实时系统中，但是在交互的实时娱乐系统中，会造成负载的分布发生剧烈的变化，此时帧间相关性被打破，导致上述算法失败。

本文提出一个基于机器学习的四分屏绘制系统负载平衡算法。基本思想是将绘制任务在屏幕空间划分为四个可独立完成且负载量相当的子任务来实现负载平衡。关键在于建立一个机器学习模型，对绘制帧在特定的子屏幕下的负载进行准确且高效的预测。本文将负载预测问题抽象为机器学习中的回归问题，同时考虑到复杂场景中的绘制参数较多所带来的一系列问题，选择XGBoost 算法作为学习和预测负载的机器学习模型。

1 相关工作

在并行绘制系统中，根据负载的分配方式在运行时是否改变，可将负载平衡策略分为静态和动态两类。

静态负载平衡算法，通过某种固定的方式对负载进行划分，并且在程序运行过程中保持该划分策略不变。例如，Liu[6]等提出的静态负载平衡算法，该方法通过将绘制体元划分为很多细小的3D 体元块，并且将所有体元块按照一种固定的方式划分给各绘制节点，来实现负载平衡。这种方法虽然简单且容易实现，但适应性差。现在已经基本不被使用。

动态负载平衡算法在运行时根据不同负载分布调整负载的划分方式，来达到负载平衡，其良好的适应性使其得到迅速发展并被广泛应用。例如，Erol[7]等提出并应用于Equalizer[8]的CSLB 算法，是一种基于workstealing 调度策略的算法。在该算法中，并行绘制节点共享绘制图形资源，当某绘制节点完成自己的绘制任务以后，在任务量较多的绘制节点中“steal”若干任务，以此平衡各节点间的负载，实现负载平衡。这种方法会带来额外的数据网络传输开销，所以不适用于实时并行绘制系统中。Yin[9]等提出了基于LDM（Load Distribution Map）的动态负载平衡算法，利用帧间相关性的思想，将生成的负载分布图视作下一帧的负载分布，从而进行负载划分。上述提到的动态负载平衡方法都是基于帧间相关性的思想，虽然简单高效，但是不适用于频繁交互的实时系统中。

机器学习近年来被广泛应用于计算机图形图像中，主要解决复杂的计算过程以换取效率上的提升。文献[8]使用机器学习中的线性回归方法进行了人脸识别，文献[10,11]运用梯度提升决策树算法对生态问题进行了分析和预测。不仅如此，文献[12]中支持向量机的表现也十分出色，在交通运输时间的预测更是达到了99.4%的预测精准度。

近年来，有学者将XGBoost 应用到计算机图形图像领域。例如，Ren[13]等将XGBoost 应用到图像分类上，可对图像特征进行识别。

2 绘制系统的负载平衡算法

2.1 传统四分屏负载平衡算法

（1）静态均分负载平衡算法

静态的负载平衡算法中绘制任务以一种固定的方式进行划分，并且在程序运行过程中保持该划分策略不变。基本思想是根据绘制节点的数量将负载进行划分，保证各个节点负载工作量尽可能接近。特点是简单但适应性差并且很少被实际系统所采用。

（2）基于帧间相关性的动态负载平衡算法

常见的一种动态负载平衡算法主要是利用帧间相关性这一原理，评估节点负载大小主要是根据前一帧的绘制时间以及绘制节点参数。一种改进的基于帧间相关性原理的负载平衡算法根据前一帧的平均绘制时间和当前帧的绘制时间提出的一个时间预测模型[14]，由方程（1）所示：

其中，ti+1表示第i+1 帧的预测绘制时间，ti表示第i帧的绘制时间，Average（x,i）表示第i 帧前已绘制的前x帧的平均绘制时间，Average（x,i+1）表示第i+1 帧前已绘制的前x 帧的平均绘制时间。方程（1）的展开式为：

2.2 基于XGBoost的四分屏负载平衡算法

Boosting 思想是运用梯度提升的方法进行每一轮的迭代最终组建出强学习器。因此，此方法导致了算法的运行对运行时间的开销较大，需要生成一定规模的树后才能达到具有实用性的准确率。尤其是数据集大且复杂时，运行过多的迭代运算使得当前的算力是算法应用的最大瓶颈。针对这一问题，华盛顿大学的陈天奇博士开发出了XGBoost（eXtreme Gradient Boosting），它是Gradient Boosting Machine 的一个实现，并在原有的基础上加以改进，从而极大地提升了模型训练速度和预测精度。可以说，XGBoost 是Gradient Boosting 的高效实现。

其中，yi表示第i 个样本的标签真实值，i表示算法预测值。l(i-yi)表示第i 个样本的预测误差。表示k 个树的复杂度函数，复杂度越低，泛化能力越强。其表达式为：

T 表示叶子节点的个数，w 表示节点的数值。γ 作为叶子节点的系数使XGBoost 在优化目标函数的同时相当于做了预剪枝。λ 作为w 平方模的系数也是要起到防止过拟合的作用。

3 数据集

本文数据集采集自四分屏并行绘制系统中，其选用的绘制算法为基于LLL（Light Linked Lists）[15]的静态场景算法Deferred Shading，场景图如图1 所示。

图1 Deferred Shading算法场景图

图2 绘制节点切分方式

为了模拟真实的应用场景，本文通过随机跳转光源的方式模拟真实的用户交互行为，使得绘制帧突变更加强烈。绘制系统中采集的绘制参数及其对应的绘制时间构成数据集，训练集有2,422,298 帧，测试集有286,093 帧。每帧图像由4 个绘制节点并行绘制后拼接而成，屏幕切分方式如图2 所示。每一个绘制节点均拥有独立的16 个绘制参数，绘制参数含义如表1所示。

4 实验

本文实验平台为Intel Xeon CPU E3-1231 V3@3.4GHz，32GB DDR3 内存以及NVIDIA GeForce GTX 1080 GPU。算法基于scikit-learn 机器学习库。算法预测均方误差对比如表2 所示。

表1 绘制参数定义

表2 算法均方误差对比

从表2 可以看出，在绘制帧突变较为剧烈时，基于帧间相关性原理的动态负载平衡算法无法准确预测绘制时间，相比于XGBoost 算法有较大误差。使用XGBoost 算法根据绘制参数进行的绘制时间预测较为准确。算法的测试集对比曲线如图3 所示。

图3 算法测试集对比曲线

XGBoost 算法相比于基于帧间相关性原理的动态负载平衡算法的优势在于能够根据当前帧的绘制参数预测下一帧的负载大小，以用于判断负载是否失衡。实验结果证实了XGBoost 具有更高的预测精确度。机器学习算法预测性能优势相比于传统算法依然具有很好的工程应用价值。

5 结语

本文针对基于交互的实时应用，提出了基于XGBoost 的四分屏并行绘制系统的负载平衡算法，主要是学习绘制帧的参数与负载之间的非线性对应关系，从而基于学习模型对负载的预测对绘制任务进行比较平衡的分配，最终实现负载平衡。绘制时间的预测准确性直接影响负载是否平衡。本文提出一种基于XGBoost 的机器学习模型，针对四分屏并行绘制系统的绘制参数进行了绘制时间预测。与传统的基于帧间相关性原理的动态负载平衡算法的绘制时间进行了对比实验，实验表明基于XGBoost 算法的预测性能较好。综上所述，基于XGBoost 的机器学习算法能够帮助并行绘制系统进行负载调节，以获得较优的绘制性能。