Autonomous Wavefront Propagation (AWP):Parallelizing Discrete Geodesic Algorithms With Perfect Efficiency

All the exact algorithms are based on the window data structure and they adopt t-wo types of techniques–window pruning and maintaining ordered windows–to achieve good runtime performance.Since the window complexity(worst case O?n²?and best case O(n^1.5))is tight,the sequential algorithms cannot run faster than O(n^1.5).It is challenging to parallelize discrete geodesic algorithms,due to high data dependence in window propaga-tion.After 30 years since Mitchell's seminal paper on the discrete geodesic problem,PCH is the ONLY parallel algorithm for arbitrary triangle meshes,implying that it is non-trivial to parallelize the discrete geodesic algorithms.This paper presents a new method for parallelizing geodesic algorithms on triangle meshes.Using the half-edge data structure,we define the propagation dependency graph to characterize data dependency in computing geodesics.Then,we design an active s-trategy such that the vertices and half-edges on the wavefront take the initiative to collect their input data and then propagate windows and update geodesic information in their own memory space.As a result,all the read and write operations can be carried out simultane-ously.Intuitively speaking,we use high throughput and an elegant active updating strategy to compensate the loss of ordered windows.AWP works for both exact algorithm?the CH algorithm?and approximate algorithm?the fast marching method?.Our implementation on various NVIDIA GPUs exhibit perfect linear speedup,i.e.,doubling the computational power?i.e.,FLOPS?doubles the speed.Computational results on GTX Titan Xp show that AWP-CH empirically runs in O?n^p?time,p?[1.25,1.35],for real-world models with anisotropy measure??2.0.Note that the sequential exact algorithms are not able to break the O(n^1.5)time barrier,due to the tight lower bound of window complexity?(n^1.5).Thanks to its perfect efficiency and the trend of increasing the number of processors in graphics hardware,we believe that the time complexity of AWP can be further improved in the near future.