高性能64位并行前綴加法器全定制設計

1、高性能 64 位并行前綴加法器全定制設計王仁平，何明華，魏榕山，陳傳東，戴惠明( 福州大學物理與信息工程學院，福建 福州 350108)摘要: 基于 64 位基 4 的 Kogge Stone 樹算法原理，采用多米諾動態(tài)邏輯、時鐘延遲多米諾和傳輸管邏輯等技術來設計和優(yōu)化并行前綴加法器的結構，到達減少了加法器各級門的延遲時間目的 為實現幅員面積小、性能 好，采用啟發(fā)式歐拉路徑算法來確定塊進位產生信號電路結構，采用多輸出多米諾邏輯來優(yōu)化塊進位傳播信號，采用 6 管傳輸管邏輯的半加器 該加法器全定制設計采用 SMIC 0 18 m 1P4M CMOS 工藝，幅員面積為0 137 9mm2 ，在最壞情

2、況下完成一次 64 位加法運算的時間為 532 26 ps關鍵詞: 并行前綴加法器; 基 4 點操作; 多米諾邏輯; 歐拉路徑算法中圖分類號: TN402文獻標識碼: AFull custom design of high performance 64 bit Parall Prefix adderWANG Ren ping，HE Ming hua，WEI Rong shan，CHEN Chuan dong，DAI Hui ming( College of Physics and Information Engineering，Fuzhou University，Fuzhou，Fujian 3

3、50108，China) Abstract: A parall prefix adder based on 64 bit radix 4 Kogge Stone tree algorithm principle is proposed in this paper The architecture is optimized using domino dynamic logic，clock delayed domi- no and transmission pipes logic，which reduces the gate delay of each stage in the adder dra

4、matically In order to achieve small layout area and good performance，heuristic Euler algorithm is adopted to de- termine the block carry generation signals circuit structure，multi output domino logic is adopted to optimize the block carry propagate signals，and six transmission pipes logic is used to

5、 build a half ad-Using SMIC 0 18 m 1P4M CMOS process for layout design，the adders area is 0 137 9mm2 derIn the worst case，the computation time is 532 26 psKeywords: parall prefix adder; radix 4 dot operation; dynamic logic; Euler algorithm; stick figure并行前綴加法器( PPA) 是超前進位加法器的變種，由于具有速度和面積兩方面的優(yōu)勢，被廣泛應用

6、于高性能微處理器設計中 在 64 位并行前綴加法器算法中，為進一步減少加法器的運算時間，人們提出 多種變體算法1 3，其中基 4 的 Kogge Stone 樹算法因其卓越的性能而成為目前 64 位及以上快速運算加 法器最常用的實現結構之一 如今，運算速度超過 GHz 的 64 位微處理器已成為主流產品，對加法器的運 算速度要求也越來越高，因此，采用動態(tài)邏輯門設計高性能的并行前綴加法器變得更加廣泛4 6本研究設計的高性能 64 位并行前綴加法器應用于 64 位微處理器，在基 4 的 Kogge Stone 樹算法基礎上，采用多米諾動態(tài)邏輯、時鐘延遲多米諾和傳輸管邏輯等技術來優(yōu)化加法器結構，采用

7、啟發(fā)式歐拉路 徑算法、邏輯圖、棍棒圖、多輸出多米諾邏輯、6 管傳輸管 XOR 邏輯等方法來減少幅員面積，提高性能采用 SMIC 0 18 m 1P4M CMOS 工藝進行設計，整個加法器的幅員面積為 0 137 9mm2 ，仿真時在最壞情況下完成一次 64 位加法運算時間為 532 26ps1 加法器算法分析和電路結構1 1 64 位基 4 的 Kogge Stone 樹算法并行前綴運算根本思想: 先計算每位的進位產生信號 Gi 和進位傳播信號 Pi ，再通過前綴運算單元計收稿日期: 2021 04 01通訊作者: 王仁平( 1972 ) ，高級講師，E mail: rpwang fzu ed

8、u cn基金工程: 福建省科技重大專項基金資助工程( 2021HZ010002) ; 福建省教育廳科研資助工程( JA09001) ; 福建省自然 科學基金資助工程( 2021J05143)863第 6 期王仁平，等: 高性能 64 位并行前綴加法器全定制設計算塊進位產生信號 Gi: j 和塊進位傳播信號 Pi: j ，并將所有的前綴運算單元按照一定規(guī)律組織成遞歸的進位樹，這樣每一位的進位信號就可通過進位樹的傳遞作用在運算結點中一步一步地計算出來 64 位并行前綴加法器基于基 4 的 Kogge Stone 樹算法如圖 1 所示7，圖中用“表示用兩個加數 A 、B 來建立相應i i進位產生信號

9、 Gi 和進位傳播信號 Pi，“表示基 4 的 Kogge Stone 樹算法中的點操作來計算塊進位產生信號 Gi: j 和塊進位傳播信號 Pi: ，j “表示用兩個加數 Ai 、Bi 和前一位進位 Co，i 1 來計算該位的和 Si 這種算法計算塊進位函數的最長時間是 O( logN ) 級門延遲，其中 N 是加法器位數，如計算其最高位的塊進位4函數 G63: 0 和 P63: 0 時間為 3 級門的延遲圖 1 64 位基 4 的 Kogge Stone 樹算法Fig 1 Arithmetic of 64 bit radix 4 Kogge Stone tree計算最高位的塊進位產生函數 G

10、63: 0 和塊進位傳播函數 P63: 0 ，具體過程如下:第一級點操作輸入在每相鄰 4 位進行，如計算 G3: 0 和 P3: 0 的點操作如式( 1) 所示:( G3: 0 ，P3: 0 )= ( G3 ，P3 ) ( G2 ，P2 ) ( G1 ，P1 ) ( G0 ，P0 )( 1)第二級點操作輸入在第一級輸出根底上每隔 4 位進行，如計算 G15: 0 和 P15: 0 的點操作如式( 2) 所示:( G15: 0 ，P15: 0 ) = ( G15: 12 ，P15: 12 ) ( G11: 8 ，P11: 8 ) ( G7: 4 ，P7: 4 ) ( G3: 0 ，P3: 0 )

11、第三級點操作輸入在第二級輸出根底上每隔 16 位 進行，如計算 G63: 0 和 P63: 0 的點操作如式( 3) 所示:( G63: 0 ，P63: 0 ) = ( G63: 48 ，P63: 48 ) ( G47: 32 ，P47: 32 )( 2)( G31: 16 ，P31: 16 ) ( G15: 0 ，P15: 0 )( 3)當算出相應位的塊進位產生函數 Gi: 0 和塊進位傳播函數 Pi: 0 ，計算該位的進位輸出如式( 4) 所示 假設最低位進位Ci，0 為 0，那么該位的進位輸出 Co，i = Gi: 0 ，( Co，i ，0) = ( Gi: 0 ，Pi: 0 ) ( C

12、i，0 ，0) = ( Gi: 0 + Pi: 0 Ci，0 ，0)( 4)1 264 位基 4 的 Kogge Stone 樹加法器結構為縮短加法器運算時間和減少幅員面積，設計了改良的 64 位基 4 的 Kogge Stone 樹加法器結構 如圖 2 所示，進位產生信號 Gi 、進位傳播信號 Pi 和進位輸出信號 Co，i 采用 動態(tài)邏輯實現、塊進位產生信號 Gi: j 和塊進位傳播信號 Pi: j 采用多米諾動態(tài)邏輯實現; 為減少多米諾動態(tài)邏輯的時鐘 負載并提高低拉驅動能力，取消了下拉網絡預充電，但由 于預充電是“行波推進，為防止存在短路電流，采用時鐘 延遲多米諾技術為各級多米諾動態(tài)邏輯

13、提供時鐘信號; 半圖 2 改良的 64 位基 4 的 Kogge Stone樹加法器結構Fig 2 Modified adder structure of 64 bit radix 4Kogge Stone tree864福州大學學報( 自然科學版)第 39 卷加器采用面積小且運算速度快的 6 管傳輸管邏輯實現主要模塊設計和優(yōu)化基 4 的 Kogge Stone 樹算法 64 位并行前綴加法器模塊包括: 進位產生信號和進位傳播信號電路、塊 進位產生信號和塊進位傳播信號電路、時鐘延時多米諾、計算進位電路和求和電路 進位產生信號、進位 傳播信號和計算進位的動態(tài)邏輯電路設計相對簡單，因此，重點對塊進

14、位產生信號電路設計、塊進位傳播 信號電路設計、求和電路設計和時鐘延時多米諾技術等進行研究22 1塊進位產生信號和塊進位傳播信號電路設計用基 4 點操作計算塊進位產生函數 Gi: 0 和塊進位傳播函數 Pi: 0 ，由于各基 4 點操作的電路結構一致，以實現塊進位產生信號 G3: 0 和塊進位傳播信號 P3: 0 來進行研究2 1 1塊進位產生信號電路設計復合邏輯門幅員要實現面積小且性能好的條件是物理連接的晶體管能通過擴散區(qū)進行重疊，使復合邏輯門可用連續(xù)的擴散區(qū)來實現 ( 即一個器件的漏區(qū)也是下一個器件的源區(qū)) ，這樣即可以減少幅員面 積，又無需導線和過孔進行連接，減少寄生參數 為到達復合邏輯門

15、的幅員能用連續(xù)擴散區(qū)實現，采用邏 輯圖基于歐拉路徑算法得到復合邏輯門輸入端的排列順序，然后用棍棒圖8( 不標尺寸器件、只注重器件 相對位置和連接關系的象征性符號) 研究幅員繪制策略，得到幅員的拓撲結構根據點操作算法，G3: 0 輸出表達式可寫成式( 5) 所示:G3: 0= G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 = P3 ( P2 ( P1 G0 + G1 ) + G2 ) + G3( 5)G3: 0 對應組合邏輯電路如圖 3 所示的實線局部，為 6 級兩輸入與或結構 對這種結構電路，可用基于啟發(fā)式的歐拉路徑算法來進行幅員設計 啟發(fā)式歐拉路徑算法的理論 根底是

16、: 對于多級與或結構的組合邏輯，如果每一個與 / 或 門的輸入端數目為奇數，那么在相應的邏輯圖中，下拉網絡 PDN 和上拉網絡 PUN 存在一致的歐拉路徑 為滿足啟發(fā)式 歐拉路徑算法輸入端數目為奇數要求，在每個與 / 或門參加 一個用虛線表示的“假想輸入，這些“假想輸入統(tǒng)一放在 圖的上方運用歐拉路徑算法設計塊進位產生信號 G3: 0 復合門版 圖步驟是先 繪 制 邏 輯 圖，邏輯圖是用圓點代表電路節(jié)點，圖 3 塊進位產生信號 G3: 0 邏輯電路Fig 3 Logic circuit of block carry generation signal G3: 0邊是用控制晶體管的柵信號命名，再根

17、據啟發(fā)式歐拉路徑算法的理論根底，研究得到下拉網絡 PDN 的邏輯圖如圖 4 所示圖 4 塊進位產生信號 G3: 0 邏輯圖Fig 4 Logic diagram of block carry generation signal G3: 0圖 5 塊進位產生信號 G3: 0 電路原理圖Fig 5 Circuit schematic of block carry generation signal G3: 0865第 6 期王仁平，等: 高性能 64 位并行前綴加法器全定制設計歐拉路徑是通過邏輯圖中所有節(jié)點并且只經過每條邊一次的一條路徑，在歐拉路徑中邊的順序等于在復合門幅員中輸入端的順序 本設計選

18、擇歐拉路徑為 G3 P3 G2 P2 G1 P1 G0 X0 X1 X2 X3 X4 X5 ，X0 X1 X2 X3 X4 X5 是 假想輸入，在幅員設計中不存在 根據所選擇的歐拉路徑，對應多米諾動態(tài)邏輯電路圖如圖 5 所示在設計塊進位產生信號 G3: 0 復合門幅員時，先用棍棒圖 來研究幅員繪制策略，得到電路幅員的拓撲結構 選擇歐拉 路徑為 G3 P3 G2 P2 G1 P1 G0 ，在歐拉路徑中邊的順序等于在復合 門幅員中輸入端的順序，得到的棍棒圖如圖 6 所示，物理連 接的晶體管能通過擴散區(qū)進行重疊連接，這樣即減少幅員面 積，又無需導線和過孔進行連接，減少寄生參數2 1 2 塊進位傳播信

19、號電路設計為減 少幅員面積和提 高 性 能，對 塊 傳 播 信 號 P3: 0圖 6 塊進位產生信號 G3: 0 棍棒圖Fig 6 Stick figure of block carry generation signal G3: 0=P3 P2 P1 P0 電路，利用多輸出多米諾邏輯 ( 動態(tài)邏輯門在一個門中可產生不同邏輯功能) 特點，在圖 5 根底上共享 P3 P1 這 種方法對預充電器件數目沒有減少，但 P3 P1 為兩個輸出所共 享，減少求值晶體管數目，也減少前一級的扇出數，最終基 4 點操作的動態(tài)邏輯電路實現如圖 7 所示2 1 3基 4 點操作動態(tài)電路的優(yōu)化基 4 點操作動態(tài)電路有

20、多個輸入端，為降低大扇入電路的延時，提高性能，根據 Elmore 延時模型可知，最靠近輸出 的 P3 管電阻在延時公式中出現的次數最多，應當使 P3 管的 電阻最小 ( 即 寬 長 比 最 大) 依 次 類 推 因 此，對 下 拉 網 絡 PDN，從輸出往下采用逐級加大晶體管尺寸，即 P2 P1 = G0 P3 ，能到達降低起主要作用的電阻，同時使器件電容的增 加保持在一定的范圍內 通過仿真分析可知，逐級加大晶體 管尺寸與各個管子相同尺寸相比傳播延時減少約 10% 圖 7 基 4 點操作的動態(tài)實現Fig 7 Dynamic implementation of radix 4 dot opera

21、tion由 64 位基 4 的 Kogge Stone 樹算法可知，輸出的 G3: 0 和 P3: 0 要去驅動較大負載，如果由大扇入再直接去驅動大負載，那么該電路的延時很長，性能差 可采用下面方法進行優(yōu)化: 引入靜態(tài)反相器，在預充電期間 n 型動態(tài)門輸出充電至 VDD，通過反相器輸出為 0，而反相器輸出又是下一級動態(tài)多米諾門輸入，因 此可取消下拉網絡預充電管，減少時鐘負載并提高低拉的驅動能力; 同時引入的靜態(tài)反相器隔離了由大 扇入直接驅動大負載，提高了速度; 另外該反相器還可用來驅動一個漏泄器件以抵抗漏電和電荷分享，解 決了動態(tài)電路中信號完整性問題9 由于第一級與第二級的塊信號輸出要驅動較大

22、負載，在估算出負載 電容根底上，采用 3 個具有相同門努力的反相器組成反相器鏈來實現傳播延時最小對一個較大尺寸的晶體管意味著有較長柵線，較長柵 線有較高電阻，從而降低器件的性能 本設計對一個較大 尺寸的晶體管采用許多小的晶體管并聯來構成，采用低電 阻的金屬線旁路連接較短的柵線可降低電阻，提高器件性圖 8 基 4 點操作的幅員Fig 8 Layout of radix 4 dot operation能，同時各個模塊的幅員做到相同高度，便于集成和連接，最后得到基 4 點操作的幅員如圖 8 所示2 2 求和電路設計異或門 XOR 是加法運算的根本單元，基于如圖 9( a) 所示 CMOS 互補邏輯的

23、 10 管 XOR 在面積和功耗上都不經濟，而基于如圖 9( b) 所示 10 管傳輸門 XOR 邏輯，節(jié)省了面積和功耗，但是互補控制信號增 加了電路的復雜度 由 WangJyh Ming 提出了 6 管傳輸管 XOR 邏輯如圖 9 ( c) 所示10，結構簡單，面積 小，性能好，運算速度比 10 管 CMOS 互補邏輯快 27 9% ，比 10 管傳輸門邏輯快 20% ，且無需互補信號由于使用傳輸管邏輯，高電平輸出時可能存在閥值壓降導致反相器輸出存在靜態(tài)功耗 通過綜合考慮面866福州大學學報( 自然科學版)第 39 卷積和性能，半加器選擇基于 6 管傳輸管 XOR 邏輯( a) 10 管 C

24、MOS XOR( b) 10 管傳輸門 XOR ( c) 6 管傳輸管 XOR圖 9 異或門實現比擬Fig 9 Implementation Comparison of XOR gate2 3時鐘延時多米諾和 H 樹分布時鐘延時匹配是采用時鐘延時多米諾技術，它的每一級時鐘由前一級時鐘和后一級時鐘推導來進行確定，具體的時鐘延時要求如下: 只有在當前這一級預充電穩(wěn)定輸出為0 后才能對下一級開始進行預充電; 在當前這一級求值邊 沿時，下一級必須充電結束，這樣才能取消下拉網絡預充 電管和防止存在短路電流 由于每一級時鐘信號都有較大 的驅動負載，如計算第一級塊進位產生信號和塊進位傳播 信號的時鐘信號 C

25、LK1 就連接有 126 個 PMOS 管，因此采用 反相器延時加上時鐘路徑上的傳輸門以及 H 樹結構時鐘分 布技術來設計時鐘延時驅動，具體電路如圖 10 所示，形成16 個子葉節(jié)點，每個子葉節(jié)點再去驅動 8 個 PMOS 管，傳 輸門總是導通，而時鐘路徑的延時那么可能通過這些器件的 尺寸來進行調整圖 10 時鐘延時多米諾邏輯和 H 樹分布Fig 10 Clock delay domino logic and H tree distribution3仿真結果分析和比擬加法器幅員設計完成后，用 Assura 工具先對它進行物理驗證，包括設計規(guī)那么檢查( DRC) 、電氣規(guī)那么檢查( ERC) 和

26、幅員與原理圖一致性檢查( LVS) ，物理驗證通過后，再用 Assura 工具提取幅員的寄生參數并采用 ss 的 Spectre 模型基于最長進位傳播路徑條件下進行后仿真 根據塊進位函數動態(tài)實現電路特點， 可知當輸入 A 為全“0，B 為全“1，最低位進位 Ci，0 為“1時，將使進位傳播路徑最長，即在該條件下可 以得出整個加法器關鍵路徑的延時，后仿真得 CLK0、P0 、P3: 0 、P15: 0 、P63: 0 、Co，63 和 S63 波形如圖 11 所示 在最壞條件下測得關鍵路徑( 從 CLK0 到第 63 位和輸出 S63 ) 的延時為 532 26 ps，從中可知本文設計的 64

27、位整數加法器部件可運行在 1 8 GHz 的工作頻率在設計基 4 的 Kogge Stone 樹算法 64 位并行前綴加法器同時，也用相同工藝的靜態(tài) CMOS 技術來設 計相同結構的加法器，對每個階段的關鍵路徑延時比擬結果如表 1 所示，從中可知采用多米諾動態(tài)邏輯、時鐘延遲多米諾和傳輸管邏輯等技術實現的電路性能有非常大改善表 1 多米諾動態(tài)邏輯和靜態(tài) CMOS 關鍵路徑延時比擬Tab 1 Comparison domino dynamic logic with static CMOS on the critical path delay時鐘延遲多米諾加法器靜態(tài) CMOS 加法器t延時 / ps

28、t延時 / ps邏輯邏輯Pi / GiP4 / G4P16 / G16P64 / G64 進位( Co，i ) 求和( Si )Pi / GiP4 / G4P16 / G16P64 / G64 進位( Co，i ) 求和( Si )531171441355231112283354378135180867第 6 期王仁平，等: 高性能 64 位并行前綴加法器全定制設計圖 11 最壞情況下關鍵路徑波形仿真結果Fig 11 Wave simulation results on critical path in worst case4結論設計高性能加法器部件需要在實現算法、電路結構、采用技術、器件參數

29、、幅員設計等各個方面進行優(yōu)化和改良 本文實現算法和電路結構采用改良的 64 位基 4 的 Kogge Stone 樹加法器結構，采用技術有多米諾動態(tài)邏輯、多輸出多米諾邏輯、6 管傳輸管實現 XOR 邏輯、時鐘延遲多米諾邏輯和 H 樹分布等， 器件參數優(yōu)化主要對基 4 點操作動態(tài)電路進行，幅員設計采用啟發(fā)式毆拉路徑算法、邏輯圖、棍棒圖對基4 點操作動態(tài)電路進行 最終設計的 64 位加法器面積為 0 137 9 mm2 ，在最壞情況下完成一次加法運算時 間為 532 26 ps 本設計廣泛采用動態(tài)電路實現，在速度和面積方面有很大的優(yōu)勢，但功耗相對較大以及 動態(tài)結點易受到來自各方面噪聲影響，因此還需要進一步研究動態(tài)電路工作在相對較低功耗且可靠性相 對較高的設計技術參考文獻:1 Dozza D，Gaddoni M，Baccarani G A 3 5ns，64 bit carry lookahead adder C/ / Proceedings of IEEE International Symposi-um on Circuit and Systems 1996: 297 3002 Matthew S，Krishnamurthy R，Anders M，et al Sub 500ps 64 b ALUs in 0 18 mm SO