（电子科学与技术专业论文）高性能算术逻辑部件研究与全定制设计.pdf

国防科学技术大学研究生院学位论文 a b s t r a c t a l ui so n eo ft h em o s ti m p o r t a l l ta 1 1 du s u a l i yu s e dc o m p u t i n gu n i t si nm i c r o p m c e s s o r s ，t 1 1 e s p e e da 1 1 dp o w e rd i s s i p a t i o n o fa l uh a v ei r n p o r t a n te f f e c to nm ep e r f o r n l a n c eo fw h o l e m i c r o p r o c e s s o r n 悖a l ud e s 培n e dw i mt h em e t h o d o l o g yo ff u l lc u s t o mc a nr e a l i z eh i g h e r s p e e d ，l o w e rp o w e rd i s s i p a t i o na n ds m a l l e ra r e a ，a 1 1 d i th a sg r e a tv a l u ei na p p l i c a t i o na i l d s i g n i 6 c a n tm e m i n gi np r a c t i c e 1 1 1 i sm e s i se m p h a s i z e so n 伽lc u s t o md e s i g nm c 1 0 d o i o g yo f 王l i 曲p e r f o r m a n c ea l u 皿e p r o p o s e d6 4b i t sh i g hp e r f o a n c ea l u i so p t i m i z c da ta l g o 瑚砷l e v e l ，l o g i cl 州e l ，c i r c 试tl e v e l a n dl a y o u tl e v e l ，a n di si m p l 锄e n t e di no 1 8 f mc m o sp r o c e s s f u 曲e 廿n o r e ，m ct e s t i n g t e c h n i q u eo ft h ea l u i sd i s c u s s e d n d s 血e s i sm a i n l yc o r l 扛i b u t e st ot l l ef o l l o w i n ga s p e c t ： 1 an e wn o t i o nc a i l e d “p e o n n a i l c e v e c t o r ”t oq u a n t i f i c a t i o n a l l ym e a s u r et h ep e f l b m 脚c e o fc o r ea d d e ri sp r o p o s e d a c c o r d i n gt ot h et h e o r yo f “p e r f o m a n c e v e c t o r ”，a no p t i m i z e d 嫩曲 s p e e dp a r a l l e la d d e ra l g o r i m mi sp r o p o s e d t h ea l g o r i m mc o m b i n e s 、v i t l lm ea d v a n 协g e so f p a r a l l e lp r e f i xa d d e r sa n dc a i t ys e l e c ta d d e r st oa c h i e v eag o o db a l a n c e 锄o n gs p e e d ，p o w e r r d i s s i p 砒i o na n d a r e a 2 u s i n g “l 0 9 i c a le f 如r t ”m e t i l o dt oa n a l y z et h ec i r c u i t sc r i t i c a ip a m ，a n dc h o o s e 1 e o p t i m i z e ds i z eo ft r a n s i s t o r si nt h e o r yb y “sm e 廿1 0 d t h e n ，u s i n gs t at e c h n i q u es i m u l a t e sa n d a 1 1 a l y z e st h ec i f c u i tt oo p t i m i z e 仃_ a n s i s t o r ss i z e 舢啦! e r ，a i l dt h ec i r c u i to p t i m i z a t i o n 撕血m e t i c b a s e do ns t ai sg a i n e d r e s u l t sp m v e dt h a tt h eo p t i m i z a t i o ns t r a t e g yo fc o m b i n i n gt h e o r ya n d p r a c t i c eh a v eb e t t e re f f e c t 3 i n 够p i c a lc a s e ，t h ed e l a yo fc r i t i c a lp a t hi s1 3 8 玎s ，p o 、 ，e rd i s s i p a t i o ni s4 5 3 m 形a n d l a y o u ta r e ao fm ea l ui so 0 5 1 1 2 ，l m 2 t h ed e s 酒a c l l i c v e st h eg o a lo f h i g h e rs p e e d ，l o w e r p o w e rd i s s i p a t i o na 1 1 ds m a l l e r 盯e a 4 an o v e lb i s tt e c h n i q u ef o rn l ep r o p o s e da l uh a sb e e nd i s c u s s e di nm et 1 1 e s i s nc 蛐 a c h i e v e1 0 0 f 孤1 tc o v e r a g ew i mf e wt e s tp a t t e m s i nc o n c l u s i o n ，t h et e c h n i q u eh 懿b e t t c r e f f i c i e n c ya r l dl o 、 ，e rc o s t k e yw o r d s ：a r j t h m e t i ca n dl o g i c a lu n i t a d d e r ，p a r a j i e ip r e 再x ，p e - 0 r m a n c e v e c t o r l o g i c a ie f f o r t ，s t a l i c 丁i m i n ga n a i y s i s ，b u i i t - ns e i ft e s t ，f u i ic u s t o md e s i g n 第j i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 算术逻辑部件性能发展 图2 1串行进位加法器 图2 2 进位跳跃加法器一 图2 3 进位选择加法器一 图2 44 位超前进位模块 图2 5 超前进位加法器： 图2 6 并行前缀加法器 图2 7 几种加法器速度比较一 图2 8 几种加法器面积比较 图2 9 加法器三步操作示意 图2 1 0 前缀运算表示的串行加法器 图2 1 1 并行前缀加法器示意一 图2 1 2 方块三角单元信号连接 图2 1 3 方块单元模型 图3 1k 0 9 9 e - s t o n e 树型结构 图3 2b r e n t 硷u n g 树型结构 图3 3s k l a f l s k y 树型结构一 图3 4h a n c a r l s o n 树型结构 图3 5l a d n e r - f i s c h e r 树型结构 图3 6 酗l o w l e s 【2 ，l ，1 ，1 树型结构 图3 7 性能向量的三维图表示 图3 8 本文设计的6 4 位高速加法器 图3 9 关键路径与非关键路径一 图3 1 0 本文提出的结构在性能向量图中的位置 图4 1 指针加一 图4 2 左移指针加 图4 3 输入输出接口一 图4 4 移位器逻辑结构一 图4 5 算术逻辑部件总体结构一 图4 6 前缀运算和缓冲单元逻辑 图4 7 改进后的前缀运算单元一 图4 84 位串行加法器逻辑，进位为“o ” 图4 94 位串行加法器逻辑，进位为“1 ” 3 。6 7 7 l i l 9 1 0 1 0 “ 1 2 1 3 1 4 1 5 1 7 1 7 18 1 8 1 9 1 9 2 l 2 2 2 3 2 4 2 6 2 6 2 7 2 9 3 1 31 3 2 3 3 3 3 第1 i i 页 国防科学技术大学研究生院学位论文 图5 1 增加级数以减小晶体管尺寸3 6 图5 _ 2 电路调整前后参数归一化比较一 图5 3 移位器电路实现， 图5 4 异或逻辑的电路结构 图5 5 归一化延时与电气功效的关系 图5 6 加法器电路结构一 图5 7 加法器关键路径 图5 8 加法器和选择电路 图5 9 与或非、或与非门及其逻辑功效 图5 1 0 静态时序分析原理 图5 1 1 优化前后s p i c e 模拟结果比较 图6 1 算术逻辑部件版图布局规划 图6 24 位位片结构与版图实现 图6 3 电源、地线设计 图6 4 算术逻辑部件整体版图 图6 5 算术逻辑部件关键路径s p i c e 模拟结果 图6 6 全定制与半定制设计比较 图6 7 加法器性能参数横向比较 图7 1 线性反馈移位寄存器 图7 2 特征分析寄存器 图7 3算术逻辑部件内建自测试结构 3 7 3 8 3 8 4 0 4 2 4 2 4 3 4 3 4 5 4 8 5 2 5 4 5 5 5 6 5 6 5 7 5 8 6 5 6 5 6 7 第1 v 页 国防科学技术大学研究生院学位论文 表目录 表2 1 前缀运算封闭性 表3 1 树形进位结构比较一 表4 1 加、减操作指令功能描述 表4 2 逻辑操作指令功能描述 表4 3o p 咖e 执行的操作 表4 4 s l l i rb i t 表示的操作 表4 5 逻辑改变前后信号真值表 表5 1电路调整前后参数比较 表5 2 常用逻辑门的逻辑功效膏 表5 - 3 常用逻辑门的寄生延时p 表5 4 关键路径各级的逻辑功效和分支功效一 表5 5 计算得出各级逻辑门输入电容 表5 6 各条路径分析列表 表5 7 第l 条关键路径时序分析 表5 8 第一次调整后各条路径分析列表 表5 9 第一次调整后关键路径时序分析 表6 1电路及版图模拟结果 表6 2 算术逻辑部件横向比较一 表6 3 加法器横向比较 表7 1c 押产生部分测试 表7 2 前缀运算扩展 表7 3 输入为d 的方块单元正常和故障时信号传播 表7 4 输入为口的方块单元正常和故障时信号传播 表7 5 输入为d 的方块单元正常和故障时信号传播一 表7 6 串行进位加法器测试向量一 表7 7 预置向量 1 4 2 0 2 5 2 6 2 7 2 8 3 3 3 7 3 9 3 9 4 3 4 4 4 6 4 6 4 6 4 7 5 7 5 7 5 8 6 1 6 l 6 2 6 2 6 2 6 4 6 6 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：商性能笠苤望磐登坐e 翌嚣生垒塞剑选盐 学位论文作者签名：至! 盐 日期： 婀年z 月，尹日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：匿性鳇差盔堡塑叠鲑叠壅生全塞魁遮盐 学位论文作者签名：童! ! ：装 作者指导教师摊：i 丝亟坠 日期：弦疗年；月j 穸日 日期： 了年f 2 月仲日 i 堕堕型兰垫查查堂婴壅竺堕堂竺鎏兰 第一章绪论 1 1 课题研究背景 作为信息技术的基础平台，高性能微处理器已经成为当前通信、计算机等领域技术发 展的代表。高性能微处理器的发展，将是未来集成电路发展的重要因素，也成为高性能运 算和信息处理的决定因素，它将彻底变革人们的工作、学习和生活方式。当前，高档计算 机市场对高性能微处理器的需求飞速增长，据信这一市场份额已经突破千亿美元，再辅之 以外设、网络、软件和服务，其市场规模将不可估量。因此，可以说高性能微处理器的研 究是整个信息技术和计算机应用市场竞争的重要焦点和关键内容【”。 随着微电子技术飞速进步，集成电路工艺进入深亚微米阶段，特征尺寸已减小到了 0 1 8 m 以下，o 1 3 m 的工艺成为成熟工艺。基于工艺技术水平的提高，微处理器性能有了 惊人的发展，微处理器不断的更新换代，性能迅速提高。从1 9 7 1 年i n t e l 公司推出第一块 4 位微处理器芯片4 0 0 4 至今，微处理器技术得到长足发展。目前6 4 位微处理器的芯片的 速度已经超过了1 g h z ，而且2 g h z 以上的3 2 位微处理器已经问世。微处理器要达到如此 高的速度，其关键路径上运算部件的运算时间必须足够小。另外，无论精简指令集计算机 ( r e d u c e di n s 拄u c t i o ns e tc o n m u t e r ，s c ) 还是复杂指令集计算机( c o m p l e xi n s 咖c t i o ns e t c o m p u t e r ，c i s c ) ，6 4 位体系结构将是高端微处理器一种必然趋势。关键路径上运算部件 性能的提高对6 4 位体系结构的微处理器将起着重要的作用【6 ”。 算术逻辑部件( 心i t h m e t i ca n dl o g i c a lu 【l i t ，a l u ) 是微处理器中最重要和最常用的部 件，它是集多种算术功能和逻辑功能于一体的单元电路，能提供强大的算术运算和逻辑运 算能力。一般来讲，微处理器内部主要由数据通路和控制通路两部分组成，算术逻辑部件 是数据通路的重要组成部分，是微处理器的核心功能部件，它的性能往往决定着整个系统 的性能。 在现代微处理器中，具有单周期延迟的算术逻辑运算部件的性能是高性能处理核心的 一个重要因素，它的速度和功耗这两个参数尤其重要【2 l 【3 l 。第一，数据处理核心主要进行 整数处理和浮点处理，算术逻辑部件作为数据处理核心的最重要部分，它的运算速度对整 个系统性能具有非常重要的影响。由其负责处理的算术逻辑运算类指令是处理器中运算量 最大，使用频率最高的指令，根据a m d a l l l 定律和大概率事件优先原则，算术逻辑部件应 具有较小的延迟，才能使整个系统的性能提高。第二，算术逻辑部件也是整个处理器中功 率密度最高的部分之一，过大的电流和功率密度将导致芯片中该部分频繁出现热点和热 区。现代高性能微处理器的时钟频率已经达到l g h z 以上，在高频运行的情况下，经过长 时间的积累，热区会出现温度尖峰，导致处理器性能下降、功能错误甚至芯片烧毁。当前 高性能微处理器正在向多个运算引擎的趋势发展，如i m e l 公司的p e n t i u m4 处理器内部有 3 个算术逻辑部件，基于e p i c 的i t a i l i u m 处理器设计了4 个算术逻辑部件 4 j ，而在n a j l i u m 第1 页 国防科学技术大学研究生院学位论文 2 里甚至有多达6 个算术逻辑部件【5 】，更有甚者，微软公司新一代游戏机x b o x 的图形处理 器竟然集成了4 8 个算术逻辑部件! 大量的部件复制设计使功率密度增长的问题更加严重。 这些问题对算术逻辑部件的高速度和低功耗设计提出越来越高的要求。采用全定制方 法设计速度快、面积小、功耗低的算术逻辑部件，有非常重要的意义。 随着我国国民经济信息化的进程，对信息安全提出了很高的要求，高端计算领域的安 全尤其重要，国产自主微处理器可为服务器安全提供基础保障，为此我国正在大力发展具 有自主知识产权的高性能微处理器。本论文正是基于国内对商性能微处理器的需求，针对 高性能6 4 位微处理器中的算术逻辑部件进行研究和设计。而且，本课题针对0 1 8 “研深亚 微米工艺，探讨了深亚微米全定制设计方法，并应用于论文的电路设计中。 1 2 国内外相关研究 国际上对高性能算术逻辑部件的研究已经有多年的历史，并且一些研究已经达到较高 的水平。一些具有代表性的研究主要有： d e c 1 9 9 2 年，美国d e c 公司推出的a l p h a 2 1 0 6 4 处理器中，率先采用单周期延迟的算术逻 辑部件。该部件为6 4 位结构，采用0 7 和m 的c m o s 工艺实现，用于时钟频率为2 0 0 m h z 的处理器。该设计在当时堪称流水平【6 】； c u h k 香港中文大学( c u h k ) 电子工程系曾研究出1 6 位流水线结构的算术逻辑部件，该部 件采用了一种新颖的异步流水线技术。采用0 ，劬撒的c m o s 工艺制造，可应用在3 7 0 m h z 的处理器中【7 】： h i t a c h i 1 9 9 3 年，日本日立公司( c e n t r a lr c s e a r c h l a b o r a t o r y ，h i t a c h i ，l t d ) 研制出采用双传输 管逻辑( d p l ) 实现的3 2 位算术逻辑部件，使用o 2 靴m 工艺线，2 5 y 电压。该部件延迟 为1 5 珊1 8 】； i b m 2 0 0 4 年，r e n e s a s 公司( r e n e s a st e c l l i l o l o g yc o r p ) 和i b m 公司( i b mt j w 瞻沿n r e s e 盯c hc e n t e r ) 研究出一种双阱双电源电压的6 4 位算术逻辑部件，由于采用双阱和双电 源电压的技术，延迟和功耗大大降低。该部件可达到1 1 6 g h z 的频率【9 l ； i n t e l 1 2 0 0 1 年m t e l 公司研制的算术逻辑部件，在o 1 即mc m o s 工艺下延迟仅为4 8 2 筇。由 于采用了先进的结构和绝缘体硅( s 0 i ) 技术，使得性能有很大提升，同时使功耗降低【1 0 j ； i n t e l 2 i n t e l 公司最近推出的新一代p e n t i u m 和x e o n 处理器的算术逻辑部件，采用9 0 n m 工艺， 在进行6 4 位运算时频率可以达到4 g h z 。同时，它还可以进行3 2 位运算，频率高达7 g h z 。 第2 页 国防科学技术大学研究生院学位论文 由于采用了最先进的9 0 刀朋工艺，双电源电压技术，独特的逻辑和电路结构等，该部件达 到了非常高的性能】。 图1 1 表示了算术逻辑部件在性能方面的发展。图中纵坐标为部件的运行频率，单位 为g h z 。 d e cc u h xh i m c h il b ml 州e l li n t e l 2 图1 1 算术逻辑部件性能发展 然而，国内对于高性能算术逻辑部件的研究还不是很多，研究水平也不高。采用全定 制对算术逻辑部件进行专门设计的单位较少，大多数设计都是采用半定制的方法，因此性 能较低，频率一般只能达到1 0 0 m h z 2 0 0 m h z 。例如，2 0 0 3 年中科院研制的6 4 位高性能 微处理器“龙芯( g o d s o n ) ”问世，2 0 0 5 年又推出其第二代产品“龙芯2 号【1 2 】【1 习【1 4 l 。 虽然该款处理器主频号称可达到4 0 0 m h z 5 0 0 m i z ，但是龙芯系列处理器的算术逻辑部件 仍采用标准单元的方法设计，性能相对来说仍然较差。 这种情况与国内高性能微处理器的研究水平相对落后有关。相比之下，国外i n t e l 、 a m d 、t i 等公司均采用专门设计的全定制电路实现，这种方法虽然开发周期较长，但设 计出的电路速度快、功耗低、面积小，具有很多优势。因此，我们在全定制电路的设计积 累上，显得非常迫切和必要。 1 3 课题主要工作 本课题主要对高性能低功耗算术逻辑部件的设计进行研究，主要采用全定制的方法， 从部件的算法、逻辑结构、电路形式、物理版图等层次设计优化，实现了一款6 4 位高性 能通用算术逻辑部件，并研究了一种适用于该部件的高效内建自测试方法。 本文的主要工作有以下几点： 算法设计 算法设计是整个设计的最高层次，采用先进的算法是提高运算部件性能的最根本、最 有效的方法【15 1 。本文在分析几种经典加法器算法的基础上，提出“性能向量”的概念，用 来定量衡量并行前缀加法器的整体性能。根据对“性能向量”的分析，构造出种优化的 第3 页 把0 j 口j 口j d j 口矾t土王王a仉n 国防科学技术大学研究生院学位论文 高速并行加法器算法。经理论分析和实际模拟，该算法具有很好的性能。 逻辑设计 同一种算法可以对应不同的逻辑结构，因此逻辑结构的设计非常重要。逻辑结构的选 择和逻辑级数优化，特别是对关键路径的优化，可以有效地提高部件性能。本文对算术逻 辑部件的逻辑结构进行了分析和设计，并对关键路径进行了优化，使得整体性能和功耗都 有所改善。 电路设计 电路设计是将逻辑结构映射到晶体管级的过程。电路设计时要考虑电路结构和晶体管 尺寸，这关系到电容电阻等很多物理因素，是一个复杂的迭代过程。好的设计具有电路速 度快、晶体管数目少、输入电容小、噪声容限大等优点。本文针对所设计部件的具体结构， 使用理论推导和实际模拟相结合的方法进行分析，从而确定电路结构和晶体管最佳尺寸， 使关键路径延时最小，整个电路达到最佳的性能。 版图设计 版图是设计的最终实现形式。版图设计将直接影响最终芯片的速度、功耗和面积。从 各模块的布局规划、布局、布线，到单元的版图形状、信号线摆放、电源与地线设计等都 是需要考虑的因素。手工设计的版图具有紧凑的结构，比自动综合工具在性能、功耗和面 积上都有很大改善。本文设计的版图具有较理想的延时、面积和功耗参数。 内建自测试方法研究 将测试码产生及测试响应分析逻辑置入电路内部的测试方法称为内建自测试。内建自 测试包括测试码的产生策略、分析测试响应的策略和实现上述策略的结构。本文根据所设 计的算术逻辑部件的结构，研究了一种独特的内建自测试方法，并对测试码的产生策略进 行了理论分析和证明。该方法具有l o o 的故障覆盖率，并且只需要较少的测试向量，有 很高的效率和较低的代价。 1 4 课题研究成果 本课题研究了高性能通用微处理器算术逻辑部件的设计，在算法、逻辑、电路、版图 等层次进行设计和优化，最终以版图的形式实现了一款高性能通用算术逻辑部件，并研究 了一种适用于该部件的内建自测试方法。经实际模拟，在x 公司o 1 趴m 工艺库的典型情 况下，该算术逻辑部件的延迟为1 ，3 8 珊，平均功耗4 5 3 坍矾版图面积o 0 5 11 2 肌m 2 ，达到 了较高的性能，并且具有较小的功耗和面积。 本文的主要创新体现在以下几点： 提出“牲能向量”的概念 本文在分析并行前缀加法器经典算法的基础上，提出“性能向量”的概念，用来定量 衡量算术逻辑部件核心加法器的性能，并由此衍生出“性能指标”的概念作为性能评价的 参数。“l 生能向量”和“性能指标”可以量化的反映并行前缀加法器的综合性能，对加法 第4 页 国防科学技术大学研究生院学位论文 器的设计有理论指导意义。 构造出一种优化的高速并行加法器算法 本文根据“性能向量”和“性能指标”的理论推导，构造出一种优化的高速并行加法 器算法。该算法结合了并行前缀加法器和进位选择加法器算法，在逻辑级数、最大扇出和 布线通道三个方面进行折衷，具有较好的综合性能。实际的模拟也证明了该算法在速度、 面积和功耗方面有较强优势。 算术逻辑部件电路分析优化 本文使用“逻辑功效”的方法对电路关键路径进行理论分析，依此来确定晶体管理论 上的最佳尺寸，使得延时最小；使用静态时序分析对电路进行模拟分析，进一步优化调整 尺寸，并总结出基于时序分析的电路优化算法。结果证明，这种理论与实际结合的优化策 略具有较好的效果。 针对算术逻辑部件的内建自测试方法研究 本文研究了一种独特的内建自测试方法，专门针对本文所设计的算术逻辑部件结构。 这种方法产生的测试向量与算术逻辑部件的位数成线性关系，并且具有1 0 0 的故障覆 盖率，因此具有较高的效率和较低的代价。 1 5 文章的组织 本文在组织上采取专题讨论的形式，分别对上述研究内容进行分析讨论，各章之间按 照全定制的设计流程排列。 第一章给出了课题背景和课题研究的主要内容： 第二章对算术逻辑部件中核心加法器的常用算法及相关理论进行介绍； 第三章对并行前缀加法器算法进行量化分析研究，提出“性能向量”的概念，并构造 出一种优化的高速并行加法器算法： 第四章论述算术逻辑部件逻辑结构的设计优化： 第五章对算术逻辑部件的电路进行分析与优化，讨论了电路参数的优化策略： 第六章给出了算术逻辑部件的版图实现技术和模拟结果； 第七章对算术逻辑部件测试进行讨论，研究了一种内建自测试方法，并进行分析和证 明。 以上七章构成了本文的主体结构。 第八章对全文进行总结，并对未来的工作进行展望。 第5 页 国防科学技术大学研究生院学位论文 第二章加法器算法及相关理论 算术逻辑部件主要处理算术运算指令和逻辑运算指令，它的核心单元是加法器。这个 加法器是影响算术逻辑部件整体性能的关键部分，因为几乎所有的算术运算和逻辑运算， 都要通过它来完成，因此称之为“核心加法器( a d d e rc o r e ) ”。对核心加法器的优化设 计是本课题的研究重点之一。本章将介绍加法器的常用算法以及相关理论，主要讨论各种 加法器相关研究情况和当前最常用的并行前缀加法器算法及相关理论，为以后的研究打下 基础和铺垫。 2 1 加法器相关研究 在微处理器和数字信号处理器中，加法器是整数部件和浮点部件的核心运算单元，因 此它的运算时间是微处理器最重要的性能限制因素之一。在高性能微处理器中，加法器用 在算术逻辑单元、内存地址产生单元以及整数部件和浮点部件中；在数字信号处理器中， 加法器用于离散余弦变换、快速傅立叶变换等运算【1 6 】。二十世纪6 0 年代，人们对加法器 的结构和实现已经有非常多的研究。到现在为止，人们提出了各种各样的加法器结构，可 谓五花八门 1 6 】【1 8 j 。最简单的如串行进位加法器( c 锄了r i p p l ea d d e r ，c r a ) 、进位跳跃 加法器( c a n ys k i pa d d e r ，c k a ) ，以及较高速度的进位选择加法器( c a h ys e l e c ta d d e r ， c s a ) 、超前进位加法器( c a n 了l o o k a l e a da d d e r ，c l a ) 和并行前缀加法器( p a r a l l e lp r c f i 】( a d d e r ) 等 i9 j 。这些结构都有各自的优缺点，在实际应用时，应根据具体的设计目标和要 求进行选择。 串行进位加法器( c r a ) 串行进位加法器是最简单、最基本的加法器结构，其结构如图2 1 所示。串行进位加 法器的进位像水波一样依次通过每位，因此也称为“行波进位加法器”。它每次只能进行 一位运算，因此速度很慢。 三落 s 2s is 日 图2 1 串行进位加法器 第6 页 国防科学技术大学研究生院学位论文 串行加法器的延迟随着操作数位数的增加而线性增大。当前大多数台式计算机采用3 2 位字长，而服务器则要求6 4 位，超级计算机或多媒体处理器等速度很快的计算机( 如s 0 n y 公司的游戏机p l a ys 诅t i o n2 ) 要求的字长则高达1 2 8 位。加法器速度与位数的线性关系使 得采用串行进位加法器很不实际【2 0 1 。因此需要改进算法，使得加法器的延时如 d ( d 【2 l 】。 进位跳跃加法器( c k a ) 进位跳跃加法器是串行进位加法器的改进结构。它将整个加法器分为几个组，如果某 组的所有进位传播信号都为“1 ”，则将该组的进位输入直接传送到输出，而不需要进行 进位运算。这个过程好像进位做了一个跳过该组的动作，因此称为进位跳跃加法器。 为了实现跳跃进位，每组需要增加一个多路选择器和一个与门，如图2 2 所示。这种 结构可以提高加法器的运算速度，但是，速度的提高只有在某些特定的情况下才会出现。 因此，进位跳跃加法器仍然需要提高运算速度才能满足高性能计算的需要。 c ( b ，+ 。i “b h b )( a i + 。l a h a ) ( s h m l s + 1 s 0 图2 2 进位跳跃加法器 进位选择加法器( c s a ) 进位选择加法器 2 习采用资源复制的基本思想，用硬件来换取速度。它将整个加法器分 为几个组，每组有两条路径，进位输入为“o ”和“1 ”的两种情况通过两条路径同时计算。 一旦该组进位输入信号到来，通过多路选择器选择正确的进位输出与和值。其结构如图2 3 所示。 图2 3 进位选择加法器 由于采用了前瞻的思想，因此进位选择加法器的速度有很大提高。如果整个加法器分 为m 组，则运算延时可由第一组进位延时、m 个多路选择器的延时及一个和产生延时相加 第7 页 国防科学技术大学研究生院学位论文 得到。进位选择加法器虽然具有较快的速度，但由于它采用了资源复制的方法，因此实现 代价也成倍增加。 一般的进位选择加法器每组具有相同的位数，延迟也与位数成线性关系，称为“线性 进位选择加法器”。如果不把每组设置为相同的位数，而是从低位到高位组内位数逐渐增 大，例如第一组2 位，第二组3 位，等三组4 位，等等。这种逐组位数加长的方法使加法 器结构具有亚线性延迟的特性【2 0 1 。经过计算，这种结构的延迟与位数的平方根成正比，因 此称为“平方根进位选择加法器”。 超前进位加法器( c l a ) 在设计更快速的加法器时，避免逐级进位很重要，但是这一效应仍然以某种形式存在 于进位跳跃和进位选择加法器中。超前进位加法器【2 3 】提供了一种解决该问题可能的方法。 在超前进位加法器中，当进位输入巳进入超前进位模块，各级的进位输出将同时产生，每 一位的进位输出与和值输出都与前面的位无关，因而有效地消除了逐级进位效应，因此加 法时间与位数无关。图2 4 是一个超前进位模块的逻辑图。 一 图2 44 位超前进位模块 但是，研究图2 4 的结构会发现，与位数无关的加法时间只是一种理想的情况，真正 的延时至少随位数线性地增加。这是由于当位数增大时，超前进位模块具有很大的扇入， 这将使电路结构较复杂；如果用较简单的门来实现，则要求多个逻辑层次。这两种情况都 会使传播延时增加。而这种加法器的面积也随着位数增大而迅速增加。因此，超前进位结 构常用在位数较小的情况，般来说不大于4 。 s ( 1 ) 图2 5 超前进位加法器 第8 页 国防科学技术大学研究生院学位论文 图2 5 所示的组内超前进位、组间串行进位的结构是超前进位加法器的一种常见实现 方式。另外，组内串行、组间并行以及组内并行、组间并行的结构也常常被采用。 并行前缀加法器( p r e 6 x ) 并行前缀加法器是超前进位的一种改进结构，它将位加法器的进位传播信号层次化 地分解为位子组合，并将进位产生和进位传播组织成递归的树型结构。并行前缀加法器 使用一种特殊的方式产生各位的进位输出，这种方式称为“前缀运算( p r e f i xc o m p u 诅t i o n ) ”。 所有进位产生和传播信号并行地通过前缀运算单元进行运算，同时输出进位信号。各个前 缀运算单元通过递归的方式连接起来，即可形成整个加法器。图2 6 是并行前缀加法器的 一种实现方式。 51 41 31 21 1109 8 7654 3210 、 l 一- i ：，_ ，事。j 一一一，一一- ! ，一一厂_ ，一 l 。，e i 。_ 。_ _ ：，；_ ，粤丫 高亓f 葡嗣甬商甬秸诸苗了 1 1 而高褊希誓薪手豁蔫丁 r 亩1剥嵩藩餮剞寸j j ：0 1 40 1 3 0 1 2 。0 1 1 ：0 1 0 ：09 1 0 807 ：0 6 ：05 ：o4o3 ：o 2 。010 o o 图2 6 并行前缀加法器 对于位加法运算，并行前缀加法器最少只需l o g ，步就可完成进位的运算，因此也 称为“对数超前进位加法器” 2 ”。并行前缀加法器的运算速度是各种加法器结构中最快的， 同时，它由许多相同的前缀运算单元组成，结构规整，容易实现。由于这些优点，并行前 缀加法器成为当前最常用的高速加法器结构。 图2 7 和图2 8 分别对以上五种经典加法器算法在6 4 位位宽时的运算速度和版图面积 进行了比较1 2 ”。其中，图2 8 的纵坐标是对数坐标。 由图2 7 和图2 8 可以看出，串行进位加法器速度最慢，面积最小：进位跳跃加法器 速度有很大提高，而面积只有较小的增加：进位选择加法器和超前进位加法器的速度相差 不大，都能达到较快的速度，但超前进位加法器的面积比进位选择加法器大出1 0 倍以上! 因此单一的超前进位加法器在位数较大时很不实用，性价比很低，必须与其它结构进行 组合；并行前缀加法器速度最快，是进位选择加法器的1 5 倍，而其面积却相对增长较少， 比进位选择加法器略高，只有超前进位加法器的1 4 左右。分析结果表明，并行前缀加法 器具有速度和面积两方面的优势，是设计时首选的结构。 由于并行前缀加法器优秀的性能特性和较小的面积代价，因此得到了广泛的应用。为 了设计高速的并行加法器结构，有必要对并行前缀加法器的算法进行深入研究。2 2 节 将重点对并行前缀算法进行分析和讨论。 第9 页 里堕型堂垫娄盔堂竺塑生堕兰堡笙奎 面祝 l i m c r ac k ac s ac l a p r 雌x 图2 7 几种加法器速度比较 c r ac k ac s ac l a p r q l x 图2 8 几种加法器面积比较 2 2 并行前缀算法分析 并行前缀加法器是当前最常用的加法器实现结构，它具有结构规整、逻辑简单、互连 容易的优点，便于在v l s i 中高效地实现，因此在现代高性能微处理器中被广泛采用。下 面将重点对并行前缀加法器的算法进行分析与讨论。 对于位加法运算，定义一= a 一1 以一：鸽表示加法器的被加数，b = 巩一。吼一：玩表 示加数，s = 晶一，& 一：晶表示4 与曰相加的和，c j ( v f ，0 f 一1 ) 表示每位的进位。为 了讨论的方便，本节假设该加法运算无进位输入c 。对于相同结构的有进位输入的加法器， 本文讨论的结果也同样适用。 根据上述定义，每位的和s 与进位e 的表达式为： c = 4 皿+ ( 4 0 e ) c f i ，( v f ，l s f 一1 )( 2 1 ) 第1 0 页 国防科学技术大学研究生院学位论文 墨5 4 0 e o g i ，( v f ，l f 一1 ) ( 2 2 ) 当f _ o 时，和值晶与进位c 0 的表达式为： c o2 4 岛 ( 2 3 ) 岛= 4 0 岛 ( 2 4 ) 由公式( 2 1 ) 和( 2 2 ) 可知，s 和c 的计算都依赖于前一级的进位c 因此提高加法器 运算速度的关键在于产生进位的速度。考虑公式( 2 1 ) 和( 2 2 ) 的特点，定义加法运算的进位 产生信号g j 和进位传播信号p 如下： g j = 4 旦，( v f ，0 f 一1 ) ( 2 5 ) p2 4 0 e ，( v f ，o s f 一1 ) ( 2 6 ) 当g f = 1 时，将保证在g 产生一个进位，而与c j 一无关；当鼻= 1 时，将保证如果c j 一有 一个进位输入，该进位可以传播至c l 。注意到，g f 和只仅与4 、e 有关，而与进位输入c f 一， 无关a 根据公式( 2 5 ) 与( 2 6 ) 的定义，公式( 2 1 ) 和( 2 2 ) 可改写为： c = g l + p e l ，( v f ，1 f 一1 ) ( 2 7 ) s2 只o c ( v f ，1 s f ! 一1 ) ( 2 8 ) 分析公式( 2 7 ) 与( 2 8 ) 可知，整个加法可以分为三步操作：第一步进行预处理，计算出 进位产生信号g j 和进位传播信号只，由公式( 2 5 ) 和( 2 6 ) 定义；第二步进行每一位进位信号 c 的运算，完成公式( 2 7 ) 表示的操作：第三步进行最后的和值产生，公式( 2 8 ) 表示了和值 产生的运算。图2 9 是加法器三步操作的示意。 ( a n 小