一種并行結構有符號乘累加器的設計

張琳， 田現忠,2 ，趙興文 ，顏廣 ，葛兆斌

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

?

一種并行結構有符號乘累加器的設計

張琳1， 田現忠1,2，趙興文1，顏廣1，葛兆斌1

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

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

關鍵詞：乘累加器；有符號數；可變系數

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

1補碼的分布式算法

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

(1)當被乘數為任意整數，乘數為正整數時

被乘數{x}補=x0·x1x2…xn=2n+1+x，

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

{x}補{y}補=x0·x1x2…xn×0·y1y2…yn

=(2n+1+x)×y

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

=2n+1+xy

={xy}補。

(1)

此時乘積的結果就等于x與y的補碼直接相乘。

(2)當被乘數為任意整數，乘數為負整數時

被乘數{x}補=x0·x1x2…xn，

乘數{y}補=1·y1y2…yn=2n+1+y，

y={y}補-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}補={x}補(0·y1y2…yn)+{-x}補×2n。

(2)

當乘數為負數時，補碼的乘積結果等于x的補碼與y的補碼去掉符號位后的乘積-x的補碼乘以最高位(符號位)。

由此可以獲得定點補碼乘法的統一公式為

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

(3)

其中-x的補碼由x的取反加1得到

(3)分布式算法

考慮如下的乘積項：

c,x為有符號數時，表達式如下

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

重新分別求和，并考慮補碼乘法規則結果如下

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

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

c[N-1]補(xB-2[N-1]2B-2+xB-3[N-1]2B-3+…+x0[N-1]20)+{-c[N-1]}補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]}補xB-1[0]+

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

(4)

分布式算法硬件結構如圖1所示。

圖1　分布式結構Fig.1　Structure of a distributed algorithm

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

表1　系數規則

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

2仿真結果與分析

2.1仿真結果

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

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

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為仿真的結果。

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

2.2算法分析

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

3結論

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

參考文獻:

[1]陳楊生，顏剛鋒. 硬件實現基于BP神經網絡設計的帶阻FIR濾波器[J]. 浙江大學學報:工學版，2006, 40(7)：1146-1149.

[2]趙宇玲. 基于FPGA的信號采集與處理系統設計與實現[D]. 南京：南京理工大學，2008.

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

[4]MEYER-BAESE U.數字信號處理的 FPGA 實現[M].北京：清華大學出版社，2006.

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

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

[7]李勇，裘式綱，王鳳學，等. 計算機原理與設計[M]. 長沙：國防科技大學出版社，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的稀疏矩陣向量乘的設計研究[J]. 計算機應用研究，2014, 31(6)：1756-1759.

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

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

[13]徐琪，段哲民. 泰勒級數的DDS設計與FPGA實現[J]. 計算機工程與應用，2014, 50(5)：208-211.

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

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

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

文獻標識碼：A

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

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

基金項目：山東省科學院先導科技專項;山東省自主創新及成果轉化專項(2014CGZH1104)

收稿日期：2015-06-11

DOI:10.3976/j.issn.1002-4026.2016.02.018