DOI ： 10.7544/issnl000-1239.2021.20210069
58(6) : 1192 1203, 2021
计算机研究与发展
Journal of Computer Research and Development
王谛石嵩吴铁彬刘亮谭弘兵郝子宇过锋李宏亮
(江南计算技术研究所江苏无锡214083)
(*********************)
A High Performance Accelerator Design for Ultra-Long Point Floating-Point FFT
Wang Di, Shi Song, Wu Tiebin, Liu Liang, Tan Hongbing, Hao Ziyu, Guo Feng, and Li Hongliang
iangnan Institute of Computing Technology , Wuxi , Jiangsu 214083)
Abstract Fast Fourier transform (FFT) plays a key role in digital signal processing. With the
increasing demand of high performance ultra-long point FFT , digital signal processor (DSP ) is
becoming more and more dificult to meet the demand, so integrated FFT accelerators have become an important development trend. In order to support ultra-long point FFT , this paper extends the two dimensional decomposition algorithm of FFT to multi-dimensional , and we propose a high
performance ultra-long point FFT accelerator architecture which can be integrated into DSP. In this architecture, three-dimensional transposition operation is realized by using collision-free addressing
method with prime number memory banks ; efficient twiddle factor generation is realized by recursive algorithm ； FFT operation circuit is refined by using single precision floating-point fused dot product
and fused add-subtract operation. Finally, this paper realizes the single precision floating-point
FFT calculation within 4G points. The synthesis result shows that the proposed FFT accelerator can run at
a frequency of more than 1GHz and its performance can reach 640Gflop/s, which has been greatly
improved in terms of points and performance compared with the existing research.
Key words fast Fourier transform (FFT ) ； multi-dimensional decomposition algorithm ； three
dimensional transposition operation ； twiddle factor generation ； accelerator
摘 要 快速傅里叶变换(fast Fourier transform, FFT)在数字信号处理中占据核心地位.随着高性能
超长点数FFT 需求的增长，数字信号处理器(digital signal processor, DSP)的计算能力越来越难以满
足需求，集成FFT 加速器成为重要的发展趋势.为了支持超长点数FFT，将2维分解算法推广到多维 ,
提出一种可集成于DSP 的高性能超长点数FFT 加速器结构.该结构通过基于素数个存储体的无冲突
体编址方法实现了 3维转置运算；通过递推算法实现了高效铰链因子生成；使用单精度浮点二项融合点 积运算和融合加 减运算，对FFT 运算电路进行了精细化设计.实现了对4G 点数单精度浮点FFT 计算 的支持.综合结果表明:FFT 加速器运行频率能够达到1 GHz 以上，性能达到640Gflop/s.在支持的点数 和性能方面都较已有研究成果取得大幅提升. 关键词 快速傅里叶变换；多维分解算法；维转置运算；铰链因子生成；加速器
中图法分类号TP332
收稿日期：2021—01—20；修回日期=2021-04-23
基金项目：“核高基”国家科技重大专项基金项目(2018ZX01028-102)
This work was supported by the National Science and Technology Major Projects of Hegaoji (2018ZX01028-102).
通信作者：李宏亮(hongliangli@ 2 63 )
王谛等：一种高性能超长点数浮点FFT加速器设计193
离散傅里叶变换(discrete Fourier transform, DFT)作为时域和频域转换的基本运算，在数字信号处理中占据核心地位［1］，应用领域十分广泛.快速傅里叶变换⑵(fast Fourier transform,FFT)是DFT的快速算法，FFT的提出促进了数字信号处理的发展，被评选为20世纪科学和工程界最具影响力的十大算法之一［3］.随着高速采样和实时信号处理技术的发展，高性能超长点数FFT的需求迅速增长⑷.由于FFT的算法复杂度为O(N lg N),FFT 和以FFT为基础的各类时频变换算法的计算占比愈发凸显.例如，在国际大科学工程一一平方公里阵列(square kilometer array,SKA)射电望远镜项目中，FFT的计算占比达40%［］.目前已有FFT计算架构的最大吞吐率能达到100GS/s量级讯，并且吞吐率需求以指数级速度增长，大概每5年增长10倍［7］,
数十年来发展出数字信号处理器(digital signal processor,DSP)、现场可编程门阵列(field programmable gate array,FPGA)和专用集成电路(application specific integrated circuit.,ASIC)等多种数字信号处理平台.DSP具有强大的运算能力和良好的可编程性，在满足性能需求的条件下，DSP是构建数字信号处理系统的首选器件.但受到指令串行执行和处理器寻址模式的限制，传统DSP的FFT 运算能力低于FPGA和ASIC实现归.
“通用核心+加速器”的结构在获得通用处理器可编程性和灵活性的同时又能提升特定应用的性能与功耗效率，是未来处理器发展的重要方向.为了提高DSP的FFT处理能力，在DSP中集成FFT加速器成为必然选择，已有大量理论研究［9］和实际产品［10］出现.现有研究成果存在2点不足：1)与DSP 核心
相比，FFT加速器的峰值性能没有体现出明显优势；2)对于超长点数FFT的支持能力有限.
本文针对集成于DSP的FFT加速器开展研究工作.注意到将FFT的2维分解算法推广到多维后，可以将每一维的点数控制在16个点以内，从而能用固定的小点数FFT实现几乎任意长度的FFT，本文在此基础上提出面向超长点数FFT的多维分解算法.针对FFT多维分解算法中的转置和较链因子生成这2种核心运算开展研究，提出了素数体片上3维转置存储器结构解决访存带宽利用率低的问题，提出了较链因子递推生成算法解决坐标旋转数字计算机(coordinate rotational digital computer, CORDIC)算法迭代计算周期长的问题.最后，对每一维处理中的小点数FFT进行了精细化电路设计.本文设计的FFT加速器能够实现最长4G点数的单精度浮点FFT计算，运行频率能够达到1GHz以上，性能达到640Gflop/s.在点数和性能方面都较已有研究成果取得大幅提升.
1相关研究
经过数十年的研究，FFT算法发展了许多种类.根据运算形式的不同可以将FFT分为时间抽选(decimation in time,DIT)和频率抽选(decimation in frequency,DIF).根据基本蝶形运算单元的粒度则可以将FFT分为基2、基4、基8、基16、多基和素数基等.与此同时，大量的流水化和并行化FFT实现结构也被提出，例如阵列并行结构、单路延时置换(single-path delay commutator,SDC)结构、单路延时反馈(single-path delay feedback,SDF)结构、多路延时置换(multi-path delay commutator,MDC)结构和多通路延时反馈(multi-path delay
feedback,MDF)结构等［9］.
许多研究针对基本运算单元进行精细化设计例如，采用基22算法1，对偶序号使用基2算法，对奇序号使用基4算法，减少运算量；采用不同实现方式的乘法器［11］获得较小的开销；以CORDIC算法为基础，将复数乘法与旋转因子求值统一到一个迭代运算中［12］，减少蝶形运算复杂度；通过运算过程中的动态位宽调整［13］，减少资源开销和功耗；采用二项融合点积(fused dot product,FDP)运算和融合加减(fused add-subtract,FAS)运算［14］，实现高效的浮点复数运算.这些研究在小点数FFT计算中普遍取得明显的优势，然而，提升长点数FFT计算效率需要超出基本运算单元的范畴进行考虑.
对于长点数FFT，计算的中间结果无法全部存储在芯片内部.Winograd傅里叶变换算法［15］(Winograd Fourier transform algorithm,WFT A)利用旋转因子特性对FFT进行分解，使用规模较小的2维FFT模拟实现规模较大的一维FFT，是一种高效且资源占用相对较少的FFT实现方法.在处理器"17］和FPGA［418］上对长点数FFT的实现普遍采用了这种2维分解算法.
长点数FFT加速器的研究大多在2维分解算法基础上进行改进.Yang等人采用一种支持基2、基4、基8、基16可重构运算单元，实现FFT运算中蝶形运算单元的灵活配置，达到最佳的能效.
1194计算机研究与发展2021,58（6）
Tang等人提出一种基数灵活可配的MDF结构，适用于可变长度多路FFT.Chen等人"口提出一种基于CORDIC算法的可重构浮点FFT加速器结构，通过旋转方向预测减少硬件开销，通过旋转角度的实时生成节省存储需求.于东等人[22]在FFT处理器中将缓存划分成32个体，通过对缓存的灵活调度实现“乒乓”操作，提高长点数FFT的运算性能.雷元武等人⑷设计了一种基于矩阵转置操作的可变长度FFT加速器结构，提出“乒乓”多体数据存储器、基于基本块的快速矩阵转置算法、结合查表和基于CORDIC算法的混合旋转因子产生策略等优化方法.在这些研究中，运算量的精简、旋转因子高效生成和提高存储访问效率始终是关注的重点.
2算法分析
2.1FFT算法介绍
N点序列X o，x,…，x”}的DFT定义为
N-1
X严DFT（x”）=Y（x”W N）,（1）
”=0
其中,€[（）,N—1]，旋转因子W n=e N
Cooley-Tukey算法⑵是目前应用最为广泛的FFT算法.根据旋转因子（W N）在计算过程中的位置分为DIT和DIF两类.
以基2DIT算法为例进行简要说明[23].当N 为偶数时，令X）”=X2…,X1,=X2”1（0W”W N/2—1,”为整数）.若X o,=DFT（x o,）X i,= DFT（x i,）,（0W k W N/2—1，为整数），则:
X k=X o,+X1,wn,
{”（2）
\x k2=X o,—X1,W N.
式（2）表明：若将任何一偶数点序列按”的奇偶性分成2个子序列，则原序列的DFT可由2个子序列DFT的线性组合得到.
按照式（1）直接进行N点DFT计算，需要N2次复数乘法和N（NT）次复数加法，而采用式（2）的蝶形运算方法则只需（N lb N）/2次复数乘法和N lb N次复数加法.FFT算法极大缩减了DFT的运算量.
2.2多维分解FFT算法
pcg
观察式（2）可以发现，每一级蝶形运算的输入数据都是上一级蝶形运算输出数据混洗的结果.而且，随着蝶形运算级数的增加，混洗的范围越来越大.这就导致，当FFT的点数长到无法在加速器内部一次性加载所有输入数据的时候，将会产生大量的非连续访存，这与半导体存储器采用并行总线方式提高带宽的机制不兼容.对于超长点数FFT运算需要到访存连续性较好的算法.
假设N=L X M，由式（1）得：
L-1M-1
X p X M+q=为（（（工（X m X L+l wm）w q w i p）,（3）l= 0'm=0
其中,p€[0,L—1],q€[0,M—1].
从式（3）可以看出,N点DFT分解为了2维.第1维是独立的L组M点DFT（其结果需要乘以铰链因子W N），第2维是独立的M组L点DFT.所以，可以将长点数FFT转化为小点数FFT的2维分解: 1）将N点的数据分解为L行M列的矩阵; 2）对所有行分别做M点的FFT；3）将所有元素与各自的较链因子相乘；4）进行矩阵转置，得到M行L列的矩阵；5）对所有行分别做L点的FFT；6）再次进行矩阵转置，得到结果.
将上述2维分解进一步推广.假设N=B d，由式（3）得:
B-1
Y0=（工（X”d_1B d-1+”4_2丽-2+•••+”B+g W B-1d-1））”d-1=0
（”d_2B d-2+------”B+^0）
W d
Y
B-
=（丫（Y0W k-2d-2
”B-2=0
））w B-”B d-3-----”B+”n）
B-
y-2=（
E”））w d0,
”=0
X k0B d-1+k1B d-2+—+k d-2B+k d-1=Y d-1=
B-
、E y—w；"”。）,
”0=0
（4）其中, ”0,”1,1G[0,B—I]；k0,k1,・・・,k1G [0,B—1].根据式（4）可以得到基础FFT点数为B 的d维分解算法.
算法1.FFT的多维分解算法.
FFT_MD（d；X0,x1，…，x b”1）:/*递归定义B点FFT作为基本运算，参数d为维度*/
①for i from0to B d1―1do
②（0,1，…,B1）~（x i，x；f—1i,x-B f—1i，
…1）B f—1i）；
③（几右，…，"1）~FFT（0…1）;
④if d Hl then
⑤（0t1，…t B1）~（0，t1，…1）
（w；d,w；d,…,w；T）；
王谛等：一种高性能超长点数浮点FFT加速器设计1195
⑥end if
⑦(X i，:c B f-1,,x B
(10,t1,…，，B1)；
⑧end for
⑨if d M1then
⑩for i from0to B—1do
⑪FFT_MD(d—1；x,B d-1,x,B d-1t,
…，X,B—1B d-11)；
⑫end for
⑬end if
算法1总共进行d轮，每轮完成B d1组B点FFT.每个元素读、写各d次，参与B点FFT运算d 次，乘较链因子d—1次.
如果存储器的访问粒度为B个点，则算法1中的访存将是“按维连续”的.最基本的运算单元就是B点FFT，每次运算都是在相应的维上连续的B个数据参与运算.采用第3节中将要介绍的3维转置存储器则可以将“按维连续”的访存转换为连续访存，从而解决了超长点数FFT运算的访存连续性问题．
另外，在算法1中计算顺序是按照第d维到第1维进行的，计算第i维(K/C d)的B d1个B点FFT的过程是相互独立的.当其他维坐标固定时，第/维和第i—1维构成一个B X B的矩阵.如果以这样的矩阵为基本处理单元，则2维处理可以合并，读、写B d2次B2个元素可以进行B d2X2B次B 点FFT运算.运算次数不变的情况下，读、写次数还能减半.
3设计实现
考虑到超长点数FFT的精度要求，本文选择单精度浮点作为基本数据表示.在此基础上，选择16点FFT作为基本运算.
3.1数据流处理
从根本上说，FFT计算过程中需要以2的幂为步长交叉访问数据，这与存储器的连续访问机制不匹配，导致存储带宽利用率低，计算性能无法充分发挥.3维转置运算搭建了连续访问数据与跨步交叉访问数据之间的桥梁.在此基础上，通过2维转置实现算法1中2维处理的合并，进一步减少访存量. 3.1.13维转置运算
假设存储器的访问粒度为B个点，则意味着FFT加速器每次必须按第1维的B个点进行读、写.为了存储一个第i维和第/—1维构成的B X B 矩阵，需要具备存储B3个点的能力.因为，读入B3个点才能同时得到B个完整的第/维和第/—1维构成的B X B矩阵.此时，如果能够按照第i维或第/—1维同时将B个数据取出，则实现了无带宽损失的3维转置运算．
存储器的访问粒度按照16个点设计，具备存储163=4096个点的能力，容量为32KB，使用静态随机访问存储器(static random access memory, SRAM)实现.SRAM无法进行任意方向的读写，即便采用2维
SRAM阵列［24］(每个存储单元变成了2个端口，增大了SRAM的面积)仍然难以实现3维转置运算.因此，本文采用基于SRAM的无冲突体编址技术实现3维转置运算．
根据高庆狮等人［25］对素数存储系统的研究，对于跨步为2的幂的访问，采用素数个存储体，即可消除存储体访问冲突.假设访问地址为a,a+2r, a+2X2r,…,+15X2r，采用17个存储体.令2r mod17=J，则各地址所在的体为a mod17,(+t) mod17,(a+2t)mod17,…，(a+15t)mod17.如果第i个地址和第j个地址落在同一个体，即(a+ it)mod17=(a+jt)mod17，则(一j')t mod17= 0，只有i=J等式才能成立.
3维转置运算的存储体可以存储一个多维张量中按照某3维截取的一个立方体.由于采用17个体在跨步为2的幂访问时不存在体冲突，可以并行读入该立方体，并且对任意2维并行转置读出.作为转置用存储器，每个体需要存储16/17=241个点，即每个体宽度为64b(8B)、深度为241.
按照3维编址进行分析.初始状态下，第1组写入地址为(0,0,0)〜(0,0,15)，第2组写入地址为(0,1,0)〜(0,1,15)，依次类推，当写入地址为(15, 15,0)-(15,15,15)时，完成全部4096个点的写入.在完成地址(15,0,0)-(15,0,15)的写入后，即可读出转置后的第1组地址(0,0,0)〜(15,0,0).所以，当4096个点完全写入时，已读出多组数据，下一批4096个点可以流水写入.
上海校讯通
工程预算编制新的4096个点第1组写入地址为(0,0,0)〜(15,0,0)，第2组写入地址为(0,1,0)-(15,1,0)，依次类推，当写入地址为(0,15,15)-(15,15,15)时，完成全部4096个点的写入.在完成地址(0,0, 15)-(15,0,15)的写入后，
即可读出转置后的第1组地址(0,0,0)-(0,0,15).
1196
计算机研究与发展2021, 58(6)
根据读/写的维序即可计算读/写操作下一拍的
心境恶劣gp5中文版下载3维编址(n ,y x ).
根据3维编址得到体地址与体内地址为
Ad d r intra_bank (162n + 16y +x ) mod 17 =
(z — y +x ) mod 17 ,
< Addr mner_bank = |_(162 Z + 16y + X ) / 1 7 J =
"5)
15z +y + |_(z —y + x )/17」.
并不需要对所有地址进行计算，每次读/写的
16个地址，只需要先计算出第1个所在的体地址和
体内地址，其余15个可以快速得到.另外，对于以2
的幂加1为除数的除法和模运算存在快速硬件实现
方法［5］.
从式(5)所显示的体地址规律可以看出，第1维 和第3维都是连续循环递增的，第2维是连续循环
递减的.无论是输入数据还是输出数据，可以根据地
址计算出移位位数.分别对输入/输出的16个数据 进行顺序和逆序排列之后移位，移位采用2级对数 移位器•总体结构如图1所示：
2级对数移位器
t f t f t
乡/ ；竹［个个；个个；卜
国家突发公共事件总体应急预案
ft 个
2级对数移位器
2级对数移位器
<—控制通路<—数据通路
壘建性g 羽佐吐体体体体体体体体体
4 5 6 7 8 9 10 11 12 13 14 15 16
丰一宇才yl 二宇亨|H||1||H||lj j 尹岸軽尹
卞卞卞卞卞卞卞卞卞卞［；忖；竹；林；;f
2级对数移位器
Fig. 1 Structure of 3-dimensional transposition operation module
图1 3维转置运算模块结构
3.1.2 2维转置运算2维转置运算采用行向输入、列向输出的存储
器阵列实现•需要存储162 =256个点，存储容量为2
KB.芯片中容量较小的存储器阵列可以采用触发
器.SRAM 或锁存器实现.SRAM 的面积和功耗开 销最小，但是由于2维转置运算对存储器有特殊要 求，需要按行写入、按列读出，标准SRAM 不支持该
功能，因此需要采用定制设计［4］，开发周期长且不 利于扩展.触发器的面积和功耗开销最大.因此，选
择锁存器作为基本存储单元.2维转置运算的存储 器如图2 所示.
通过2个这样的锁存器阵列来实现转置处理的 流水化，如图3所示.读选择信号和写选择信号互为
反相，根据读、写次数来进行判断•
3.2铰链因子处理
对FFT 运算点数的支持并不需要无限大，超出 主存容量是没有意义的•加速器按照最大支持4G 点
FFT 设计，则存储容量需要32 GB，基本达到当前
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议