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

图1 按频率抽取的基2³ FFT算法

Fig.1 Decimation in frequency radix-2³ FFT algorithm

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

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

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

(4)

\begin{array}{l} p_{i} = a_{i} \oplus b_{i} \\ g_{i} = a_{i} \cdot b_{i} \end{array}\}

式中:0≤i≤L-1;a_i为A的第i位;b_i为B的第i位;p_i为加法第i位的传播信号;g_i为加法第i位的生成信号.

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

(5)

\begin{array}{l} c_{i, e} = g_{i} + p_{i} \cdot c_{i - 1} \\ s_{i, e} = p_{i} \oplus c_{i - 1} \end{array}\}

式中:s_i,_e为第i位的精确和;c_i,_e为第i位产生的精确进位信号.

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

(6)s_i,_a=p_i+c_i-1, c_i,_a=g_i

式中:s_i,_a为第i位的近似和;c_i,_a为第i位产生的近似进位信号.

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

(7)

\begin{array}{l} s_{0} = p_{0} \oplus C_{in} \\ c_{0} = g_{0} + p_{0} \cdot C_{in} \\ s_{i} = Φ \cdot s_{i, e} + \bar{Φ} \cdot s_{i, a} \\ c_{i} = Φ \cdot c_{i, e} + \bar{Φ} \cdot c_{i, a} \end{array}\}

式中:s₀为加法和的第1位;p₀为传播信号的第1位;g₀为生成信号的第1位;c₀是第1位产生的进位信号;Φ为模式控制信号.当Φ为1时,采用精确加法逻辑;当Φ为0时,采用近似加法逻辑.

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

(8)

\begin{array}{l} d_{cs} = \overset{\cdot}{p_{n - 1}} \\ s_{i, a}^{cs} = s_{i, a} \cdot d_{cs} \end{array}\}

式中:d_cs为符号检错信号; $s_{i, a}^{cs}$ 为纠错后的进位和.

1.2 位宽可调的乘法模块

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

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

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

本文使用只读存储器(ROM)存储旋转因子.存储子模块能够根据乘法器的精度模式,从对应的地址中取出 $W_{N}^{kn}$ ,根据所需精度的不同将旋转因子的低z位为0(z为旋转因子需要缩小的位宽),减小了旋转因子的有效位宽,然后送入对应的复数乘法器中.通过调整旋转因子的有效数据位宽能够调整乘法器的部分积个数,从而进一步调整乘法器的精度.

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

2 基2³ FFT的近似计算分析

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

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

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

图2

图2 单节点近似蝶形的SQNR

Fig.2 SQNR of single approximate butterfly node

基于分析的结果,可得出以下结论:

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

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

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

表1 512点FFT近似蝶形配置

Tab.1 Approximate butterfly configuration of 512 FFT

蝶形节点9的j值	各蝶形节点j值的选取 (蝶形节点1~9排列)
0	(4, 3, 3, 3, 2, 2, 1, 1, 0)
1	(4, 3, 3, 3, 2, 2, 1, 1, 1)
2	(4, 3, 3, 3, 2, 2, 2, 2, 2)
3	(4, 3, 3, 3, 3, 3, 3, 3, 3)
4	(4, 4, 4, 4, 4, 4, 4, 4, 4)
5	(5, 5, 5, 5, 5, 5, 5, 5, 5)
6	(6, 6, 6, 6, 6, 6, 6, 6, 6)
7	(7, 7, 7, 7, 7, 7, 7, 7, 7)

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

图3

图3 蝶形计算不同近似配置下的精度

Fig.3 Accuracy of butterfly computation at different configurations

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

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

表2 各个乘法节点的旋转因子范围

Tab.2 Rotation factor ranges of each multiplication node

乘法节点	旋转因子
1	$W_{8}^{0}$ ~ $W_{8}^{3}$
2	$W_{8}^{0}$ 、 $W_{8}^{2}$
3	$W_{512}^{0}$ ~ $W_{512}^{441}$
4	$W_{8}^{0}$ ~ $W_{8}^{3}$
5	$W_{8}^{0}$ 、 $W_{8}^{2}$
6	$W_{64}^{0}$ ~ $W_{64}^{49}$
7	$W_{8}^{0}$ ~ $W_{8}^{3}$
8	$W_{8}^{0}$ 、 $W_{8}^{2}$

乘法节点2、5、8中旋转因子的实部与虚部均只有1与0两种情况,因此不会引入量化误差.乘法节点1、4、7中的 $W_{8}^{1}$ 与 $W_{8}^{3}$ 会因量化无理数 $\sqrt[]{2}$ /2引入误差,通过MATLAB误差分析结果,显示相较32位双精度浮点数,将 $\sqrt[]{2}$ /2量化至10位的精度已能够满足大部分应用场景.

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

图4

图4 同时调整乘法节点3与6时的SQNR

Fig.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

图5 两类节点同时近似模式的SQNR

Fig.5 SQNR of two types of nodes with approximate modes

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

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

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

(9)Q_PDP=

\frac{P_{mul} t_{bf}}{S_{sqnr}}

式中:t_bf为蝶形计算单元的延时;P_mul为16×14位乘法器的功耗.

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

表3 FFT处理器的5种计算模式

Tab.3 Five computation modes of FFT processer

模式	九级蝶形模块的j值 (从模块1~9)	w_mul	Q_PDP	S_sqnr
精确	(0, 0, 0, 0, 0, 0, 0, 0, 0)	14	11.33	55.49
近似0	(0, 0, 0, 0, 0, 0, 0, 0, 0)	10	9.34	51.88
近似1	(3, 3, 3, 3, 2, 2, 1, 1, 1)	10	8.89	49.45
近似2	(3, 3, 3, 3, 2, 2, 2, 2, 2)	10	9.20	46.12
近似3	(3, 3, 3, 3, 3, 3, 3, 3, 3)	8	8.67	37.26

3 实现与验证

3.1 功能仿真

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

图6

图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 mm².为了进一步获取电路设计的功耗信息,本文基于超大规模数字集成电路功耗评估的标准流程,结合Synopsys VCS仿真后的翻转率文件,Synopsys ICC的布局布线后所抽取的寄生参数,在Synopsys PT中获取功耗评估结果.

图7

图7 精度可调FFT处理器芯片版图

Fig.7 Chip layout of accuracy configurable FFT processor

3.3 性能比较

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

(10)t_nm=

\frac{t_{cyc}}{Y}

(11) E_nm=

\frac{P t_{cyc} \times 10^{3}}{M {(U / 1.8)}^{2} YlbY}

(12) A_nm=

\frac{A \times 10^{3}}{M {(τ / 180)}^{2} lbY}

式中:P为处理器的功耗;t_cyc 为完成一轮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,9,10]中处理器的SQNR相近,差值均在3 dB以内,但归一化后的能耗分别为文献[8,9,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所示.其中:Q_ssim为图形结构相似性.

表5 不同FFT处理器对比结果

Tab.5 Comparison of different FFT processors

已发表的 FFT文献	本文设计的FFT 不同工作模式	FFT点数	工艺/nm	工作电压/V	输入位宽	S_sqnr/dB
—	精确模式	512	180	1.8	16	55.51
—	近似0					51.62
—	近似1					49.06
—	近似2					45.98
—	近似3					37.45
文献[10]	—	2048	90	1	8	40
文献[9]	—	4096	65	1.2	16	51
文献[8]	—	8192	130	1.2	10	53.28
最大工作频率/MHz	数据通路	面积/mm²	归一化面积	功耗/mW	归一化能耗	测试结果
128.4	1	2.07	230.0	30.26@60 MHz	91.48	EDA工具功耗评估
128.4				27.51@60 MHz	83.16
134.0				27.50@60 MHz	83.13
140.4				27.50@60 MHz	83.13
146.8				25.53@60 MHz	77.18
250	4	3.1	282.8	63.72@40 MHz	117.29	实测
125	1	1.05	671.0	33.5@40 MHz	157.03	实测
400	1	2.7	398.2	35.7@40 MHz	107.79	实测

图8

图8 图像平滑处理结果

Fig.8 Results of image smoothing

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

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

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

4 结语

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

(本文编辑:石易文)

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

VENKATESAN

, AGARWAL

, ROY

et al.

MACACO: Modeling and analysis of circuits for approximate computing[C]//2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

San Jose, CA, USA: IEEE, 2011: 667-673.

[2]

MITRA S

. 数字信号处理: 基于计算机的方法[M]. 余翔宇. 第4版.北京: 电子工业出版社, 2012.

MITRA S

Digital signal processing: A computer-based approach[M]. YU Xiangyu. 4th ed. Beijing: Publishing House of Electronics Industry, 2012.

DOI:10.1109/TVLSI.2018.2879675 URL [本文引用: 1]

[3]

LIU S

, LIU D

A high-flexible low-latency memory-based FFT processor for 4G, WLAN, and future 5G

[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2019, 27(3):511-523.

[4]

PASHAEIFAR

, KAMAL

, AFZALI-KUSHA

, et al.

Approximate reverse carry propagate adder for energy-efficient DSP applications

[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2018, 26(11):2530-2541.

DOI:10.1109/TVLSI.2018.2859939 URL [本文引用: 1]

[5]

BECHER

, ECHAVARRIA

, ZIENER

et al.

A LUT-based approximate adder [C]//2016 IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)

Piscataway, NJ, USA: IEEE, 2016: 27.

[6]

LINGAMNENI

, ENZ

, PALEM

et al.

Highly energy-efficient and quality-tunable inexact FFT accelerators [C]//Proceedings of the IEEE 2014 Custom Integrated Circuits Conference

San Jose, CA, USA: IEEE, 2014: 1-4.