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

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

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

?

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

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

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

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

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

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

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

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

(1)當(dāng)被乘數(shù)為任意整數(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)

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

(2)當(dāng)被乘數(shù)為任意整數(shù)，乘數(shù)為負(fù)整數(shù)時(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ù)時(shí)，補(bǔ)碼的乘積結(jié)果等于x的補(bǔ)碼與y的補(bǔ)碼去掉符號(hào)位后的乘積-x的補(bǔ)碼乘以最高位(符號(hào)位)。

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

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

(3)

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

(3)分布式算法

考慮如下的乘積項(xiàng)：

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

最高位xB為符號(hào)位，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)算速度，我們采用并行算法對(duì)乘積項(xiàng)進(jìn)行處理，每次可令操作數(shù)移動(dòng)2～3位，可以進(jìn)一步地提高運(yùn)算的速度，但是結(jié)構(gòu)也相應(yīng)的要復(fù)雜很多。當(dāng)同時(shí)移動(dòng)3位時(shí)，新的系數(shù)c[n]將通過(guò)下面表1的規(guī)則獲得。

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

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

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

2.1仿真結(jié)果

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

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

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算法分析

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

3結(jié)論

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

參考文獻(xiàn):

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

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

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

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

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

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

[7]李勇，裘式綱，王鳳學(xué)，等. 計(jì)算機(jī)原理與設(shè)計(jì)[M]. 長(zhǎng)沙：國(guó)防科技大學(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]. 計(jì)算機(jī)應(yīng)用研究，2014, 31(6)：1756-1759.

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

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

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

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

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

[16]胡少軒. 基于FPGA的MAC FIR濾波器的實(shí)現(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

中圖分類(lèi)號(hào)：TN431.2

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

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

作者簡(jiǎn)介：張琳(1987-)，女，碩士，研究方向?yàn)榍度胧綉?yīng)用開(kāi)發(fā)編程。Email：zhanglin987326@126.com

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

收稿日期：2015-06-11

DOI:10.3976/j.issn.1002-4026.2016.02.018