Shortest path ray tracing on parallel GPU devices

Sequential main function

Algorithm 2 is the sequential main function that call the parallel kernels to perform the ray tracing. Its parameters are the indices $(si,sk)$ of the source vertex. The array $v$ holds the velocity values at each vertex location, obtained from the velocity model. The arrays $tt$ and $auxtt$ will be used to store the traveltime from source vertex to each other vertex. At the beginning they are set to $\infty$ (or another big value) except for the traveltime of source vertex that is set to $tt[si][sk]=0$. The arrays $pr$ and $auxpr$ will contain the indices of the predecesor vertex of each vertex along the ray. Their starting values are $(-1,-1)$ for all vertices. At this point we call the kernel function to precalculate the weights of each vertex. The ray tracing is conducted next by calling the two function kernels Relaxation and WriteBack in a loop while the boolean variable $stop$ is false. The reason to have divided the work among these two kernels is that it is necessary to synchronize all threads after the work done by first kernel and this global synchronization is only possible by having the rest of the code in another kernel.

Shortest path ray tracing on parallel GPU devices