next up previous [pdf]

Next: Method Up: Monsegny & Agudelo: Shortest Previous: Monsegny & Agudelo: Shortest

Introduction

Shortest path ray tracing is a method to trace rays using a graph that represents the velocity model. The vertices of the graph have defined locations in the velocity model. The edges between vertices have weights associated with the traveltime of a seismic ray that crosses from one of its adjacent vertices to the other. It is an instance of the single source shortest path problem (SSSP) that is classic in graph theory. Finding the shortest path from one vertex to another using these weights is an aproximation to the seismic ray between them by Fermat's principle (Moser, 1991). This approximation will get closer to the seismic ray when the vertex and edge coverage is dense, although this is computationally expensive. This method was introduced in Nakanishi and Yamaguchi (1986) and Moser (1991).

This ray tracing method has some advantages (Moser, 1991). It can calculate raypaths from one vertex to all other vertices in the velocity model simultaneously. Traditional restrictions of other methods like shadow zones and difracted raypaths are properly handled, and the velocity model can be complex. As the resulting raypath is only an aproximation, it can serve as a very good starting point to other more precise methods.

One of the main drawbacks of this method is its calculation velocity (Leidenfrost et al., 1999). If it is properly implemented with priority queues its computational complexity is $O(n\log n)$ where $n$ is the number of vertices. Nevertheless, some implementations report almost an order of magnitude more time consumed that other alternatives like finite differences eikonal solvers and wavefront construction (Leidenfrost et al., 1999).

Graphics processing units (GPUs) are a commodity programable hardware that have found a place in scientific computation. They can run concurrently millions of threads with very cheap context switch and high computational throughput. It is possible to decompose the shortest path calculation in a such a way that a GPU can handle this calculation. Indeed, some have used GPUs to solve the SSSP problem in general graphs with millions of vertices, although some approaches require atomic memory operations (Harish and Narayanan, 2007), which are expensive in GPU devices. It will be show that there is a solution that does not need this kind of memory operations.


next up previous [pdf]

Next: Method Up: Monsegny & Agudelo: Shortest Previous: Monsegny & Agudelo: Shortest

2013-10-09