Parallelization of 3D Pseudo-Bending Algorithm for Seismic Ray Tracing

Document Type : Research Note

Authors

1 Earthquake Research Center, Ferdowsi University of Mashhad

2 Department of Geology, Faculty of Science, Ferdowsi University of Mashhad

Abstract

Bending ray tracing is a technique for finding the shortest travel path from a fixed source to a fixed receiver. Ray tracing is a time-consuming computing technique in applications such as tomography, which involves a large number of source-receiver pairs. In this regard, parallel programming makes it possible to reduce the running time of a serial program significantly by breaking it into a discrete series and solve it by different processing units simultaneously. Along with the rapid development of parallel computing technologies in both hardware architecture and system software, parallel computing is growing rapidly in a broad range of scientific computing applications. In this paper, the parallelization of pseudo-bending ray tracing algorithm is presented using both task and data parallelization strategies. In the task parallelization, the bending calculation of each path section is distributed to different processors, while in the data parallelization, due to the independent calculation for each pair of source-receiver, the data parts are distributed to different processors. The performance results of the parallelizations of the pseudo-bending algorithm for ray tracing in a 3D velocity model are shown using OpenMP, which is an application programming interface for shared memory multiprocessing programming. The advantage of OpenMP programming model is its simplicity to parallelize an existing serial code. This is especially useful now that multi-core CPUs are common. The results show the effectiveness and efficiency of the approach. A significant speedup in the ray tracing implementation is achieved. This reduction in computation time allows more rays to be traced, which directly affects the accuracy of tomography results. Sufficient ray coverage is needed to obtain tomography images with perfect resolution.

Keywords

References

1-      Rawlinson, N., Hauser, J. and Sambridge, M. (2007) Seismic ray tracing and wavefront tracking in laterally heterogeneous media. Advances in Geophysics, 49, 203–273.
2-      Vidale, J.E. (1988) Finite-difference calculation of travel times. Bulletin of the Seismological Society of America, 78(6), 2062-2076.
3-      Rawlinson, N., Sambridge, M. (2004) Multiple reflection and transmission phases in complex layered media using a multistage fast marching method. Geophysics, 69(5), 1338–1350.
4-      Langan, R.T., Lerche, I., Cutler, R.T. (1985) Tracing of rays through heterogeneous media: An accurate and efficient procedure. Geophysics, 50(9), 1456–1465.
5-      Sun, Y. (1993) Ray tracing in 3-D media by parameterized shooting. Geophysical Journal International, 114(1), 145–155.
6-      Mao, W., Stuart, G.W. (1997) Rapid multi-wave-type ray tracing in complex 2d and 3d isotropic media. Geophysics, 62(1), 298–308.
7-      Cores, D., Fung, G.M., Michelena, R.J. (2000) A fast and global two point low storage optimization technique for tracing rays in 2D and 3D isotropic media. Journal of Applied Geophysics, 45(4), 273–287.
8-      Xu, T., Zhang, Z., Gao, E., Xu, G., Sun, L. (2010) Segmentally Iterative Ray Tracing in Complex 2D and 3D Heterogeneous Block Models. Bulletin of the Seismological Society of America, 100(2), 841-850.
9-      Mohammadzaheri, A., Sadeghi, H., Hosseini, S.K., Navazandeh, M. (2013) DISRAY: a distributed ray tracing by map-reduce. Computer & Geosciences, 52(0), 453–458.
10-  Jacob, K.H. (1970) Three-dimensional seismic ray tracing in a laterally heterogeneous spherical Earth. Journal of Geophysical Research, 75(32), 6675–6689.
11-  Wesson, R.L. (1971) Travel-time inversion for laterally inhomogeneous crustal velocity models. Bulletin of the Seismological Society of America, 61(3), 729-746.
12-  Julian, B.R., Gubbins, D. (1977) Three-dimensional seismic ray tracing. Journal of Geophysics, 43(1), 95–113.
13-  Pereyra, V., Lee, W.H.K., Keller, H.B. (1980) Solving two-point seismic-ray tracing problems in a heterogeneous medium, Part 1. A general adaptive finite difference method. Bulletin of the Seismological Society of America,70(1), 79–99.
14-  Um, J., Thurber, C. (1987) A fast algorithm for two-point seismic ray tracing. Bulletin of the Seismological Society of America, 77(3), 972–986.
15-  Zhao, D., Hasegawa, A., Horiuchi, S. (1992) Tomographic imaging of P and S wave velocity structure beneath Northeastern Japan. Journal of Geophysical Research, 97(B13), 19909–19928.
16-  Koketsu, K., Sekine, S. (1998) Pseudo-bending method for three-dimensional seismic ray tracing in a spherical earth with discontinuities. Geophysical Journal International, 132(2), 339–346.
17-  Sadeghi, H., Suzuki, S., Takenaka, H. (1999) A two-point, three-dimensional seismic ray tracing using genetic algorithms. Physics of the Earth and Planetary Interiors, 113(0), 355–365.
18-  Koulakov, I. (2009) LOTOS code for local earthquake tomographic inversion. Benchmarks for testing tomographic algorithms. Bulletin of the Seismological Society of America, 99(1), 194-214.
19-  Kiessling, A. (2009) An introduction to parallel programming with OpenMP, The University of Edinburgh, A Pedagogical Seminar (accessed 24 September 2020), URL: https://www.roe.ac.uk/ifa/postgrad/pedagogy/2009_kiessling.pdf.
20-  Amdahl, G.M. (1967) Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the American Federation of Information Processing Societies (AFIPS Press, vol 30), Washington, DC, pp. 483-485.
21-  Klemm, M., Supinski, B. (2019) OpenMP Application Programming Interface Specification Version 5.0. Independently published. 668 P.
1-      Rawlinson, N., Hauser, J. and Sambridge, M. (2007) Seismic ray tracing and wavefront tracking in laterally heterogeneous media. Advances in Geophysics, 49, 203–273.
2-      Vidale, J.E. (1988) Finite-difference calculation of travel times. Bulletin of the Seismological Society of America, 78(6), 2062-2076.
3-      Rawlinson, N., Sambridge, M. (2004) Multiple reflection and transmission phases in complex layered media using a multistage fast marching method. Geophysics, 69(5), 1338–1350.
4-      Langan, R.T., Lerche, I., Cutler, R.T. (1985) Tracing of rays through heterogeneous media: An accurate and efficient procedure. Geophysics, 50(9), 1456–1465.
5-      Sun, Y. (1993) Ray tracing in 3-D media by parameterized shooting. Geophysical Journal International, 114(1), 145–155.
6-      Mao, W., Stuart, G.W. (1997) Rapid multi-wave-type ray tracing in complex 2d and 3d isotropic media. Geophysics, 62(1), 298–308.
7-      Cores, D., Fung, G.M., Michelena, R.J. (2000) A fast and global two point low storage optimization technique for tracing rays in 2D and 3D isotropic media. Journal of Applied Geophysics, 45(4), 273–287.
8-      Xu, T., Zhang, Z., Gao, E., Xu, G., Sun, L. (2010) Segmentally Iterative Ray Tracing in Complex 2D and 3D Heterogeneous Block Models. Bulletin of the Seismological Society of America, 100(2), 841-850.
9-      Mohammadzaheri, A., Sadeghi, H., Hosseini, S.K., Navazandeh, M. (2013) DISRAY: a distributed ray tracing by map-reduce. Computer & Geosciences, 52(0), 453–458.
10-  Jacob, K.H. (1970) Three-dimensional seismic ray tracing in a laterally heterogeneous spherical Earth. Journal of Geophysical Research, 75(32), 6675–6689.
11-  Wesson, R.L. (1971) Travel-time inversion for laterally inhomogeneous crustal velocity models. Bulletin of the Seismological Society of America, 61(3), 729-746.
12-  Julian, B.R., Gubbins, D. (1977) Three-dimensional seismic ray tracing. Journal of Geophysics, 43(1), 95–113.
13-  Pereyra, V., Lee, W.H.K., Keller, H.B. (1980) Solving two-point seismic-ray tracing problems in a heterogeneous medium, Part 1. A general adaptive finite difference method. Bulletin of the Seismological Society of America,70(1), 79–99.
14-  Um, J., Thurber, C. (1987) A fast algorithm for two-point seismic ray tracing. Bulletin of the Seismological Society of America, 77(3), 972–986.
15-  Zhao, D., Hasegawa, A., Horiuchi, S. (1992) Tomographic imaging of P and S wave velocity structure beneath Northeastern Japan. Journal of Geophysical Research, 97(B13), 19909–19928.
16-  Koketsu, K., Sekine, S. (1998) Pseudo-bending method for three-dimensional seismic ray tracing in a spherical earth with discontinuities. Geophysical Journal International, 132(2), 339–346.
17-  Sadeghi, H., Suzuki, S., Takenaka, H. (1999) A two-point, three-dimensional seismic ray tracing using genetic algorithms. PhysicsoftheEarthandPlanetaryInteriors, 113(0), 355–365.
18-  Koulakov, I. (2009) LOTOS code for local earthquake tomographic inversion. Benchmarks for testing tomographic algorithms. Bulletin of the Seismological Society of America, 99(1), 194-214.
19-  Kiessling, A. (2009) An introduction to parallel programming with OpenMP, The University of Edinburgh, A Pedagogical Seminar (accessed 24 September 2020), URL: https://www.roe.ac.uk/ifa/postgrad/pedagogy/2009_kiessling.pdf.
20-  Amdahl, G.M. (1967) Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the American Federation of Information Processing Societies (AFIPS Press, vol 30), Washington, DC, pp. 483-485.
21-  Klemm, M., Supinski, B. (2019) OpenMP Application Programming Interface Specification Version 5.0. Independently published. 668 P.
Journal of Seismology and Earthquake Engineering
Volume 21, Issue 4
November 2019
Pages 49-56

Files

Share

How to cite

Statistics