（微电子学与固体电子学专业论文）多核处理器高性能alu单元设计研究.pdf

摘要摘要算术逻辑部件( a l u ) 作为微处理器中最重要和最常用的运算部件之一，它的速度和功耗对整个微处理器性能具有重要的影响。本文深入研究了a l u 的结构和核心加法器原理，根据网络处理器中微处理器的特点，实现了一种应用于微引擎的3 2 位a l u 部件。该a l u 支持3 2 位微引擎的所有逻辑运算和算术运算指令。通过采用全定制设计方法，在算法、电路、版图等各个层次分别进行设计优化，使a l u的性能得到提升。通过对现有a l u 结构和加法器原理进行分析研究，在普通并行前缀加法器基础上进行改进，采用不等位分组实现进位的方法，即在组内采用并行前缀进位、组外采用串行进位的方法实现加法器进位。为了降低电路的晶体管数量，减小芯片面积，采用传输管逻辑作为a l u 的电路实现方式，并通过理论计算和s p i c e 仿真两种方式对关键路径的参数进行优化。用h s p i c e 在频率为5 0 0 m i z ，电源电压为2 5 v 的条件下进行仿真，延时为0 8 4 璐，平均功耗为4 0 m w ，晶体管数量为5 0 0 8 。在o 2 5 u m 工艺的典型条件下，借助c a l i b r e 完成a l u 全定制版图物理检查及寄生参数提取。用h s p i c e 仿真所实现版图的关键路径延时为1 1 n s ，平均功耗为4 8 m w ，版图面积为0 0 5 4 n m 2 。关键词：m ea l u 并行前缀加法器全定制版图a b s t k i c ta b s t r a c t崩t l l m e t i cl o g i cu 1 1 i ti so n eo fm em o s ti i i 印n a n ta i l dc o m m o nc o m p u t i n gc o m p o n e n t si 1 1m em i c r o p r o c e s s o r - t h es p e e d 卸dp o w e rd i s s i p a t i o nh 嬲as i 画f i c 锄ti i i l p a c to ni i l i c r o p r o c e s s o r sp e 响姗a l l c e t h es 仰c t u r eo fa l u 锄da d d e r 研n c i p l ei ss t u d i e d 证t h i sm e s i s a c c o r d i n gt 0t h ec h 牡a c t e r i s t i c so fi i l i c r o p r o c e s s o ri nt h en e t w o r kp r o c e ss _ o r s ，a3 2 - b i ta l uc o m p o n e n ta p p l i e di 1 1 廿1 el n i c r 0 e n g i n ei sd e s i 印e d ns u p p o n sa l lt l l el o g i c a lo p e r a t i o n sa n d 撕岫e t i ci r 塔t n i c t i o n so f3 2 - b i tm i c r 0 一e n g i n e b ym l l - c u s t o md e s i 口，t l l ed e s i 印o p t i m i z a t i o ni sc 秭e do u tt 0i i i l p r o v et 1 1 ep e r f - o m l 锄c eo fa l ui nm e 甜g o r i t h m ，c i r c u i ta r l dl a y o u tl e v e l t h r o u 曲t l l ea i l a l y s i so nt 1 1 ee x i s t i n ga l us t r u c t u r ea n dt h ea d d e r 砸n c i p l e ，m eg e n e r a lp a m l l e lp r e f i xa d d e ri si n l p r o v e db y 甜l e i i cg r o u p 堍m e t t l o dt 0g e n e r a t ec 邺7 0 u t t h a ti sp a r a l l e lp r e f i xc a r 巧i n 印u p 锄ds e r i a lc a 盯y e ng r o u p s i i lo r d e rt o 同u c et h et r 锄s i s t o rn u m b e ro ft h ec u i t a l ui si i l l p l e m e n t e d 诵mp a s s 一缸a r l s i s t o rl o g i c t h o u 曲t 1 1 e o r e t i c a lc a l c u l a t i o n 孤1 ds p i c es i m u l a t i o i l t h et r a n s i s t o rs i z eo fc r i t i c a lp a t l li so p t i m i z e d w h e nt 1 1 en - e q u e n c yi s5 0 0 m i z ，p o w e rs u p p l yv o l t a g ei s2 5 vh s p i c es i i i l u l a t i o nr e s u l t si i l d i c a t e 仕l a t 面t i c a lp a md e l a yi s0 8 4 1 1 s ，a v e r a g ep o 、) i 惯c 0 n s 眦l p t i o ni s4 0 m w ，a n dt 啪s i s t o rn u m b e ri s5 0 0 8 u 1 1 d e rm ec o n d i t i o no ft ) r p i c a lo 2 5 p mp r o c e s s ，t h ep h y s i c a je x 锄i m 【t i o na n dp a r a u s i t i ce x 位l c t i o no fa l ui sc o r n p l e t i 耐、7 i ，i t hc a l i b r e h s p i c es h i l u l a t i o ns h o 、st l l a tt l l ec r i t i c a lp a t hd e l a yo f1 1 璐，a v e r a g ep 0 、张rc o n s u m p t i o ni s4 8 m w ；l a y o u ta r e ai so 0 5 4 m m 2 k e y w o r d ：m ea l up a r a u e ip r ：f i xa d d e rf u u - c u s t o ml a y o u t西安电子科技大学学位论文创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：盥日期尘! ! ：圭：l ?西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)日期2 1 里：墨：生日期翌! 竺：i ：! !第一章绪论第一章绪论1 1 课题研究背景当前，随着计算机、通信、网络技术的发展，信息技术的发展在国家经济发展中占据了很重要的地位，而微处理器的发展已经成为在通信、网络、计算机等领域技术发展的代表。微处理器的应用非常广泛，从普通的消费电子到高性能的网络处理器，再到航天航空等国防技术的特殊领域，作为大规模集成电路重要部分的高性能微处理器设计已是整个信息技术和计算机应用市场竞争的重要焦点和关键内容【l 】。另外，无论精简指令集计算机( r e d u c e di n s t n l c t i o ns e tc o m p u t e r ，r j s c )还是复杂指令集计算机( c o m p l e xi i l s 仃u c t i o ns e tc o m p u t e r ，c i s c ) ，6 4 位体系结构将是高端微处理器的一种必然趋势。关键路径上运算部件性能的提高对“位体系结构的微处理器将起着重要的作用1 2 】。随着微电子技术的快速发展，集成电路工艺已经进入深亚微米阶段，特征尺寸越来越小，集成度越来越高。建立在集成电路技术发展基础之上的微处理器性能也有了飞速的发展。从1 9 7 1 年i n t e l 第一块微处理器芯片诞生以来，微处理器芯片按摩尔定律的速度不断的更新换代。目前2 g h z 以上的微处理器早已问世，而6 4 位微处理器芯片的速度也已经超过了l g h z ，微处理器要达到如此高的速度，作为其关键路径上的a l u 的运算时间必须非常小1 3 j 。算术逻辑单元( a l u ) 是微处理器或微控制器的核心单元，快速a l u 的研究对于微处理器性能提高具有重要作用。算术逻辑单元( a d t h m e t i c 觚dl o g i cu 血，a l u ) 是微处理器中用于数据计算的单元，是最重要的运算部件之一。它能提供强大的算术运算、移位运算和逻辑运算，是集多种算术和逻辑运算功能于一体的单元。一般微处理器内部主要由数据通路和控制电路两部分组成，算术逻辑单元是数据通路的关键组成部分，是微处理器的核心功能部件，它的速度、功耗和面积对整个微处理器性能都有很大的影响。在现代微处理器中，具有单周期延迟的算术逻辑单元的性能是高性能处理器核心的一个重要因素，它的速度和功耗这两个性能参数尤为重要【4 】【5 1 。第一，进行整数运算的算术逻辑单元是数据处理核心的重要部分，它的运算速度对整个微处理器系统的运算速度有着非常重要的影响。第二，算术逻辑单元也是整个处理器中功率密度最高的部分之一，过大的电流和功率密度将导致芯片中该部分频繁出现热点和热区。现代高性能微处理器的时钟频率已经达到l g h z 以上，在高频运行的情况下，经过长时间的积累，热区会出现温度尖峰，导致处理器性能下降、功2多核处理器高性能a l u 单元设计研究能错误甚至芯片烧毁【5 】。当前高性能微处理器正在向多个运算引擎的趋势发展，如i n t e l 公司的p e n t i 啪4 处理器内部有3 个算术逻辑部件，基于e p i c 的i t a _ m 啪处理器设计了4 个算术逻辑部件【6 】，而在n a n i u i 以里用了6 个算术逻辑部彳牛【。7 1 ，更有甚者，微软的新一代游戏机x b o x 的图形处理器竟然集成了4 8 个算术逻辑部件。大量的部件复制设计使功率密度增长的问题更加严重i s 】。这些问题对算术逻辑部件的高速度和低功耗设计提出越来越高的要求。采用全定制方法设计速度快、面积小、功耗低的算术逻辑部件，有非常重要的意义。为此我国正在大力发展具有自主知识产权的高性能微处理器。本论文正是基于高性能网络处理器中6 个同构多核微处理器的设计，对此3 2 位微处理器中的算术逻辑部件进行研究和设计。而且，本课题在基于0 2 5 岬工艺条件下，探讨了深亚微米全定制电路的设计方法，并应用于论文的电路设计和版图验证中。1 2 国内外相关研究国际上对高性能算术逻辑部件的研究已经有多年的历史，并且一些研究已经达到较高的水平。众多先进技术被算术逻辑部件的设计所采用，如绝缘体硅( s o d技术、双电源电压技术等。采用这些技术，可以达到更高的性能和更低的功耗。一些具有代表性的研究主要有：d e c1 9 9 2 年，美国d e c 公司推出的a l p h a 2 1 0 6 4 处理器中，率先采用单周期延迟的算术逻辑单元。该部件为“位结构，采用0 7 5 “m 的c m o s 工艺实现，用于时钟频率为2 0 0 m h z 的处理器。该设计在当时堪称一流水平【9 】。c u n h香港中文大学( c u 阳叼电子工程系曾研究出1 6 位流水线结构的算术逻辑部件，该部件采用了一种新颖的异步流水线技术。采用0 6 p m 的c m o s 工艺制造，可应用在3 7 0 m h z 的处理器中【1 们。h i t a c m1 9 9 3 年，日本日立公司( c e 劬啪r e s e a r c hl a b o r a t 0 吼h i t a c t i i ，l t d ) 研制出采用双传输管逻辑( d p l ) 实现的3 2 位算术逻辑单元，使用0 2 5 岬l 的c m o s 工艺，2 5 v电压，该部件延迟为1 5 n s 【l l 】。i i l t e l 12 0 0 1 年i n t e l 公司研制的算术逻辑运算部件，在o 1 8 肛l 的c m o s 工艺下延迟仅为4 8 2 p s 。由于采用了先进的结构和绝缘体硅( s o i ) 技术，使得性能有很大提升的同时降低功耗【1 舶。i b m第一章绪论2 0 0 4 年，r e n e s 嬲公司( r e n e s 雒t e c l i l o l o g ) ，c o 印) 和i b m 公司( i b mt j w a t s o nr e s e a r c hc e n t e r ) 研究出一种双阱双电压的6 4 位算术逻辑部件，由于采用双阱和双电压的技术，延迟和功耗均大大降低。该部件可达到1 1 6 g h z 的频率1 1 3 1 。i n t e l 22 0 0 5 年，i i l t e l 公司推出的p e n t i u m 和x e o n 处理器的算术逻辑单元，采用9 0 眦工艺，在进行6 4 位运算时频率可以达到4 g h z 。同时，它还可以进行3 2 位运算，频率高达7 g h z 。由于采用了先进的9 0 t l i l l 工艺，双电源电压技术，独特的逻辑和电路结构等，该部件达到了非常高的性削1 4 】。图1 1 表示了算术逻辑单元在性能方面的发展。图中纵坐标为部件的运行频率，单位为g h z 。、4 o3 53 o2 5n舌2 o譬1 5 oo 5o od e cc u h nh i t a c h li b mi 僻1i n t e “2图1 1 算术逻辑单元性能发展然而，国内采用全定制对算术逻辑部件进行专门设计的单位较少，大多数设计都是采用半定制的方法。中科院计算所于2 0 0 1 年开始研制龙芯处理器，2 0 0 2 年8 月研制成功的龙芯1 号是国内第一款3 2 位通用c p u ，2 0 0 3 年1 0 月研发成功的龙芯2 号是国内第一款6 4 位通用c p u ，2 0 0 5 年又推出其第二代产品【1 5 】1 1 6 】【1 7 1 ，2 0 0 9年研制成功的龙芯3 号是我国第一款多核通用c p u 。经过多年的研发积累，龙芯c p u 设计技术已经达到世界先进水平。但是相比之下，国外i n t e l 、w d 、t i 等公司均采用专门设计的全定制电路实现，这种方法虽然开发周期较长，但设计出的电路速度快、功耗低、面积小，具有很多优势。因此，我们在全定制电路的设计积累上，显得非常迫切和必要。1 3 论文来源及主要工作本论文来源于国家重点研究项目，对高性能算术逻辑单元进行设计实现。主要采用全定制设计方法，从部件的算法、电路结构与参数、物理版图等方面进行4多核处理器高性能a l u 单元设计研究优化，实现了一款3 2 位高性能a l u 。本文的主要工作有以下几点：1 ) 算法分析通过对比分析多种移位器、加法器的实现算法和电路结构，确定采用桶形移位器与改进的并行前缀加法器算法结构来执行高速运算的a l u 结构。通过对传统的并行前缀加法器进行改进，采用不等位分组的方法较好地减少了加法器的延时，提高了整体电路的运算速度。2 ) 电路设计在进行电路设计时，对数据通路部分，采用基于传输管逻辑的设计策略，极大地减少了算术逻辑单元的晶体管数目，有效地优化了芯片的面积，减小了进位延时，并通过理论计算和s p i c e 仿真对关键路径参数进行优化。3 ) 版图验证及性能评估版图是设计的最终实现形式，将直接影响最终芯片的速度、功耗和面积。本文对在咖o s o 上实现的版图借助c a l i b r e 实现了物理验证及寄生参数提取，验证与仿真结果表明本文设计的a l u 具有较理想的延时、功耗和面积。1 4 本文结构本论文主要研究了应用于多核处理器中的a l u ，并设计出一款高性能3 2 b i t - a l u 。本文对高性能a l u 进行了研究、设计与优化，具体文章结构安排如下：第一章为绪论。论述课题背景和课题研究的主要内容。第二章为a l u 相关技术的发展研究。首先分析了a l u 的结构和分类，进而重点研究了其中移位器和核心加法器的算法和实现结构，并分析和对比不同加法器算法在速度、面积等性能方面的优劣。通过对a l u 相关算法的分析和比较，本文确定采用复合的a l u 结构，桶形移位器完成移位功能，并行前缀加法和串行进位相结合来执行加法的操作。第三章为m e 中a l u 电路的优化设计。本章按照系统所要求的a l u 功能，以及在第二章算法分析的基础上，对a l u 中核心加法器、移位器、逻辑运算分别进行了设计。重点从算法和电路两个方面对加法器做优化设计：算法上，通过对并行前缀加法器采用不等位分组实现优化；电路上，采用传输管逻辑实现数据通路，可以有效地减少整个电路晶体管的使用数目，从而有效地减小芯片的面积。第四章为全定制a l u 版图物理验证。对各个单元及全局版图借助c a l i b r e 实现了d r c 、l v s 检查以及寄生参数提取，并对后端提取的带寄生参数的网表进行s p i c e 性能仿真，通过对比说明所设计的a l u 达到了较小的延时、功耗和面积的第一章绪论性能要求。第五章为结束语，对全文工作进行总结，指出课题研究取得的成果和不足，以及进一步的工作展望。第二章a l u 相关技术研究7第二章a l u 相关技术研究算术逻辑单元主要处理算术运算指令和逻辑运算指令，它有很多种结构，核心单元是加法器。加法器是影响算术逻辑部件整体性能的关键部分。加法器的优化设计对于a l u 的性能是非常重要的。本章将介绍各种a l u 结构和各种加法器、移位器的常用算法及相关理论，讨论各种树形加法器结构，通过比较各种加法器的结构与性能，实现符合m e 性能要求的a l u 电路。2 1a l u 的结构及分类a l u 在功能结构上可以分为独立方式和复合方式两种。加法器独立方式是先实现所有算术运算指令，然后在加法器外围加上其他电路再实现逻辑运算指令；复合方式是将算术运算和逻辑运算指令全部放在一起，由操作控制信号来控制执行何种指令操作，这是一种集成的多功能a l u 结构。例如，最早的4 位多功能算术逻辑部件a l u 7 4 1 8 1 【l8 】就是将指令集成在一个片内电路中，它是采用五条控制线( s o ，s l ，s 2 ，s 3 ，和m ) 对指令操作方式进行控制选择的。a l u 的电路结构可以分为静态电路、非树型动态电路和树型电路结构三种。静态设计的优点是结构简单，功耗小，但缺点是面积大，频率不高；非树型结构的动态电路设计的最大优点是速度较快，缺点是功耗比较大；树型结构的优点是速度最快，它的最大延时是随着l o g ，增长，缺点是面积较大，功耗也较大，常用在操作位数多于3 2 的结构中l l 州。对于具体的功能和电路结构如何选择应该根据系统的要求做深入分析而定。2 2 核心加法器的算法研究加法器是整数部件和浮点部件的核心运算单元，它的运算速度是微处理器的性能提高最重要的限制因素之一。在高性能微处理器中，加法器用在算术逻辑单元、内存地址产生单元以及整数部件和浮点部件中；在数字信号处理器中，加法器用于离散余弦变换、快速傅立叶变换等运算【2 0 j 。二十世纪6 0 年代，对加法器已经有非常多的研究，到现在，人们提出了各种各样的加法器结构【2 1 】【2 2 1 。最简单的如串行进位加法器、跳跃进位加法器、以及较高速度的进位选择加法器、超前进位加法器和超前进位加法器的改进算法并行前缀加法器( p a r a j l e lp r e f a d d e r ) 等【2 3 】。这些结构有各自的优缺点，在实际应用时，应根据具体的设计目标和性能要求进行选择。8多核处理器高性能a l u 单元设计研究下面重点研究当前加法器的几种常用算法和实现结构。2 2 1 基本的加法器原理最简单的加法器就是一位半加器和全加器，两者唯一的不同就是全加器有进位信号，而半加器没有。半加器( h a )半加器( h a l fa d d e r ) 的原理如图2 1 中真值表，电路有两个输入a 和功以及两个输出岱和o ，逻辑表达如式( 2 1 ) 、( 2 2 ) 。cs豳图2 1 半加器的符号及操作s = 彳0 君式( 2 1 )c = 彳b式( 2 2 )半加器只计算两个输入数据位的和，如果有向高位的进位就输出进位。半加器是最简单的加法器，它通常和全加器组合实现较复杂的加法运算瞄】。图2 2 为基于逻辑表达式和与非门的电路结构。abs( a )csc( ”图2 2 半加器的逻辑电路结构ab全加器( f a )和半加器相比，全加器有一个进位输入，通常接受来自低位的进位。可以用图2 3 的真值表及简单的符号图来描述。第二章a l u 相关技术研究94b l4ec 一。s ? c to0 o00olololo ololl001o0ll0ollo1lol0lll1ll图2 3 全加器符号及功能表和与进位的逻辑表达式为：s f = 爿。0 b ，o c 。一l式( 2 3 )g = 4 e + g 一，( 彳。oe )式( 2 4 )从式( 2 3 ) 、( 2 - 4 ) 可以看出，全加器可以有很多种电路结构实现方式。图2 4 给出了基于半加器电路结构，也可以根据上述表达式由异或和与或逻辑们组成。4 置j 图2 4 全加器逻辑电路式( 2 _ 4 ) 是产生进位输出的方程，它的任何一项都可以使输出为1 。因此定义加法运算中的进位产生信号g 。和进位传播信号只【2 卯，逻辑表达如式( 2 - 5 ) 、式( 2 - 6 ) 所示。g ，= 彳。e式( 2 5 )只= 4oe式( 2 6 )由此可将公式( 2 3 ) 和( 2 - 4 ) 改写成：s = 只oc f 一。式( 2 - 7 )g = g + 只g l式( 2 8 )分析公式( 2 7 ) 和( 2 8 ) 可知，完成加法运算需要三步：首先根据公式( 2 5 ) 和( 2 6 )计算出进位产生信号g ，和进位传播信号只；然后利用公式( 2 7 ) 进行最终“和 值的计算；最后根据公式( 2 8 ) 完成每一位进位信号c 。的运算。因为进位产生项g 、1 0多核处理器高性能a l u 单元设计研究进位传播项尸生成部分以及和的生成部分操作相对比较简单，而进位链的部分比较复杂，它是加法器的关键。2 2 2 串行进位加法器( c r a )串行进位加法器是进位原理最简单的加法器结构，其结构如图2 5 所示。它每次只能进行一位运算，产生一个向高一级的进位，因此速度很慢。串行进位加法器的延时随着操作数位数的增加而线性增大。当前大多数台式计算机采用3 2 位字长，服务器则要求6 4 位，超级计算机或多媒体处理器等速度很快的计算机( 如s o n y 公司的游戏机p l a ys t a t i o n2 ) 瞄j 要求的字长则高达1 2 8 位。加法器速度与位数的线性关系使得采用串行进位加法器很不实耐1 。7 1 。因此需要改进算法，使得加法器的延时，。 伙) 。图2 5 串行进位加法器由于进位信号依次通过各级传输，进位链的延迟较大。通过改进使偶数位和奇数位有不同的进位逻辑如图2 6 所示，其中粗线所示为快速进位链，由n a n d链组成 3 1 。l 尉i厂t = 副k = 亍( 隼：i1-：一| lv ：彳一一舛iiyiliilo - 一lllli量，fll。i图2 6 进位链改进的串行进位加法器2 2 3 跳跃进位加法器( c k a )跳跃进位加法器是串行进位加法器的改进结构。加法器中的关键路径延时主要是由进位链传输引起的，串行进位加法器的问题在于每级的运算必须等待前一第二章a l u 相关技术研究级进位。为了减小进位传播延时，使进位绕过没有进位产生的加法器进行传播，因此称为进位跳跃加法器。图2 7 为进位跳跃加法器结构的原理图。当r 、日、最、b 同时为1 时，进位信号跳过进位链直接传给c 3 。为了实现跳跃进位，每组需要增加一个多路选择器和一个与门，这种结构可以提高加法器的运算速度，但是，速度的提高只有在某些特定的情况下才会出现。图2 7 跳跃进位加法器结构的基本原理如果将一个n 位加法器分组，对于每个组来说，如果组中所有位异或为1 ，那么本组的进位输入信号就可以直接跳过本组传输到下一个组中。组间进位信号可以是串行进位也可以是跳跃进位，采用串行进位的称为一级跳跃进位加法器，否则为多级跳跃进位加法器。分组时各组的位数不必相同，具体根据实际情况确定。2 2 4 进位选择加法器( c s a )在串行进位加法器中，每一个全加器必须等待进位输入到达之后才能产生一个输出的进位。如果提前计算出进位为0 和进位为1 的两种情况，在进位来到时只需判断应该输出那一个结果，而不用重新进行加法器运算，这样的结构称为进位选择加法器【2 7 1 。其结构如图2 8 所示【2 8 】，加法器的第f 位至什3 位不等待第扣l位的输出进位到达，而是对o 和1 两种可能性都进行进算。图2 8 进位选择加法器1 2多核处理器高性能a l u 单元设计研究图2 8 标出了加法器的关键路径。每一级进位链只有一个选择器的延时，因此进位选择加法器的速度有很大的提高。一般的进位选择加法器每个组具有相同的位数，延迟也与位数成线性关系，称为“线性进位选择加法器”。如果不把每组设置为相同的位数，而是从低位到高位组内位数逐渐增大，这一加法器逐级加长的简单方法使加法器结构具有亚线性延迟的特性【2 引。经过计算，这种结构的延迟与位数的平方根成正比，因此称为“平方根进位选择加法器 。2 2 5 超前进位加法器( c l a )在设计更快速的加法器时，逐级进位仍然以某种形式存在于进位跳跃和进位选择加法器中。超前进位加法器提供了一种解决该问题的方法【2 9 】【3 0 】。在超前进位加法器中，当输入g 进入模块，各级的进位输出将同时产生，每一位的进位输出、“和 值输出都与前面的位无关，因而有效的消除了逐级进位效应，它的加法时间与位数无关。根据式( 2 8 ) ，将g 按位逐级展开可得：c f = g + 只e - |= q + ( q l + 一l g 一2 )= q + 只g i 一。+ 一。g i 一：+ z z 一鼻r g 0 + 只一。丑r g式( 2 - 9 )从进位项的表达式可以看出，与位数无关的加法时间只是一种理想情况，真正的延时随位数线性地增加。图2 9 利用超前进位公式的自对偶性和递归性建立了一个镜像结构【2 引。一l -广一l -广j jl -1 l厂r jl -1 、广l 厂一i。1- 、r j r _- j一、r -j。、r _j。1f -ggqgg图2 94 位超前进位加法器镜像实现电路第二章a l u 相关技术研究当位数增大时，超前进位模块具有很大的扇入，这将使电路结构较复杂；如果用较简单的门来实现，则要求多个逻辑层次。这两种情况都会使传播延时增加。而这种加法器的面积也随着位数增大而迅速增加。因此，超前进位加法器结构很难实现位数较高的加法。研究表明超前进位加法器的位数为4 时最佳，这时超前进位加法器可以在速度与面积之间取得最优的折衷1 3 。图2 1 0 所示的组内超前进位、组间串行进位的结构是超前进位加法器的一种常见实现方式。每个c l a 模块完成一个m 位的超前进位加法运算。另外，组内串行、组间并行以及组内组间都并行的结构也常常被采用j 。c 0s os ls 。图2 1 0 组内超前进位、组间串行进位结构加法器2 2 6 并行前缀加法器( p r e f i x )c - d并行前缀加法器是超前进位算法的一种改进结构。由前面分析知道超前进位计算在实际中至多只能限于4 位，不能较好的应用于宽位加法器中。为了建立快速加法器，把进位传播和进位产生组织成递归的树型结构。一个比较有效地实现方法是将位加法器的进位传播信号层次化地分解为位子组合：c = g + c f 一。= g i + ( g l + e l ( g f 一：+ 一：( q 一3 + p 一，( + 名c 。) ) ) )= q + q q + p 一。( g 一2 + 一2 ( g l 一3 + 一3 ( + 异巳) ) ) )= g i + 只：h e 一2式( 2 - l o )在式( 2 1 0 ) 中，进位传播过程被分解为两位的子组合。如果将c ，进一步分解，则可将整个进位传播信号分解为f 位子组创2 7 j 。g ，和只，分别表示一组( 从第f 位至第，位) 的进位产生函数和进位传播函数，对于几位构成一组的粥逻辑( f 七，) ，如果该组产生一个进位，则g ，等于l ，而与前一组的进位输入无关。如果一个输入进位传播通过整个这一组，则只，等于l 。这一条件等同于前面讨论过的进位旁路加法器。该组的组进位产生和传播信号可以表示为：g f j = 嚷+ ：i q 吐j式( 2 1 1 )1 4多核处理器高性能a l u 单元设计研究p ：，= 如最，式( 2 - 1 2 )新的进位表达式的形式与原来超前进位的相同，只是进位产生和进位传播信号由块进位产生和块进位传播表达式所替代。由点操作理论可知：( g ，p ) ( g 。，p 。) = ( g + p g ，即。)式( 2 - 1 2 )点操作服从结合律，但不符合交换律。并行前缀加法器就是使用这种特殊的方式产生各位的进位输出。所有进位产生和传播信号并行地通过点操作单元进行运算，同时输出进位信号。利用点操作单元，可以构成一个树结构来有效地计算所有2 l 1个位置即( 1 ，3 ，7 ，1 5 等) 上的进位( f = l ，l o g ：) 。最重要的优点是在位置2 1上的进位只需要1 0 9 ，步就可以计算出来。换言之，一个位加法器的输出进位可以在l o g ：的时间内计算出来。只计算在位置2 ，- 1 上的进位显然是不够的，还需要推导出在中间位置上的进位信号。实现这一点的一个方法是在每一位上都重复这一树结构，如图2 1 1 【3 2 】对于- 1 6 的情形所示。例如，位置6 处的进位通过组合块( 6 ：3 ) 和( 2 ：o ) 的结果来计算。这个结构常常称为k o g g e s t o n e 树【2 9 1 ，它是基数为2 的树结构中的一种。基数为2 是指这一树结构是二进制树，它在每一结构层次上一次只组合两个进位字。整个加法器需要4 9 个复杂逻辑门，每个都实现点操作。此外，还需要1 6 个逻辑模块在第一层上产生进位传播和进位产生信号( g ，和p ) ，以及1 6 个门产生和。s bs 哺s bs 晓s l ls ms ，s is ，s 6s ，s is ，s 2s ls 图2 1 1k o g g e - s t o n e1 6 位并行前缀加法器图对于并行前缀加法器已存在许多研究，它有很多具体实现结构，这些结构的不同主要在于进位树的构造方法。常见的有二进制和四进制前缀运算树。由于二进制进位树扇入较小，结构简单，延时和面积特性都比四进制进位树好【3 3 1 ，因此多 寸寸一 百二3 莳二3一n 目二3 冒；3 寸0 3 莳寸一一寸：3一1 日二3 寸寸一 。百暑可一 莳兰3一替二sn 百c 可一一莳；可一 n 呵2 3第二章a l u 相关技术研究1 5数设计都采用这种结构【3 4 1 。具有代表性的并行前缀进位树有k o g g e s - t o n e 树、b r e n t k u i l g 树和s 心a i l s k y 树以及由它们衍生出的几种结构，如h a i l c a l l s o n 树、l a d i l e r - f i s c h e r 树、k n o w l e s 树等。k o g g e - s t o n e 树结构图2 1 1 为k o g g e - s t o n e 树结构【3 2 】，它的运算结点为l 0 9 2 一+ 1 ，当n 为3 2 时，前缀运算结点多达1 2 9 个，这造成了面积和功耗方面较大的代价，也使互连线增多，在版图实现上造成困难f l 纠。b r e n t k u n g正向二进制树结构不足以产生全部进位位，因此需要一个反向二进制树来实现其它进位位，这一结构组合中间的结果以产生其余的进位位。一种较为简单的b r e l l t k u i l g 树【3 5 】被提出，如图2 1 2 所示。它有正反两个二迸制树，正向二进制树只实现2 一1 位置上的进位信号，反向二进制树来实现其它位的进位。运算结点为2 一2 一l 0 9 2 ，当n 为3 2 时，前缀运算结点几乎是k o g g e - s t o n e 树结点的二分之一，这大大减少了实现代价和连线复杂度。但是b r e l l t - k u n g 树的逻辑级数却增加为2 l 0 9 2 一1 ，当n 为3 2 时，逻辑级数为9 级，是k o g g e - s t o n e 树的将近两倍，这导致速度明显降低。另外，b r e n t k 吼g 树布线结构不太规则，并且各个门的扇出也不太相同，这使得性能的优化比较困难。因此，b r e n t k u i l g 加法器很不适合位数较大的加法器【聊。i一_l一_i_ _l_一_ _l_ _一i_豳雷_雷置。一一。一一一，一，一一i ，一一，一一_ ，一。一一，一一一一。s l ss hs bs ns us 博s 9s is 1s bs ，s ls ls 1s ls o图2 1 2b r e n t k u n g 树结构s h a i l s l ( ) r 树s k l a n s k y 删树的逻辑级数为l o g ：，只需要一个布线通道，运算结点也只有( l 0 9 2 忉2 个，n 为3 2 时有8 0 个前缀运算结点，为k o g g e s t o n e 结构的6 2 。一莳0飞 百二弋一莳二弋一n每弋一i 寸一n 二飞 口镯：飞 莳二飞一- 目二飞 。目；弋一2 每吕可一i 二可一莳二可n1日ci弋一莳；_飞 莳二可1 6多核处理器高性能a l u 单元设计研究但是，s l d a i l s k y 结构的最大扇出却随着逻辑级数n 的增加而线性增大，当n 为3 2时最大扇出达到17 ，这使得电路负载急剧增大，对电路面积和运算速度都有影响，也使晶体管尺寸优化变得非常困难1 9 1 。s k l a n s k y 树形结构如图2 1 3 所示。_国_一一_目ii-_ _i _l i1ii _-i- _ilil。，一一多少l 一一一乡少一一一一多少i ，一_ 多少_ 一一孑孑罗髟l ，一一孑孑罗歹_ _ 一，；孑多爹爹爹歹移s l ss hs ns ns us 协s 9s is ，s s ，s is 3s ts ls 口图2 1 3s k l a i l s b 树形结构h a l l c a r l s o n 树t h a n 和d c a d s o n 在1 9 8 7 年提出h a l l c a d s o n 树形结构【3 7 1 ，其结构如图2 1 4所示。在h 趴- c a l l s o n 加法器中，采用奇偶相间的位片式设计，主体进位树只计算奇数位( g 一。c 。c 3c 1 ) 的进位，进而通过奇数位的进位来产生偶数位( c 一：c 一。c ：c 0 ) 的进位。这样，主体进位树只需要计算一半的进位，从而避免了完全进位树结构，减少了复杂度。它的运算节点为( l o g ：忉2 个，当n 为3 2时为8 0 个，是k o g g e - s t o n e 结构的6 2 ，这与s “a i l s k y 结构相同。h a n c 砌s o n结构具有最小的扇出2 ，最大布线通道为4 ，都比k o g g e s t o n e 结构小，并且结构也较规整。但是，h a n c 耐s o n 树的逻辑级数为1 0 9 ：+ 1 ，比理想情况略大，因此在速度上有一些损失【1 9 】。l a d n e r - f i s c h e r 树l 础l e i 一f i s c h e r 树形结构【3 8 】是b r e n t 1 0 u n g 结构的改进，它对逻辑级数和最大扇出进行折衷，用扇出的增大来换取逻辑级数的减小，其结构如图2 1 5 所示。l a d n e 卜f i s c h e r 树具有最小的布线通道1 ，可根据具体需要来调节逻辑级数和最大扇出之间的权重。它的运算节点较小，结构较规整，因此是一种较好的结构。但是对于速度要求较高的应用，这种结构往往不太适合f 捌。k n o w l e s 树第二章a l u 相关技术研究英国的s i m o nl o o w l e s 在1 9 9 9 年提出一组加法器结构3 9 1 ，人们将这组结构统称为k n o w l e s 树形加法器。所有的k n o w l e s 树都具有最小的逻辑级数( 1 0 9 ：) ，它们在布线通道和最大扇出之间进行折衷，因此具有很好的速度和面积特性k n o w l e s加法器采用【口，6 ，c ，j 】的命名方式来描述各种不同类型的进位树结构。& &s ，s ：s 。&sss ，&墨&岛是s -岛图2 1 4h 锄c 训s o n 树形结构_i_ l一ll i_i_i一目圉一il一_目 圉_一。l。i。i。，一一歹多少歹多少i ，一一，一一一：；乡乡歹7i _ 一一，_ ，一一，一一。s ，s s ，五25 ls o禺&5 7瓯也j 5 3j 2j lj o图2 1 5l a d n e r - f i s c h e r 树型结构其中【口，6 ，c ，d 】分别表示l 0 9 2 一1 级、l 0 9 2 一2 级、l o g ：一3 级等自后向前各级的扇出。图2 1 6 表示了l o w l e s 【2 ，l ，l ，l 】加法器的结构。由于鼬l o w l e s 树是一组树形加法器结构，因此可根据具体需要来选择合适的形式，达到布线通道和最大扇出之间最佳的折衷【1 9 j 。多核处理器高性能a l u 单元设计研究s bs l s 堪s us i ts 协s 9s ls 1s 6s ，s ls 3s 2s ls o图2 1 6l ( n o w l e s 树型结构2 2 7 力口法器性能比较图2 1 7 和图2 1 8 分别对以上五种经典加法器算法在6 4 位位宽时的运算速度和版图面积进行了比较【3 。其中，图2 1 7 的纵坐标为百分比，图2 1 8 的纵坐标是对数坐标。由此可以看出，串行进位加法器速度最慢，面积最小；进位跳跃加法器速度有很大提高，而面积只有较小的增加；进位选择加法器和超前进位加法器的速度相差不大，都能达到较快的速度。但超前进位加法器的面积比进位选择加法器大很多，因此单一的超前进位加法器在位数较大时很不实用；并行前缀加法器速度最快，而其面积却相对增长较少，分析结构表明，并行前缀加法器具有速度和面积两方面的优势，是设计时首选的结构【8 j 。c r ac i ac s ac l p r e l f x图2 1 7 几种加法器速度比较 每0 3一百二一莳二一n c 3 简：弋一一n 目二 口目9 寸飞一一莳二一。筒6 30 l 舍可一 i 兰3 莳二!。百二可_)一i ；寸一一莳盒soo 山山正第二章a l u 相关技术研究1 9豳圈_ l _翟一c f 认c k ac s ac l p r e f i x图2 1 8 几种加法器面积比较2 3 移位器的算法移位操作是一种重要的算术操作，广泛应用于浮点单元、换算单元以及常数的乘法器中。目前移位器的实现主要有三种结构：基于多路选择开关的移位器结构、桶形移位器和对数移位器，下面分别介绍各种移位器的实现结构。2 3 1 基于多路选择开关的移位器结构一个可控制的移位器实质上就是一个复杂的多路开关电路。图2 1 9 是一个简单的一位左右移位器【2 8 1 。根据不同的控制信号，输入字或者左移或者右移，或者维持不变。虽然这一结构比较简单，不需要译码电路，但当移位的位数较多时，许多这样的单元串联起来使结构变的复杂，不实用而且速度极慢。右移不移左移图2 1 9 一位可控制的( 左右) 移位器多核处理器高性能a l u 单元设计研究2 3 2 桶形移位器图2 2 0 是一个桶形移位器的结构1 2 引。它由一个晶体管阵列构成，其行数等于数据的字长，而列数等于最大的移位宽度，控制线沿对角线布置通过该阵列，结构与版图的布局相同。每次只有一个控制线为有效高电平，此时每一行只有一个晶体管导通将数据传送到输出端。桶形移位器的最大优点是信号最多只需通过一个传输门。换言之，传播延时在理论上是常数，与移位器的位数或移位器的规模无关。但在实际中并不是这样，因为缓冲器输入端的电容会随着最大移位宽度线性地增加。这一电路的一个重要特点就是移位单元的尺寸由金属线的节距来确定。444一t一 广jh 厂j 卜1 厂j胡一一丁一一丁一丁ii卜 一；1 厂j i 1 广jltitif 丁5 慢liitjh 广j v 帏一t：ti t岛b玩砒s | i j is j i i图2 2 0 可控制向右移位、移位宽度为0 3 的桶形移位器2 3 3 对数移位器桶形移位器把整个移位器实现为传输管的单个阵列，而对数移位器则采用分级的方法。总的移位数值被分解为若干个2 的指数值。一个具有最大移位宽度m的移位器包括l o g ，肘级，它的第f 级或者把数据移动2 位或者原样传送数据。图2 2 1 是