一种基于sort‑first负载平衡的异质绘制节点并行图形绘制方法

摘要

本发明提供一种基于sort‑first负载平衡的异质绘制节点并行绘制方法，包括：获取绘制集群中的异质绘制节点的性能参数；构建异质绘制节点所构成的绘制集群的性能二叉树；估计屏幕空间内的图元分布；利用异质绘制节点的性能二叉树，确定叶子节点对应的异质绘制节点的绘制区域；根据确定的屏幕划分位置对屏幕进行划分，分配给各个异质绘制节点执行并行图形绘制；各异质绘制节点负载状态不满足负载平衡要求时重新确定屏幕划分位置。本发明考虑了异质绘制节点性能对并行绘制的影响，根据各绘制节点性能来分配任务量。同时对各异质绘制节点绘制时间进行统计，在保证负载平衡的基础上，尽可能减少任务重新分配的次数，提高绘制效率。

说明书

技术领域

本发明属于并行绘制技术领域，特别涉及一种基于sort-first负载平衡的异质绘制节点并行图形绘制方法。

背景技术

当前3D游戏及其它图形交互应用的画面效果越来越细腻真实，输出分辨率对于计算机的图形绘制性能要求也越来越高。当单一计算机的绘制性能难以达到绘制需求时，需要采用更加适合高分辨率的并行绘制方式进行渲染。

目前并行绘制技术主要三种结构：sort-first，sort-middle以及sort-last结构。在这三种绘制结构中，sort-first结构因其对绘制资源利用率高以及网络带宽需求低等优势，成为了搭建并行绘制集群的最佳选择。Roble、Whelan、Whitman、Mueller等人基于屏幕划分精细网格的思想，通过对载入场景的数据进行预处理操作，估算出屏幕的总渲染量，之后将图元数据包围盒与精细网格进行比较获得带权值的网格，进而再进行基于图元数据的屏幕划分。然而这些算法对计算机集群中现有资源有限制，即要求所有渲染处理器节点有相同软硬件配置，比如同样的CPU、GPU、内存、操作系统等，一定程度上限制了相应方法的适用性。文献“Sort-first parallel volume rendering”在面向同质节点的基础上，提出了一种基于屏幕划分精细网格的思想的sort-first动态负载平衡方案，并且方法的改进点主要侧重在体绘制技术上。文献“Equalizer：A Scalable Parallel Rendering Framework”，文献“Practical Parallel Rendering of Detailed Neuron Simulations”中则并没有使用图元数据划分的方式，而是通过对各节点绘制时间进行反馈的方式来实现负载平衡方案，这种通过反馈的方式避免了节点性能差异的问题，但划分准确度不如基于图元数据划分的方法。

可见，上述基于图元数据的负载平衡方法中，对于绘制节点的选取多采用的是基于同质节点的方案，这些方案虽然可以解决sort-first负载平衡问题，但是在实际的应用过程中，因为成本等因素导致绘制节点配置有差异，这会严重影响负载平衡效果，不利于实际环境下的应用。

发明内容

针对现有技术存在的不足，本发明提供一种基于sort-first负载平衡的异质绘制节点并行图形绘制方法。

本发明的技术方案是：

一种基于sort-first负载平衡的异质绘制节点并行绘制方法，包括：

步骤1、获取绘制集群中的异质绘制节点的性能参数；

步骤2、构建异质绘制节点所构成的绘制集群的性能二叉树：依据各异质绘制节点的性能参数，以图形绘制集群中的异质绘制节点为叶子节点，以异质绘制节点的性能参数为叶子节点的权值，自下而上构建性能二叉树，父节点的权值为其叶子节点权值之和；二叉树中节点之间的权值比作为sort-first并行绘制的图形分割比；

步骤3、估计屏幕空间内的图元分布；

步骤4、利用异质绘制节点的性能二叉树，确定叶子节点对应的异质绘制节点的绘制区域；通过性能二叉树对图形分割比进行动态调整，以适应异质绘制节点环境；

步骤5、根据确定的屏幕划分位置对屏幕进行划分，分配给各个异质绘制节点执行并行图形绘制；

步骤6、并行图形绘制过程中各异质绘制节点负载状态不满足负载平衡要求时，返回步骤4重新确定屏幕划分位置。

步骤1所述获取图形绘制集群中的异质绘制节点的性能参数，具体方法如下：

取屏幕中央一块区域A，同时分配给n个异质绘制节点进行绘制，但并不输出图像，仅返回异质绘制节点i的绘制时间ti，绘制时间ti与异质绘制节点i的性能成反比，异质绘制节点i的性能参数其中i＝1，2……n，t_max绘制最慢的异质绘制节点所用的绘制时间。

所述步骤3包括：

步骤3.1、计算待绘制图元数据的3D包围盒，以3D包围盒中的图元数据量为权值，为3D包围盒赋予权值和ID；

步骤3.2、将3D包围盒投影到屏幕空间，转换为2D包围盒，并根据屏幕空间范围进行裁剪，得到各异质绘制节点的图元分布估计结果。

所述步骤4包括：

步骤4.1、分别对当前性能二叉树中各节点的左右叶子节点进行递归操作，判断性能二叉树的节点以及其左右叶子节点是否均为空：如果是，则执行步骤5，否则计算左右叶子节点的权值比值M，执行步骤4.2；

步骤4.2、创建两个列表listA及listB，其中listA初始为空，listB初始为屏幕区域中所有2D包围盒对应的ID；

步骤4.3、在屏幕区域中由左向右进行扫描，当扫描线到达2D包围盒起点，在listA列表中加入该2D包围盒对应的ID；当扫描线到达2D包围盒终点，在listB列表中移除该2D包围盒对应的ID，并计算listA中ID对应的权值之和与listB中ID对应的权值之和的比值K；

步骤4.4、当K大于等于M时，返回当前扫描线位置，左叶子节点的对应的异质绘制节点的绘制区域为屏幕区域起点到扫描线位置；右叶子节点对应的异质绘制节点的绘制区域为扫描线位置到屏幕区域终点，扫描线位置即屏幕分割位置；否则执行步骤4.3。

所述步骤6包括：

步骤6.1、统计各异质绘制节点的绘制时间t，并求出各异质绘制节点的平均绘制时间；

步骤6.2、计算每个异质绘制节点的绘制时间与该异质绘制节点的平均绘制时间之差的绝对值，即每个异质绘制节点的绘制时间误差；

步骤6.3、计算各异质绘制节点的绘制时间误差和Δt即负载状态；

步骤6.3、设绘制时间误差和上限是Δtmax、负载平衡要求为Δt＜Δtmax，并行绘制过程中各异质绘制节点负载状态不满足负载平衡要求即Δt≥Δtmax时，执行步骤4重新确定屏幕分割位置；否则执行步骤5。

有益效果：

本发明是在DPBP自适应负载平衡方法的基础上，提出了一种基于sort-first负载平衡的异质绘制节点并行图形绘制方法，考虑了异质绘制节点性能对并行绘制的影响，根据各绘制节点性能来分配任务量，增加了对于异质绘制节点性能的判断，并采用基于二叉树的方法实现对屏幕任意比例划分，并利用sort-first帧间相似性的特点，减少任务分配次数，提升效率。同时对各异质绘制节点绘制时间进行统计，在保证负载平衡的基础上，尽可能减少任务重新分配的次数，提高绘制效率。在更新策略上，当前方法使用了较为简单的时间统计的方式。

附图说明

图1为本发明具体实施方式中系统环境结构示意图；

图2为本发明具体实施方式中基于sort-first负载平衡的异质绘制节点并行图形绘制方法流程图；

图3为本发明具体实施方式中由8台异质绘制节点组成的绘制集群的性能二叉树示意图；

图4为本发明具体实施方式中采用DPBP算法进行屏幕划分流程图；

图5为本发明具体实施方式中对屏幕空间内包围盒进行裁剪划分示意图；

图6为本发明具体实施方式中步骤6具体流程图；

图7为本发明具体实施方式中负载平衡状态示意图。

具体实施方式

下面结合附图对本发明的具体实施方式做详细说明。

本实施方式基于驻留模式的sort-first体系结构，通过在各个绘制节点存储渲染过程中所需的资源来减少绘制过程中的网络负担。实施本发明基于sort-first负载平衡的异质绘制节点并行图形绘制方法的系统环境如图1所示，包括应用节点、客户端节点和服务器节点。应用节点用于启动图形绘制应用即输入待绘制的图形，服务器节点用于分配和发送绘制指令给异质绘制节点，客户端节点用于进行图形绘制。一组性能不同的客户端节点(异质绘制节点)组成绘制集群。

一种基于sort-first负载平衡的异质绘制节点并行绘制方法，如图2所示，包括：

步骤1、获取绘制集群中的异质绘制节点的性能参数；本步骤主要解决异质节点绘制性能差异问题，将各绘制节点的绘制行能进行参数化，便于后续进行绘制区域划分操作。

任意一个软硬件因素的差异均可能会影响绘制节点的绘制性能，因此在获取绘制节点的性能参数时，通过软硬件差异来计算节点性能复杂且不精确，因而考虑采用绘制时间这一直观参数来简化操作。所述获取图形绘制集群中的异质绘制节点的性能参数，具体方法如下：

取屏幕中央一块区域A，同时分配给n个异质绘制节点进行绘制，但并不输出图形，仅返回异质绘制节点i的绘制时间t_i，绘制时间t_i与异质绘制节点i的性能成反比，异质绘制节点i的性能参数其中i＝1，2……n，t_max绘制最慢的异质绘制节点所用的绘制时间。

步骤2、构建异质绘制节点所构成的绘制集群的性能二叉树；本步骤主要解决异质节点情况下屏幕负载的不等比划分问题，为后续实现异质绘制节点环境下的绘制区域划分做准备。

依据各异质绘制节点的性能参数，以图形绘制集群中的异质绘制节点为叶子节点，以异质绘制节点的性能参数为叶子节点的权值，自下而上构建性能二叉树，父节点的权值为其叶子节点权值之和；二叉树中节点之间的权值比作为sort-first并行绘制的图形分割比；

DPBP(Dynamic Pixel Bucket Partition Algorithm)算法的分割方式决定了其可以通过参数设置实现任意比例的分割，从而适应异质绘制节点划分的情况。依据各绘制节点的性能参数Pi，可以获取任意两异质绘制节点性能参数比，即图形分割比。对于n个异质绘制节点，可以自下而上构建出一棵二叉树来描述每次划分的分割比，其中，叶子节点数量即为实际异质绘制节点数量，叶子节点的权值为性能参数Pi；父节点的权值为其叶子节点权值之和。图3为一种由n＝8台异质绘制节点组成的绘制集群的性能二叉树，其中，叶子节点数量即为实际绘制节点数量，其权值为性能参数Pi；父节点权值为其叶子节点权值之和。采用此二叉树，可以实现对屏幕负载的不等比划分。

步骤3、估计屏幕空间内的图元分布；本步骤主要目的是通过对待绘制图元数据进行预处理，获取屏幕空间内的负载分布情况，用于后续对异质节点进行绘制区域划分。

采用DPBP算法估计屏幕空间内的图元分布，具体方法如下：

步骤3.1、计算待绘制图元数据的3D包围盒，以3D包围盒中的图元数据量为权值，为3D包围盒赋予权值和ID；这个操作在渲染/并行绘制的过程中只执行一次。

步骤3.2、将3D包围盒投影到屏幕空间，转换为2D包围盒，并根据屏幕空间范围进行裁剪，得到各异质绘制节点的图元分布估计结果。

根据屏幕空间范围进行裁剪的具体方法如图5所示：根据需要绘制的屏幕分辨率，建立基于x轴和y轴的两个像素数组，像素数组的长度分别为目标屏幕的长和宽；将每个2D包围盒分别向x轴与y轴投影，同时记录下x、y方向上投影产生的线段端点，不在屏幕区域内的2D包围盒将被删除；部分与屏幕相交的包围盒会被裁剪。

步骤4、利用异质绘制节点的性能二叉树，确定叶子节点对应的异质绘制节点的绘制区域；通过性能二叉树对图形分割比进行动态调整，以适应异质绘制节点环境；本步骤的目的是通过引入异质绘制节点的性能二叉树，解决异质绘制节点环境下各绘制节点负载平衡问题，改善了DPBP算法在异质绘制节点环境下负载平衡效果不佳的问题。

采用DPBP算法确定叶子节点对应的异质绘制节点的绘制区域，如图4所示，具体方法如下：

步骤4.1、分别对当前性能二叉树中各节点的左右叶子节点进行递归操作，判断性能二叉树的节点以及其左右叶子节点是否均为空：如果是，则执行步骤5，否则计算左右叶子节点的权值比值M，执行步骤4.2；

步骤4.2、创建两个列表listA及listB，其中listA初始为空，listB初始为屏幕区域中所有2D包围盒对应的ID；

步骤4.3、在屏幕区域中由左向右进行扫描，当扫描线到达2D包围盒起点，在listA列表中加入该2D包围盒对应的ID；当扫描线到达2D包围盒终点，在listB列表中移除该2D包围盒对应的ID，并计算listA中ID对应的权值之和与listB中ID对应的权值之和的比值K；

步骤4.4、当K大于等于M时，返回当前扫描线位置，左叶子节点的对应的异质绘制节点的绘制区域为屏幕区域起点到扫描线位置；右叶子节点对应的异质绘制节点的绘制区域为扫描线位置到屏幕区域终点，扫描线位置即屏幕分割位置；否则执行步骤4.3。

步骤5、根据确定的屏幕分割位置对屏幕进行划分，分配给各个异质绘制节点执行并行绘制；

步骤6、并行绘制过程中各异质绘制节点负载状态不满足负载平衡要求时，返回步骤4重新确定屏幕划分位置。

如图6所示，所述步骤6包括：

步骤6.1、统计各异质绘制节点的绘制时间t，并求出各异质绘制节点的平均绘制时间；

步骤6.2、计算每个异质绘制节点的绘制时间与该异质绘制节点的平均绘制时间之差的绝对值，即每个异质绘制节点的绘制时间误差；

步骤6.3、计算各异质绘制节点的绘制时间误差和Δt即负载状态；

步骤6.3、设绘制时间误差和上限是Δtmax、负载平衡要求为Δt＜Δtmax，并行绘制过程中各异质绘制节点负载状态不满足负载平衡要求即Δt≥Δtmax时，执行步骤4重新确定屏幕分割位置；否则执行步骤5。

本实施方式中，执行基于sort-first负载平衡的异质绘制节点并行绘制方法所达到的负载平衡状态如图7所示，其中的实线表示每一异质绘制节点(节点1、节点2、节点3、节点4)的绘制时间，点状线表示所有异质绘制节点对每一帧的平均绘制时间，虚线表示当前帧和下一帧的分隔线，第0帧各异质绘制节点的绘制时间误差和Δt＝0，第1帧各异质绘制节点的绘制时间误差和Δt＝5，第2帧各异质绘制节点的绘制时间误差和Δt＝6，第3帧各异质绘制节点的绘制时间误差和Δt＝6，第3帧各异质绘制节点的绘制时间误差和Δt＝9，第4帧各异质绘制节点的绘制时间误差和Δt＝0。