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

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

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

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.