【摘 要】
:
目前现有的测地线算法,都是基于窗元数据结构所提出的,且都是采用两方面的技术点来提升算法的时间效率。一是窗元的裁剪,二是维护窗元的处理顺序。由于窗元的复杂度严格在O(n
论文部分内容阅读
目前现有的测地线算法,都是基于窗元数据结构所提出的,且都是采用两方面的技术点来提升算法的时间效率。一是窗元的裁剪,二是维护窗元的处理顺序。由于窗元的复杂度严格在O(n1.5)~O(n2)之间,所以串行测地线算法的运行效率是无法快于O(n1.5)。在窗元的传播过程中,由于数据间的高依赖性,导致了测地线算法的并行化遇到了极大的挑战。自从Mitchell首次开创性的提出离散测地线问题至今已经有30年了,(Parallel Chen-Han,PCH算法)是目前唯一的并行测地线算法。本论文根据半边数据结构,提出了传播依赖关系图来进一步描述测地线计算过程中的数据依赖关系,并且设计一套主动更新策略:让位于波前上的顶点和半边采取主动获取数据的操作,然后在各自的内存空间中进行窗元的传播和测地线信息的更新。因此,所有的读写操作都是互不冲突且高度并行的。本文基于这套策略提出了基于三角网格上的并行测地线算法(Autonomous Wavefront Propagation,AWP算法)。直观的说,本文使用高吞吐和优雅的主动更新策略来弥补传统算法上维护窗元顺序的代价。AWP算法框架可适用于传统精确测地线算法(The Chen-Han Algorithm,CH算法)和近似算法(The Fast Marching Method,FMM算法)。该算法在不同的NVIDIA GPU上实现了完美的线性加速,并且在GTX Titan Xp的计算结果表明AWP-CH对于现实世界的模型与各向异性测量τ≤2.0的模型上的运行时间都能达到O(np),p∈[1.25,1.35]。AWP算法打破了传统串行算法不能够打破O(n1.5)的时间界限,并且由于AWP完美的效率与图形处理器计算能力的关系,相信AWP的运行效率会在不久的将来可以得到进一步的提高。
其他文献
等价多路由网络(Equal-Cost Multipath Routing,ECMP)是指到达同一个目的地址存在多条不同路由的网络环境,例如,在数据中心网络和无线Mesh网络中,任意一对源节点和目的节点之
熏鸡是中华传统酱卤肉制品的典型代表之一,因其风味独特而深受消费者青睐。熏制材料是形成熏鸡特征风味的关键因素,传统工艺一般采用果木、茶末、白糖等。本研究首先以沟帮子
近年来,在“一带一路”倡议和建设国家中心城市大背景下,西安“电视问政”通过搭建沟通平台,整合信息渠道,全面连接政府、媒体与公众,初步实现了凝聚发展共识,协力解决社会问题,树立和引导公众正面认知的目标。“电视问政”切实为大西安国家中心城市建设创造良好舆论环境,整体提升美誉度,对城市形象建构和社会治理优化起到了很好的促进作用,凸显出西安本地媒介参与社会治理的卓越能力。本文研究西安“电视问政”,旨在为西
我国在全面实施不动产统一登记后,登记制度不断完善,登记方式不断向信息化、智能化发展。不动产登记的改革,有效提高了登记效率,维护了交易秩序,更好的保护了权力人的合法权益,展现了政府在公共管理上的重要作用。天津市作为直辖市,一直走在不动产登记改革的前线,自2015年开始实施统一登记以来,登记水平有了大幅度提高,但在实际工作中,仍存在制度不完善、信息化水平偏低等问题。市区不动产登记代表了天津市不动产登记
随着我国电信运营商的整合和3G牌照的发放,围绕3G网络的建设工作逐步展开。为应对市场的激烈竞争,中国联通3G联合工作组制定了《新联通WCDMA网络规划总体方案》和《新联通WCD
1 前言熔铸锆刚玉耐火制品是玻璃熔窑的关键砌筑材料,其质量优劣直接影响着玻璃熔窑的寿命、玻璃质量的好坏及玻璃窑炉的其他经济指标。由于这种材料的重要性,国家质量技术监
随着新时期教育教学改革的深入,教育教学改革已经成为当今世界教育的时代主题和核心使命。近年来,体育舞蹈在我国发展迅速,许多少儿体育舞蹈培训机构应运而生。我国各类少儿体育舞蹈训练机构中,缺乏少儿拉丁舞专项力量训练。专项力量素质是影响少儿拉丁舞技术水平和在体育舞蹈竞赛中取得优秀的运动成绩重要因素之一,同时专项力量素质训练也是提升拉丁舞动作速度的重要因素之一。本文以“专项力量素质训练对少儿拉丁舞动作速度提
近年来,人们在皮影戏保护方面展开了很多的研究与探索。为了改变皮影戏传统文化的现状,我们在皮影戏的数字保护方面做了研究与探索。针对于目前的仿真形式缺少对皮影戏整体综
随着个人终端的多元化、应用软件的丰富化以及办公娱乐的移动化,利用智能终端访问无处不在的云服务来处理个人日常已经成为常态。然而,由于环境和应用场景的不确定性,终端用
随着移动通信的快速发展,移动终端的数量和业务需求迅猛增长。为应对这一局面,异构 Small Cell(小蜂窝)网络(Hetergeneous Small Cell Networks)成为当前移动通信的发展趋势