基于波前主动传播的高效并行测地线算法

《基于波前主动传播的高效并行测地线算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基基基于于于波波波前前前主主主动动动传传传播播播的的的高高高效效效并并并行行行测测测地地地线线线算算算法法法AutonomousWavefrontPropagation(AWP):ParallelizingDiscreteGeodesicAlgorithmswithPerfectEfficiency学科专业：计算机科学与技术研究生：黄才宝指导教师：于瑞国副教授天津大学计算机科学与技术学院二〇一七年十二月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，，除了文中特别加以标注和致谢之处外论文中不包含其他人己经发表或撰写过的研宂成果，也不包

2、含为获得天津大学或其他教育机构的学位或证一书而使用过的材料。与我同工作的同志对本研宄所做的任何贡献均己在论文中作了明确的说明并表示了谢意。？学位论文作者签名：日：签字日期年月／／学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、汇编以供查阅和借阅。同意学校、缩印或扫描等复制手段保存向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：技导师签名：４：月曰签字曰期：＞年

3、ｉ月曰签字曰期年ｐ／〇／＂／摘摘摘要要要目前现有的测地线算法，都是基于窗元数据结构所提出的，且都是采用两方面的技术点来提升算法的时间效率。一是窗元的裁剪，二是维护窗元的处理顺序。由于窗元的复杂度严格在O(n1.5)∼O(n2)之间，所以串行测地线算法的运行效率是无法快于O(n1.5)。在窗元的传播过程中，由于数据间的高依赖性，导致了测地线算法的并行化遇到了极大的挑战。自从Mitchell首次开创性的提出离散测地线问题至今已经有30年了，（ParallelChen-Han，PCH算法）是目前唯一的并行测地线算法。本论文根据半边数据结构，提出了传播依赖关系图来进一步描述测地线计算

4、过程中的数据依赖关系，并且设计一套主动更新策略：让位于波前上的顶点和半边采取主动获取数据的操作，然后在各自的内存空间中进行窗元的传播和测地线信息的更新。因此，所有的读写操作都是互不冲突且高度并行的。本文基于这套策略提出了基于三角网格上的并行测地线算法（AutonomousWavefrontPropagation,AWP算法）。直观的说，本文使用高吞吐和优雅的主动更新策略来弥补传统算法上维护窗元顺序的代价。AWP算法框架可适用于传统精确测地线算法（TheChen-HanAlgorithm，CH算法）和近似算法（TheFastMarchingMethod，FMM算法）。该算法在不同

5、的NVIDIAGPU上实现了完美的线性加速，并且在GTXTitanXp的计算结果表明AWP-CH对于现实世界的模型与各向异性测量τ≤2.0的模型上的运行时间都能达到O(np),p∈[1.25,1.35]。AWP算法打破了传统串行算法不能够打破O(n1.5)的时间界限，并且由于AWP完美的效率与图形处理器计算能力的关系，相信AWP的运行效率会在不久的将来可以得到进一步的提高。关键词：离散测地线，波前主动传播，CH算法，FMM算法IABSTRACTAlltheexactalgorithmsarebasedonthewindowdatastructureandtheyadoptt-w

6、otypesoftechniqueswindowpruningandmaintainingorderedwindowstoachievegoodruntimeperformance.Sincethewindowcomplexity(worstcaseO(n2)andbestcaseO(n1.5))istight,thesequentialalgorithmscannotrunfasterthanO(n1.5).Itischallengingtoparallelizediscretegeodesicalgorithms,duetohighdatadependenceinwindo

7、wpropaga-tion.After30yearssinceMitchell’sseminalpaperonthediscretegeodesicproblem,PCHistheONLYparallelalgorithmforarbitrarytrianglemeshes,implyingthatitisnon-trivialtoparallelizethediscretegeodesicalgorithms.Thispaperpresentsanewmethodforparalleliz