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

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

作　　者：刘云彪 陈纯毅[1] 胡小娟[1] 邢琦玮 杨华民[1] 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)

机构地区：[1]长春理工大学计算机科学技术学院,吉林长春130022

出　　处：《图学学报》2020年第2期237-245,共9页Journal of Graphics

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

摘　　要：为了提高利用光线跟踪集群绘制生成高分辨率复杂场景画面的并行度,提出基于贪心策略的多结点并行光线跟踪负载均衡算法。首先根据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.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]