高性能64位并行前缀加法器全定制设计_王仁平

第39卷第6期

201112福州大学学报（自然科学版）Journal of Fuzhou University （Natural Science Edition ）Vol．39No．6Dec．2011DOI ：CNKI ：35－1117/N．20111220．1002．027文章编号：1000－2243（2011）06－0862－06

高性能64位并行前缀加法器全定制设计

王仁平，何明华，魏榕山，陈传东，戴惠明

（福州大学物理与信息工程学院，福建福州350108）

摘要：基于64位基4的Kogge －Stone 树算法原理，采用多米诺动态逻辑、时钟延迟多米诺和传输管逻辑等技

术来设计和优化并行前缀加法器的结构，达到减少了加法器各级门的延迟时间目的．为实现版图面积小、性能

好，采用启发式欧拉路径算法来确定块进位产生信号电路结构，采用多输出多米诺逻辑来优化块进位传播信

号，采用6管传输管逻辑的半加器．该加法器全定制设计采用SMIC 0．18μm 1P4M CMOS 工艺，版图面积为

0．1379mm 2，在最坏情况下完成一次64位加法运算的时间为532．26ps．

关键词：并行前缀加法器；基4点操作；多米诺逻辑；欧拉路径算法

中图分类号：TN402文献标识码：A

Full －custom design of high －performance 64－bit Parall －Prefix adder

WANG Ren －ping ，HE Ming －hua ，WEI Rong －shan ，CHEN Chuan －dong ，DAI Hui －ming

（College of Physics and Information Engineering ，Fuzhou University ，Fuzhou ，Fujian 350108，China ）

Abstract ：A parall －prefix adder based on 64－bit radix －4Kogge －Stone tree algorithm principle is

clock delayed domi-proposed in this paper．The architecture is optimized using domino dynamic logic ，

no and transmission pipes logic ，which reduces the gate delay of each stage in the adder dramatically．

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

and six transmission pipes logic is used to build a half －ad-optimize the block carry propagate signals ，

der．Using SMIC 0．18μm 1P4M CMOS process for layout design ，the adder ’s area is 0．1379mm 2．

In the worst case ，the computation time is 532．26ps．

Keywords ：parall －prefix adder ；radix －4dot operation ；dynamic logic ；Euler algorithm ；stick figure

并行前缀加法器（PPA ）是超前进位加法器的变种，由于具有速度和面积两方面的优势，被广泛应用于高性能微处理器设计中．在64位并行前缀加法器算法中，为进一步减少加法器的运算时间，人们提出多种变体算法，其中基4的Kogge －Stone 树算法因其卓越的性能而成为目前64位及以上快速运算加法器最常用的实现结构之一．如今，运算速度超过GHz 的64位微处理器已成为主流产品，对加法器的运

［4－6］．算速度要求也越来越高，因此，采用动态逻辑门设计高性能的并行前缀加法器变得更加广泛［1－3］

本研究设计的高性能64位并行前缀加法器应用于64位微处理器，在基4的Kogge －Stone 树算法基础上，采用多米诺动态逻辑、时钟延迟多米诺和传输管逻辑等技术来优化加法器结构，采用启发式欧拉路

6管传输管XOR 逻辑等方法来减少版图面积，提高性能．径算法、逻辑图、棍棒图、多输出多米诺逻辑、

2采用SMIC 0．18μm 1P4M CMOS 工艺进行设计，整个加法器的版图面积为0．1379mm ，仿真时在最坏情

况下完成一次64位加法运算时间为532．26ps．

1

1．1加法器算法分析和电路结构64位基4的Kogge －Stone 树算法

并行前缀运算基本思想：先计算每位的进位产生信号G i 和进位传播信号P i ，再通过前缀运算单元计收稿日期：2011－04－01

通讯作者：王仁平（1972－），高级讲师，E －mail ：rpwang@fzu．edu．cn

基金项目：福建省科技重大专项基金资助项目（2009HZ010002）；福建省教育厅科研资助项目（JA09001）；福建省自然

科学基金资助项目（2009J05143）

算块进位产生信号G i ：j 和块进位传播信号P i ：j ，并将所有的前缀运算单元按照一定规律组织成递归的进位树，这样每一位的进位信号就可通过进位树的传递作用在运算结点中一步一步地计算出来．64位并行前

［7］“□”缀加法器基于基4的Kogge －Stone 树算法如图1所示，图中用表示用两个加数A i 、B i 来建立相应

表示基4的Kogge －Stone 树算法中的点操作来计算块进位产生进位产生信号G i 和进位传播信号P i ，“○”

信号G i ：j 和块进位传播信号P i ：，◇”表示用两个加数A i 、B i 和前一位进位C o ，i －1来计算该位的和S i ．这j “

N 种算法计算块进位函数的最长时间是O （log 4）级门延迟，其中N 是加法器位数，如计算其最高位的块进位

函数G 63：0和P 63：0时间为3级门的延迟

．

图1

Fig．164位基4的Kogge －Stone 树算法Arithmetic of 64－bit radix －4Kogge －Stone tree

计算最高位的块进位产生函数G 63：0和块进位传播函数P 63：0，具体过程如下：

第一级点操作输入在每相邻4位进行，如计算G 3：0和P 3：0的点操作如式（1）所示：

（G 3：0，P 3：0）=（G 3，P 3）·（G 2，P 2）·（G 1，P 1）·（G 0，P 0）（1）

第二级点操作输入在第一级输出基础上每隔4位进行，如计算G 15：0和P 15：0的点操作如式（2）所示：

（G 15：0，P 15：0）=（G 15：12，P 15：12）·（G 11：8，P 11：8）·（G 7：4，P 7：4）·（G 3：0，P 3：0）（2

）

第三级点操作输入在第二级输出基础上每隔16位进

行，如计算G 63：0和P 63：0的点操作如式（3）所示：

（G 63：0，P 63：0）=（G 63：48，P 63：48）·（G 47：32，P 47：32）

·（G 31：16，P 31：16）（G 15：0，P 15：0）（3）

当算出相应位的块进位产生函数G i ：0和块进位传播函

数P i ：0，计算该位的进位输出如式（4）所示．若最低位进位

C i ，0为0，则该位的进位输出C o ，i =G i ：0，

（C o ，i ，0）=（G i ：0，P i ：0）·（C i ，0，0）=（G i ：

1．20+P i ：0C i ，0，0）（4）64位基4的Kogge －Stone 树加法器结构

为缩短加法器运算时间和减少版图面积，设计了改进

的64位基4的Kogge －Stone 树加法器结构如图2所示，进

位产生信号G i 、进位传播信号P i 和进位输出信号C o ，i 采用

动态逻辑实现、块进位产生信号G i ：j 和块进位传播信号P i ：j

采用多米诺动态逻辑实现；为减少多米诺动态逻辑的时钟图2改进的64位基4的Kogge －Stone 负载并提高下拉驱动能力，取消了下拉网络预充电，但由树加法器结构

于预充电是“行波”推进，为避免存在短路电流，采用时钟Fig．2Modified adder structure of 64－bit radix －4延迟多米诺技术为各级多米诺动态逻辑提供时钟信号；半Kogge －Stone tree

加器采用面积小且运算速度快的6管传输管逻辑实现．

2主要模块设计和优化

基4的Kogge －Stone 树算法64位并行前缀加法器模块包括：进位产生信号和进位传播信号电路、块进位产生信号和块进位传播信号电路、时钟延时多米诺、计算进位电路和求和电路．进位产生信号、进位传播信号和计算进位的动态逻辑电路设计相对简单，因此，重点对块进位产生信号电路设计、块进位传播信号电路设计、求和电路设计和时钟延时多米诺技术等进行研究．

2．1块进位产生信号和块进位传播信号电路设计

用基4点操作计算块进位产生函数G i ：0和块进位传播函数P i ：0，由于各基4点操作的电路结构一致，以实现块进位产生信号G 3：0和块进位传播信号P 3：0来进行研究．

2．1．1块进位产生信号电路设计

复合逻辑门版图要实现面积小且性能好的条件是物理连接的晶体管能通过扩散区进行重叠，使复合逻辑门可用连续的扩散区来实现（即一个器件的漏区也是下一个器件的源区），这样即可以减少版图面积，又无需导线和过孔进行连接，减少寄生参数．为达到复合逻辑门的版图能用连续扩散区实现，采用逻

［8］辑图基于欧拉路径算法得到复合逻辑门输入端的排列顺序，然后用棍棒图（不标尺寸器件、只注重器件

相对位置和连接关系的象征性符号）研究版图绘制策略，得到版图的拓扑结构．

根据点操作算法，G 3：0输出表达式可写成式（5）所示：

G 3：0=G 3+P 3G 2+P 3P 2G 1+P 3P 2P 1G 0=P 3（P 2（P 1G 0+G 1）+G 2）+G 3（5

）

G 3：0对应组合逻辑电路如图3所示的实线部分，为6级

两输入与或结构．对这种结构电路，可用基于启发式的欧

拉路径算法来进行版图设计．启发式欧拉路径算法的理论

基础是：对于多级与或结构的组合逻辑，如果每一个与/或

门的输入端数目为奇数，则在相应的逻辑图中，下拉网络

PDN 和上拉网络PUN 存在一致的欧拉路径．为满足启发式

欧拉路径算法输入端数目为奇数要求，在每个与/或门加入

“假想”一个用虚线表示的输入，这些“假想”输入统一放在

图的上方．

运用欧拉路径算法设计块进位产生信号G 3：0复合门版

图步骤是先绘制逻辑图，逻辑图是用圆点代表电路节点，图3Fig．3块进位产生信号G 3：0逻辑电路Logic circuit of block carry generation signal G 3：0

边是用控制晶体管的栅信号命名，再根据启发式欧拉路径算法的理论基础，研究得到下拉网络PDN 的逻辑图如图4所示

．

图4

Fig．4块进位产生信号G 3：0逻辑图

0图5Fig．5块进位产生信号G 3：0电路原理图

0Logic diagram of block carry generation signal G 3：Circuit schematic of block carry generation signal G 3：

欧拉路径是通过逻辑图中所有节点并且只经过每条边一次的一条路径，在欧拉路径中边的顺序等于在复合门版图中输入端的顺序．本设计选择欧拉路径为G 3P 3G 2P 2G 1P 1G 0X 0X 1X 2X 3X 4X 5，X 0X 1X 2X 3X 4X 5是假想输入，在版图设计中不存在．根据所选择的欧拉路径，对应多米诺动态逻辑电路图如图5所示

．

在设计块进位产生信号G 3：0复合门版图时，先用棍棒图

来研究版图绘制策略，得到电路版图的拓扑结构．选择欧拉

路径为G 3P 3G 2P 2G 1P 1G 0，在欧拉路径中边的顺序等于在复合

门版图中输入端的顺序，得到的棍棒图如图6所示，物理连

接的晶体管能通过扩散区进行重叠连接，这样即减少版图面

积，又无需导线和过孔进行连接，减少寄生参数．

2．1．2块进位传播信号电路设计

为减少版图面积和提高性能，对块传播信号P 3：0图6块进位产生信号G 3：0棍棒图Stick figure of block carry generation

signal G 3：0=Fig．6P 3P 2P 1P 0电路，利用多输出多米诺逻辑（动态逻辑门在一个

门中可产生不同逻辑功能）特点，在图5基础上共享P 3P 1．

这

种方法对预充电器件数目没有减少，但P 3P 1为两个输出所共

享，减少求值晶体管数目，也减少前一级的扇出数，最终基4

点操作的动态逻辑电路实现如图7所示．

2．1．3基4点操作动态电路的优化

基4点操作动态电路有多个输入端，为降低大扇入电路

的延时，提高性能，根据Elmore 延时模型可知，最靠近输出

的P 3管电阻在延时公式中出现的次数最多，应当使P 3管的

电阻最小（即宽长比最大）．依次类推．因此，对下拉网络

PDN ，从输出往下采用逐级加大晶体管尺寸，即P 2＜P 1=G 0

＜P 3，能达到降低起主要作用的电阻，同时使器件电容的增

加保持在一定的范围内．通过仿真分析可知，逐级加大晶体

管尺寸与各个管子相同尺寸相比传播延时减少约10%．Fig．7图7基4点操作的动态实现Dynamic implementation of radix －4dot

operation

由64位基4的Kogge －Stone 树算法可知，输出的G 3：0和P 3：0要去驱动较大负载，如果由大扇入再直接去驱动大负载，则该电路的延时很长，性能差．可采用下面方法进行优化：引入静态反相器，在预充电期间n 型动态门输出充电至VDD ，通过反相器输出为0，而反相器输出又是下一级动态多米诺门输入，因此可取消下拉网络预充电管，减少时钟负载并提高下拉的驱动能力；同时引入的静态反相器隔离了由大扇入直接驱动大负载，提高了速度；另外该反相器还可用来驱动一个漏泄器件以抵抗漏电和电荷分享，解

［9］决了动态电路中信号完整性问题．由于第一级与第二级的块信号输出要驱动较大负载，在估算出负载

电容基础上，采用3个具有相同门努力的反相器组成反相器链来实现传播延时最小

．

对一个较大尺寸的晶体管意味着有较长栅线，较长栅

线有较高电阻，从而降低器件的性能．本设计对一个较大

尺寸的晶体管采用许多小的晶体管并联来构成，采用低电

阻的金属线旁路连接较短的栅线可降低电阻，提高器件性

能，同时各个模块的版图做到相同高度，便于集成和连接，

最后得到基4点操作的版图如图8所示．

2．2Fig．8图8基4点操作的版图Layout of radix －4dot operation 求和电路设计

异或门XOR 是加法运算的基本单元，基于如图9（a ）所示CMOS 互补逻辑的10管XOR 在面积和功耗上都不经济，而基于如图9（b ）所示10管传输门XOR 逻辑，节省了面积和功耗，但是互补控制信号增

［10］加了电路的复杂度．由WangJyh －Ming 提出了6管传输管XOR 逻辑如图9（c ）所示，结构简单，面积

小，性能好，运算速度比10管CMOS 互补逻辑快27．9%，比10管传输门逻辑快20%，且无需互补信号．由于使用传输管逻辑，高电平输出时可能存在阀值压降导致反相器输出存在静态功耗．通过综合考虑面

积和性能，半加器选择基于6管传输管XOR 逻辑

．

（a ）10管CMOS XOR （b ）10管传输门XOR （c ）6管传输管XOR

图9

Fig．9异或门实现比较Implementation Comparison of XOR gate

2．3时钟延时多米诺和H

树分布

时钟延时匹配是采用时钟延时多米诺技术，它的每一

级时钟由前一级时钟和后一级时钟推导来进行确定，具体

的时钟延时要求如下：只有在当前这一级预充电稳定输出为

0后才能对下一级开始进行预充电；在当前这一级求值边

沿时，下一级必须充电结束，这样才能取消下拉网络预充

电管和避免存在短路电流．由于每一级时钟信号都有较大

的驱动负载，如计算第一级块进位产生信号和块进位传播

信号的时钟信号CLK1就连接有126个PMOS 管，因此采用

反相器延时加上时钟路径上的传输门以及H 树结构时钟分

布技术来设计时钟延时驱动，具体电路如图10所示，形成

16个子叶节点，每个子叶节点再去驱动8个PMOS 管，传

输门总是导通，而时钟路径的延时则可能通过这些器件的

尺寸来进行调整．图10时钟延时多米诺逻辑和H 树分布Fig．10Clock －delay domino logic and H －tree distribution

3仿真结果分析和比较

加法器版图设计完成后，用Assura 工具先对它进行物理验证，包括设计规则检查（DRC ）、电气规则检查（ERC ）和版图与原理图一致性检查（LVS ），物理验证通过后，再用Assura 工具提取版图的寄生参数并采用ss 的Spectre 模型基于最长进位传播路径条件下进行后仿真．根据块进位函数动态实现电路特点，

“0”，B 为全“1”，最低位进位C i ，0为“1”可知当输入A 为全时，将使进位传播路径最长，即在该条件下可

以得出整个加法器关键路径的延时，后仿真得CLK0、P 0、P 3：0、P 15：0、P 63：0、C o ，63和S 63波形如图11所示．在最坏条件下测得关键路径（从CLK0到第63位和输出S 63）的延时为532．26ps ，从中可知本文设计的64位整数加法器部件可运行在1．8GHz 的工作频率．

在设计基4的Kogge －Stone 树算法64位并行前缀加法器同时，也用相同工艺的静态CMOS 技术来设计相同结构的加法器，对每个阶段的关键路径延时比较结果如表1所示，从中可知采用多米诺动态逻辑、时钟延迟多米诺和传输管逻辑等技术实现的电路性能有非常大改善．

Tab．1表1多米诺动态逻辑和静态CMOS 关键路径延时比较Comparison domino dynamic logic with static CMOS on the critical path delay

静态CMOS 加法器

逻辑

P i /Gi

P 4/G4

P 16/G16

P 64/G64

进位（C o ，i ）

求和（S i ）t 延时/ps[***********]时钟延迟多米诺加法器t 延时/ps逻辑P i /Gi P 4/G4P 16/G16P 64/G64进位（C o ，i ）

求和（S i ）[**************]

图11

Fig．11最坏情况下关键路径波形仿真结果Wave simulation results on critical path in worst －case

4结论

设计高性能加法器部件需要在实现算法、电路结构、采用技术、器件参数、版图设计等各个方面进行优化和改进．本文实现算法和电路结构采用改进的64位基4的Kogge －Stone 树加法器结构，采用技术有多米诺动态逻辑、多输出多米诺逻辑、6管传输管实现XOR 逻辑、时钟延迟多米诺逻辑和H 树分布等，器件参数优化主要对基4点操作动态电路进行，版图设计采用启发式殴拉路径算法、逻辑图、棍棒图对基4点操作动态电路进行．最终设计的64位加法器面积为0．1379mm 2，在最坏情况下完成一次加法运算时间为532．26ps．本设计广泛采用动态电路实现，在速度和面积方面有很大的优势，但功耗相对较大以及动态结点易受到来自各方面噪声影响，因此还需要进一步研究动态电路工作在相对较低功耗且可靠性相对较高的设计技术．

参考文献：

［1］Dozza D ，Gaddoni M ，Baccarani G．A 3．5ns ，64bit carry －lookahead adder ［C ］//Proceedingsof IEEE International Symposi-

um on Circuit and Systems．1996：297－300．

［2］Matthew S ，Krishnamurthy R ，Anders M ，et al ．Sub －500ps 64－b ALUs in 0．18mm SOI /BulkCMOS ：design and scaling

J ］．IEEE Journal of Solid －State Circuits ，2001，36（11）：1636－1646．trends ［

［3］孙旭光，毛志刚，来逢昌．改进结构的64位CMOS 并行加法器设计与实现［J ］．半导体学报，2003，24（3）：203－208．［4］Mathew S ，Anders M ，Krishnamurthy R ，et al ．A 4GHz 130nm address generation unit with 32b sparse －tree adder core ［J ］．

IEEE Journal of Solid －State Circuits ，2003，38（5）：689－695．

［5］Mathew S K ，Anders M A ，Bloechel B ，et al ．A 4GHz 300mW 64b integer execution ALU with dual supply voltages in 90nm

CMOS ［J ］．IEEE Journal of Solid －State Circuits ，2005，40（1）：162－163．

［6］Jin Zhan －peng ，Shen Xu －bang ，Bai Yong －qiang．A 64－bit fast adder with 0．18μm CMOS technology ［C ］//Proceedings

of IEEE International Symposium on Communications and Information Technologies．Beijing ：［s．n．］，2005：1167－1171．［7］王仁平，J ］．半导体技术，2010，35（11）：1116－1121．何明华，陈传东，等．64位超前进位对数加法器的设计与优化［

［8］Rabeay J M．数字集成电路－电路、系统与设计［M ］．周润德，译．北京：清华大学出版社，2008：171－431．［9］David A Hodges．数字集成电路分析与设计－深亚微米工艺［M ］．将安平，译．北京：清华大学出版社，2005：235－

266．

［10］吴金，应征．高速浮点乘法器设计［J ］．电路与系统学报，2005，10（6）：6－10．

（责任编辑：林晓）