基于近似计算的精度动态可调FFT处理器

马丽萍， 张骁煜， 白雨鑫， 陈 鑫， 张 颖

(南京航空航天大学 电子信息工程学院，南京 210016)

目前, 移动设备的计算需求越来越多地侧重在音视频处理、模式识别及数据挖掘等方面.这些应用场景都具备一个共同特征, 最终结果无需是一个精确值，只需产生一个能够满足需求的近似结果即可.在图像处理中，一定的锐度损失或分辨率损失在人眼看来都是可接受的, 因而这类系统能容忍在一定范围内的误差[1].针对这些应用场景的芯片设计可以通过人为引入误差来降低电路的复杂度，进而提升芯片的其他性能.

快速Fourier变换 (FFT) 处理器是数字信号处理系统中必不可少的模块之一[2]，有关高速与高精度FFT处理器的研究已进入了相对成熟的状态[3-5]，而近似FFT处理器的相关研究仍处在起步阶段.文献[6]将电压缩放调节技术应用于FFT处理器，并通过穷举法选取了FFT处理器中最优的近似加法器及近似乘法器类型，但是这种设计缺乏理论上的分析论证，没有充分利用FFT算法的容错特性.同时，对基本近似计算单元的建模会消耗大量时间，具有一定的局限性.文献[7]讨论了FFT计算中削减每一级数据处理位宽的近似方式，同时给出了多种FFT处理器结构在不同精度需求下各级数据处理位宽的最优配置，但是无法进行精度动态调整, 只适用于特定的场景.

在不同的应用场景下，FFT处理器对于精度、性能与功耗的需求都有一定的差别，精度可调的FFT处理器能够根据不同场景的需求动态调节处理器的精度、性能和功耗，具有很强的实际应用价值.图片处理中，在进行图片预览时，采用近似程度较大的模式，快速得到图片的整体信息而不追求精确的细节；需要查看原图时，就需要调整至精确模式；对于存储空间有限或者功耗有限制时，就需要多种近似模式来满足不同的需求，获取不同精确程度的信息，从而实现功耗和速度的最优，且相比于采用多个只能用于固定场景的FFT处理器，精度动态可调FFT的面积开销最小.因此，本文以512点基23单路径延时反馈(SDF) FFT处理器作为设计目标.精度可调FFT处理器可工作在精确计算模式与4种近似计算模式下，可实现精度、速度、功耗的动态调节.所提设计基于180 nm互补金属氧化物半导体 (CMOS)技术实现，通过专业电子自动化设计(EDA)工具评估性能，相对于精确模式，处理器在近似模式下的最高工作频率提升约14.33%；工作频率为60 MHz时，功耗降低约15.61%.本文提出了一种基于近似计算的精度可调FFT处理器设计思路，证明所提出的设计具有良好的实用价值.

1 精度可调FFT处理器设计

假设x[n]为时域中长度为N的序列(n为每个元素的序号，0≤n≤N-1)，其离散Fourier变换的定义形式如下式所示：

(1)

式中：X[k]为变换域中一个长度为N的序列；k为每个元素的序号.常用记号WN的表达式可以表示为

WN=e-j2π/N

(2)

则将WN代入式(1)后，可改写为

(3)

若长度为N的序列满足N=2l，其中l为3的倍数，即长度N为8的幂，则可以将经过变换后的X[k]按照先后顺序分为8个子序列，定义为Xm[k]，其中m为子序列的序号，0≤m≤7.xm[n]为Xm[k]变换前的序列.按频率抽取的基23FFT算法流图与硬件结构实现的对照图如图1所示.

图1 按频率抽取的基23 FFT算法Fig.1 Decimation in frequency radix-23 FFT algorithm

精度动态可调FFT处理器的整体硬件结构中共需9个蝶形计算单元，2个非常系数复数乘法器和6个常系数乘法器.其中：本文在蝶形节点和旋转因子乘法节点上分别提出了一种截断进位链的可配置近似蝶形计算单元和一种位宽可调的乘法模块，在此基础上完成了精度动态可调FFT处理器的设计.

1.1 可配置近似蝶形计算单元

对于L位二进制加法，若A与B为加法的两个加数，Cin为加法的进位输入.则加法中的传播信号和生成信号可以表示为

(4)

式中：0≤i≤L-1；ai为A的第i位；bi为B的第i位；pi为加法第i位的传播信号；gi为加法第i位的生成信号.

精确加法的逻辑表达式可表示为

(5)

式中：si,e为第i位的精确和；ci,e为第i位产生的精确进位信号.

随着输入信号位宽的增加，精确加法器的关键路径为加法器的进位链.截断进位的近似加法将某一位的进位输出信号截断，减少关键路径的长度和降低翻转率.本文采用预测进位的截断进位加法逻辑为

si,a=pi+ci-1,ci,a=gi

(6)

式中：si,a为第i位的近似和；ci,a为第i位产生的近似进位信号.

通过比较可知，式(5)和(6)具有相同的部分，因此，本文设计一种可配置近似蝶形计算单元，通过双路选择器使其可工作在精确及近似两种模式，其逻辑表达为

(7)

此外，FFT处理器中的定点数都是以二进制补码的形式存储与计算的，当式(6)中的近似加法应用于二进制补码计算时，可能因截断进位而引起符号位的错误.经分析得，符号位发生错误只在A与B符号相反，且正数的绝对值大于或等于负数的绝对值时发生的.因此通过引入符号纠错单元，解决近似蝶形计算单元符号位发生错误的问题.其逻辑表达式为

(8)

1.2 位宽可调的乘法模块

由旋转因子近似计算分析可知，旋转因子量化至14位即可认为是精确计算的结果，而蝶形模块的计算结果均为16位，因此本文设计的是 16×14位乘法器.

复数乘法器用于实现复数乘法.为了提高乘法器的工作频率，本文设计的乘法器采用流水线结构.第1级流水采用Booth编码生成部分积并完成部分积压缩，第2级流水进行加法与截位操作.

由于FFT的数据位宽是16位，乘法器得到的结果为30位，需要将结果截去14位.旋转因子的实部与虚部范围均在[-1, 1]之间，所以乘法器的结果不会大于被乘数的大小，据此可知乘法器输出数据的符号位后两位必与符号位相同.根据这一特性，可选择截去乘法器符号位的后两位及低12位的数据，并且在截去低12位数据时将数据进行四舍五入以降低误差.

值得指出的是，由Booth算法可知，若想通过将乘数低z位复位为0的方式减少部分积，则z为 [0,8] 之间的偶数.

改革开放释放了科研设计院所和科技人员的所有潜力，也释放了人的生产力，将设计成果推到了产业发展的第一线。市场经济的规律，对设计提出了更高的要求。产品设计不仅要解决工程设计的结构、功能等问题，还要解决其形态、色彩、造型等问题。中国的设计发展要在产品与商品、生产与市场、科技与文化之间重新找到平衡点，才能走得更远。因此，中国的工业设计应运而生。

2 基23 FFT的近似计算分析

通过MATLAB搭建误差分析平台，以量化信噪比(SQNR)作为指标[7-8]，评估在不同节点进行近似计算对FFT运算的影响.

2.1 蝶形计算节点的近似计算分析

将近似FFT模块中的9个蝶形单元视作9个计算节点，第1级蝶形为节点1，依次类推.对其中1个蝶形节点进行近似计算，剩余8个蝶形节点采用精确计算，从而分析每个蝶形节点对最终输出结果的影响.分别对蝶形节点1～9中的第j位采用式(3)的近似运算，在误差分析平台对9个蝶形节点采用近似计算后FFT输出的SQNR如图2所示.其中：Ssqnr为FFT的输出的SQNR.

图2 单节点近似蝶形的SQNRFig.2 SQNR of single approximate butterfly node

基于分析的结果，可得出以下结论：

(1) 近似计算位j越接近高位，引入的平均误差就越大.FFT位置越靠前的蝶形节点对误差的容忍度越高.

(2) 每一个蝶形节点都存在一个阈值jth，当j小于jth时，近似计算对最终结果产生的影响非常小.从蝶形节点1～9各个节点jth排列为(4, 3, 3, 3, 2, 2, 1, 1, 0).

根据MATLAB误差分析结果可知，蝶形节点9对输出结果的影响最大，因此在对9个蝶形节点进行近似设计时应该从后向前考虑，首先确定蝶形节点9的j值，再依次决定靠前蝶形节点的j值.当某一蝶形节点的jth大于蝶形节点9的j值时，选取jth作为该蝶形节点第j位的截断进位值；当该蝶形节点的jth小于蝶形节点9的j值时，考虑到蝶形节点9会截取该蝶形节点所保留的位宽，保留更多的位宽不会带来精度上非常明显的提高，所以选取蝶形节点9的j值作为该节点的j值.遵循这种思路，可以获得蝶形节点9的j值从0～7变化时所有蝶形节点的j值，如表1所示.

表1 512点FFT近似蝶形配置Tab.1 Approximate butterfly configuration of 512 FFT

通过MATLAB对上述配置仿真得到的FFT输出精度如图3所示，其中：j9为蝶形节点9的j值.当蝶形节点9的j值逐渐增大时，SQNR仍然呈线性下降，蝶形节点9的j值每增加1，输出结果的SQNR下降约6 dB.

图3 蝶形计算不同近似配置下的精度Fig.3 Accuracy of butterfly computation at different configurations

2.2 旋转因子乘法节点的近似计算分析

在512点基23FFT计算中共有8次旋转因子乘法，将这8次旋转因子乘法按先后顺序分别视作乘法节点1～8，则8个乘法节点的旋转因子范围如表2所示.

表2 各个乘法节点的旋转因子范围Tab.2 Rotation factor ranges of each multiplication node

乘法节点3与6的旋转因子采用对低于量化后最低位的数据进行四舍五入的量化方式.经过仿真验证发现，旋转因子乘法中每个节点对最终结果的影响程度是基本相同的.且当旋转因子量化至14位定点数时即可认为是精确计算，因此可对每个节点进行同样大小的位宽缩减.将乘法节点3与6的旋转因子位宽同时从16位缩减至6位时输出结果的SQNR如图4所示，其中：w为乘法节点3与6的旋转因子位宽.

图4 同时调整乘法节点3与6时的SQNRFig.4 SQNR of adjusting multiplication nodes 3 and 6

2.3 两类节点同时近似计算的效果

现考虑对蝶形节点与旋转因子乘法节点这同时采用近似计算，图5为两类节点同时近似计算时输出结果的SQNR，9个蝶形计算单元采用表1中节点9的j值从1～6的近似配置，旋转因子乘法节点3与节点6的量化位宽w范围为6～14位.

图5 两类节点同时近似模式的SQNRFig.5 SQNR of two types of nodes with approximate modes

由分析结果可知，当节点9的j值较小时，SQNR的变化趋势与精确蝶形运算的结果基本相同.当节点9取较大j值时，由于蝶形节点的近似计算已经引入了较大误差，缩减旋转因子位宽对输出结果的SQNR的影响已变得不明显.

2.4 精度可调FFT处理器的近似方案选择

近似蝶形模块的近似计算主要影响蝶形计算单元的延时，即FFT处理器的最大工作频率，而位宽可调的乘法模块的近似计算主要影响16×14位乘法器的功耗，即主要影响FFT处理器的功耗.QPDP为精度归一化后的功耗延时积，根据QPDP可评估不同配置的近似效果，可表示为

(9)

式中：tbf为蝶形计算单元的延时；Pmul为16×14位乘法器的功耗.

由图3和5中的数据可得出，SQNR大于35 dB的16种配置方案的QPDP，在近似方案中有13种近似配置的QPDP小于精确配置，将QPDP优于精确配置的13种方案的SQNR分为55±3、50±3、45±3、40±3 dB这4个区间，在4个区间中分别选取QPDP最小的配置作为精度可调FFT处理器的近似计算模式.精度可调FFT处理器的5种计算模式如表3所示，其中：wmul为乘法位宽.

表3 FFT处理器的5种计算模式Tab.3 Five computation modes of FFT processer

3 实现与验证

3.1 功能仿真

功能仿真验证平台的结构如图6所示.将FFT处理器的输入设置为范围在[-1, 1]中的随机数，利用MATLAB的软件计算结果及ModelSim软件中的硬件计算结果计算FFT处理器在5种模式下输出的SQNR，结果与MATLAB误差仿真平台结果的SQNR基本一致，符合设计预期.

图6 功能仿真验证平台Fig.6 Function simulation verification platform

3.2 后端实现

最终采用台积电TSMC 180 nm CMOS工艺基于超大规模数字集成电路标准设计流程对FFT处理器完成后端实现，设计中的随机存取存储器(RAM)与ROM采用ARM Artisan公司的知识产权(IP)核.

最终通过设计规则检查和版图与原理图一致性检查的芯片版图如图7所示，尺寸为 1.44 mm×1.44 mm，面积为2.07 mm2.为了进一步获取电路设计的功耗信息，本文基于超大规模数字集成电路功耗评估的标准流程，结合Synopsys VCS仿真后的翻转率文件，Synopsys ICC的布局布线后所抽取的寄生参数，在Synopsys PT中获取功耗评估结果.

图7 精度可调FFT处理器芯片版图Fig.7 Chip layout of accuracy configurable FFT processor

3.3 性能比较

由于不同 FFT 处理器的最大处理点数、实现工艺及电压等参数均不相同，因此需要将参数归一化后对比.FFT处理器的归一化计算时间tnm、能耗Enm及面积Anm的计算方法为[9]

(10)

(11)

(12)

式中：P为处理器的功耗；tcyc为完成一轮FFT计算所需的时间；M为数据的通路；U为芯片的电压；A为芯片面积；Y为最大计算点数；τ为处理器所用工艺.

精度可调FFT处理器与已发表精确FFT处理器的对比结果如表5所示.在近似模式3下处理器的最大工作频率提升约14.33%，当工作频率为 60 MHz 时，功耗降低约15.61%.其余3个近似模式的功耗平均降低了约9%.

精度可调FFT处理器分别针对乘法器与蝶形计算单元进行了优化，因此面积相较其余3种处理器均具有一定优势.文献[8]与[10]采用的数据处理位宽分别为10位与8位，使得计算单元的关键路径长度小于精度可调FFT处理器，因此具有更高的最大工作频率.

文献[9]与精度可调FFT处理器采用相同的16位数据处理位宽，在近似模式3下精度可调FFT处理器的最大工作频率相较于文献[9]增大了17.44%，性能方面有明显提升.精度可调FFT处理器在计算模式为精确模式、近似模式0、近似模式3时的SQNR分别与文献[8-10]中处理器的SQNR相近，差值均在3 dB以内，但归一化后的能耗分别为文献[8-10]的84.87%、52.96%、65.80%.虽然本文的功耗结果是EDA工具功耗评估获得的，但是产业界普遍认为该流程获得功耗信息在数量级上是可信的；且经过归一化计算之后，本次提出的FFT处理器在不同近似模式下相比已有的FFT处理器功耗下降均超过15%，因此本设计和其他文献相比，在能耗方面具有一定优势.

3.4 图像处理中的验证

由表5可知，在近似模式3下处理器的SQNR降低了约31.9%，其余3个近似模式的SQNR分别降低了9%、15.6%、17.17%.本小节将精度可调FFT处理器应用于图像的频率域处理中来验证处理器在实际应用中的表现，使用Butterworth高通滤波器对图像进行平滑处理的结果如图8所示.其中：Qssim为图形结构相似性.

表5 不同FFT处理器对比结果Tab.5 Comparison of different FFT processors

图8 图像平滑处理结果Fig.8 Results of image smoothing

图像结构相似性(SSIM)能够有效地衡量两幅图像的相似度，通常用于评估图像的失真程度，其取值范围为0～1.Qssim越大表示失真程度越小，当Qssim为1时，表示两张图像完全相同.

FFT处理器在4种近似模式下图像平滑后的图像结构相似性的Qssim均大于0.95.在近似模式0的场景下，图像质量是最好的，功耗相对于精确模式略有下降；近似模式1与近似模式0处理后图像与精确模式处理后图像无明显差别，但是最大工作频率有所提高，提高了数据吞吐率；近似模式2最大工作频率进一步提高，但是图像清晰度也略有下降；近似模式3下，图像质量进一步下降，但是工作率达到最大且功耗降到最低，比较适用于“图像预览”这样的工作场景，不需要非常清晰的画质，但是需要低功耗以及较大的吞吐量.

近似模式2与近似模式3处理后的图像存在一定的画质劣化，但仍可清晰分辨出图像内容，说明处理器的所有计算模式在图像平滑时有较好的表现，具有良好的实用价值.

4 结语

本文在国内外近似电路的现有研究进展基础上提出了一种基于近似计算的精度可调FFT处理器.通过对FFT算法进行建模仿真确定了FFT的容错特性，在此基础上将近似加法器及可调节位宽的乘法器应用在FFT处理器的设计中，并根据性能与精度等参数的对比确定了FFT处理器的计算模式.精度可调FFT处理器能够在精确模式及4种近似模式下切换，实现精度、速度与功耗的动态调整，从而满足不同场景的需求.将精度可调FFT处理器应用于图像边缘提取及图像平滑处理中，处理结果表明在近似程度最大的计算模式下精度可调FFT处理器的结果仍具有一定的可用性，表明精度动态可调FFT处理在图像处理中具有良好的应用前景.由于条件限制，本文设计的性能指标均是通过专业EDA工具的标准评估流程得到的，未来该设计改进后将尽量进行流片实测.