基于贪心策略的多结点并行光线跟踪负载均衡算法

刘云彪，陈纯毅，胡小娟，邢琦玮，杨华民

基于贪心策略的多结点并行光线跟踪负载均衡算法

刘云彪，陈纯毅，胡小娟，邢琦玮，杨华民

(长春理工大学计算机科学技术学院，吉林 长春 130022)

为了提高利用光线跟踪集群绘制生成高分辨率复杂场景画面的并行度，提出基于贪心策略的多结点并行光线跟踪负载均衡算法。首先根据GPU的并行特性将屏幕空间划分成若干正方形图像块，并基于移动物体球形包围体在屏幕空间的投影构建二值绘制时间影响度图。然后依据时空相关性利用上一帧图像块耗时和二值绘制时间影响度图建立渲染任务队列，通过两步负载均衡实现多渲染结点任务的动态分配。最后进行了实验验证和分析，结果表明该方法具有良好的负载均衡效果，在5个渲染结点的绘制效率最高能提升4.96倍。

光线跟踪；高分辨率图像；负载均衡；多结点绘制；贪心策略

光线跟踪技术[1]是计算机图形学中一个重要研究分支，目前在影视制作、虚拟现实、医学研究、辅助设计等领域发挥重要作用[2-3]。光线跟踪能够呈现其他渲染方法难以实现的反射、折射和阴影等效果，并且光线跟踪算法容易实现。然而，光线跟踪为生成更加真实的图像需要从视点发射千万数量级的光线，并根据场景、光源和材质等信息决定是否继续跟踪光线，最终得到渲染图像[4]。因此，光线跟踪的耗时庞大，难以应用于复杂场景的实时绘制。

针对光线跟踪绘制速率的提升，现存的研究大致有2个方向：①加速结构的构建；②并行执行。空间加速结构能够减少光线与几何物体的基础单元(三角形、球体等)在求交过程花费的时间。通过如层次包围盒(bounding volume hierarchy，BVH)[5]、八叉树[6]和KD树[7]等加速结构降低了光线跟踪算法对于硬件性能的依赖，且保证光线跟踪渲染效果的同时减少部分绘制时间，实现简单场景的实时绘制效果，但不能满足复杂场景实时绘制速率的要求。由于光线追踪发射的光线相互独立，理论上能够在并行处理器上同时计算出所有像素的颜色值。实际上GPU虽然具有强大的并行处理能力[8]，但仍不能实现高分辨率图像所有像素的同时计算。在这种情况下，使用多GPU渲染是一种可行的提升渲染速度的解决方案[9-10]。

为实现光线跟踪集群渲染复杂场景，本文提出一种基于贪心策略的多结点光线跟踪负载均衡算法，首先构造二值绘制时间影响度图，构造方法结合球形包围体和空间投影算法；其次利用上一帧图像块的绘制时间和二值绘制时间影响度图建立任务队列；结合贪心策略进行第一步负载均衡，在不影响绘制效率的情况下，得到受移动物体影响的图像块绘制时间；最后将剩余任务再次利用贪心策略进行第二步负载均衡，提高复杂场景的绘制效率。

1 相关工作

现有的多结点并行光线跟踪方法包括：图像分解并行和场景几何分解并行。图像分解并行是每个渲染结点负责图像的部分区域，而场景数据通常复制到每个渲染结点的内存中。场景几何分解并行是每个渲染结点负责场景的部分数据，光线在渲染结点间传播[11]。由于场景几何分解并行方法存在数据一致性问题以及数据传输开销大等缺点，本文采用图像分解并行方式。多结点并行绘制中整个任务的绘制时间由耗时最长的结点决定，有负载均衡算法的渲染集群要优于无负载均衡算法的渲染集群[12-13]，因此负载均衡算法是 一个重要的研究分支。

负载均衡[14-15]的研究有很多，张正昌等[16]提出基于warp线程优化的动态调度策略，提高算法在BVH阶段的效率，实现GPU并行优化算法在光线跟踪的应用，结合GPU的计算特性实现加速效果，却未对多结点渲染方式进行研究。CHEN等[17]提出基于任务的动态负载均衡算法，利用队列机制在多个GPU有效实现负载均衡效果，提升计算效率，但是通信频繁。COSENZA等[18]利用连续计算阶段之间的时间一致性，将网格式计算映射到处理器集群上。通过预测二叉树划分渲染任务到各个独立的处理器，并且表明图像块的数量影响系统性能，但是仅给出绘制速率提升未对负载均衡效果进行分析。以及文献[11]提出通过光栅化渲染方式得到像素击中点的相关信息，估算出每个像素的耗时，最终生成预测耗时图。然后利用KD-Tree将预测耗时图分成多个耗时相近的渲染任务，分配到各个渲染结点进行光线跟踪，最后采用工作窃取(work-stealing)实现负载均衡，该方法的负载均衡效果良好，但是需要设置的参数过多不利于算法的通用性。针对上述问题，本文在考虑GPU并行计算特性的同时，设计了新的负载均衡方法：一方面采取集中式负载均衡减少数据传输量；另一方面，通过两阶段结合贪心策略的任务分配，提高负载均衡效果。

2 算法原理与实现

2.1 算法思想概述

本文算法基于光线跟踪框架，采用BVH加速结构，利用CPU作为控制结点实现负载均衡算法，GPU作为渲染结点执行全局光照下场景渲染任务。负载均衡算法的核心内容可分2个部分：屏幕空间划分和负载均衡。屏幕空间划分，将屏幕空间划分成若干正方形图像块；负载均衡，在一帧图像块绘制时间分配渲染任务，并提出二值绘制时间影响度图解决快速移动物体产生的影响，通过2步负载均衡实现渲染任务的分配。算法工作流程如图1所示。

2.2 屏幕空间划分

屏幕空间划分的方式对多结点并行绘制有着重要的影响，为加快绘制速率实现负载均衡效果，本文选取正方形作为屏幕空间划分的单元。利用正方形划分屏幕空间会存在剩余空间不足以划分的情况，此时需要将剩余部分归入邻近的图像块。屏幕空间块划分过程如图2所示。选择正方形作为屏幕空间划分的单元是由于正方形相对于其他相同面积图形其对角线长度最短，图像块跨越多个几何物体可能性最低。因此，图像块包含几何物体的属性尽可能一致，能减少并行光线跟踪分支情况，降低绘制时间。

图1 负载均衡工作流程图

图2 屏幕空间块分块示意

GPU在并行计算时，利用计算耗时与延迟(准备执行下一条指令所需的时钟周期数量)重叠，达到隐藏延迟的效果。所有的warp[18]调度器在延迟期间的每个时钟周期都有指令要发出时，能够最大化GPU的资源利用率。因此，GPU处理足够多的并行线程能够有效隐藏延迟，充分发挥GPU的并行计算性能以及最大化吞吐量。如图3所示，并行线程指令运行流程。其中，表示GPU执行warp最大的数量，H2D表示数据从主机到设备的传输周期，Kernel表示执行时钟周期，D2H表示数据从设备到主机的传输周期。

图3 并行线程指令运行流程

2.3 二值绘制时间影响度图

场景中视点或物体在一定速度范围内移动，根据时空相关性同一图像块相邻两帧的绘制时间相近，但屏幕空间存在快速移动的物体时，同一图像块相邻两帧的绘制时间可能存在较大的差异。为有效实现负载均衡，提出二值绘制时间影响度图。进行精细计算的时间成本过高增加负载均衡算法时间，利用简单的二值图(非0即1)描述移动物体对图像块绘制时间的影响。二值绘制时间影响度图通过移动物体的球形包围体在屏幕空间的投影判断移动物体对下一帧图像块绘制时间的影响，其构造方式表述为

其中，C为图像块绘制时间产生影响的阈值；P为相交面积与图像块面积的比值；I为移动物体对该图像块的影响。如图4所示，将球形包围体投影到屏幕空间并且计算物体对图像块绘制时间的影响，其中数值1表示移动物体对图像块绘制时间产生了影响，而数值0则表示未产生影响。

影响绘制时间的图像块有2种，重新投影绘制时间产生影响的图像块和上一帧绘制时间受影响的图像块。如图5所示，物体移动时二值绘制时间影响度图的变化。

图5 二值绘制时间影响度图变化

2.4 负载均衡

负载均衡的主要目的在于实现各个渲染结点绘制时间的均衡，依据本文的屏幕空间划分方法，绘制高分辨率的图像时大多数图像块内执行线程数量相同，但不同的图像块绘制几何物体不同，绘制时间可能存在较大的差异。本文的负载均衡算法结合了贪心策略、消息队列机制以及二值绘制时间影响度图，通过分配到渲染结点不同数量的图像块，使渲染结点达到负载均衡的效果。本文将图像块分成绘制时间受到影响的图像块和未受到影响的图像块2类。首先控制结点创建渲染任务队列0，根据二值绘制时间影响度图将绘制时间产生影响的图像块顺序存入队列0，其次将剩余图像块根据上一帧的绘制时间(第一帧将面积作为上一帧绘制时间)按照降序存入队列0，如图6(a)所示，屏幕空间分成6个图像块，图像块的数字表示该图像块上一帧的绘制时间，*表示绘制时间产生影响的图像块。随后将渲染任务队列中的任务分配到渲染结点，由于绘制时间影响图是描述移动物体是否对图像块绘制时间产生影响，无法判断具体影响的程度，因此将绘制时间产生影响的图像块和部分绘制时间未受影响的图像块同时分配到渲染结点。绘制时间产生影响的图像块按数量平均分配，绘制时间未受影响的图像块根据贪心策略分配。利用贪心策略为渲染结点分配渲染任务队列中的元素过程可用式(2)和式(3)表示

其中，为渲染结点的数量；为渲染耗时最小的渲染结点序号；t为结点执行已分配任务所需的时间；为渲染任务队列队首图像块的绘制时间。即分配渲染任务队列队首的图像块到当前耗时最小的渲染结点。如图6(b)所示执行第1步负载均衡，计算各个渲染结点已分配未受影响图像块的耗时，渲染结点1和2耗时分别为0和28，耗时最少的渲染结点是1，此时控制结点分配0队首图像块到1，然后渲染结点执行控制结点分配的图像块并记录其绘制时间，同时计算下一帧该图像块的绘制时间影响情况。当渲染结点处理完所有绘制时间受影响的图像块并且正在处理未受影响图像块时，控制结点根据返回的信息可以计算出渲染结点已分配任务的耗时，然后利用贪心策略分配剩余图像块到渲染结点，如图6(c)所示，执行第2步负载均衡，根据受影响图像块的绘制时间，计算出渲染结点1和2的耗时分别为30和35，然后按照负载均衡算法分配下一个图像块到耗时最小的渲染结点1，进行上述算法直到渲染任务队列0为空，本文负载均衡算法的具体步骤为：

步骤1.构造渲染任务队列0，设置绘制时间受影响图像块数量，阈值，设绘制时间受影响图像块次数为，绘制时间受影响图像块标志符。

步骤2.若>，图像块面积作为绘制时间，并且令=0。

步骤3. 根据图像块上一帧渲染耗时(第一帧将面积作为渲染耗时)按降序存入渲染任务队列0，令=0。

步骤4.将队列0前个图像块顺序分配到渲染结点的同时利用贪心策略分配部分图像块到渲染结点。

步骤5.若=，执行步骤6，否则执行步骤7。

步骤6.根据渲染结点已分配任务的耗时，利用贪心策略分配剩余图像块到渲染结点。

步骤7. 接收渲染结点发送的信息，令=+1。若<=，令=1，更新结点已分配任务耗时，否则令=0。

步骤8.若下一帧该图像块绘制时间受影响，令=1，绘制时间用无穷大代替。

步骤9.若=1，则下一帧该图像块绘制时间受影响。

步骤10.若为最后一个图像块，算法结束，否则执行步骤7。

图6 负载均衡算法

2.5 数据传输

数据传输是光线跟踪负载均衡算法的重要组成部分，影响负载均衡算法的执行时间。为降低光线跟踪负载均衡算法的耗时，本文采用多线程将数据传输时间隐藏在渲染任务执行时间。如 图7(a)所示，渲染结点以串行方式执行渲染任务和数据传输的运行流程，整个过程的耗时等于全部指令耗时相加。如图7(b)所示，采用多线程方式执行渲染任务和数据传输，由于数据接收部分仅包括图像块的起始坐标、终止坐标和标志符(判断是否更新渲染场景的相关数据)，数据接收时间可忽略不计，因此以串行方式进行数据接收和任务执行。然后采用多线程方式将发送数据和任务执行时间重叠，能够有效降低负载均衡算法时间，提升绘制速率。多线程执行渲染任务的具体步骤如下：

(1) 线程1。

步骤1.创建缓冲区Buffer1和Buffer2用于存储渲染结果，创建线程2用于向控制结点发送渲染结果。

步骤2.接收渲染任务信息。

步骤3.当标志符为真，则更新渲染场景数据。

步骤4.执行渲染任务，若执行次数为奇数将渲染结果存入Buffer1，否则存入Buffer2。

步骤5.向线程2发送信号，执行步骤2。

(2) 线程2。

步骤1.若接收到线程1的信号，则执行步骤2。

步骤2. 若执行次数为奇数，传输Buffer1的渲染结果，否则传输Buffer2的渲染结果。执行步骤1。

图7 任务运行流程

3 实验结果与分析

3.1 实验设备及参数设置

实验环境由一个控制结点和多个渲染结点组成，控制结点的配置：Intel(R) Xeon(R) E3-1225 v3 @ 3.20 GHz CPU，4 GB内存和NVIDIA Quadro K600 GPU。渲染结点的配置：Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz，8 GB内存和NVIDIA Quadro P4000 GPU。使用NVIDIA CUDA SDK 10.1和NVIDIA OptiX SDK5.0.1作为开发工具。其中K600有172个CUDA核心，P4000有1 792个CUDA核心。图像分辨率统一设置为4096×2160像素，光线最大递归深度设为5。实验场景如图8所示，其中场景1和2为静态场景，场景3~6为动态场景。

图8 实验场景

3.2 负载均衡效果

本文算法的目的在于实现多渲染结点的负载均衡，为判断负载均衡效果引入绘制时间归一化标准差，计算方法为

表1为静态场景在4个渲染结点时不同分块情况下的平均归一化标准差，其中在场景1进行2组实验，分别是在光源数量为50和150的情况下进行不同分块的实验，光源位置在场景上方。场景2的实验是在125个光源下进行，其中 25个光源在场景上方，100个光源在窗外。从 表1可以看出，场景1在150个光源下比50个光源的平均归一化标准差大。单个像素绘制时间增加会导致图像块绘制时间差异变大，负载均衡效果降低。虽然场景2的绘制时间少，但是没有50个光源下场景1的负载均衡效果好，因此决定负载均衡效果的主要因素是图像块绘制时间的差异。

表2是静态场景在5个渲染结点时不同分块下的平均归一化标准差，可以看出图像块分辨率为480×480时，由于图像块之间绘制时间相差较大，并且总体图像块数量少，因此该分辨率比其他图像块分辨率的负载均衡效果差。随着图像块分辨率的减小，图像块之间的绘制时间差异降低，并且可分配到单个渲染结点的图像块数量增加，所以平均归一化标准差随图像块数量增加而降低，能够有效实现负载均衡效果。

对比表1和表2，若图像块分辨率较高，可分配到单个渲染结点图像块数量少，相同场景在相同分块情况下5个渲染结点比4个渲染结点的平均归一化标准差大。随着图像块分辨率的降低，图像块的总体数量会增加，并且单个图像块绘制时间降低，不同数量结点的平均归一化标准差越接近。因此图像块分辨率为384×384时，不同场景的平均归一化标准差基本平稳，图像块分辨率降低对负载均衡效果提升的收益降低。

表1 静态场景在4个渲染结点时不同分块情况下的平均归一化标准差对比

表2 静态场景在5个渲染结点时不同分块情况下的平均归一化标准差对比

表3以5个渲染结点绘制静态场景，并且视点以每帧0.5°，1.0°和1.5°的速度旋转时的平均归一化标准差。当视点旋转速度加快，图像块内物体变化的速度提升，因此图像块绘制时间的变化加剧，使用上一帧图像块绘制时间作为当前帧图像块绘制时间的偏差增加，所以随着视点旋转速度的增加，负载均衡的效果降低。从表3可以看出当视点以相同速度旋转，图像块分辨率降低能够提升负载均衡效果。对比表3中场景1和场景2，在相同图像块分辨率情况下视点以相同速度旋转，场景1较场景2的平均归一化标准差小，因此场景中存在反射现象对绘制时间的影响 更大。

表3 静态场景在视点旋转时不同分块情况下的平均归一化标准差对比

表4以5个渲染结点绘制动态场景，并且视点以每帧0.5°旋转时不同分块情况下的平均归一化标准差。在相同图像块分辨率的情况下，场景3和场景4的平均归一化标准差低于场景5和场景6，进一步证明场景中存在对移动物体的反射会对负载均衡效果产生影响。而场景6比场景5的平均归一化标准差小是因为反射到移动物体区域所在图像块绘制时间和上一帧该图像块绘制时间更接近。场景3和场景4在图像块分辨率降低时负载均衡效果的提升比场景和场景6的提升更高，该情况的出现说明场景5和场景6会对移动物体反射。

表4 动态场景在视点旋转时不同分块情况下的平均归一化标准差对比

3.3 传输时间

本文渲染图像的分辨率为4096×2160，图像共有33.75 M字节，传输一帧图像需要大量的时间。因此采用多线程方式降低传输时间。图像块绘制时间大于其传输时间，因此利用多线程将传输耗时隐藏在渲染任务执行时间内，总传输时间等于最后一个图像块的传输时间。多线程传输耗时如图9所示，随图像块数量增加数据传输耗时隐藏越多。能够有效降低传输耗时在负载均衡算法耗时的比例，提升绘制效率。

图9 渲染结果传输时间

3.4 图像块分辨率的选取

图像块数量的增加能够提升负载均衡效果以及降低渲染结果传输时间，但GPU隐藏延迟时间降低，因此需要考虑图像块尺寸。为最大化提升渲染效率本文图像块尺寸利用式(5)确定，即

其中，为图像宽度；为图像高度；为图像高度与图像块边长的比值；为渲染结点的数量；为平均分配到渲染结点图像块的数量。实验参数设置：=4096，=2160，=10。确定距离最近且大于×的值，然后通过得到图像块尺寸。本文在CUDA架构实现GPU并行计算，warp (由32个线程组成)是GPU执行指令时的调度单位，若warp不足32个线程，则需要填充至32个线程。填充的线程占据一定资源但对任务没有任何贡献，因此保证图像块数量相同条件下，图像块边长像素数是32的倍数，能够减少warp线程填充情况，有利于资源的充分利用[19]。

3.5 算法对比与分析

本文与静态和动态负载均衡算法[20]进行对比。共进行4组对比实验，实验参数见表5。由于对比实验是在5个渲染结点进行，因此通过式(5)计算得到图像块分辨率为384×384。本文算法属于图像分解并行，而静态负载均衡算法和文献[20]算法也均属于图像分解并行，因此通过4组对比实验能够体现本文算法的性能。

表5 对比实验参数

如图10所示，3种负载均衡算法的对比实验。可以看出本文算法在静态场景和动态场景中都能有效实现负载均衡效果，并且本文算法比静态负载均衡算法和文献[20]的负载均衡算法的效果更好。本文算法的归一化标准差也更加平稳，不会出现大幅度的波动。

图11为3种负载均衡算法渲染效率提升的对比。为减少实验误差，对比实验采用50帧绘制图像性能提升的平均值。可以看出本文算法在不同场景下的性能提升均较另外2种负载均衡算法的提升高，并且本文算法在动态场景的效率提升更明显，能够最大化利用计算资源。

图10 归一化标准差对比实验

图11 绘制效率提升

4 结束语

本文提出多结点并行光线跟踪负载均衡算法。依据GPU的并行特性设计屏幕空间的划分方法，采用正方形作为分块单元，将屏幕空间划分成若干正方形图像块。根据连续计算的时间相关性利用上一帧图像块的渲染耗时以及移动物体对图像块绘制时间影响构建渲染任务队列，然后依据贪心策略将图像块队列的渲染任务分配到渲染结点，由渲染结点执行对应的渲染任务，实现多结点动态任务分配，并且在渲染结点采用多线程将数据传输时间和计算时间重叠，能够隐藏传输时间，提升绘制效率。实验结果表明本文算法具有良好的扩展性和通用性，在5个渲染结点情况下，静态场景绘制效率能够提升4.964 1倍，视线移动的静态场景能够提升4.921 9倍，视线移动的动态场景能够提升4.835 2倍，有效实现负载均衡效果。

尽管本文算法能够有效实现负载均衡效果，但依旧存在改进空间：①构造二值绘制时间影响图的方法，本文采用球形包围体投影判断对图像块绘制时间的影响，在后续工作中将使用更精确且简单的方法得到镜面对移动物体反射的情况。②将算法进行扩展延伸，应用于路径跟踪中。

[1] WHITTED T. An improved illumination model for shaded display[J]. Communications of the ACM, 1980, 23(6): 343-349.

[2] 卢贺齐, 鲍鹏, 冯结青. 基于OpenCL的实时KD-Tree与动态场景光线跟踪[J]. 计算机辅助设计与图形学学报, 2013, 25(7): 963-973.

[3] 王妙一, 王斌, 雍俊海. GPU 上的水彩画风格实时渲染及动画绘制[J]. 图学学报, 2012, 33(3): 73-80.

[4] 宋元杰, 王璐, 孟祥旭. 采用Intel集成众核架构的并行光线追踪加速方法[J]. 计算机辅助设计与图形学学报, 2015, 27(12): 2313-2322.

[5] HU Y S, WANG W J, LI D, et al. Parallel BVH construction using locally density clustering[J]. IEEE Access, 2019, 7: 105827-105839.

[6] 张文胜, 解骞, 钟瑾, 等. 基于八叉树邻域分析的光线跟踪加速算法[J]. 图学学报, 2015, 36(3): 339-344.

[7] ZHANG J, GUO H Q, HONG F, et al. Dynamic load balancing based on constrained k-d tree decomposition for parallel particle tracing[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1): 954-963.

[8] 吴恩华, 柳有权. 基于图形处理器(GPU)的通用计算[J]. 计算机辅助设计与图形学学报, 2004, 16(5): 601-612.

[9] CHEN M, HUANG H F. A Real-time parallel ray-tracing method based on GPU cluster[C]//2018 IEEE International Conference of Safety Produce Informatization (IICSPI). New York: IEEE Press, 2018: 327-330.

[10] 孙昭, 柳有权, 张彩荣, 等. 一种场景内容分布的交互式渲染系统[J]. 图学学报, 2019, 40(1): 87-91.

[11] COSENZA B, DACHSBACHER C, ERRA U. GPU cost estimation for load balancing in parallel ray tracing[C]// Proceedings of the International Conference on Computer Graphics Theory and Applications. Heidelberg: Springer, 2013: 139-151.

[12] JIANG Y C. A survey of task allocation and load balancing in distributed systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(2): 585-599.

[13] 王海峰, 陈庆奎. 图形处理器通用计算关键技术研究综述[J]. 计算机学报, 2013, 36(4): 757-772.

[14] STEINER D, PAREDES E G, EILEMANN S, et al. Dynamic work packages in parallel rendering[C]// Proceedings of the 16th Eurographics Symposium on Parallel Graphics and Visualization. Goslar: Eurographics Association, 2016: 89-98.

[15] 杨际祥, 谭国真, 王荣生. 并行与分布式计算动态负载均衡策略综述[J]. 电子学报, 2010, 38(5): 1122-1130.

[16] 张正昌, 何发智, 周毅. 基于动态任务调度的层次包围盒构建算法[J]. 计算机辅助设计与图形学学报, 2018, 30(3): 491-498.

[17] CHEN L, VILLA O, KRISHNAMOORTHY S, et al. Dynamic load balancing on single-and multi-GPU systems[C]//2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). New York: IEEE Press, 2010: 1-12.

[18] COSENZA B, CORDASCO G, DE CHIARA R, et al. Load balancing in mesh-like computations using prediction binary trees[C]//2008 International Symposium on Parallel and Distributed Computing. New York: IEEE Press, 2008: 139-146.

[19] ELTANTAWY A, AAMODT T M. Warp scheduling for fine-grained synchronization[C]//2018 IEEE International Symposium on High Performance Computer Architecture (HPCA). New York: IEEE Press, 2018: 375-388.

[20] YANG C Z, CHEN C Y, HU X J, et al. Dynamic load balancing algorithm based on per-pixel rendering cost estimation for parallel ray tracing on PC clusters[C]//14th Conference on Image and Graphics Technologies and Applications, IGTA 2019. Heidelberg: Springer, 2019: 591-601.

Load balancing algorithm based on greedy strategy for multi-node parallel ray tracing

LIU Yun-biao, CHEN Chun-yi, HU Xiao-juan, XING Qi-wei, YANG Hua-min

(School of Computer Science and Technology, Changchun University of Science and Technology, Changchun Jilin 130022, China)

A load-balancing algorithm based on greedy strategy for multi-node parallel ray tracing was proposed to improve the parallelism degree of applying ray tracing cluster to producing high-definition pictures of complex scenes. Firstly, according to parallel property of GPU, the screen space was divided into a number of square image blocks. Based on the projection of the spherical bounding box of moving objects on the screen, the binary rendering time influence map was constructed. Then on the basis of the spatiotemporal correlation, the rendering task queue was established by combining the time consumed by the previous image block and the binary rendering time influence map. Then the dynamic allocation of multi-rendering node tasks was realized through two-step load-balancing. Finally, the method was verified and analyzed based on experimental data. The results showed that this method presents good load-balancing effect, and the rendering efficiency can be improved by up to 4.96 times.

ray tracing; high-definition picture; load balancing; multi-node rendering; greedy strategy

TP 391

10.11996/JG.j.2095-302X.2020020237

A

2095-302X(2020)02-0237-09

2019-10-12；

2019-12-03

国家自然科学基金项目(U19A2063)；吉林省科技发展计划(20170101005JC, 20180519012JH, 20190302113GX)；吉林省教育厅“十三五”科学技术研究项目(JJKH20200792KJ, JJKH20200799KJ)

刘云彪(1994–)，男，吉林长春人，硕士研究生。主要研究方向为三维场景建模与绘制。E-mail：LiuYunBiao@163.com

陈纯毅(1981–)，男，重庆人，教授，博士，博士生导师。主要研究方向为三维场景建模与绘制等。E-mail：chenchunyi@hotmail.com