Analysing Memory Performance when computing DFTs using FFTW

Abstract: Discrete Fourier Transforms (DFTs) are used in a wide variety of dif-ferent scientific areas. In addition, there is an ever increasing demand on fast and effective ways of computing DFT problems with large data sets. The FFTW library is one of the most common used libraries when computing DFTs. It adapts to the system architecture and predicts the most effective way of solving the input problem. Previous studies have proved the FFTW library to be superior to other DFT solving libraries. However, not many have specifically examined the cache memory performance, which is a key factor for overall performance. In this study, we examined the cache memory utilization when computing 1-D complex DFTs using the FFTW library. Testing was done using bench FFT, Linux Perf and testing scripts. The results from this study show that cache miss ratio increases with problem size when the input size is smaller than the theoretical input size matching the cache capacity. This is also verified by the results from the L2 prefetcher miss ratio. However, the study show that cache miss ratio stabilizes when exceeding the cache capacity. In conclusion, it is possible to use bench FFT and Linux Perf to measure cache memory utilization. Also, the analysis shows that cache memory performance is good when computing 1-D complex DFTS using the FFTW library, since the miss ratios stabilizes at low values. However, we suggest further examination ofthe memory behaviour for DFT computations using FFTW with larger input sizes and a more in-depth testing method.