本文是一篇计算机论文范文，本文设计了一种针对ARMv8架构的实数FFT算法优化技术体系。结合ARMv8架构特征，采用SIMD向量化技术，对实数FFT算法的并行、蝶形网络、访存以及寄存器的使用等都进行了优化。提升了实数FFT算法在ARMv8平台上的性能的同时，也对其他算法在ARM处理器上的实现和部署有着一定的参考意义。
1 绪论
1.1 研究背景及意义
高性能计算已被公认为继理论科学和实验科学之后，人类认识并改造世界的第三大科学研究方法，是科技创新的重要手段[1-2]。高性能计算与理论科学和实验科学相比，有其三个重要的优越性[3]。首先，高性能计算能够有效的避免真实实验带来的资源消耗，避免材料的浪费。其二，能够最快速度的获取和掌握研究对象发展变化的所有信息，加快科研工作者的研究进度。三，能够低成本反复地进行研究实验，减少资金对研究工作的限制。作为当前社会科技创新的重要手段，高性能计算被广泛应用于计算金融、国防科技、医学成像、图像编码、大数据分析、CAE仿真、动漫渲染、物理化学、石油勘探、生命科学、气象环境等众多领域[1]。
虽然我国计算机行业相较于美国等一些西方国家兴起较晚，但近年来，我国对基础硬件设施的不断投入，超级计算机的发展也从零起步，到现在已是世界先进水平。国内的“神威·太湖之光”超级计算机和“天河二号”超级计算机[4]至今依旧位列全球超级计算机500强前列。与高性能超级计算机的快速发展相比，我国的科学计算基础软件生态发展速度相对较缓，相对于世界上的一些超算强国仍具有一定的差距。科学计算，如核心数学库、并行计算库和高性能计算中间件等一些基础软件栈较为缺乏[2]。科学应用软件长期依赖于国外软件，已成为制约我国高性能计算发展的重要原因。作为科学计算中最重要算法之一的快速傅里叶算法，其研究与高性能实现对于高性能计算应用程序的发展有着重要的意义。
1.2 国内外研究现状
1.2.1 相关算法库
FFT算法是高性能领域中最为重要的基础算法之一。被IEEE期刊“科学与工程计算”评为二十世纪的十大算法之一[13]。一个高性能的FFT算法库能够为科学计算提供强有力的支撑，因此，各个开源社区和硬件厂商都结合不同的处理器架构特征，研制出自家的高性能算法库，以完善相应的软件生态，满足用户的科学计算和应用需求。如，麻省理工学院的开源FFTW库、Intel的MKL商业库、ARM厂商的ARMPL库、AMD的AOCL数值计算库和NVIDIA的CUFFT库等众多库。其中，FFTW库、MKL库和ARMPL库较为著名，而FFTW库和ARMPL库针对ARMv8架构做出了相应优化。
1）FFTW开源库
FFTW[7][14-16]（The Fastest Fourier Transform in the West）算法库由麻省理工学院的Matteo Frigo 和 Steven G. Johnson于1997年3月发布，历经二十多年更新维护，现在最新版本是FFTW3.3.9。FFTW作为著名的FFT开源库，有着性能高、可移植性好、一维和多维转换等特点，能够良好地支持任意规模、各种数据类型的离散傅里叶变换（DFT）[14]。由于FFTW相比很多FFT库较早，且得益于移植性好和不俗的性能，目前已普遍被学术界和工业界所接受，许多硬件厂商的数值库也提供了FFTW函数接口规范，便于用户的应用程序适应自家计算机系统。
2）ARMPL商业库
ARMPL[17]（ARM Performance Libraries）商业库是ARM公司为完善ARM的软件生态和满足用户的高性能计算需求针对ARMv8平台推出的高性能商业库。在ARM服务器和HPC领域，ARMPL扮演着重要的角色，为ARM处理器上的高性能计算应用程序提供优化，支持FFTW的guru和MPI接口。
2 处理器架构和并行优化技术
2.1 ARMv8架构
ARM[28]（Advanced RISC Machine）体系架构是ARM公司为满足市场低成本、低功耗和高性能的需求，所研制的处理器架构。其广泛应用于移动通信领域、嵌入式领域以及服务器领域等众多领域。目前高性能计算机世界500强第一位的日本超级计算机Fugaku（富岳）正是以富士通的48核ARM处理器A64FX打造而成。自二十世纪八十年代，ARM初代体系架构发布以来，已更新迭代了9个主要版本，每代版本的设计都有差异，目前最新版本为ARMv9。由于ARMv9发布不久，且ARMv8仍是市场主流，因此本文的工作在ARMv8处理器上进行完成，对ARM体系架构的介绍也围绕ARMv8架构展开[29]。
现如今的主流CPU计算平台中，SIMD向量化技术是一种非常常见的、用于增加处理器计算效率的并行技术。ARMv8架构是首款支持64位指令集的ARM架构，采用了NEON技术[30]来支持SIMD向量化，同时提供了32个128位宽的浮点数寄存器，一个寄存器上可一次处理4个单精度浮点数或者两个双精度浮点数，能够有效增加浮点数寄存器的吞吐量。ARM软件生态相较于X86较差，提供的优化库空间也比较有限，性能也可能不是最优的一个情况。比如ARM公司针对ARMv8架构提供的高性能库ARMPL的FFT部分，在应用环境中相对于开源FFTW的性能表现不佳，可进一步进行优化[30]。
ARMv8的多级缓存系统[31]。受功耗等各类因素的影响限制，单核处理器的主频不能够无限制的提升，因此处理器逐渐由单核架构往多核架构方向进行发展。同时，多级缓存系统能够有效的节省带宽，提升数据的访问效率。高速缓存技术，能够最大化地发挥程序访问的空间局部性和时间局部性，把处理器将要使用的数据存放到缓存系统中，这样处理器在运行时的访存操作则可以直接在缓存上进行，不用对主存和磁盘进行频繁的访问，避免了程序进入等待期，从而能够最大限度地提高程序的性能。ARMv8架构的处理器通常采用了多层级的访存系统[28]。
2.2 SIMD向量化
随着社会的发展，人类对计算能力的需求愈加的旺盛，高性能计算也愈发的受到人们的重视。高性能计算领域中，大气模拟、石油勘探开发、天体力学、航空航天、基因测序以及科学计算等一系列的问题[1]都需要强大的算力才能完成，而有关这些问题的部分程序代码，往往具有非常高的并行性[32]，因此并行计算技术则显得尤为重要。目前几乎所有主流的处理器厂商都为自家处理器提供了SIMD扩展部件，使其处理器的计算能力尽可能高。
SIMD（Single Instruction Multiple Data，SIMD）指令集[33-37]，即具有单指令多数据流的指令集。随着，英特尔公司于1996年首次在奔腾处理器上面集成了MMX（Multi-Media Extensiona）过后，SIMD向量化扩展随即成为了各大处理器厂商所关注的重点，现在在各个微处理器上已逐渐形成了普及。SIMD扩展对于访存模式重复、天然数据并行以及在局部数据上有重复操作的程序，有着非常明显的性能提升[35]。
ARM架构中的SIMD向量化技术主要是将需要4次读取的浮点数，分1次或者2次读入到浮点寄存器当中，然后使用SIMD指令，并行处理多个数据，增加计算能力和吞吐量，如图2.2 SIMD向量化效果图所示，有四组数据均要做加法操作，若采用标量指令的话，和图中前半部分一样，需要执行四次加法指令才能完成，采用向量化指令，则只需要一条指令，即可完成四组数据的加法操作[39]。因此适当的使用向量化操作能够大幅度提升处理器的性能。各个厂商的处理器支持的浮点寄存器宽度各不相同，其中128位、256位和512位这三种宽度较为常见。ARMv8架构的处理器采用的是128位宽度的浮点寄存器，因此一个浮点寄存器可同时存放四个单精度浮点数或者两个双精度浮点数[28]。
3 实数FFT算法及其改进 ................................ 13
3.1 复数FFT算法原理 ........................................ 13
3.2 传统实数FFT算法 .................................. 16
4 实数FFT算法实现与优化 ....................................... 30
4.1 蝶形网络的优化 ............................................... 30
4.1.1 传统蝶形网络图 ...................................... 30
4.1.2 Stockham蝶形网络图 ................................ 31
5 性能分析 ................................................. 52
5.1 实验环境搭建 ............................................ 52
5.2 测试性能 ............................................. 53
5 性能分析
5.1 实验环境搭建
本文的实数FFT算法在ARMv8架构的鲲鹏920处理器上实现运行，处理器时钟频率为2.6GHz。FFTW库和ARMPL库采用当前最新版本的FFTW 3.3.9和ARMPL 21.0。
FFTW是一个目前应用最为广泛，且非常成熟的FFT开源库，而ARMPL是ARM公司针对ARM平台所开发的高性能商业库，因此针对ARMv8架构的实数FFT，两者是不错的性能比较对象。具体实验环境配置如表5.1。
6 总结与展望
6.1 本文工作总结
我国科学计算经过三十多年的努力和发展，已经取得了非常长远的进步，但仍旧有着许许多多的挑战。经过这么多年的投入和研究，我国超级计算机硬件水平已经处于世界前列，像“神威·太湖之光”和“天河二号”这样的超级计算机历经数年依旧能够保持超级计算机世界500强前列。但目前面对我们国家超级计算机如此深厚的硬件实力，却没有与之相对应的软件生态。由于我国在科学计算软件方面如基础算法库、并行算法库等方面缺乏长期的知识和技术累积，以及资金的投入不足，导致我国科学计算软件严重依赖于国外，已经限制到了我国高性能计算的进一步发展，因此，加强我国科学计算软件的研发，建立长期的发展路线是我国目前高性能计算领域亟待解决的问题。
被美国数学家Gilbert Strang称为“我们一生中最重要的数值算法”的FFT算法，是科学计算领域中，最重要的核心基础算法之一。在众多实时信号处理领域中，FFT算法都是其不可或缺的算法。因此，一个高性能的FFT算法库能够推动科学计算、工程应用等多个领域的发展，同时也能够加速高性能计算的发展。目前各大厂商和研究机构已经构建了复数FFT算法库，能够满足绝大部分的应用。但实数FFT算法在图形图像处理、数据压缩等领域有着复数FFT不可替代的作用。而传统的实数FFT算法，存在着计算优化复杂，实现方式存在冗余操作，并未将实数FFT算法性能优化到极致，面对这些问题，本文在现有基础上开展了如下工作：
1）在离散傅里叶变换基础定义上，对实数FFT算法进行了重新推导实现，最终提出了一种针对实数FFT的快速算法（DRFFT）。并且设计了一种针对实数FFT的计算模式，能够对离散傅里叶变换的输入序列直接进行实数FFT计算，并在实数FFT计算完成后，直接得出所需的输出序列，去除了传统的实数FFT算法的split转换操作，引入和使用了更为简化的R2C蝶形、C2R蝶形、R2C_II蝶形和C2R_II蝶形，降低了访存开销，最大限度的提高了算法的性能。
2）设计了一种针对ARMv8架构的实数FFT算法优化技术体系。结合ARMv8架构特征，采用SIMD向量化技术，对实数FFT算法的并行、蝶形网络、访存以及寄存器的使用等都进行了优化。提升了实数FFT算法在ARMv8平台上的性能的同时，也对其他算法在ARM处理器上的实现和部署有着一定的参考意义。
参考文献（略）