查看文章

Several SOA (state of the art) self-tuning software libraries exist, such as the Fastest Fourier Transform in the West (FFTW) for fast Fourier transform (FFT). FFT is a highly important kernel and the performance of its software implementations depends on the memory hierarchy's utilization. FFTW minimizes register spills and data cache accesses by finding a schedule that is independent of the number of the registers and of the number of levels and size of the cache, which is a serious drawback. In this paper, a new methodology is presented, achieving improved performance by focusing on memory hierarchy utilization. The proposed methodology has three major advantages. First, the combination of production and consumption of butterflies' results, data reuse, FFT parallelism, symmetries of twiddle factors and also additions by zeros and multiplications by zeros and ones when twiddle factors are zero or one, are fully …