  Discrete cosine transform (DCT) and other Fourier-related transforms have
broad applications in scientific computing. However, off-the-shelf
high-performance multi-dimensional DCT (MD DCT) libraries are not readily
available in parallel computing systems. Public MD DCT implementations leverage
a straightforward method that decomposes the computation into multiple 1D DCTs
along every single dimension, which inevitably has non-optimal performance due
to low computational efficiency, parallelism, and locality. In this paper, we
propose a new acceleration paradigm for MD DCT. A three-stage procedure is
proposed to factorize MD DCT into MD FFT and highly-optimized
preprocessing/postprocessing with efficient computation and high arithmetic
intensity. Our paradigm can be easily extended to other Fourier-related
transforms and other parallel computing systems. Experimental results show that
our 2D DCT/IDCT CUDA implementation has a stable, FFT-comparable execution
time, which is $2\times$ faster than the previous row-column method. Several
case studies demonstrate that a promising efficiency improvement can be
achieved with our paradigm. The implementations are available at
https://github.com/JeremieMelo/dct_cuda/tree/reconstruct.
