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

  • 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.

Author Biographies

Jiri Jaros, Faculty of Information Technology Brno University of Technology, Brno
Jiri Jaros is an assistant professor and Marie Curie Fellow at Brno Univeristy of Tehchnology. For more than a decade, he has been working in the area of high performance computing, scientific code development, numerical simulations and computer architectures. He has worked with several outstanding research teams in Australia and United Kingdom on the development of large scale simulation tools for personalized medicine. He is a co-founder of the k-Wave project (http://www.k-wave.org). Since the first beta release in 2010, k-Wave has rapidly become the de facto standard software in the field, with almost 8000 registered users in 60 countries (from both academia and industry). The toolbox now underpins a wide range of international research in ultrasound and photoacoustics, ranging from the reconstruction of clinical photoacoustic images to fundamental studies into the design of ultrasound transducers.
Filip Vaverka, Faculty of Information Technology Brno University of Technology, Brno
Filip Vaverka is currently a PhD student at Brno University of Technology working in the field distributed CUDA programming.
Bradley E. Treeby, Department of Medical Physics and Bioengineering University College London, London
Bradley Treeby was born in Albany, Australia. He received his BE degree with first class honors in mechatronics engineering and his PhD in acoustics and mechanical engineering from the University of Western Australia, Australia, in 2003 and 2007, respectively. He is currently an EPSRC Early Career Fellow in the Department of Medical Physics and Biomedical Engineering at University College London, UK. His research interests include biomedical ultrasound, numerical methods, and high performance computing. He has published more than 60 scientific papers, and is the co-author of an open-source acoustics toolbox for MATLAB called k-Wave.

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.
Published
2016-09-06
Issue
Vol 3 No 3 (2016)
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.