1 December 1993 Sequential and parallel block-structured shortest-path ray-tracing algorithms
Author Affiliations +
Shortest path network algorithms have been applied to geophysical raytracing by Nakanishi and Yamaguchi and Moser. In the present work two new algorithms are introduced which further exploit the special structure of network models as applied to geological structures. The algorithm differs in the scanning order of network blocks in a processing queue. An early version of this concept, with computed examples was given. Mathematical correctness of both algorithms, `block-greedy' and `block-breadth', is established. It is then shown that block- greedy limits the updating cycles per block but is inherently sequential whereas block-breadth may incur back-tracking but allows parallel execution. Shared memory architectures allow block level parallelization with guided self-scheduling on a global queue. Message-passing architectures allow direct parallel counterparts to sequential breadth-first execution.
© (1993) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Olin G. Johnson, Olin G. Johnson, Tien-wan Yang, Tien-wan Yang, } "Sequential and parallel block-structured shortest-path ray-tracing algorithms", Proc. SPIE 2033, Mathematical Methods in Geophysical Imaging, (1 December 1993); doi: 10.1117/12.164837; https://doi.org/10.1117/12.164837

Back to Top