Fast Fourier transforms for the evaluation of convolution products: CPU versus GPU implementation. (18th December 2013)

• Record Type: Journal Article
• Authors: Van de Wiele, B.; Vansteenkiste, A.; Van Waeyenberge, B.; Dupré, L.; De Zutter, D.; Dupre, Luc; Geuzaine, Christophe
• Is Part Of: International journal of numerical modelling. Volume 27:Number 3(2014:May/Jun.)
• Page Start: 495
• Page End: 504
• Publication Date: 2013-12-18
• Subjects: Electric networks -- Mathematical models -- Periodicals; Electronics -- Mathematical models -- Periodicals; 621.3011
• DOI: 10.1002/jnm.1960
• Languages: English
• ISSNs: 0894-3370

Abstract

<abstract abstract-type="main" id="jnm1960-abs-0001"> <title>SUMMARY</title> <p id="jnm1960-para-0006">In a large variety of research areas, convolution products that relate a physical quantity in some observation points with their sources are encountered. When the sources and the observation points coincide, the numerical evaluation of the physical quantity typically leads to order <italic>N</italic>² numerical problems. Here, fast Fourier transforms are widely used to reduce the computations to order <italic>N</italic>log <italic>N</italic> complexity. When adopting Fourier transforms (FFT) for finite physical problems, zero padding is required. Hence, in 2D and 3D problems, an optimization of the evaluation of the convolution product includes a non‐execution of Fourier transforms on arrays containing only zeros in the forward 2D or 3D FFT scheme and their corresponding arrays in the inverse 2D or 3D FFT scheme. This paper describes the implementation of such an approach on graphical processing units (GPUs) and compares the time gains on GPU and on CPU. It is found that on CPU, the speedup corresponds with the theoretical limit, while in the GPU implementation, the memory bandwidth limits the speedup ratio. Copyright © 2013 John Wiley &amp; Sons, Ltd.</p> </abstract>