一種自定時的前置進位加法器設計

摘 要:從時序控制的角度出發，研究提高加法器性能的方法。在研究前置進位加法器的算法和結構后，又對多米諾電路的時鐘控制技術進行深入分析。結合前置進位結構和自定時時鐘控制，設計了一個32 b多米諾加法器。該加法器能有效地提高時鐘使用率。在TSMC 0.18 μm工藝下，加法器的最大延時為970 ps，約為相同工藝下13倍FO4的延時。

關鍵詞:加法器;自定時;多米諾;前置進位

中圖分類號:TN710文獻標識碼:B

文章編號:1004-373X(2010)02-019-03

Design of Self_timed Prefix_carrying Adder

XU Li1，XIN Xiaoning1，YANG Zhijia2

(1.Shenyang University of Technology，Shenyang，110178，China;2.Shenyang Institute of Automation，Chinese Academy of Sciences，Shenyang，110015，China)

Abstract:From the point of time_controlling，the method of improving the performance of adder is researched.After discussing the algorithm and structure of prefix_carrying adder，the time_controlling technology of Domino circuit is analyseddeeply.Combined the structure of prefix_carrying and self_timing，a 32 b Domino adder is designed.The usage of clock is enhanced efficiently by the adder.In TSMC0.18 μm process，the adder′s maximal delay is 970 ps，about 13 times of the delay of FO4 in the same process.

Keywords:adder;self_timed;Domino;prefix_carrying

加法器是一種基本的運算電路，幾乎所有的數字運算都會用到。加法器完成一次加法操作所需要的時間基本上決定了數字運算電路的主頻。因此研究高速加法器對提高數字運算電路的性能具有重要意義。多米諾電路的時序控制是制約加法器工作速度的瓶頸之一[1]。現今大部分加法器采用的同步時鐘都需要構建時鐘樹，并降低了時鐘的利用率[2]。本文介紹的自定時時鐘不僅能夠克服這方面的問題，還能有效地利用時鐘資源。以漢_卡爾森(Han Carlson，HC)算法[3]為例，在TSMC 0.18 μm工藝下，采用多米諾邏輯設計了一種32位自定時的加法器，最大延時為970 ps，約為相同工藝下FO4延時的13倍。

1 前置進位加法器的算法及結構

前置進位樹是目前流行的高速加法器結構。樹型結構可以分為很多種。本文所采用的HC算法就是其中的一種。HC算法在高位加法器設計上突出了優勢。這種算法集合了KS和BK兩種算法的優點[4]，在獲得最小扇出的同時，實現的級數僅為log2 (n+1)，其中n為加法器的位數[5]，同時也減少了級間布線。

1.1 前置進位算法

加法器的前置進位算法定義了三個重要的信號:進位生成信號G、進位傳播信號P和進位消除信號K。前置進位樹就是這些信號的堆疊[6]。對于某一位而言，其邏輯表達式為:

G=A#8226;B， P=A⊕B

K=A#8226;B=A+B

對于連續的一組加數和被加數而言，這些信號能夠遞歸地定義為:

Gi:j=Gi:k+Pi:kG(k-1):j， Pi:j=Pi:kP(k-1):j

Ki:j=Ki:k+Pi:kK(k-1):j，i≥k>j

經過log2(n+1)級前置進位樹，組信號被整理成Gi:0，Pi:0，Ki:0(n>i≥0)的形式，那么運算和就可以表示為:

Si=G(i-1):0Pi_l+K(i-1):0Pi_h

1.2 HC進位樹結構

HC進位樹先在奇數位計算2位組前置信號{(G1:0，P1:0，K1:0)，(G3:1，P3:1，K3:1)…(G31:29，P31:29，K31:29)}，再用這些2位組前置信號計算4位組前置信號{(G3:0，P3:0，K3:0)，(G5:2，P5:2，K5:2)…(G31:27，P31:27，K31:27)}。依此類推，從而計算出所有奇數位的組前置信號{(G1:0，P1:0，K1:0)，(G3:0，P3:0，K3:0)…(G31:0，P31:0，K31:0)}。最后用一級邏輯行波到偶數位，即得到所有位的組信號{(G1:0，P1:0，K1:0)，(G2:0，P2:0，K2:0)…(G30:0，P30:0，K30:0)，(G31:0，P31:0，K31:0)}。32位HC進位樹結構如圖1所示。

圖1 32位HC進位樹結構

2 多米諾加法器時序設計

2.1 常規的多米諾電路時序控制

對于多米諾電路的時序控制，通常將電路分為延時大致相等的兩部分。對于前一部分電路，時鐘在前半個周期內求值，在后半個周期內預充。對后一部分操作相反，如此反復。在每部分電路的末端加入一個鎖存器，使該部分進行預充時保留其前一周期的計算結果[7]。如圖2(a)所示，數據必須在時鐘下降前的建立時間內到達鎖存器中，再通過鎖存器向后傳播。這種常規方法在鎖存器延時、時鐘偏斜和不平衡邏輯等方面具有較高的時序控制開銷，從而降低了多米諾邏輯的性能優勢。

2.2 容偏斜的多米諾電路時序控制

容偏斜的多米諾電路時序控制方法要求時鐘在高電平重疊，且重疊時間可以使第二相在第一相預充之前進行求值。這樣就可以去掉每一相邊界上的鎖存器，克服了常規時序控制方法的缺點。但是，容偏斜時序同時引入了另外一個矛盾，即必須保證即使在最差的時鐘偏斜情況下，時鐘的重疊也必須足以使電路正常工作[8]。否則就會造成時序混亂，出現計算錯誤。這無疑增加了設計難度，如圖2(b)所示。

2.3 時鐘延時的多米諾電路時序控制

時鐘延時多米諾邏輯不像通常的多米諾邏輯中所有級的門都使用統一的時鐘，而是每一級門都使用其自己的時鐘。這些時鐘隨著數據計算一起在模塊中像波紋一樣傳播，如圖2(c)所示。

時鐘延時多米諾邏輯由全局時鐘通過延時單元產生多相交疊時鐘。其下一相時鐘上升沿的到來必須等待前一級電路的所有信號計算完成。即使某一級電路的大部分邏輯門都可以很快地完成計算，但只要有一個邏輯門的速度非常慢，延時單元的延時也要設計為最慢延時，而且還要留有20%門延遲的余量[9]。同時，相鄰兩相時鐘也要有足夠的重疊，以確保在最差時鐘偏斜的情況下，第二相時鐘可以在第一相預充之前進行求值。這也就限制了加法器的運算速度。

2.4 自定時時鐘

2.4.1 雙軌多米諾邏輯

雙軌多米諾邏輯的所有信號均用兩個互補信號表示。它的一個突出特點就是可以表示計算是否完成。在計算未完成的狀態下，一對互補的輸出都會使其中一個輸出跳變為高電平。所以，在一對互補輸出信號上加入一個與非門就可以檢測到計算是否已經完成。

圖2 多米諾電路的時序控制

2.4.2 自定時控制

前置信號G，P，K的邏輯“或”就類似于雙軌多米諾邏輯的檢測信號。預充時，檢測信號的值為邏輯“0”;計算完成后，G，P，K中一定有一個信號跳變為“1”，檢測信號也隨之跳變。

三輸入多米諾或門是由三個NMOS管并聯而成的，其運算速度較靜態或門快很多。所以，使用Ti=Gi+Pi+Ki表示計算是否完成，并不占用很大的邏輯延時。相反，其延時可以作為延時余量。同理，這種檢測信號可以推廣到組前置信號中，如圖3所示。

圖3 多米諾電路的自定時控制

根據自定時時鐘控制理論，結合雙軌多米諾邏輯中檢測信號的思想，構建出每級的自定時時鐘信號。由于把每一級的模塊進行分組，產生的自定時時鐘不需要驅動下一級的所有時鐘控制晶體管，所以自定時時鐘信號有一個相對小的扇出，也就去掉了時鐘緩沖器電路。該方法精確地控制了下一級多米諾邏輯的求值啟動時間，不僅不需要再進行時鐘樹設計，還避免了由于時鐘偏斜帶來的負面影響，提高了電路的工作效率。這種自定時時鐘控制加法器具有不可忽視的設計優勢。圖4就是加法器關鍵路徑上的自定時時鐘信號。

圖4 進位樹上的時鐘信號

3 加法器設計

3.1 前置進位加法器的結構

圖5中前置進位加法器先根據輸入的加數和被加數產生相應的前置信號。再由進位樹對前置信號進行處理，得出所有組的進位信號。最后計算出加法和[10]。

3.2 性能仿真

要測量加法器的運算速度，首先要選擇該加法器的關鍵路徑。加法器的關鍵路徑就是其最大延時路徑(圖1中粗線)。對于加法器的第i位，如果Ai≠Bi，則該位的進位輸出依賴于進位輸入;如果Ai=Bi，那么該位的進位使獨立于進位輸入。因此最差情況就是，每一位二進制加數A均不等于被加數B。在這種情況下，進位輸入需要從最低位依次傳遞到最高位。

設置最大延時情況下的輸入A[31:0]= 32′b1，B[31:0]=32′b0。用HSpice對加法器的關鍵路徑仿真。圖6中的A為整體時鐘信號，B為關鍵路徑上的和。結果顯示，延時為980 ps。

圖5 加法器的結構

圖6 關鍵路徑的Hspice仿真

4 結 語

基于加法器的前置進位樹結構，在分析多米諾電路時序控制的基礎上，指出了樹型結構存在時序設計的困難。使用自定時控制技術設計出一個32位加法器。在獲得較快速度的同時，又方便了多米諾電路的時序設計。

參考文獻

[1]Smith A Beaumont，Lim C.Parallel Prefix Adder Design[A].Proc.15th IEEE Symposium Computer Arithmetic\\.2001:218_225.

[2]Huang C，Wang J，Huang Y.Design of High_performance CMOS Priority Encoders and Incrementer/Decrementers using Multilevel Lookahead and Multilevel Folding Techniques[J].IEEE Solid_State Circuits，2002，37(1):63_76.

[3]Parhami B.Computer Arithmetic:Algorithms and Hardware Designs\\.Oxford:Oxford University Press，2000.

[4]David Harris.A Taxonomy of Parallel Prefix Networks[A].Proc.37th Asilomar Conf.Signals，Systems and Computers\\.2003:2 213_2 217.

[5]Neil H E Weste，David Harris.CMOS VLSI Design:A Circuits and Systems Perspective[M].北京:機械工業出版社，2005.

[6]王禮平，王觀鳳.超前進位加法器混合模塊延遲公式及優化序列[J].微電子學與計算機，2004，22(1):125_155.

[7]Weste N，Eshraghiam K.Principles of CMOS VLSI Design[M].Boston:Addison Wesley，1993.

[8]Harris D，Horowitz M A.Skew_Tolerant Domino Circuits[J].IEEE Journal of Solid_State Circuit，1997，32:1 702_1 711.

[9]Rabaey Jan M.數字集成電路設計透視[M].北京:清華大學出版社，1998.

[10]李振，高德遠.32位最大速率流水加法器的研究與實現[J].微電子學與計算機，2006，24(8):12_24.

作者簡介 徐 麗 1984年出生，碩士研究生。研究方向為集成電路設計。

辛曉寧 1965年出生，教授，碩士生導師。研究方向為片上系統及嵌入式軟硬件設計。

楊志家 研究員。研究方向為集成電路設計、片上系統設計、實時嵌入式系統技術和現場總線與工業以太網技術。