張琳， 田現(xiàn)忠,2 ，趙興文 ，顏廣 ，葛兆斌

(1． 山東省科學(xué)院自動化研究所，山東 濟(jì)南 250014；2．吉林大學(xué)儀器科學(xué)與電氣工程學(xué)院，吉林 長春 130026)

?

一種并行結(jié)構(gòu)有符號乘累加器的設(shè)計

張琳1， 田現(xiàn)忠1,2，趙興文1，顏廣1，葛兆斌1

(1． 山東省科學(xué)院自動化研究所，山東 濟(jì)南 250014；2．吉林大學(xué)儀器科學(xué)與電氣工程學(xué)院，吉林 長春 130026)

摘要：本文采用補(bǔ)碼分布式算法，簡化了有符號數(shù)、無符號數(shù)以及混合符號數(shù)的乘加減運(yùn)算，通過改進(jìn)累加器樹結(jié)構(gòu)、全加器邏輯電路，設(shè)計了一種新型乘累加器結(jié)構(gòu)。通過Altera公司的EP1C3T144C8實現(xiàn)了該乘累加器6個9位有符號操作數(shù)的乘累加運(yùn)算的功能和時序仿真,結(jié)果證明了該算法的有效性。該設(shè)計解決了常規(guī)DA分布式算法系數(shù)不能更新和占用大量RAM資源的缺點，可以應(yīng)用到數(shù)字濾波器設(shè)計中，也可以作為快速的運(yùn)算單元應(yīng)用到DSP數(shù)字信號處理器中。

關(guān)鍵詞：乘累加器；有符號數(shù)；可變系數(shù)

乘累加器是信號處理當(dāng)中的基本運(yùn)算單元，是fir濾波器和自適應(yīng)濾波器的主要結(jié)構(gòu)，其速度和占用芯片資源的多少是影響數(shù)字硬件實現(xiàn)的關(guān)鍵性因素[1]。乘累加器主要分為迭代、線性陣列和并行結(jié)構(gòu)，早期采用迭代結(jié)構(gòu)使用軟件實現(xiàn)乘法操作，后來逐漸發(fā)展成設(shè)計專用的硬件乘累加器，以獲得更高的性能。目前高性能的乘法操作都是采用硬件實現(xiàn)的乘累加器，而且多是采用并行結(jié)構(gòu)[2]。目前國內(nèi)外并行乘累加器的算法主要有Booth算法和Wallace樹，當(dāng)前流行的部分積產(chǎn)生算法就是在Booth算法的基礎(chǔ)上改進(jìn)的。雖然改進(jìn)的Booth算法可以減少部分積的數(shù)量，減少了硬件開銷且提高了電路性能，但是當(dāng)階數(shù)比較高的時候，Booth算法的編碼邏輯卻能帶來顯著的資源開銷。Wallace樹開辟了并行結(jié)構(gòu)的先河，與傳統(tǒng)算法相比，基于Wallace樹的分布式算法可極大地減少硬件電路規(guī)模，很容易實現(xiàn)流水線處理，提高電路的執(zhí)行速度，而且不受器件的限制[3]。 為了克服現(xiàn)有乘累加器的不足，同時為即將研制的通用數(shù)字神經(jīng)處理器MCU提供一個高速的運(yùn)算單元，本文對乘累加器算法進(jìn)行了改進(jìn)，采用補(bǔ)碼的分布式算法并在硬件電路上得以實現(xiàn)。

1補(bǔ)碼的分布式算法

分布式算法(distributed arithmetic, DA)與傳統(tǒng)算法實現(xiàn)乘加運(yùn)算的不同在于執(zhí)行部分積運(yùn)算的先后順序不同[4]。分布式算法在完成乘加功能時是通過將各輸入數(shù)據(jù)每一對應(yīng)位產(chǎn)生的積預(yù)先進(jìn)行相加形成相應(yīng)部分積，然后再對各部分積進(jìn)行累加形成最終結(jié)果，而傳統(tǒng)算法是等到所有乘積產(chǎn)生之后再進(jìn)行相加來完成乘加運(yùn)算的。因為大多數(shù)的乘累加過程會涉及到有符號數(shù)的運(yùn)算，所以這里的乘累加器所針對的操作數(shù)統(tǒng)一采用補(bǔ)碼。采用補(bǔ)碼運(yùn)算在進(jìn)行加法運(yùn)算的時候不需要考慮操作數(shù)的正負(fù)，也不需要對結(jié)果進(jìn)行轉(zhuǎn)換，直接使用全加器就可以得到正確的結(jié)果。所以說補(bǔ)碼的分布式算法簡化了有符號數(shù)、無符號數(shù)以及混合符號數(shù)的乘加減運(yùn)算，可以使加法樹在有符號的多操作樹累加中得到應(yīng)用，同樣時延更小的華萊士樹也可以在這里使用，可以進(jìn)一步提高運(yùn)算的速度[5-12]。補(bǔ)碼乘運(yùn)算規(guī)則：

(1)當(dāng)被乘數(shù)為任意整數(shù)，乘數(shù)為正整數(shù)時

被乘數(shù){x}補(bǔ)=x0·x1x2…xn=2n+1+x，

乘數(shù){y}補(bǔ)=0·y1y2…yn(y≥1)，

{x}補(bǔ){y}補(bǔ)=x0·x1x2…xn×0·y1y2…yn

=(2n+1+x)×y

=2n+1×y+xy(mod 2n+1)

=2n+1+xy

={xy}補(bǔ)。

(1)

此時乘積的結(jié)果就等于x與y的補(bǔ)碼直接相乘。

(2)當(dāng)被乘數(shù)為任意整數(shù)，乘數(shù)為負(fù)整數(shù)時

被乘數(shù){x}補(bǔ)=x0·x1x2…xn，

乘數(shù){y}補(bǔ)=1·y1y2…yn=2n+1+y，

y={y}補(bǔ)-2n+1

=1·y1y2…yn-2n+1

=0·y1y2…yn+2n-2n+1

=0·y1y2…yn-2n,

xy=x(0·y1y2…yn)-2n×x,

{xy}補(bǔ)={x}補(bǔ)(0·y1y2…yn)+{-x}補(bǔ)×2n。

(2)

當(dāng)乘數(shù)為負(fù)數(shù)時，補(bǔ)碼的乘積結(jié)果等于x的補(bǔ)碼與y的補(bǔ)碼去掉符號位后的乘積-x的補(bǔ)碼乘以最高位(符號位)。

由此可以獲得定點補(bǔ)碼乘法的統(tǒng)一公式為

{xy}={x}補(bǔ)×(0·y1y2…yn)+{-x}補(bǔ)×2n×y0，

(3)

其中-x的補(bǔ)碼由x的取反加1得到

(3)分布式算法

考慮如下的乘積項：

c,x為有符號數(shù)時，表達(dá)式如下

最高位xB為符號位，xb表示x的第b位，乘積y可以表示為

重新分別求和，并考慮補(bǔ)碼乘法規(guī)則結(jié)果如下

y=c[0]補(bǔ)(xB-2[0]2B-2+xB-3[0]2B-3+…+x0[0]20)+{-c[0]}補(bǔ)xB-1[0]2B-1+

c[1]補(bǔ)(xB-2[1]2B-2+xB-3[1]2B-3+…+x0[1]20)+{-c[1]}補(bǔ)xB-1[1]2B-1+…+

c[N-1]補(bǔ)(xB-2[N-1]2B-2+xB-3[N-1]2B-3+…+x0[N-1]20)+{-c[N-1]}補(bǔ)xB-1[N-1]2B-1

=(c[0]xB-2[0]+c[1]xB-2[1]+…+c[N-1]xB-2[N-1])2B-2+

(c[0]xB-3[0]+c[1]xB-3[1]+…+c[N-1]xB-3[N-1])2B-3+…+

(c[0]x0[0]+c[1]x0[1]+……+c[N-1]x0[N-1])20+({-c[0]}補(bǔ)xB-1[0]+

{-c[1]}補(bǔ)xB-1[1]+…+{-c[N-1]}補(bǔ)xB-1[N-1])2B-1。

(4)

分布式算法硬件結(jié)構(gòu)如圖1所示。

圖1　分布式結(jié)構(gòu)Fig.1　Structure of a distributed algorithm

另外，為了追求更快的運(yùn)算速度，我們采用并行算法對乘積項進(jìn)行處理，每次可令操作數(shù)移動2～3位，可以進(jìn)一步地提高運(yùn)算的速度，但是結(jié)構(gòu)也相應(yīng)的要復(fù)雜很多。當(dāng)同時移動3位時，新的系數(shù)c[n]將通過下面表1的規(guī)則獲得。

表1　系數(shù)規(guī)則

加法器樹也可以采用華萊士樹代替，可以進(jìn)一步減小加法器的進(jìn)位延時。

2仿真結(jié)果與分析

2.1仿真結(jié)果

采用Altera公司的Cyclone EP1C3作為目標(biāo)器件，用Verlog HDL描述了整個設(shè)計，并在Quartus開發(fā)系統(tǒng)中完成了整個設(shè)計的輸入、功能仿真和時序仿真，最后生成編程文件。乘累加器的目標(biāo)器件EP1C3T144C8的工作頻率為101.9 4 MHz，邏輯單元占總資源的2%，所用的引腳數(shù)占總引腳數(shù)的23%，我們通過6個乘積項9位有符號數(shù)的乘累加在目標(biāo)器件上進(jìn)行算法的驗證。

當(dāng)x和系數(shù)c的取值分別取以下值時，最終乘累加器的計算結(jié)果為-58 600,得到了正確的結(jié)果，說明該乘累加器的設(shè)計是正確的。

x1=100;x2=200;x3=30;x4=40;x5=50;x6=60;

c1=-100;c2=-200;c3=-30;c4=-40;c5=-50;c6=-60;

圖2為仿真的結(jié)果。

圖2　乘累加器仿真結(jié)果Fig.2　Simulation results of the multiply-accumulator

2.2算法分析

對比目前的DA分布式算法和采用乘法器結(jié)構(gòu)的MAC，本文的設(shè)計具有更多的優(yōu)勢。傳統(tǒng)的DA分布式算法，需要根據(jù)系數(shù)c計算累加值后儲存在LUT中，這樣帶來兩個問題。第一，不能即刻更新系數(shù)c，每一次更新都需要重新計算大量的累加值，這限制了分布式算法的應(yīng)用范圍。第二，隨著階數(shù)(N)和數(shù)據(jù)位數(shù)的增加，LUT所需的ROM也將以2的N次方迅速地增加。采用乘法器結(jié)構(gòu)的MAC，乘法器占用資源多，且即使高端FPGA內(nèi)部的乘法器數(shù)量也滿足不了并行運(yùn)算的消耗[13-16]。而本文設(shè)計的乘累加器使用加法器樹來代替原來的LUT，這樣的處理可以使系數(shù)c可以隨時更改數(shù)值，使得基于分布式算法的乘累加器不再局限于定系數(shù)乘累加運(yùn)算，而且對FPGA內(nèi)部RAM的需求也降到了0。

3結(jié)論

本文設(shè)計了一種并行結(jié)構(gòu)采用補(bǔ)碼分布式算法的乘累加器，并在EP1C3T144C8器件中實現(xiàn)。這種乘累加器改變了原來DA分布式算法系數(shù)固定的缺點，并且不需要大量的ROM用來作為系數(shù)表,所占用芯片的面積更小，實現(xiàn)了符號數(shù)的乘累加計算，擴(kuò)展方便，特別適合于可編程邏輯器件的實現(xiàn)。該乘累加器性能先進(jìn)，可以被廣泛的運(yùn)用到其他數(shù)字硬件設(shè)計中。但是，該乘累加器還有不少可改進(jìn)之處，比如采用并行算法縮短運(yùn)算周期，利用Wallace tree代替普通的加法器樹等等，能夠進(jìn)一步地簡化算法，減少延時降低功耗。

參考文獻(xiàn):

[1]陳楊生，顏剛鋒. 硬件實現(xiàn)基于BP神經(jīng)網(wǎng)絡(luò)設(shè)計的帶阻FIR濾波器[J]. 浙江大學(xué)學(xué)報:工學(xué)版，2006, 40(7)：1146-1149.

[2]趙宇玲. 基于FPGA的信號采集與處理系統(tǒng)設(shè)計與實現(xiàn)[D]. 南京：南京理工大學(xué)，2008.

[3]蘭景宏. 高性能乘累加器的設(shè)計研究[D]. 北京： 北京大學(xué)，2005.

[4]MEYER-BAESE U.數(shù)字信號處理的 FPGA 實現(xiàn)[M].北京：清華大學(xué)出版社，2006.

[5]李梅，王蘭勛. 分布式算法在FIR數(shù)字濾波器實現(xiàn)中的應(yīng)用[J]. 通信技術(shù)，2008，41(8):15-16.

[6]CILETTI M D. Verlog HDL 高級數(shù)字設(shè)計[M]. 北京：電子工業(yè)出版社，2005.

[7]李勇，裘式綱，王鳳學(xué)，等. 計算機(jī)原理與設(shè)計[M]. 長沙：國防科技大學(xué)出版社，1989.

[8]SUNDER S.A fast multiplier based on modified Boothalgorithm [J]. Int J Electronics,1993,75(2)：199-208.

[9]SAIT S M. A novel technique for fast multiplication [J]. Int J Electronics，1999,86(1):67-77.

[10]張禾，陳客松. 基于FPGA的稀疏矩陣向量乘的設(shè)計研究[J]. 計算機(jī)應(yīng)用研究，2014, 31(6)：1756-1759.

[11]于亞萍，陳雪強(qiáng)，劉源，等. 基于FPGA串并結(jié)合FIR濾波器的設(shè)計[J]. 湖北農(nóng)業(yè)科學(xué)，2012, 51(14)：3092-3095.

[12]鄒翠，謝憬，謝鑫君. 基于高性能浮點乘累加器的浮點協(xié)處理器設(shè)計[J]. 信息技術(shù)，2014(7) : 121-124.

[13]徐琪，段哲民. 泰勒級數(shù)的DDS設(shè)計與FPGA實現(xiàn)[J]. 計算機(jī)工程與應(yīng)用，2014, 50(5)：208-211.

[14]鄧耀華，吳黎明，張力鍇. 基于 FPGA 的雙 DDS 任意波發(fā)生器設(shè)計與雜散噪聲抑制方法[J].儀器儀表學(xué)報，2009，30(11)：2255-2261.

[15]黃丹連. 高吞吐率單雙精度可配置浮點乘累加器的設(shè)計與實現(xiàn)[D]. 上海：上海交通大學(xué)，2011.

[16]胡少軒. 基于FPGA的MAC FIR濾波器的實現(xiàn)[J]. 山西焦煤科技，2011(11):44-46.

Design of a parallel signed multiply-accumulator

ZHANG Lin1,TIAN Xian-zhong1,2,ZHAO Xing-wen1,YAN Guang1,GE Zhao-bin1

(1. Institute of Automation, Shandong Academy of Sciences, Jinan 271018, China;2. School of Instrumentation & Electrical Engineering, Jilin University, Changchun 130026, China)

Abstract∶We employ complement distributed algorithm to simplify addition, subtraction and multiplication of signed number, unsigned number and the number with mixed symbols. We further design a new multiply-accumulator structure through improving tree structure of an accumulator and logic circuit of a full adder. It is implemented with EP1C3T144C8 device from Altera company. Its effectiveness is proved through multiply-accumulating functionality and timing simulation result of six nine-bit signed operands. Its design overcomes the negatives of large RAM resource occupancy and no coefficient update of conventional distributed algorithm (DA). It can therefore be applied to the design of digital filters, and digital signal processors (DSP) as a rapid compute unit.

Key words∶multiply-accumulator; signed-number; variable coefficient

中圖分類號：TN431.2

文獻(xiàn)標(biāo)識碼：A

文章編號：1002-4026(2016)02-0096-05

作者簡介：張琳(1987-)，女，碩士，研究方向為嵌入式應(yīng)用開發(fā)編程。Email：zhanglin987326@126.com

基金項目：山東省科學(xué)院先導(dǎo)科技專項;山東省自主創(chuàng)新及成果轉(zhuǎn)化專項(2014CGZH1104)

收稿日期：2015-06-11

DOI:10.3976/j.issn.1002-4026.2016.02.018