Sequential and parallel block-structured shortest-path ray-tracing algorithms

Olin G. Johnson; Tien-wan Yang

doi:10.1117/12.164837

1 December 1993 Sequential and parallel block-structured shortest-path ray-tracing algorithms

Olin G. Johnson, Tien-wan Yang

Proceedings Volume 2033, Mathematical Methods in Geophysical Imaging; (1993) https://doi.org/10.1117/12.164837
Event: SPIE's 1993 International Symposium on Optics, Imaging, and Instrumentation, 1993, San Diego, CA, United States

Abstract

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.

Citation Download Citation

Olin G. Johnson and Tien-wan Yang "Sequential and parallel block-structured shortest-path ray-tracing algorithms", Proc. SPIE 2033, Mathematical Methods in Geophysical Imaging, (1 December 1993); https://doi.org/10.1117/12.164837

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available