目前现有的测地线算法,都是基于窗元数据结构所提出的,且都是采用两方面的技术点来提升算法的时间效率。一是窗元的裁剪,二是维护窗元的处理顺序。由于窗元的复杂度严格在O(n^1.5)～O（n²）之间,所以串行测地线算法的运行效率是无法快于O(n^1.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（n^p）,p∈[1.25,1.35]。AWP算法打破了传统串行算法不能够打破O(n^1.5)的时间界限,并且由于AWP完美的效率与图形处理器计算能力的关系,相信AWP的运行效率会在不久的将来可以得到进一步的提高。