海报：通过FFT特定内核在CPU上生成快速FFT内核

…4270POSTER:通过FFT特定指令在CPU上生成快速FFT内核0Zhihao Lilizhihao.cs@gmail.comSKLP，计算技术研究所，中国科学院华为技术有限公司0Haipeng Jia �0jiahaipeng@ict.ac.cnSKLP，计算技术研究所，中国科学院0Yunquan Zhangzyq@ict.ac.cnSKLP，计算技术研究所，中国科学院0Yuyan Sunsyysunshining@icloud.com华为技术有限公司0Yiwei Zhangzhangyiwei21b@ict.ac.cnSKLP，计算技术研究所，中国科学院0Tun Chenchentun@ict.ac.cnSKLP，计算技术研究所，中国科学院0摘要0本文提出了一种基于算法特定指令（ASI）的快速傅里叶变换（FFT）代码生成框架，名为FFTASI，通过建立ASI和各种硬件平台的架构特定指令之间的映射，生成统一的与架构无关的蝶形核心，可以将其转化为与架构相关的核心。FFTASI在CPU上在性能和生产力之间取得了良好的平衡。0CCS概念： • 软件及其工程 →软件库和存储库；源代码生成。0关键词：FFT，FFTASI，SVE，RISC-V，代码生成01 引言0快速傅里叶变换（FFT）是高性能计算（HPC）的七个计算模式之一[1]。泛用的FFT库，如FFTW[2]，需要支持大量不同基数的蝶形核心，以处理任意大小的离散傅里叶变换（DFT）。然而，随着计算机架构的多样性和复杂性的增加，开发高性能FFT库面临两个主要挑战：1）优化困难。因为不同基数的蝶形核心有不同的计算特性，优化它们需要不同的优化策略。2）移植困难。因为蝶形核心的性能与底层架构紧密相关，所以在新的架构出现时，这些核心需要重新优化以保持性能。0� 相关作者0未经许可，个人或课堂使用本作品的部分或全部的数字或印刷副本是免费的，前提是不得为盈利或商业目的制作或分发副本，并且副本上附有本通知和第一页的完整引用。必须尊重本作品第三方组件的版权。对于其他所有用途，请联系所有者/作者。PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，加拿大©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35774770与底层架构密切相关，蝶形核心的可移植性差。当新的架构出现时，这些蝶形核心需要重新优化以保持性能。0FFT内核生成0算法逻辑0架构特定蝶形核心集0蝶形核心转换器0架构特定蝶形核心0NEON0RISC-V0SVE0优化的FFT公式0蝶形核心生成器0ASI块0与架构无关的ASI蝶形核心0计算流设计师ASI设计师0基本操作0计算流ASI内部指令0ASI块构造器0图1. FFTASI框架02 FFTASI框架0FFTASI旨在平衡不同架构上FFT库的性能、可移植性和生产力。目前支持ARMNEON、SVE和RISC-V架构。如图1所示，FFTASI包含五个组件：1）计算流设计师根据AutoFFT优化的FFT公式[3,4]定义计算流，以最小化算术运算。计算流融入专家优化经验和FFT特性。这些与架构无关的流是整个FFTASI框架的性能保证。2）ASI设计师提取FFT的基本操作，并将它们定义为一组算法特定的SIMD内部指令，称为ASI。这些自定义的ASI是表达计算流所需的基本算术操作，如复数加法。1632641282565121024204840968192163843276865536131072248102549812253434415677298751125283539695625154351984527783357214287555125771751.52.5.54.55.5163264128256512102420484096819216384327686553613107234567892549812253434415677298751125283539695625154351984527783357214287555125771753.03.5.0.55.05.516326412825651210242048409681921638432768655361310720.5.0.52.02549812253434415677298751125283539695625154351984527783357214287555125771750.00.5.01.52.04280PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏郅浩等人，PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魏郅浩等人。0FFTASI AutoFFT ARMPL FFTW FFTE0FFT代码生成框架FFTASI，用于平衡FF0, Ras Bodik, James Demmel, Tony Keaveny, Kurt0图2. ARM SVE、NEON和RISC-V CPU上的双精度1D复杂FFT性能0流。它们与ISA无关，确保在不同平台上的可移植性。3)ASI块生成器使用ASIs将多个ASI块构建为ASI流，以使用ASIs将计算流表达为ASI流。由于ASI块可以高效准确地表达计算流，它们可以为所有基数生成与架构无关的ASI蝶形内核。4)蝶形内核生成器从计算流中继承计算逻辑和优化信息，并根据需要调用精心设计的ASI块以生成所有基数的与架构无关的ASI蝶形内核。5)蝶形内核转换器建立ASI与特定ISA之间的映射，将与架构无关的ASI蝶形内核转换为高效的与架构相关的内核。FFTASI将硬件相关信息限制在ASI和ISA之间的映射上。在此过程中，开发人员不需要熟悉FFT。为了确保高性能，FFTASI结合了专家的优化经验来构建与架构无关的计算流。为了保证生产力，FFTASI将硬件依赖降低并限制在ASI和指令集架构（ISA）之间的映射上。03 评估0实验在三个架构上运行：1）一款带有SVE-256的ARM处理器。2）昆蓬920，一款基于ARMNEON的处理器。3）玄铁C910MP，一款基于RV64GC的RISC-V处理器。FFTASI使用四个代表性的FFT库进行评估：1）事实上的标准FFT库FFTW；2）ARM官方的FFT库ARMPL；3）AutoFFT，一个可以生成汇编FFT代码的库；4）FFTE，第一个支持基于SPIRAL生成的SVE FFT内核的ARMSVE-512的包。我们在ARMNEON、SVE和RISC-V架构上使用最佳FFT库对FFTASI进行评估，如图2所示。在ARM NEON和ARMSVE架构上，FFTASI的运行速度比经过优化的AutoFFT略慢，但平均比最广泛使用的FFT库FFTW、ARM官方产品ARMPL和使用SPIRAL生成的SVEFFT内核的FFTE分别快1.36倍、1.41倍和1.56倍左右。至于RISC-V架构，FFTASI相对于FFTW实现了3倍的性能提升。0值得讨论FFTASI和AutoFFT之间的性能差距。FFTASI和AutoFFT都采用了相同的优化公式。然而，在代码生成过程中，FFTASI将优化放在较高的SIMD内部函数级别，以减少优化困难，提高开发效率，而将寄存器分配和使用策略留给后端编译器。这是FFTASI在性能和生产力之间的妥协。0结论0本文提出了一种新颖的FFT代码生成框架FFTASI，用于平衡FFT的性能和生产力。FFTASI利用ASI表达系统，集成了优化经验，生成统一的与架构无关的ASI蝶形内核，可以通过建立ASI和各种架构的特定指令之间的映射将其转化为硬件特定的内核。FFTASI的运行速度略慢于汇编优化的AutoFFT，但通常比其他最先进的库，如FFTW、ARMPL和FFTE等，快得多。0致谢作者要感谢所有审稿人对他们深思熟虑的评论。本工作得到中国国家自然科学基金会的资助，资助号码为61972376、62072431、62032023。0参考文献0[1]  Krste Asanovic, Ras Bodik, James Demmel, Tony Keaveny, KurtKeutzer, John D Kubiatowicz, Edward A Lee, Nelson Morgan, GeorgeNecula, David A Patterson等. 2008. 基于伯克利观点的UCBerkeley并行计算实验室的研究议程。加利福尼亚大学伯克利分校EECS系，技术报告(2008)。0[2]  Matteo Frigo和Steven G. Johnson. 2005. FFTW3的设计和实现。Proc.IEEE 93, 2 (2005), 216–231。关于“程序生成、优化和平台适应性”的特刊。0[3]  Zhihao Li, Haipeng Jia, Yunquan Zhang, Tun Chen, Liang Yuan,Luning Cao和Xiao Wang. 2019. AutoFFT:一种基于模板的用于ARM和X86CPU的FFT代码自动生成框架。在高性能计算、网络、存储和分析国际会议论文集中。1-15。0[4]  Zhihao Li, Haipeng Jia, Yunquan Zhang, Tun Chen, Liang Yuan, andRichard Vuduc. 2020. ARM和x86 CPU上高性能FFT内核的自动生成。IEEETransactions on Parallel and Distributed Systems 31, 8 (2020),1925–1941。