FFTASI：基于算法专用指令的快速傅立叶变换代码生成框架的研究与优化分析

427→海报：通过FFT特定的内在函数在CPU上生成快速FFT内核中国科学cs@gmail.com计算技术研究所国家重点实验室华为技术有限公司公司ysunshining@icloud.com华为技术有限公司公司HaipengJiaJiangeng@ict.ac.cn中科院计算所ei21b@ict.ac.cn中国科学院计算技术研究所SKLP张云泉q@ict.ac.cn中科院计算所陈敦chentun@ict.ac.cn中科院计算所摘要提出了一种基于算法专用指令（ASI）的快速傅立叶变换（FFT）代码生成框架（FFTASI），用于在FPGA中生成统一的结构，与底层架构紧密相关，Butterfly的性能可移植性较差。当一个新的架构出现时，这些蝴蝶需要重新优化以保持性能。依赖的蝶形核可以被转换成通过建立ASI与用于各种硬件平台的架构特定指令之间的映射，来实现架构相关的内核。FFTASI在CPU的性能和生产力之间取得了很好的平衡CCS概念：·软件及其工程软件库和仓库;源代码生成.关键词：FFT，FFTASI，SVE，RISC-V，代码生成1引言快速傅立叶变换（FFT）是高性能计算（HPC）的七大计算模式之一[1]。一个通用的FFT库，如FFTW [2]，需要支持大量的蝶形内核，用于各种根FFT核生成ASI块来处理任意大小的DFT然而，随着计算机体系结构的多样性和复杂性的增加，高性能FFT库的开发面临两个主要挑战：1）难以优化。由于不同的根有多种类型的蝴蝶，不同的蝴蝶有自己的计算特性，优化它们需要不同的优化策略。（2）港硬因为蝴蝶的表演Correpondingauthor允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，无需付费，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页上带有此通知和完整的引用本作品的第三方组件的版权必须得到尊重。 对于所有其他用途，请联系所有者/作者。PPoPP©2023版权归所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.3577477图1.FFTASI框架2 FFTASI框架FFTASI旨在平衡各种架构上FFT库的性能、可移植性和生产力它目前支持ARM NEON、SVE和RISC-V架构。如图 FFTASI 包 含 五 个 组 件 ： 1 ） 计 算 流 设 计 器 基 于AutoFFT的优化FFT公式[ 3，4 ]定义计算流，最大限度地计算流包含专家优化经验和 FFT特性。这些与架构（arch）无关的流是整个FFTASI框架的性能保证。2）ASI设计器提取FFT的基本操作，并将它们定义为一组称为ASI的算法特定的SIMD内在函数。这些自定义的ASI是基本的算术运算，如复数加法，需要表达计算算法逻辑优化的FFT公式基本操作计算流设计器计算流ASI块构造函数ASI设计师ASI Intrinsics霓虹黄油杏仁生成器非拱形ASI黄油果仁SVE奶油夹心TransformerRISC-VArch-Specific Butter内核…Arch-Specific Butter Butterfly KernelSet428PPoPP自动FFT ARMPL FFTW FFTE(a) SVE，2例1086425.54.53.52.51.5(b) SVE，非2n(c) 霓虹灯，2个98765435.55.04.54.03.53.0(d) 氖，非2n2.01.51.00.5(e) RISC-V，2个2.01.51.00.50.0(f) RISC-V，非2n图2.ARMSVE、NEON和RISC-VCPU上的双精度1D复数FFT性能溪流它们独立于ISA，确保跨不同平台的可移植性3）ASI块构造器构造多个ASI块以使用ASI将计算流精确地表示为ASI流由于ASI块可以高效准确地表达计算流，因此它们可以为自动生成与拱无关的ASI蝶形核提供动力。4）蝶形内核生成器从计算流继承计算逻辑和优化信息，并根据需要调用精心设计的ASI块，以生成所有根的与拱无关的ASI蝶形内核。5）蝶形内核Transformer建立ASI和特定ISA之间的映射，将与拱无关的ASI蝶形内核转换为高效的拱相关内核。FF-TASI将硬件相关信息限制为ASI和ISA之间的映射。在此过程中，开发人员不需要熟悉FFT。为了确保高性能，FFTASI结合专家为了确保生产力，FFTASI降低并限制了硬件对ASI和指令集架构（ISA）之间映射的依赖性。3评价实验在三种体系结构上进行：1）ARM处理器，采用SVE-256。2）鲲鹏920，一款基于ARM NEON的处理器。3）基于RV 64 GC的RISC-V处理器--玄铁C910 MP。FFTASI是用四种有代表性的FFT库进行评估的：1）事实上的标准FFT库FFTW;2）ARM官方FFT库，ARMPL; 3）AutoFFT，一个可以生成汇编FFT代码的库; 4）FFTE，第一个支持ARM SVE-512的软件包，带有SPIRAL生成的FFT内核。我们使用ARM NEON、SVE和RISC-V架构上的同类最佳FFT库评估FFTASI，如图所示。2.在ARM NEON和ARMSVE架构上，FFTASI的运行速度比优化良好的AutoFFT慢约11%，但平均速度分别比最广泛使用的FFT库FFTW、ARM官方产品ARMPL和使用SPIRAL生成的SVEFFT内核的FFTE至于RISC-V架构，FFTASI的性能比FFTW提高了3倍。值得讨论的是，FFT和AutoFFT。 FFTASI和AutoFFT采用相同的优化公式。然而，在代码生成期间，FFTASI将优化放在较高的SIMD内函数级别，以降低优化难度并提高开发效率，将寄存器分配和使用策略留给后端编译器。这是FFTASI在性能和生产力之间做出的4结论本文提出了一种新的FFT代码生成框架，FFTASI，以平衡FFT的性能和生产力 FF-TASI利用集成了优化经验的ASI表达式系统，生成统一的与架构无关的ASI蝶形内核，通过建立ASI与各种架构的特定指令之间的映射，可以将其转换为硬件特定内核。FFTASI的运行速度比汇编优化的AutoFFT稍慢，但通常比其他最先进的库（如FFTW、ARMPL和FFTE）快。致谢作者要感谢所有的评论者，感谢他们富有洞察力的评论。本工作得到了国家自然科学基金项目61972376号 、 62072431 号 、 62072432 号 、 62072433 号 、62072434号、62072435号、62072436号、62072437号的资助。62032023。引用[1] Krste Asanovic，Ras Bodik，James Demmel，Tony Keaveny，KurtKeutzer，John D Kubiatowicz，Edward A Lee，Nelson Morgan，George Necula，David A Patterson，et al.2008年加州大学伯克利分校的并行计算实验室加州大学伯克利分校EECS系。 Rep（2008）.[2] Matteo Frigo和Steven G.约翰逊2005年FFTW3. Proc. IEEE 93，2（2005），216-231. 关于“程序生成、优化和平台适配”的特刊[3] ZhihaoLi ， Haipeng Jia ， Yunquan Zhang ， Tun Chen ， LiangYuan，Luning Cao，and Xiao Wang. 2019. AutoFFT：一个基于模板的FFT代码自动生成框架，适用于ARM和X86 CPU。高性能计算、网络、存储和分析国际会议集。1比15[4] Zhihao Li ， Haipeng Jia ， Yunquan Zhang ， Tun Chen ， LiangYuan，and Richard Vuduc. 2020年。在arm和x86处理器上自动生成高 性 能 fft 核 IEEE Transactions on Parallel and DistributedSystems31，8（2020），1925-1941。GFLOPSGFLOPS1632641282565121024204840968192163843276865536131072254981225343441567729875112528353969562515435198452778335721428755512577175GFLOPSGFLOPS1632641282565121024204840968192163843276865536131072254981225343441567729875112528353969562515435198452778335721428755512577175GFLOPSGFLOPS1632641282565121024204840968192163843276865536131072254981225343441567729875112528353969562515435198452778335721428755512577175