TY - JOUR

T1 - Cache-efficient parallel eikonal solver for multicore CPUs

AU - Nikitin, Alexandr A.

AU - Serdyukov, Alexandr S.

AU - Duchkov, Anton A.

PY - 2018/6/1

Y1 - 2018/6/1

N2 - Numerical solution of the eikonal equation is frequently used to compute first-arrival travel times for a given velocity model in seismic applications. Computations for large three-dimensional models become expensive requiring the use of efficient parallel solvers. We present new parallel implementations of the fast sweeping and locking sweeping methods optimized for shared memory systems such as multicore CPUs; we call them block fast sweeping method (BFSM) and block locking sweeping method (BLSM). Proposed methods are based on the domain decomposition approach with a special attention paid to high efficiency of the cache utilization and task execution synchronization. Performance tests on realistic models show high parallel efficiency of 85–95% on modern multicore CPUs and require the same number of iterations to converge as do the serial sweeping methods. We also highlight the importance of properly selecting the stopping criterion in the iterative sweeping methods aiming for a balance between computational time and accuracy of the result required by an application. In particular, we show that in seismic applications one can reach reasonable accuracy of computed travel times while dramatically reducing the number of iterations compared to the case of using the full convergence stopping criterion.

AB - Numerical solution of the eikonal equation is frequently used to compute first-arrival travel times for a given velocity model in seismic applications. Computations for large three-dimensional models become expensive requiring the use of efficient parallel solvers. We present new parallel implementations of the fast sweeping and locking sweeping methods optimized for shared memory systems such as multicore CPUs; we call them block fast sweeping method (BFSM) and block locking sweeping method (BLSM). Proposed methods are based on the domain decomposition approach with a special attention paid to high efficiency of the cache utilization and task execution synchronization. Performance tests on realistic models show high parallel efficiency of 85–95% on modern multicore CPUs and require the same number of iterations to converge as do the serial sweeping methods. We also highlight the importance of properly selecting the stopping criterion in the iterative sweeping methods aiming for a balance between computational time and accuracy of the result required by an application. In particular, we show that in seismic applications one can reach reasonable accuracy of computed travel times while dramatically reducing the number of iterations compared to the case of using the full convergence stopping criterion.

KW - Eikonal equation

KW - Fast sweeping method

KW - Parallel algorithm

KW - Seismic

KW - Shared memory

KW - VISCOSITY SOLUTIONS

KW - FAST SWEEPING METHOD

KW - HAMILTON-JACOBI EQUATIONS

KW - ALGORITHMS

KW - CONTINUATION

KW - FINITE-DIFFERENCE CALCULATION

UR - http://www.scopus.com/inward/record.url?scp=85041112384&partnerID=8YFLogxK

U2 - 10.1007/s10596-018-9725-9

DO - 10.1007/s10596-018-9725-9

M3 - Article

AN - SCOPUS:85041112384

VL - 22

SP - 775

EP - 787

JO - Computational Geosciences

JF - Computational Geosciences

SN - 1420-0597

IS - 3

ER -