Spectral Domain Decomposition Using Local Fourier Basis: Application to Ultrasound Simulation on a Cluster of GPUs

Jiri Jaros; Filip Vaverka; Bradley E. Treeby

doi:10.14529/jsfi160305

Authors

Jiri Jaros Faculty of Information Technology Brno University of Technology, Brno
Filip Vaverka Faculty of Information Technology Brno University of Technology, Brno
Bradley E. Treeby Department of Medical Physics and Bioengineering University College London, London

DOI:

https://doi.org/10.14529/jsfi160305

Abstract

The simulation of ultrasound wave propagation through biological tissue has a wide range of practical applications. However, large grid sizes are generally needed to capture the phenomena of interest. Here, a novel approach to reduce the computational complexity is presented. The model uses an accelerated k-space pseudospectral method which enables more than one hundred GPUs to be exploited to solve problems with more than 3*10^9 grid points. The classic communication bottleneck of Fourier spectral methods, all-to-all global data exchange, is overcome by the application of domain decomposition using local Fourier basis. Compared to global domain decomposition, for a grid size of 1536 x 1024 x 2048, this reduces the simulation time by a factor of 7.5 and the simulation cost by a factor of 3.8.

References

G. F. Pinton, J. Dahl, S. Rosenzweig, and G. E. Trahey, "A heterogeneous nonlinear attenuating full-wave model of ultrasound," IEEE Trans. Ultrason. Ferroelectr. Freq. Control,vol. 56, no. 3, pp. 474-488, 2009.

J. Jaros, A. P. Rendell, and B. E. Treeby, "Full-wave nonlinear ultrasound simulation on distributed clusters with applications in high-intensity focused ultrasound," Int. J. High Perf. Comput. Appl., vol. 30, no. 2, pp. 137-155, 2016.

J. Gu and Y. Jing, "Modeling of wave propagation for medical ultrasound: a review," IEEE Trans. Ultrason. Ferroelectr. Freq. Control, vol. 62, no. 11, pp. 1979-1992, 2015.

K. Okita, R. Narumi, T. Azuma, S. Takagi, and Y. Matumoto, "The role of numerical simulation for the development of an advanced HIFU system," Comput. Mech., vol. 54, no. 4, pp. 1023-1033, 2014.

J. P. Boyd, Chebyshev and Fourier Spectral Methods. Mineola, New York: Dover Publications, 2001.

N. N. Bojarski, "The k-space formulation of the scattering problem in the time domain," J. Acoust. Soc. Am., vol. 72, no. 2, pp. 570-584, 1982.

T. D. Mast, L. P. Souriau, D. L. Liu, M. Tabei, A. I. Nachman, and R. C. Waag, "A kspace method for large-scale models of wave propagation in tissue.," IEEE Trans. Ultrason. Ferroelectr. Freq. Control, vol. 48, no. 2, pp. 341-354, 2001.

M. Tabei, T. D. Mast, and R. C. Waag, "A k-space method for coupled first-order acoustic propagation equations," J. Acoust. Soc. Am., vol. 111, no. 1, pp. 53-63, 2002.

B. E. Treeby, J. Jaros, A. P. Rendell, and B. T. Cox, "Modeling nonlinear ultrasound propagation in heterogeneous media with power law absorption using a k-space pseudospectral method," J. Acoust. Soc. Am., vol. 131, no. 6, pp. 4324-4336, 2012.

M. I. Daoud and J. C. Lacefield, "Distributed three-dimensional simulation of B-mode ultrasound imaging using a first-order k-space method.," Phys. Med. Biol., vol. 54, no. 17, pp. 5173-5192, 2009.

J. C. Tillett, M. I. Daoud, J. C. Lacefield, and R. C. Waag, "A k-space method for acoustic propagation using coupled first-order equations in three dimensions," J. Acoust. Soc. Am., vol. 126, no. 3, pp. 1231-1244, 2009.

J.-L. Vay, I. Haber, and B. B. Godfrey, "A domain decomposition method for pseudo-spectral electromagnetic simulations of plasmas," J. Comput. Phys., vol. 243, pp. 260-268, 2013.

J. Jaros, V. Nikl, and B. E. Treeby, "Large-scale Ultrasound Simulations Using the Hybrid OpenMP/MPI Decomposition," in Proceedings of the 3rd International Conference on Exascale Applications and Software, pp. 115-119, Association for Computing Machinery, 2015.

M. Pippig, "PFFT-An extension of FFTW to massively parallel architectures," SIAM J. Sci. Comput., vol. 35, no. 3, pp. C213-C236, 2013.

M. Frigo and S. G. Johnson, "The Design and Implementation of FFTW3," Proceedings of the IEEE, vol. 93, no. 2, pp. 216-231, 2005.

D. Pekurovsky, "P3DFFT: A Framework for Parallel Computations of Fourier Transforms in Three Dimensions," SIAM J. Sci. Comput., vol. 34, no. 4, pp. C192-C209, 2012.

A. Gholami, J. Hill, D. Malhotra, and G. Biros, "AccFFT: A library for distributed-memory FFT on CPU and GPU architectures," arXiv, p. arXiv:1506.07933, 2015.

K. Czechowski, C. Battaglino, C. McClanahan, and K. Iyer, "On the Communication Complexity of 3D FFTs and its Implications for Exascale," in Proceedings of International Supercomputing Conference, ACM, 2012.

M. Israeli, L. Vozovoi, and A. Averbuch, "Spectral multidomain technique with local Fourier basis," J. Sci. Comput., vol. 8, no. 2, pp. 135-149, 1993.

J. P. Boyd, "Asymptotic fourier coefficients for a C1 bell (smoothed-"top-hat") & the Fourier extension problem," J. Sci. Comput., vol. 29, no. 1, pp. 1-24, 2005.

M. Ding and K. Chen, "Staggered-grid PSTD on local Fourier basis and its applications to surface tissue modeling.," Optics Exp., vol. 18, no. 9, pp. 9236-9250, 2010.

M. Garbey and D. Tromeur-Dervout, "Parallel Algorithms with Local Fourier Basis," J. Comp. Phys., vol. 173, pp. 575-599, 2001.

A. D. Pierce, Acoustics: An Introduction to its Physical Principles and Applications. New York: Acoustical Society of America, 1989.

J.-P. Berenger, "Three-dimensional perfectly matched layer for the absorption of electromagnetic waves," J. Comput. Phys., vol. 127, no. 2, pp. 363-379, 1996.

J. P. Boyd, "A Comparison of Numerical Algorithms for Fourier Extension of the First, Second, and Third Kinds," J. Comput. Phys., vol. 178, no. 1, pp. 118-160, 2002.

M. J. Quinn, Parallel Programming in C with MPI and OpenMP. McGraw-Hill Education Group, 2003.

HPC Advisory Council, "Interconnect Analysis: 10GigE and InfiniBand in High Performance Computing," tech. rep., HPC Advisory Council, 2009.

B. E. Treeby and B. T. Cox, "A k-space Greens function solution for acoustic initial value problems in homogeneous media with power law absorption," J. Acoust. Soc. Am., vol. 129, no. 6, pp. 3652-3660, 2011.

J. L. Robertson, B. T. Cox, and B. E. Treeby, "Quantifying numerical errors in the simulation of transcranial ultrasound using pseudospectral methods," in IEEE Int. Ultrason. Symp., pp. 2000-2003, 2014.

NVIDIA, "CUDA Toolkit Documentation v7.5," tech. rep., NVIDIA, 2015.

NVIDIA, "cuFFT Library User’s Guide," tech. rep., NVIDIA, 2015.