Page 210 - 《软件学报》2020年第10期

3186 Journal of Software 软件学报 Vol.31, No.10, October 2020

的 cache 容量为 256KB.每个从核采用了私有的 16KB 的 L1 指令 Cache 和 64KB 的 SPM(scratch pad memory).
SPM 可看作用户可控的局部数据存储 LDM(local data memory),并利用 DMA(direct memory access)控制器实现
解析和管理主存与 LDM 间的数据传输.此外,从核还提供高效的寄存器通信机制,能够使核组内同行/列的从核
进行数据交换,能够让每个从核向它的同行/列的其他从核发送(源方)或者接收(目标方)数据,源方和目标方利
用生产者-消费者模式完成数据交换.寄存器通信由 PUT 和 GET 指令对组成,源方使用 PUT 指令将通用寄存器
中的一个向量长度的数据经过从核通信网络,送入一个或者多个目标方的接收缓冲中.目标方使用 GET 指令从
接收缓冲中读取数据并送入本地通用寄存器.并行编程模型上,对于一个核组,应用程序由主核启动,借助高性
能线程库 Athread 将计算任务异步加载到从核执行,双方通过同步接口协同.由于申威 26010 处理器复杂的架构
特性,针对 FFT 算法的特点,我们主要从 LDM、DMA 和寄存器通信机制这 3 个体系结构特性来提高带宽的利
用率,从而获得较好的性能.

2 相关工作
近年来,有很多研究工作致力于 CPU、GPU 和 MIC 等平台上对 FFT 算法进行并行优化,并开发出多个优
[6]
秀的软件包.CPU 上比较著名的软件包主要包括 FFTW(fastest Fourier transform in the west) [4,5] 、UHFFT 、
[7]
SPIRAL 、ESSL 和 MKL 等.FFTW 由 MIT 的 Frigo 和 Johnson 开发,是目前使用最为广泛、运算速度较快的
离散傅立叶变换计算库.其不是采用固定算法计算变换,而是在运行时根据具体硬件和变换参数自动地选择最
佳的分解方案和不同算法,以期达到最佳效果.本文在测试算法的整体性能时会与 FFTW 库的性能进行对比.
[8]
GPU 上主要包括 CUFFT、GPUFFTW、AccFFT、FFTE 和 P3DFFT 等.其中,CUFFT 是由 NVIDIA 提供的基
于 GPU 的快速傅里叶变换函数库,它基于 Cooley-Tukey FFT 和 Bluestein 算法并采用分治的算法.GPUFFTW 项
目由美国北卡罗莱纳大学提出,使用 Stockham 的 Autosort 方法实现了基于 GPU 的一维傅立叶变换,运算速度最
高可达 29GFlops.AccFFT 采用两种数据分解方式并基于 CUFFT 和 FFTW 库实现分布式 FFT 计算,支持 CPU
和 GPU. FFTE 是 HPC challenge benchmark 的组成部分,主要利用了 cache 分块技术和 Stockham 的自动排序技
术.MIC 上主要是 Intel 公司随 MIC 协处理器发布的 MKL 数学库.
[9]
目前,对 FFT 算法的优化策略主要包括两种 :(1) 数据分块.利用分块技术对数据进行处理,将子块的数据
[8]
传输到每个处理器(线程),一般针对三维 FFT 计算;文献[9]、AccFFT、PFFT [10] 、P3DFFT 、Takahashi [11] 、
2DECOMP & FFT 和 Song [12] 等策略均利用数据分块策略进行并行优化,其中,AccFFT、PFFT、2DECOMP & FFT
和 Song 考虑了通信优化问题.另外,文献[13,14]研究了天河 1A 大型 GPU 异构集群系统上基于 Parray 语言的数
组维度类型程序设计方法.(2) 算法分解.利用算法(如 Cooley-Tukey FFT)将一个较大规模的一维 FFT 分解成一
系列较小规模的一维 FFT,每个处理器(线程)并行地完成较小规模的 FFT.文献[15,16]尝试着在 IBM Cylops 64
上使用 Cooley-Tukey FFT 算法优化 FFT 计算,并且提出了一个针对该框架的性能模型.文献[17]是在 GPU 上基
于 Stockham FFT 框架和 Cooley-Tukey FFT 算法实现,并在文献[18]中提出了一个用于生成 GPU 上优化的 FFT
内核的自动优化框架.文献[19]提出了一种基于 Cooley-Tukey FFT 算法和一套高效小规模 codelet 代码的计算
多维 FFT 框架.文献[20]在单线程 MKL 的基础上,利用 Cooley-Tukey FFT 算法和 Intel Cilk Plus 的计算框架实
现多线程并行.Nukada 等人也在文献[21−24]中对 3D FFT 算法在 GPU 架构上进行了一系列的研究.文献[25]在
单 MIC 节点上基于 Cooley-Tukey FFT 算法利用两种分解算法和两层并行方法实现了访存高效的两遍 3D FFT
算法.文献[26]在 Intel Xeon Phi 协处理器集群上实现了分布式 1D FFT 的计算并进行了访存与计算的重叠优化.
另外,文献[27]主要对 FFT 的性能进行了分析,也有一些文献 [28−32] 对稀疏型的 FFT 进行了研究,文献[33]采用快
速多极子方法来减少通信需求,文献[34]在 FFT 算法的容错方面进行了研究.
在“神威·太湖之光”上已完成的各类运算任务中,其优化主要从 LDM、DMA、向量化、计算访存重叠和寄
存器通信等方面进行设计,主要包括:杨超团队 [35] 的大气动力模拟应用项目,其获得了国际高性能计算应用领域
的最高奖“戈登贝尔奖”;付昊桓团队完成的“基于神威太湖之光的非线性地震模拟” [36] ,其获得 2017 年的“戈登
贝尔奖”;文献[37]主要是对 stencil 计算进行了优化,作者提出了一种求解欧拉大气动力学方程的有效数据流方