條件推測性十進制加法器的優(yōu)化設(shè)計

崔曉平 王書敏 劉偉強 董文雯

?

條件推測性十進制加法器的優(yōu)化設(shè)計

崔曉平*王書敏 劉偉強 董文雯

(南京航空航天大學電子信息工程學院 南京 210016)

隨著商業(yè)計算和金融分析等高精度計算應用領(lǐng)域的高速發(fā)展，提供硬件支持十進制算術(shù)運算變得越來越重要，新的IEEE 754-2008浮點運算標準也添加了十進制算術(shù)運算規(guī)范。該文采用目前最佳的條件推測性算法設(shè)計十進制加法電路，給出了基于并行前綴/進位選擇結(jié)構(gòu)的條件推測性十進制加法器的設(shè)計過程，并通過并行前綴單元對十進制進位選擇加法器進行優(yōu)化設(shè)計。采用Verilog HDL對32 bit, 64 bit和128 bit十進制加法器進行描述并在ModelSim平臺上進行了仿真驗證，在Nangate Open Cell 45nm標準工藝庫下，通過Synopsys公司綜合工具Design Compiler進行了綜合。與現(xiàn)有的條件推測性十進制加法器相比較，綜合結(jié)果顯示該文所提出的十進制加法器可以提升12.3%的速度性能。

十進制加法；條件推測十進制加法；并行前綴；進位選擇加法器

1 引言

提供硬件支持十進制浮點(Decimal Floating Point, DFP)算術(shù)運算正在成為一個熱門的研究方向，2008年發(fā)行的IEEE 754標準的修訂版本(IEEE 754-2008)[1]包括DFP算術(shù)運算的最新規(guī)范。越來越多的處理器制造商傾向于在自己的處理器芯片中集成專用的十進制浮點運算單元，IBM面向工作站和服務器的Power 6[2]微處理器以及Z10大型機[3]的處理器中已經(jīng)包括了完全符合IEEE754-2008標準的十進制浮點運算硬件單元。在處理器中提供專用的十進制運算單元將成為趨勢。

十進制算術(shù)運算中最基礎(chǔ)的十進制加法一直是研究的熱點，目前的十進制加法運算基本上采用8421二-十進制編碼(Binary Coded Decimal, BCD)，采用8421-BCD碼設(shè)計十進制加法器的優(yōu)勢在于可以利用二進制加法器中成熟且性能優(yōu)越的電路結(jié)構(gòu)來設(shè)計十進制加法器，使其電路結(jié)構(gòu)更為簡單與規(guī)整。不論在二進制加法還是十進制加法中，影響加法電路運算速度的主要因素在于低位向高位傳播的進位鏈。二進制加法和BCD 十進制加法的不同點是：(1)二進制加法的進位規(guī)則是逢二進一，其進位的產(chǎn)生與傳遞比較簡單，而十進制加法運算需要計算十進制數(shù)之間的進位，其進位規(guī)則是逢十進一。(2)4 bit編碼的8421-BCD共有16種狀態(tài)，其中6種編碼(1010,1011,1100,1101,1110, 1111)是誤碼，因此，當采用二進制運算方法對4 bit 8421-BCD進行相加運算時，需要對二進制運算結(jié)果進行修正。

為了提高8421-BCD碼十進制加法的性能，研究人員提出了多種算法與結(jié)構(gòu)，其中最經(jīng)典的兩種方法是直接十進制加法[5]和推測性十進制加法[7]。直接十進制加法是一種無需進行修正的十進制加法算法，該算法推導出直接產(chǎn)生十進制和與十進制進位的方法，在IBM S/360 Model 195機型的處理器中使用該算法完成浮點運算[4]。推測性十進制加法采用預先修正，二進制求和并再修正的算法，這種采用預先修正的十進制加法，稱之為推測性十進制加法。文獻[7-9]根據(jù)此思路提出了條件推測性十進制加法，即有條件地對操作數(shù)進行預先加6修正。

條件推測性十進制加法器主要包括+6預處理模塊、二進制并行前綴加法器模塊和十進制進位選擇加法器模塊。二進制并行前綴加法器(Parallel Prefix Adder, PPA)可以看成是超前進位加法器的一種改進結(jié)構(gòu)，其常見的結(jié)構(gòu)包括Kogge-Stone(KS)樹[18]、Brent-Kung(BK)樹[14]、Sklansky(SK)樹[15]、Han-Carlson(HC)樹[16]等基本樹形結(jié)構(gòu)和并行前綴/進位選擇混合加法器(Hybrid Parallel-Prefix/ Carry-Select Adder, PPF/CSA)結(jié)構(gòu)。并行前綴/進位選擇混合加法器被廣泛應用于寬位加法器的設(shè)計中。

文獻[7-9]使用QT (Quaternary Tree, QT)樹形結(jié)構(gòu)[12]產(chǎn)生進位信號，該結(jié)構(gòu)與基于SK的PPF/ CSL加法器結(jié)構(gòu)相同，進位選擇加法器模塊的長度為4，適用于設(shè)計4位一組的BCD十進制加法器。SK樹形結(jié)構(gòu)隨著操作數(shù)位數(shù)的增大，其最大扇出數(shù)呈線性增長，導致延遲時間增大。KS并行前綴加法器具有最短的延時，且結(jié)構(gòu)規(guī)整并具有相同的扇出因子，但不足之處是復雜度隨著操作數(shù)位數(shù)增加，因此導致面積和功耗的增大，采用基于KS的PPF/CSA加法器結(jié)構(gòu)可以得到高速的十進制加法器。本文重點研究基于KS的PPF/CSL十進制定點加法器的算法與相關(guān)結(jié)構(gòu)，并在第3節(jié)針對條件推測性十進制加法器給出優(yōu)化設(shè)計方法以降低電路的復雜度。

本文結(jié)構(gòu)如下：第2節(jié)介紹了基于8421-BCD碼的十進制加法；第3節(jié)給出了新的基于KS結(jié)構(gòu)的條件推測性十進制加法器的設(shè)計；第4節(jié)給出了仿真結(jié)果并與現(xiàn)有的二進制和十進制加法器進行了對比分析。

2 基于8421-BCD碼的十進制加法概述

在設(shè)計bit(=4)十進制加法器時，采用8421-BCD碼對兩個位寬為的十進制被加數(shù)和加數(shù)進行編碼，具體形式為

基于8421-BCD碼的十進制加法的基本算法是：首先對十進制被加數(shù)和加數(shù)按二進制加法進行運算，再對運算結(jié)果進行糾錯。產(chǎn)生錯誤的原因是十進制數(shù)相加的進位原則是“逢十進一”，而4 bit二進制數(shù)相加采用“逢十六進一”的進位原則，兩者相差6。因此，按二進制數(shù)運算規(guī)則得到的8421-BCD碼運算結(jié)果需要修正。修正的方法是當和數(shù)大于9或產(chǎn)生進位時，需要對該位的和加6修正。上述算法的最大缺陷是修正時的進位鏈會導致延時增加。研究人員提出了幾種改進方法，主要有直接十進制加法[5]，推測性十進制加法以及條件推測性加法。

1位直接十進制加法的輸入為8421-BCD碼的十進制被加數(shù)，加數(shù)以及一個1 bit的十進制進位輸入信號，直接產(chǎn)生十進制和，以及一個1 bit的十進制進位輸出,的位權(quán)是的10倍，其表達式為

推測性十進制加法對操作數(shù)的每一個十進制位先加6，然后對按照二進制的方法進行求和，如果該十進制位的進位輸出為0，則說明加6操作是多余的，進行減6修正，其結(jié)構(gòu)如圖1所示。

圖1 推測性十進制加法結(jié)構(gòu)圖

文獻[7-9]依據(jù)此思路提出有條件的推測性加法算法，該算法沒有對操作數(shù)的所有十進制位A加6，而是根據(jù)一定條件判斷是否需要對某個十進制位進行加6預操作，稱之為條件推測性十進制加法，條件推測性十進制加法結(jié)構(gòu)如圖2所示。

圖2 條件推測性十進制加法結(jié)構(gòu)圖

由此可以得到：

圖3 加6操作電路圖

3 建議的基于KS結(jié)構(gòu)的條件推測性十進制加法器的設(shè)計

在設(shè)計條件推測性十進制加法器時，完成加6預操作之后十進制進位和二進制相應位的進位信號一致，因此在二進制加法器設(shè)計中廣泛采用的并行前綴/進位選擇結(jié)構(gòu)可以用于十進制加法器的設(shè)計。文獻[7-9]采用基于SK的QT樹形結(jié)構(gòu)產(chǎn)生進位信號。典型的16 bit SK結(jié)構(gòu)如圖4所示，SK樹的邏輯級數(shù)最小，為，運算結(jié)點只有個。但是SK樹形結(jié)構(gòu)隨著操作數(shù)位數(shù)的增大，其最大扇出數(shù)呈線性增長，導致延遲時間增大。為了獲得高性能的十進制加法器，采用基于KS的并行前綴/進位選擇加法器結(jié)構(gòu)設(shè)計32 bit, 64 bit和128 bit十進制加法器，并對4 bit十進制進位選擇加法器進行優(yōu)化設(shè)計。典型的16 bit KS結(jié)構(gòu)如圖5所示。

圖4 典型16bit Sklansky前綴結(jié)構(gòu)

圖5 典型16bit Kogge-Stone前綴結(jié)構(gòu)

為了減少加法器的復雜度，本文將利用并行前綴單元對文獻[7]中的十進制進位選擇單元進行改進。令,為相應的十進制進位輸出信號，當時，運算結(jié)果無需修正；當時，不管等于0或者1,,和與無關(guān)。定義是0位和1位的方塊進位產(chǎn)生信號，是0位和1位的方塊進位傳遞信號；定義是0位、1位和2位的方塊進位產(chǎn)生信號，是0位、1位和2位的方塊進位傳遞信號。則

由式(7)和式(8)得到改進的十進制進位選擇加法器如圖6所示。

圖6 改進的十進制進位選擇加法器單元

32 bit基于KS結(jié)構(gòu)的并行前綴/進位選擇加法器由8 bit KS結(jié)構(gòu)的并行前綴加法器擴展得到，產(chǎn)生的7個進位輸出信號作為十進制4 bit進位選擇加法器單元進位選擇信號。改進的32 bit基于KS結(jié)構(gòu)的并行前綴/進位選擇十進制加法器如圖7所示。圖7中的十進制進位選擇加法器模塊如圖6所示。由圖6和圖7可以看到，充分利用并行前綴中已經(jīng)存在的方塊進位產(chǎn)生信號和方塊進位傳遞信號來簡化十進制進位選擇加法電路，避免在進位選擇加法器中重復計算，可以減小電路的復雜度。

圖7 改進的16bit基于KS并行前綴/進位選擇結(jié)構(gòu)條件推測性十進制加法器

4 實驗結(jié)果

64 bit基于KS結(jié)構(gòu)的并行前綴/進位選擇加法器由16 bit KS結(jié)構(gòu)的并行前綴加法器擴展得到，產(chǎn)生的15個進位輸出信號作為十進制4 bit進位選擇加法器單元進位選擇信號，128 bit基于KS結(jié)構(gòu)的并行前綴/進位選擇加法器由32 bit KS結(jié)構(gòu)的并行前綴加法器擴展得到，產(chǎn)生的31個進位輸出信號作為十進制4 bit進位選擇加法器單元進位選擇信號。使用Verilog HDL硬件描述語言分別對32 bit, 64 bit和128 bit基于并行前綴/進位選擇結(jié)構(gòu)的條件推測性十進制加法器進行描述。在NanGate Open Cell 45nm CMOS標準工藝庫下，通過Synopsys公司綜合工具Design Compiler進行綜合，獲得延時和面積，采用Synopsys Power Compiler獲取功耗。最終得到本文提出的32 bit, 64 bit, 128 bit十進制加法器，基于KS結(jié)構(gòu)的二進制并行前綴/進位選擇加法器[17]和文獻[9]中的電路結(jié)構(gòu)的延遲、面積、功耗參數(shù)結(jié)果如表1所示。延時對比和延時-功耗積對比如圖8和圖9所示。

圖8 改進的十進制加法器與文獻[9]和文獻[17]的延時對比

圖9 改進的十進制加法器與文獻[9]和文獻[17]的延時-功耗積對比

表1二進制、十進制加法器綜合結(jié)果比較

從圖8和圖9對比結(jié)果可知，與文獻[9]所采用的加法器結(jié)構(gòu)相比較，在不增加面積和功耗的情況下，本文提出的32 bit, 64 bit和128 bit十進制加法器的延遲分別降低9.5%, 9.6%和12.3%，隨著位寬的增加，速度提高的效果更加明顯。其延時-功耗積分別減少了14.5%, 13.0%和13.8%，其性能得到有效的改善。

與基于KS結(jié)構(gòu)的PPF/CSL的二進制加法器相比較，本文提出的32 bit, 64 bit和128 bit十進制加法器的延時-功耗積分別增加了25.9%, 28.0%和6.5%。從綜合結(jié)果來看，十進制加法器的速度低于二進制加法器。需要說明的是，十進制加法器和二進制加法器的綜合結(jié)果的比較僅具有參考意義，目前十進制算術(shù)運算只是應用于商業(yè)和金融等高精度計算領(lǐng)域，它并不能取代二進制算術(shù)運算。

5 結(jié)束語

條件推測性十進制加法器可以有效地完成十進制加法器運算，本文采用基于KS結(jié)構(gòu)的PPF/CSL加法器構(gòu)成條件推測性十進制加法器，并對4 bit進位選擇單元進行優(yōu)化設(shè)計，利用并行前綴中的方塊進位產(chǎn)生信號和方塊進位傳遞信號來簡化十進制進位選擇加法的電路。從實驗結(jié)果看出，本文提出的32 bit, 64 bit和128 bit十進制加法器相比較于文獻[9]中的電路結(jié)構(gòu)延時-功耗積分別降低了14.5%, 13.0%和13.8%。本文提出的條件推測性十進制加法器的性能得到了有效的提升。

參考文獻

[1] IEEE Std 754(TM)-2008. IEEE standard for floating-point arithmetic[S]. IEEE CS, 2008. doi: 10.1109/ieeestd.2008. 4610935.

[2] EISEN L, WARD J W, TAST H W,. IBM POWER6 accelerators: VMX and DFU[J]., 2007, 51(6): 663-684.doi: 10.1147/rd.516.0663.

[3] SCHWARZ E M, KAPERNICK J S, and COWLISHAW M F. Decimal floating-point support on the IBM system z10 processor[J]., 2009, 53(1): 4:1-4:10.doi: 10.1147/JRD.2009.5388585.

[4] WANG L K, ERLE M A, TSEN C,. A survey of hardware designs for decimal arithmetic[J]., 2010, 54(2): 8:1-8:15.doi: 10.1147/ JRD.2010.2040930.

[5] SCHMOOKLER M and WEINBERGER A. High speed decimal addition[J]., 1971, 20(8): 862-866.doi: 10.1109/T-C.1971.223362.

[6] LIU Han, ZHANG Hao, and SEOK-BUM Ko. Area and power efficient decimal carry-free adder[J]., 2015, 51(23): 1852-1854. doi: 10.1049/el.2015.0786.

[7] VAZQUEZ A and ANTELO E. Conditional speculative decimal addition[C]. Proceedings of Seventh Conference on Real Numbers and Computers, Nancy, France, 2006: 47-57.

[8] VAZQUEZ A, ANTELO E, and MONTUSCHI P. Improved design of high-performance parallel decimal multipliers[J]., 2010, 59(5): 679-693.doi: 10.1109/TC.2009.167.

[9] VAZQUEZ A, ANTELO E, and BRUGUERA J. Fast radix-10 multiplication using redundant BCD codes[J]., 2014, 63(8): 1902-1914. doi: 10.1109/TC.2014.2315626.

[10] KORNERUP P. Reviewing high-radix signed-digit adders[J]., 2015, 64(5): 1502-1505.doi: 10.1109/TC.2014.2329678.

[11] MOHANTY B K. Area-delay-power efficient carry-select adder[J].:, 2014, 61(6): 418-422.doi: 10.1109/TCSII. 2014.2319695.

[12] MATHEW S K, ANDERS M, KRISHNAMURTHY R K,. A 4 GHz 130 nm address generation unit with 32-bit sparse-tree adder core[J]., 2003, 38(5): 689-695.doi: 10.1109/JSSC.2003. 810056.

[13] KOGGE P M and STONE H S. A parallel algorithm for efficient solution of a general class of recurrence equations[J]., 1973, 22(8): 786-793.doi: 10.1109/TC.1973.5009159.

[14] BRENT R P and KUNG H T. A regular layout for parallel adders[J]., 1982, 31(3): 260-264.doi: 10.1109/TC.1982.1675982.

[15] SKLANSKY J. Conditional-sum addition logic[J]., 1960, EC-9(2): 226-231. doi: 10.1109/TEC.1960.5219822.

[16] HAN TACKDON and CARLSON D A. Fast area-efficient VLSI adders[C]. IEEE 8th Symposium on Computer Arithmetic, 1987: 49-56. doi: 10.1109/ARITH.1987.6158699.

[17] DIMITRAKOPOULOS G and NIKOLOS D. High-speed parallel- prefix VLSI Ling adders[J]., 2005, 54(2): 225-231.doi: 10.1109/TC.2005.26.

[18] HE Yajuan and CHANG C H. A power-delay efficient hybrid carry-lookahead/carry-select based redundant binary to two’s complement converter[J].&:, 2008, 55(1): 336-346.doi: 10.1109/TCSI.2007.913610.

Design of Optimized Conditional Speculative Decimal Adders

CUI Xiaoping WANG Shumin LIU Weiqiang DONG Wenwen

(,&,210016,)

There are increasing interests in hardware support for decimal arithmetic due to the demand of high accuracy computation in commercial computing, financial analysis, and other applications. New specifications for decimal floating-point arithmetic have been added to the revised IEEE 754-2008 standard. In this paper, the algorithm and architecture of decimal addition is studied comprehensively. A decimal adder is designed by using the parallel-prefix/carry-select architecture. The parallel-prefix unit is used to optimize the decimal carry select adder. The decimal adder has been realized by Verilog HDL and simulated with ModelSim. The synthesis results of this design by Design Compiler is also given and analyzed under Nangate Open Cell 45nm library. The results show that the delay performance of the proposed circuit can be improved by up to 12.3%.

Decimal addition; Conditional speculative decimal addition; Parallel prefix; Carry select adder

TN431.2

A

1009-5896(2016)10-2689-06

10.11999/JEIT151416

2015-12-14；改回日期：2016-06-08；網(wǎng)絡(luò)出版：2016-07-19

崔曉平 wnhcxp@nuaa.edu.cn

崔曉平： 女，1962年生，副教授，碩士生導師，研究方向為數(shù)字集成電路設(shè)計和計算機算術(shù)運算系統(tǒng).

王書敏： 男，1990年生，碩士生，研究方向為數(shù)字系統(tǒng)設(shè)計與計算機應用.

劉偉強： 男，1983年生，副教授，碩士生導師，研究方向為數(shù)字集成電路設(shè)計和加密硬件.

董文雯： 女，1993年生，碩士生，研究方向為數(shù)字系統(tǒng)設(shè)計與計算機應用.