ARM与X86-64平台上的FFT优化：库利-图基算法新进展

"对Cooley-Tukey FFT算法的高性能实现与优化进行了深入研究，探讨了在ARMv8和X86-64架构上的优化策略，包括蝶形网络重构、计算公共项提取以及汇编级别的SIMD优化。" 快速傅里叶变换（FFT）是一种在计算离散傅里叶变换（DFT）时显著提高效率的算法，其核心思想是将大问题分解为小问题，将计算复杂度从O(n^2)降至O(n log n)。这种高效的计算方法使得FFT在众多领域中得到广泛应用，如物理、天文学、工程、数学、密码学以及金融计算等。特别是在大型科学项目如平方公里阵列射电望远镜（SKA）中，FFT承担着巨大的计算任务，占总计算量的40%，因此对FFT的高性能实现和优化具有极高的需求。 尽管已有如ARMPL、Intel MKL和FFTW等成熟的FFT实现库，但面对算法的复杂性和应用需求的增长，仍存在优化空间。Cooley-Tukey算法作为最常用的FFT算法，其蝶形网络结构复杂，计算多样性，以及在大基实现时遇到的汇编实现困难和寄存器管理问题，都是亟待解决的关键挑战。 本文的研究重点在于三个方面：首先，通过重构蝶形网络，减少大基情况下的网络级数，降低内存访问频率，提升性能；其次，利用DFT矩阵的特性，提取蝶形计算中的公共项，简化大基计算过程；最后，采用汇编语言进行SIMD优化，结合寄存器复用和堆栈内存管理策略，有效应对寄存器不足的问题。 经过这些优化，本文在ARMv8和X86-64平台上成功实现了高性能的FFT算法库，突破了大基计算的性能瓶颈。实验结果显示，相较于FFTW、ARMPL和Intel MKL，这个新库在性能上有所提升，证明了所提出的优化方法的有效性。 这篇研究不仅深化了我们对FFT算法的理解，还为未来硬件平台上的FFT优化提供了新的思路和实践案例，对于提升科学计算和工程应用的效率具有重要意义。