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

1、高性能 64 位并行前缀加法器全定制设计王仁平，何明华，魏榕山，陈传东，戴惠明( 福州大学物理与信息工程学院，福建 福州 350108)摘要: 基于 64 位基 4 的 Kogge Stone 树算法原理，采用多米诺动态逻辑、时钟延迟多米诺和传输管逻辑等技术来设计和优化并行前缀加法器的结构，到达减少了加法器各级门的延迟时间目的 为实现幅员面积小、性能 好，采用启发式欧拉路径算法来确定块进位产生信号电路结构，采用多输出多米诺逻辑来优化块进位传播信号，采用 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) 是超前进位加法器的变种，由于具有速度和面积两方面的优势，被广泛应用

6、于高性能微处理器设计中 在 64 位并行前缀加法器算法中，为进一步减少加法器的运算时间，人们提出 多种变体算法1 3，其中基 4 的 Kogge Stone 树算法因其卓越的性能而成为目前 64 位及以上快速运算加 法器最常用的实现结构之一 如今，运算速度超过 GHz 的 64 位微处理器已成为主流产品，对加法器的运 算速度要求也越来越高，因此，采用动态逻辑门设计高性能的并行前缀加法器变得更加广泛4 6本研究设计的高性能 64 位并行前缀加法器应用于 64 位微处理器，在基 4 的 Kogge Stone 树算法基础上，采用多米诺动态逻辑、时钟延迟多米诺和传输管逻辑等技术来优化加法器结构，采用

7、启发式欧拉路 径算法、逻辑图、棍棒图、多输出多米诺逻辑、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 ，并将所有的前缀运算单元按照一定规律组织成递归的进位树，这样每一位的进位信号就可通过进位树的传递作用在运算结点中一步一步地计算出来 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 采用 动态逻辑实现、块进位产生信号 Gi: j 和块进位传播信号 Pi: j 采用多米诺动态逻辑实现; 为减少多米诺动态逻辑的时钟 负载并提高低拉驱动能力，取消了下拉网络预充电，但由 于预充电是“行波推进，为防止存在短路电流，采用时钟 延迟多米诺技术为各级多米诺动态逻辑

13、提供时钟信号; 半图 2 改良的 64 位基 4 的 Kogge Stone树加法器结构Fig 2 Modified adder structure of 64 bit radix 4Kogge Stone tree864福州大学学报( 自然科学版)第 39 卷加器采用面积小且运算速度快的 6 管传输管逻辑实现主要模块设计和优化基 4 的 Kogge Stone 树算法 64 位并行前缀加法器模块包括: 进位产生信号和进位传播信号电路、块 进位产生信号和块进位传播信号电路、时钟延时多米诺、计算进位电路和求和电路 进位产生信号、进位 传播信号和计算进位的动态逻辑电路设计相对简单，因此，重点对块进

14、位产生信号电路设计、块进位传播 信号电路设计、求和电路设计和时钟延时多米诺技术等进行研究22 1块进位产生信号和块进位传播信号电路设计用基 4 点操作计算块进位产生函数 Gi: 0 和块进位传播函数 Pi: 0 ，由于各基 4 点操作的电路结构一致，以实现块进位产生信号 G3: 0 和块进位传播信号 P3: 0 来进行研究2 1 1块进位产生信号电路设计复合逻辑门幅员要实现面积小且性能好的条件是物理连接的晶体管能通过扩散区进行重叠，使复合逻辑门可用连续的扩散区来实现 ( 即一个器件的漏区也是下一个器件的源区) ，这样即可以减少幅员面 积，又无需导线和过孔进行连接，减少寄生参数 为到达复合逻辑门

15、的幅员能用连续扩散区实现，采用逻 辑图基于欧拉路径算法得到复合逻辑门输入端的排列顺序，然后用棍棒图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 级两输入与或结构 对这种结构电路，可用基于启发式的欧拉路径算法来进行幅员设计 启发式欧拉路径算法的理论 根底是

16、: 对于多级与或结构的组合逻辑，如果每一个与 / 或 门的输入端数目为奇数，那么在相应的逻辑图中，下拉网络 PDN 和上拉网络 PUN 存在一致的欧拉路径 为满足启发式 欧拉路径算法输入端数目为奇数要求，在每个与 / 或门参加 一个用虚线表示的“假想输入，这些“假想输入统一放在 图的上方运用欧拉路径算法设计块进位产生信号 G3: 0 复合门版 图步骤是先 绘 制 逻 辑 图，逻辑图是用圆点代表电路节点，图 3 块进位产生信号 G3: 0 逻辑电路Fig 3 Logic circuit of block carry generation signal G3: 0边是用控制晶体管的栅信号命名，再根

17、据启发式欧拉路径算法的理论根底，研究得到下拉网络 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 位并行前缀加法器全定制设计欧拉路径是通过逻辑图中所有节点并且只经过每条边一次的一条路径，在欧拉路径中边的顺序等于在复合门幅员中输入端的顺序 本设计选

18、择欧拉路径为 G3 P3 G2 P2 G1 P1 G0 X0 X1 X2 X3 X4 X5 ，X0 X1 X2 X3 X4 X5 是 假想输入，在幅员设计中不存在 根据所选择的欧拉路径，对应多米诺动态逻辑电路图如图 5 所示在设计块进位产生信号 G3: 0 复合门幅员时，先用棍棒图 来研究幅员绘制策略，得到电路幅员的拓扑结构 选择欧拉 路径为 G3 P3 G2 P2 G1 P1 G0 ，在欧拉路径中边的顺序等于在复合 门幅员中输入端的顺序，得到的棍棒图如图 6 所示，物理连 接的晶体管能通过扩散区进行重叠连接，这样即减少幅员面 积，又无需导线和过孔进行连接，减少寄生参数2 1 2 块进位传播信

19、号电路设计为减 少幅员面积和提 高 性 能，对 块 传 播 信 号 P3: 0图 6 块进位产生信号 G3: 0 棍棒图Fig 6 Stick figure of block carry generation signal G3: 0=P3 P2 P1 P0 电路，利用多输出多米诺逻辑 ( 动态逻辑门在一个门中可产生不同逻辑功能) 特点，在图 5 根底上共享 P3 P1 这 种方法对预充电器件数目没有减少，但 P3 P1 为两个输出所共 享，减少求值晶体管数目，也减少前一级的扇出数，最终基 4 点操作的动态逻辑电路实现如图 7 所示2 1 3基 4 点操作动态电路的优化基 4 点操作动态电路有

20、多个输入端，为降低大扇入电路的延时，提高性能，根据 Elmore 延时模型可知，最靠近输出 的 P3 管电阻在延时公式中出现的次数最多，应当使 P3 管的 电阻最小 ( 即 宽 长 比 最 大) 依 次 类 推 因 此，对 下 拉 网 络 PDN，从输出往下采用逐级加大晶体管尺寸，即 P2 P1 = G0 P3 ，能到达降低起主要作用的电阻，同时使器件电容的增 加保持在一定的范围内 通过仿真分析可知，逐级加大晶体 管尺寸与各个管子相同尺寸相比传播延时减少约 10% 图 7 基 4 点操作的动态实现Fig 7 Dynamic implementation of radix 4 dot opera

21、tion由 64 位基 4 的 Kogge Stone 树算法可知，输出的 G3: 0 和 P3: 0 要去驱动较大负载，如果由大扇入再直接去驱动大负载，那么该电路的延时很长，性能差 可采用下面方法进行优化: 引入静态反相器，在预充电期间 n 型动态门输出充电至 VDD，通过反相器输出为 0，而反相器输出又是下一级动态多米诺门输入，因 此可取消下拉网络预充电管，减少时钟负载并提高低拉的驱动能力; 同时引入的静态反相器隔离了由大 扇入直接驱动大负载，提高了速度; 另外该反相器还可用来驱动一个漏泄器件以抵抗漏电和电荷分享，解 决了动态电路中信号完整性问题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 逻辑，节省了面积和功耗，但是互补控制信号增 加了电路的复杂度 由 WangJyh Ming 提出了 6 管传输管 XOR 逻辑如图 9 ( c) 所示10，结构简单，面积 小，性能好，运算速度比 10 管 CMOS 互补逻辑快 27 9% ，比 10 管传输门逻辑快 20% ，且无需互补信号由于使用传输管逻辑，高电平输出时可能存在阀值压降导致反相器输出存在静态功耗 通过综合考虑面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 树分布时钟延时匹配是采用时钟延时多米诺技术，它的每一级时钟由前一级时钟和后一级时钟推导来进行确定，具体的时钟延时要求如下: 只有在当前这一级预充电稳定输出为0 后才能对下一级开始进行预充电; 在当前这一级求值边 沿时，下一级必须充电结束，这样才能取消下拉网络预充 电管和防止存在短路电流 由于每一级时钟信号都有较大 的驱动负载，如计算第一级块进位产生信号和块进位传播 信号的时钟信号 C

25、LK1 就连接有 126 个 PMOS 管，因此采用 反相器延时加上时钟路径上的传输门以及 H 树结构时钟分 布技术来设计时钟延时驱动，具体电路如图 10 所示，形成16 个子叶节点，每个子叶节点再去驱动 8 个 PMOS 管，传 输门总是导通，而时钟路径的延时那么可能通过这些器件的 尺寸来进行调整图 10 时钟延时多米诺逻辑和 H 树分布Fig 10 Clock delay domino logic and H tree distribution3仿真结果分析和比拟加法器幅员设计完成后，用 Assura 工具先对它进行物理验证，包括设计规那么检查( DRC) 、电气规那么检查( ERC) 和

26、幅员与原理图一致性检查( LVS) ，物理验证通过后，再用 Assura 工具提取幅员的寄生参数并采用 ss 的 Spectre 模型基于最长进位传播路径条件下进行后仿真 根据块进位函数动态实现电路特点， 可知当输入 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 位并行前缀加法器同时，也用相同工艺的静态 CMOS 技术来设 计相同结构的加法器，对每个阶段的关键路径延时比拟结果如表 1 所示，从中可知采用多米诺动态逻辑、时钟延迟多米诺和传输管逻辑等技术实现的电路性能有非常大改善表 1 多米诺动态逻辑和静态 CMOS 关键路径延时比拟Tab 1 Comparison domino dynamic logic with static CMOS on the critical path delay时钟延迟多米诺加法器静态 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、、幅员设计等各个方面进行优化和改良 本文实现算法和电路结构采用改良的 64 位基 4 的 Kogge Stone 树加法器结构，采用技术有多米诺动态逻辑、多输出多米诺逻辑、6 管传输管实现 XOR 逻辑、时钟延迟多米诺逻辑和 H 树分布等， 器件参数优化主要对基 4 点操作动态电路进行，幅员设计采用启发式殴拉路径算法、逻辑图、棍棒图对基4 点操作动态电路进行 最终设计的 64 位加法器面积为 0 137 9 mm2 ，在最坏情况下完成一次加法运算时 间为 532 26 ps 本设计广泛采用动态电路实现，在速度和面积方面有很大的优势，但功耗相对较大以及 动态结点易受到来自各方面噪声影响，因此还需要进一步研究动态电路工作在相对较低功耗且可靠性相 对较高的设计技术参考文献: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