基于学习的复杂并行绘制系统负载平衡算法研究

Parallel rendering system is the fundamental way to solve the conflict between the requirements of the computation power of large real-time applications (such as high-end training and simulation system, interactive entertainment system and so on) and the computation power of single GPU. The project is aim to address the load balancing problem on system level for complicated parallel rendering system containing multiple algorithms and unpredictable rendering tasks. Different from the traditional load balancing algorithm which is based on the mechanism of "detecting load unbalance + doing something to restore the load balancing", our project tries to accumulate the acknowledge of load estimation from multiple times of system running by an off-line machine learning process. The proposed method can break the assumption that the rendering cost cannot be accurately estimated before the rendering is finished and achieve load-balancing at any time during the system running. Two fundamental issues have to be addressed to achieve the above goal: 1) How to extract the main factors from all possible factors which might influence the workloads of rendering tasks? 2) How to determine the internal relationships between the workload and these main factors? In this project, we attempt to use the rough set theory to address the first problem, and employ the artificial neural network to represent the relationships between the workload and the factors extracted from the first problem.

并行绘制系统是解决高端训练仿真系统，基于交互的娱乐系统等大型实时应用对计算能力的要求和单个GPU计算能力之间的矛盾的根本方法。本课题针对包含大量复杂算法和突发绘制任务的并行绘制系统，从系统层面研究其负载平衡算法。与以往负载平衡算法主要依赖"检测负载失衡+补偿操作恢复负载平衡"这种事后补救的方式不同，本课题尝试从系统的多次反复运行中，通过离线机器学习的方式，积累绘制任务负载估计的知识，最终突破以往负载平衡算法关于"在本帧绘制完成之前无法准确知道其绘制开销"的假设，实现系统在任意时刻的负载平衡。在实现如上目标的过程中，需要解决两个核心问题：1）如何从所有的可能因素中找出影响负载的主要因素；2）如何确定这些主要因素和负载之间的函数关系。我们试图通过机器学习中的粗糙集技术来探索影响负载的主要因素，并通过人工神经网络技术来表达这些因素和负载之间的函数关系。

近年来，游戏、仿真训练、虚拟现实应用对绘制真实感的要求越来越高；同时，显示系统在输出分辨率和刷新频率也出现了跳跃式发展。这些因素都对绘制系统的效率提出了严峻挑战。并行绘制是解决单机绘制能力不足和现实应用对绘制真实感、输出分辨率和帧率要求不断提高之间矛盾的一种有效手段。但现代绘制系统包含大量复杂算法，使得屏幕上不同区域负载严重不均衡；同时，频繁的用户交互操作和交互行为本身的多样化，也使得帧间的负载相关性被破坏，从而使得并行绘制系统的负载均衡成为一个很困难的问题。本课题提出通过机器学习的方法来解决这个问题，其基本思路是按屏幕划分的方式来进行负载划分，通过回归森林的方法来建立绘制参数和绘制时间之间的非线性关系。然后在绘制系统运行阶段，使用回归森林对屏幕子区域的绘制时间进行预测，最终找到负载平衡的屏幕划分方式。在如上过程中，我们主要解决了这样一些关键问题：1.在数据采集阶段，我们需要在训练集规模可控的前提下，采集尽可能有代表性的训练数据。我们提出将用户的漫游模式表达为一个概率密度分布函数，然后根据此函数来生成训练数据的视点信息；此外，我们还提出使用二叉树的方式来生成屏幕的划分方式，以进一步控制训练集的规模。2.在建立回归森林阶段，我们使用特征工程的方法，来对得到的原始特征进行优化组合，以提高回归森林的预测质量；3.在并行绘制系统运行阶段，我们提出为回归森林的每棵树的预测结果计算一个基于概率质量的相异度测量方法的置信度，并在此基础上对所有树的预测结果进行加权平均。同时，在回归森林预测屏幕子区域的绘制时间的基础上，我们还提出一个“预测-修正”的迭代算法，用于快速找到一个负载平衡的屏幕划分方式。为了验证我们的算法，我们实现了一个包含多个绘制算法的绘制系统，实验证明，我们提出的基于回归森林的负载划分方法，能比基于帧间相关性的方法获得更好的负载均衡。