2019, Vol. 45
由于人类感官的固有局限性, 如对图像、声音的细微变化不敏感, 因此诸如图像变换、音频处理等许多应用就可以采用近似计算[1], 而无需得到精确的计算结果。近似计算的关键思想是通过牺牲少量的精度来换取性能的大幅提升。在许多应用中存在乘法运算, 采用近似乘法器可以提升处理速度, 减少资源消耗。本文在研究现有近似乘法器的基础上, 设计一种新的高速近似乘法器, 并将其应用到图像处理中。
1 相关工作乘法器对于给定2个n位的操作数进行乘法操作, 其主要步骤为:
1) 将操作数按位相与, 产生一系列n位部分乘积项(Partial Product, PP)[2]。
2) 通过一些特定方式如全加、4-2压缩[2]进行累加, 将n位PP压缩为2行。
3) 对最后2行求和, 得到最终乘积。
乘法器的近似可以从上述3个步骤入手。文献[3]提出一种根据设计的乘法器(Under Designed Multiplier, UDM), 通过2乘2近似乘法器子模块来产生PP。
对PP压缩是近似研究的重点方向, 主要方法包括截断、4-2压缩[4-5]以及近似全加器累加等。文献[4-7]提出不同的4-2压缩方法来压缩PP。文献[8-9]利用或门来压缩低位的PP, 高位用精确加法器累加避免误差距离过大。
除了上述近似方法之外, 文献[10]使用米切尔对数算法及其改进形式来近似乘法操作, 获得的改进乘法器性能较好。
2 近似乘法器结构 2.1 近似加法结构对绝大部分乘法器来说, 加法器是基本元素。低位或门加法器(Lower-part-OR Adder, LOA)与容错加法器(Error-Tolerant Adder, ETA)可以对加法器低位进行不精确计算。文献[11]用模块化的思想来实现近似, 除了减少延迟外, 还可以通过改变模块的规模来控制加法器的精度。文献[12]提出近似镜像加法器(Approximate Mirror Adder, AMA)的概念, 通过删除晶体管达到简化逻辑结构的目的。
本文对AMA[12]的真值表进行修改, 结果如表 1所示。近似全加器电路结构如图 1所示。
|
下载CSV 表 1 近似全加器真值表 |
|
Download:
|
| 图 1 近似全加器电路结构 | |
近似全加器的结构较精确全加器而言大为简化, 在减少资源消耗方面具有显著效果。基于上述近似全加器, 本文提出一种新型的近似加法结构, 如图 2所示。当给定2个输入操作数a[n-1]与b[n-1]之后, 各级的进位输入也同时确定, 和s[n-1]的每位可以同时计算得出, 高位结果的计算无需等待低位计算的进位输出, 计算速度能够得到极大提升。由该加法结构实现的多位近似加法器具有不亚于超前进位加法器(Carry Look-ahead Adder, CLA)的高速性能, 而无需计算各级的进位输出则使得该加法结构能够节省较多的电路资源。
|
Download:
|
| 图 2 近似加法结构电路图 | |
流水线被广泛应用于高速数字系统设计中[13]。具有流水结构的设计能够在不增加过多硬件代价的前提下有效提高数字电路的数据处理速度, 其基本思想是将复杂的数字逻辑电路分级实现, 使每一级的电路结构简化, 在较小的时钟周期内完成电路的功能[14]。本文设计的近似乘法器(以8位为例)的流水线结构如图 3所示。对一般情况而言, 当输入为2个n位二进制数时, 该乘法器首先通过与门生成n行n位的PP, 并将其寄存至长度为2n的寄存器pp0~pp(n-1)中。定义近似长度为l(l值一般为n/4、n/2或3n/4), 对权重较小的l行PP利用2n位近似加法器累加。然后将近似部分与精确部分的和分别寄存至2n位寄存器APP与ACC中。最后利用2n位CLA将近似部分的和与精确部分的和相加, 得到最终结果。当时钟沿到来时, 上述3个操作过程同时工作, 可以提高系统的时钟频率, 进而提升数据吞吐率。
|
Download:
|
| 图 3 近似乘法器流水线结构 | |
误差距离(Error Distance, ED)表示精确结果与近似结果之差的绝对值。平均误差距离(Mean Error Distance, MED)表示一组ED的均值。归一化平均误差距离(Normalized MED, NMED)统一了不同位宽的近似乘法器的MED对比标准。错误率(Error Rate, ER)表示错误的输出结果占所有输出结果的百分比。上述参数可以有效表示近似乘法器的误差特性。
对于本文所设计的近似乘法器, 近似部分的长度(即l值)可以进行配置, 以实现乘法器的精度可控。为方便对比, 本文将基于AMA[12]的近似乘法器命名为设计1, 将基于UDM[3]的近似乘法器命名为设计2, 将基于4-2压缩[2]的近似乘法器命名为设计3。本文设计以l=4为例。不同近似乘法器的误差特性如表 2所示。其中, ED为实验的最大误差距离即ED的最大值。
|
下载CSV 表 2 不同乘法器的误差特性 |
将精确乘法器、设计1、设计2、设计3以及本文设计应用于图像处理中, 统计最大延时以及所占用的查找表(Look-Up-Table, LUT)与触发器(Flip-Flop, FF)资源。以最大延时、LUT以及FF三者之间的乘积(Delay-LUT-FF Product, DLFP)作为主要参考系数。DLFP系数越小, 表示乘法器的延时与资源消耗的总体性能越好。统计结果如表 3所示。
|
下载CSV 表 3 各乘法器资源占用对比 |
从表 3可以看出, 与其他近似乘法器相比, 本文设计的最大延时最小; 当l=6时, 本文设计LUT节省百分比达32.20%。虽然流水线的使用使整个设计增加了少量触发器资源, 但就DLFP系数而言, 本文设计在l=6时远优于其他设计。
4 近似乘法器应用将本文设计应用于DCT/IDCT图像变换[15]中以验证其实用性。矩阵相乘是DCT/IDCT的主要过程[16]。在FPGA中灰度矩阵与变换矩阵相乘主要由调用乘法器IP核来实现。本文利用基于近似乘法器所设计的近似有符号乘法器IP核来替换精确的IP核, 得到近似的DCT/IDCT结果。
为衡量图像重构质量, 本文采用峰值信噪比(Peak to Signal Noise Ratio, PSNR)作为评估参数。本文设计与其他乘法器对不同图像作DCT/IDCT处理所得到的结果如图 4所示。各重构图像的峰值信噪比如表 4所示。
|
Download:
|
| 图 4 各乘法器重构图像对比 | |
|
下载CSV 表 4 各乘法器重构后图像的PSNR值 |
从表 4可以看出, 不同图像经本文设计处理之后仍具有相当高的PSNR值, 图像的质量损失很小。对于同一幅图, 与其他近似乘法器处理之后的图像相比, 本文设计处理后的图像PSNR值最大, 图像重构的效果最好。
5 结束语本文设计一种近似乘法器, 在牺牲一定计算精度的前提下, 极大提升了乘法器的计算性能, 且其精度可以按照实际要求调节, 能够减少资源消耗和延迟。在DCT/IDCT图像变换中的实验结果表明, 本文乘法器重构图像的PSNR损失为6 dB~7 dB, 质量损失相对较小。下一步将对其进行优化, 在保证实用性的同时, 进一步减少资源消耗及时延。此外, 还将研究不同的近似设计方式, 如对逻辑综合过程的近似等。
| [1] |
YANG Tongxin, UKEZONO T, SATO T. A low-power high-speed accuracy-controllable approximate multiplier design[C]//Proceedings of the 23rd Asia and South Pacific Design Automation Conference. Washington D. C., USA: IEEE Press, 2018: 605-610.
|
| [2] |
HA Minho, LEE S. Multipliers with approximate 4-2 compressors and error recovery modules[J]. IEEE Embedded Systems Letters, 2017, 10(1): 6-9. |
| [3] |
KULKARNI P, GUPTA P, ERCEGOVAC M. Trading accuracy for power with an underdesigned multiplier architecture[C]//Proceedings of the 24th Internatioal Conference on VLSI Design. Washington D. C., USA: IEEE Press, 2011: 346-351.
|
| [4] |
SHAFIQUE M, HAFIZ R, REHMAN S, et al. Cross-layer approximate computing: from logic to architectures[C]//Proceedings of the 53rd Annual Design Automation Conference. New York, USA: ACM Press, 2016: 99.
|
| [5] |
BHARDWAJ K, MANE P S, HENKEL J. Power-and area-efficient approximate wallace tree multiplier for error-resilient systems[C]//Proceedings of the 15th International Symposium on Quality Electronic Design. Washington D. C., USA: IEEE Press, 2014: 263-269.
|
| [6] |
VENKATACHALAM S, KO S B. Design of power and area efficient approximate multipliers[J]. IEEE Transactions on Very Large Scale Integration Systems, 2017, 25(5): 1782-1786. DOI:10.1109/TVLSI.2016.2643639 |
| [7] |
ZERVAKIS G, TSOUMANIS K, XYDIS S, et al. Design-efficient approximate multiplication circuits through partial product perforation[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(10): 3105-3117. DOI:10.1109/TVLSI.2016.2535398 |
| [8] |
QIQIEH I, SHAFIK R, TARAWNEH G, et al. Energy-efficient approximate multiplier design using bit significance-driven logic compression[C]//Proceedings of the Conference on Design, Automation and Test in Europe. New York, USA: ACM Press, 2017: 7-12.
|
| [9] |
LIU Cong, HAN Jie, LOMBARDI F. A low-power, high-performance approximate multiplier with configurable partial error recovery[C]//Proceedings of 2014 Design, Automation and Test in Europe Conference and Exhibition. Washington D. C., USA: IEEE Press, 2014: 1-4.
|
| [10] |
KIM M S, DEL BARRIO A A, HERMIDA R, et al. Low-power implementation of Mitchell's approximate logarithmic multiplication for convolutional neural networks[C]//Proceedings of the 23rd Asia and South Pacific Design Automation Conference. Washington D. C., USA: IEEE Press, 2018: 617-622.
|
| [11] |
KAHNG A B, KANG S. Accuracy-configurable adder for approximate arithmetic designs[C]//Proceedings of the 49th Annual Design Automation Conference. New York, USA: ACM Press, 2012: 820-825.
|
| [12] |
GUPTA V, MOHAPATRA D, PARK S P, et al. IMPACT: imprecise adders for low-power approximate computing[C]//Proceedings of the 17th IEEE/ACM International Symposium on Low-power Electronics and Design. Washington D. C., USA: IEEE Press, 2011: 409-414.
|
| [13] |
ZHAO Guoliang. Research and implementation of 1024-point pipeline FFT algorithm based on FPGA[D].Xi'an: Xidian University, 2011.(in Chinese) 赵国亮.基于FPGA的1024点流水线结构FFT算法的研究与实现[D].西安: 西安电子科技大学, 2011. |
| [14] |
FEI Yongzhou. Research and design of 12-bit high speed pipeline ADC[D].Nanjing: Southeast University, 2017.(in Chinese) 费永舟.12位高速流水线ADC的研究和设计[D].南京: 东南大学, 2017. |
| [15] |
WU Ying. Application of DCT transform in image compression[J]. Computer and Modernization, 2013(4): 103-106. (in Chinese) 武瑛. DCT变换在图像压缩中的应用[J]. 计算机与现代化, 2013(4): 103-106. DOI:10.3969/j.issn.1006-2475.2013.04.026 |
| [16] |
XU Zhen. VLSI design of DCT/IDCT IP core based on image processing application[D].Wuhan: Huazhong University of Science and Technology, 2004.(in Chinese) 薛峥.基于图像处理应用的DCT/IDCT IP核的VLSI设计[D].武汉: 华中科技大学, 2004. |