基于GPU集群的Level Set并行高精度演化

计算物理 ›› 2016, Vol. 33 ›› Issue (3): 253-265.

• 研究论文 • 下一篇

基于GPU集群的Level Set并行高精度演化

袁斌

北京应用物理与计算数学研究所, 北京 100088

收稿日期:2015-03-09 修回日期:2015-07-16 出版日期:2016-05-25 发布日期:2016-05-25
作者简介:袁斌(1966-),男,硕士,高级工程师,主要研究方向为可视化算法与软件,E-mail:yuanbin@iapcm.ac.cn
基金资助:
中国工程物理研究院科学技术发展基金(2012B020225)资助项目

Level Set Parallel Highly Accurate Evolution Based on GPU Cluster

YUAN Bin

Institute of Applied Physics and Computational Mathematics, Beijing 100088, China

Received:2015-03-09 Revised:2015-07-16 Online:2016-05-25 Published:2016-05-25

摘要/Abstract

摘要： 设计实现基于张量积B样条的并行Level Set演化算法,张量积B样条提高了演化精度和并行度;每步演化都需要反算B样条系数.针对对角占优三对角方程组,设计实现基于精确LU分解的高精度并行追赶法,并用它反算B样条系数;采用两步通信方法,消除通信的依赖关系,实现有效的并行通信.实验表明,本文的并行算法可以有效加速演化过程.

关键词: B样条, Level Set, 混合并行, 三对角方程组

Abstract: We design and implement parallel level set evolution algorithm based on tensor product B-spline which improves accuracy and parallelism of level set evolution. Each step of evolution need compute B-spline coefficients. Furthermore, a parallel high approximation solver for diagonally dominant tridiagonal linear system based on exact LU decomposition is implemented, which is used to compute B-spline coefficients. Two step communications are used to remove communicating dependency, so as to communicate in parallel. As a result, it speeds up level set evolution efficiently.

Key words: B-spline, level set, hybrid parallelism, tridiagonal system

中图分类号:

TP391

袁斌. 基于GPU集群的Level Set并行高精度演化[J]. 计算物理, 2016, 33(3): 253-265.

YUAN Bin. Level Set Parallel Highly Accurate Evolution Based on GPU Cluster[J]. CHINESE JOURNAL OF COMPUTATIONAL PHYSICS, 2016, 33(3): 253-265.

参考文献

[1] NVIDIA.NVIDIA_CUDA_Programming_Guide[CP/OL].[2015-03-09]http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf.
[2] HOWISON M, BETHEL E W, CHILDS H. Hybrid parallelism for volume rendering on large-, multi-, and many-core systems[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(1):17-29.
[3] OSHER S, SETHIAN J. Fronts propagating with curvature dependent speed:Algorithms based on Hamilton-Jacobi formulation[J]. Journal of Computational Physics, 1988,79(1):12-49.
[4] ROSENFELD A. Edge and curve detection for visual scene anaIysis[J]. IEEE Transactions on Computers, 1971, 20(5):562-569.
[5] WITKIN A P. Scale-space filtering[C]//Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing 1984, Piscataway,NJ,USA:IEEE Press,1984:150-153.
[6] PERONA P, MALIK J. Scale space and edge detection using anisotropic diffusion[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1990,12(7):629-639.
[7] ALVAREZ L, LIONS P L MOREL J M. Image selective smoothing and edge detection by nonlinear diffusion.Ⅱ[J]. SIAM Journal on Numerical Analysis,1992,29(3):845-866.
[8] CASELLES V, KIMMEL R, SAPIRO G. Geodesic active contours[J]. International Journal of Computer Vision,1997,22(1):61-79.
[9] RUDIN L I, OSHER S, FATEMI E. Nonlinear total variation based noise removal algorithms[J]. Physica D Nonlinear Phenomena, 1992, 60(1/4):259-268.
[10] UNSER M, ALDROUBI A, EDEN M. On the asymptotic convergence of B-spline wavelets to Gabor functions[J]. IEEE Transactions on Information Theory,1992, 38(2):864-872.
[11] BRINKS R. On the convergence of derivatives of B-splines to derivatives of the Gaussian function[J]. Computational &Applied Mathematics,2008, 27(1):79-92.
[12] de BOOR C. On calculation with B-spline[J].Journal of Approximation Theory,1972,6(1):50-62.
[13] COX M G.The numerical evaluation of B-spline[J].IMA Journal of Applied Mathematics,1972,10(2):134-149.
[14] 施法中.计算机辅助几何设计与非均匀有理B样条[M].北京:北京航空航天大学出版社,1994.
[15] LARRIBA-Pey J L, NAVARRO J J, JORBA A, et al. Review of general and toeplitz vector bidiagonal solvers[J]. Parallel Computing, 1996, 22(8):1091-1126.
[16] 崔锦泰. 小波分析导论[M].程正兴,译.西安:西安交通大学出版, 1994.
[17] 何旭初,苏煜成,包雪松. 计算数学简明教程[M]. 北京:高等教育出版社, 1980.
[18] 莫则尧,袁国兴.消息传递并行编程环境[M].北京:科学出版社,2001.
[19] 袁斌.改进的均匀数据场GPU光线投射[J].中国图象图形学报,2011,16(7):1269-1275.

基于GPU集群的Level Set并行高精度演化

Level Set Parallel Highly Accurate Evolution Based on GPU Cluster

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

作者中心

审稿中心

期刊浏览

期刊介绍

[1]	王现辉, 乔慧, 张小明, 谷金良. 基于等几何分析的边界元法求解Helmholtz问题[J]. 计算物理, 2017, 34(1): 61-66.
[2]	张勇, 林皋, 胡志强, 刘俊. 基于等几何分析方法求解任意截面波导本征问题[J]. 计算物理, 2012, 29(4): 534-542.
[3]	宋昱, 王飞, 郝鹏飞, 何枫. 考虑壁面接触效应的微流动数值模拟[J]. 计算物理, 2008, 25(1): 75-82.
[4]	宫翔飞, 张树道, 江松. 界面捕捉Level Set方法的(AMR)数值模拟[J]. 计算物理, 2006, 23(4): 391-395.
[5]	陈荣三, 蔚喜军. 一维多介质可压缩Euler方程的高精度RKDG有限元方法[J]. 计算物理, 2006, 23(1): 43-49.
[6]	陈菲, 张梦萍, 徐胜利. 运动激波和气泡串相互作用的初步数值模拟[J]. 计算物理, 2004, 21(5): 443-448.
[7]	张镭, 袁礼. Ghost Fluid方法与双介质可压缩流动计算[J]. 计算物理, 2003, 20(6): 503-508.
[8]	姜洋, 赵宁, 唐维军. 界面不稳定性数值模拟中的虚拟流动方法[J]. 计算物理, 2003, 20(6): 549-555.
[9]	程军波, 唐维军, 李德元, 傅德薰. 利用Ghost Fluid方法模拟激波与柱形界面相互作用[J]. 计算物理, 2003, 20(3): 219-225.
[10]	唐维军, 赵宁, 李晓林, 张景琳, 蔚喜军. 随机扰动下三维流体界面不稳定性的并行计算[J]. 计算物理, 2001, 18(6): 539-543.
[11]	张立东, 李椿萱. 结构型网格分块生成技术[J]. 计算物理, 2001, 18(4): 325-328.
[12]	骆志刚, 李晓梅, 王正华. 循环块三对角线性方程组的一种分布式并行算法[J]. 计算物理, 2001, 18(4): 360-365.
[13]	尚智, 刘瑞兰, 苏光辉, 贾斗南. 微分方程的神经网络数值解法[J]. 计算物理, 2001, 18(3): 281-284.
[14]	唐维军, 张景琳, 李晓林, 赵宁. 三维流体界面不稳定性的Ghost方法[J]. 计算物理, 2001, 18(2): 163-169.
[15]	蔚喜军, 尤迎玖. 流体界面不稳定性数值模拟中不同介质界面的处理方法[J]. 计算物理, 2001, 18(1): 23-26.