（电路与系统专业论文）高性能并行乘法器半定制设计方法研究.pdf

浙江大学硕士学位论文 摘要 乘法器是微处理器中的重要部件，它的设计与实现直接影响着整个数字系统 的性能，因此高性能乘法器的设计仍然被关注。另一方面，激烈的市场竞争加速 了产品的上市进程，从而要求设计者尽量缩短设计时间为了兼顾乘法器的性能 和设计时间，通常使用基于标准单元库的半定制设计方法但是传统的半定制设 计方法受限于库中标准单元有限的驱动能力，无法实现最短路径延时。为此，本 文提出了基于标准单元库扩展的乘法器设计方法，消除了传统方法的不足。 本文设计并实现1 7 b i t x l 7b i t 带符号数字乘法器。为了提高乘法器的性能， 采用改进的b o o t h 编码算法，w a l l a c e 树形结构，以及基于标准单元库扩展的设计方 法。该方法使用逻辑功效模型分析乘法器的关键路径，通过构造驱动能力更为完 备的单元以实现关键路径中每一级门功效相等，从而得到最短路径延时。将 t s m c9 0 r i m 标准单元库扩展得到扩展单元库，使用两个单元库分别版图实现数 字乘法器，基于扩展单元库实现的乘法器速度提升1 0 8 7 。实验结果表明，基于 标准单元库扩展的半定制设计方法可以有效提升电路的性能，这种方法尤其适用 于电路负载过大的情况。 关键字：乘法器；标准单元库扩展；改进的b o o t h 编码算法；w a l l a c e 树；逻辑 功效 浙江大学硕士学位论文 a b s t r a c t m u l t i p l i e ri sa l li m p o r t a n tc o m p o n e n to fm i c r o p r o c e s s o r , a n dd i r e c t l ya f f e c t st h e p e r f o r m a n c eo ft h ew h o l ed i g i t a ls y s t e m f o rt h i sr e a s o n , s t u d yo nd e s i g no f h i g h - p e r f o r m a n c em u l t i p l i e ri ss t i l lc o n c e r n e d o nt h eo t h e rh a n d ，t h ei n t e n s em a r k e t c o m p e t i t i o nh a sa c c e l e r a t e dt h ep r o d u c t se n t e r i n gt h em a r k e t ，w h i c hr e q u i r e st h e d e s i g n e rt os h o r t e nd e s i g nt i m e i no r d e rt ot a k ei n t oa c c o u n tt h ep e r f o r m a n c ea n d d e s i g nt i m e ，s e m i - c u s t o md e s i g nm e t h o db a s e do ns t a n d a r dc e l ll i b r a r yi su s e dt o i m p l e m e n tm u l t i p l i e r b u tt h et r a d i t i o n a ls e m i - c u s t o md e s i g nm e t h o di sr e s t r i c t e db y s t a n d a r dc e l l sl i m i t e dd r i v i n ga b i l i t y , a n dc a n n o tr e a l i z et h es h o r t e s tp a t hd e l a y t h e r e f o r e ，t h i sp a p e rp r e s e n t e dd e s i g nm e t h o do fh i g h - s p e e dm u l t i p l i e rb a s e do i l s t a n d a r dc e l l l i b r a r ye x t e n s i o n t h i sm e t h o de l i m i n a t e s t h ed i s a d v a n t a g e so f t r a d i t i o n a lm e t h o d a17b i t x17b i ts i g n e dd i g i t a lm u l t i p l i e rw a sp r o p o s e di nt h i sp a p e r t oi m p r o v e t h ep e r f o r m a n c e ，t h em u l t i p l i e ru s e dm o d i f i e db o o t h sr e c o d i n ga l g o r i t h m ，aw a l l a c e t r e es l m c t i l r ea n dd e s i g nm e t h o db a s e do ns t a n d a r dc e l ll i b r a r ye x t e n s i o n i ta n a l y z e d c r i t i c a lp a t hu s i n gl o g i c a le f f o r tm o d e l ，a n db yc o n s t r u c t i n gc e l l sw i t hd i f f e r e n t d r i v i n gc a p a b i l i t i e s ，i ti m p l e m e n t e de q u a ll o g i c a le f f o r ti ne a c hs t a g et oa c h i e v e m i n i m u mp a t hd e l a y b a s e do nt s m c9 0 n ms t a n d a r dc e l ll i b r a r y , a ne x t e n d e dc e l l l i b r a r yw a sg e n e r a t e d ，a n dt h el a y o u t so fm u l t i p l i e rw e r ei m p l e m e n t e dr e s p e c t i v e l y c o m p a r e dt os t a n d a r dc e l ll i b r a r y , t h em u l t i p l i e ri m p l e m e n t e dw i t he x t e n d e dc e l l l i b r a r ya c h i e v e dap e r f o r m a n c ei m p r o v e m e n to f10 8 7 e x p e r i m e n t a lr e s u l t ss h o w t h a tt h es e m i c u s t o md e s i g nm e t h o d o l o g yb a s e do ns t a n d a r dc e l ll i b r a r ye x t e n s i o nc a l l i m p r o v ec i r c u i tp e r f o r m a n c ee f f e c t i v e l y , w h i c hi se s p e c i a l l ya p p r o p r i a t ef o rd e s i g n s w i t hl a r g el o a d s k e yw o r d s ：m u l t i p l i e r ；s t a n d a r dc e l ll i b r a r ye x t e n s i o n ；m o d i f i e db o o t h sr e c o d i n g a l g o r i t h m ；w a l l a c et r e e ；l o g i c a le f f o r t 浙江大学硕士学位论文 致谢 光阴似箭，日月如梭，不觉间已到了硕士毕业的时候了。 近三年的学习生涯中，我要特别感谢我的导师严晓浪教授，感谢严老师一直 以来对我的悉心关怀和尽心指导严老师以高尚的人格、谦逊的作风、渊博的学 识、严谨的治学极大地影响着我。严老师不仅慷慨地传授专业知识，而且积极地 为我们创造良好的学习环境和丰富的科研资源，这对我们各方面素质的全面发展 具有非常重要的意义。作为一名硕士生，能够师从严老师是我一生的荣幸。 其次衷心感谢葛海通老师多年来在学习工作等方面给予我的关心与指导，葛 海通老师宽广的胸怀和勤奋踏实的工作精神，让我受益匪浅。还要感谢浙江大学 超大规模集成电路设计研究所的史峥、吴晓波，何乐年、沈海斌、罗小华、张培 勇、潘赞、王维维、竺红卫、赵梦恋等老师多年来给予我的指导和帮助。 非常感谢我的师兄吕冬明博士和师姐郑丹丹博士。吕师兄和郑师姐不仅在学 习上给予我无微不至的指导，而且在工作上和生活中也传授给我诸多宝贵的人生 经验。他们帮助我从无到有地深入了解集成电路后端设计领域的重要问题，顺利 解决我在学习和科研过程中遇到的诸多问题，使我可以很好地适应研究生阶段的 学习和生活，也为离开校园踏入社会奠定了坚实的基础。与吕师兄和郑师姐一起 学习和工作的经历将成为我人生中的宝贵财富。感谢项目组的黄雪维、应琦钢、 何琰、李碧琛等同学的支持和帮助 感谢曾经一起学习和工作各位同学和同事，感谢求学途中所有曾经给予过我 帮助的人：孟建熠、黄凯、李春强、杨军、刘智力、丁永林、冯炯、莫鹏飞、刘 兵、陈志坚、徐鸿明、傅可威、沙子岩、张欣、陈晨、项晓燕、刘磊、王荣华、 武淑丽、高金加、刘畅、曾健林、冷冰、梁静、鄢传钦、刘晓东等。 最后，我要由衷的感谢父母二十五年来对我的养育之恩在这些年，你们始 终默默地支持我，无微不至地关心我，给我信心和勇气。我一定继续努力，不懈 奋斗，不辜负你们的期望。 曾宪恺 2 0 1 2 年2 月于浙大求是园 浙江大学硕士学位论文 图目录 图1 2 1w a l l a c e 树形压缩结构4 图2 1 1 乘法器原理图9 图2 2 1 阵列乘法器1 0 图2 2 2 改进的b o o t h 编码乘法器1 1 图2 2 3w a l l a c e 树形压缩结构乘法器1 2 图2 2 4c s a 阵列示意图1 3 图2 2 5 基于混合压缩器的树形乘法器一1 4 图2 3 1 改进b o o t h 编码的w a l l a c e 树形乘法器1 5 图3 1 1 改进的b o o t h 编码实现方案一1 9 图3 1 2 乘法器部分积产生电路2 0 图3 2 1 部分积符号位完全扩展2 l 图3 2 2 部分积符号位特殊处理2 l 图3 3 1c s a 压缩器实现电路2 2 图3 3 2 部分积压缩前预处理2 3 图3 3 3 部分积预处理结果2 3 图3 3 4w a l l a c e 树形压缩结构2 4 图3 3 5 基于w a l l a c e 树形结构的部分及压缩过程2 4 图4 1 1 乘法器关键路径2 5 图4 2 1 反相器充放电等效电路2 6 图4 2 2c m o s 门充放电等效电路2 9 图5 1 1 逻辑综合中面积与速度折中3 4 图5 2 1 扩展单元布局3 5 图5 2 2 自动布线建模3 6 图5 2 3 扩展单元版图实现流程3 8 图5 2 4 布线实现流程3 9 图5 2 5 扩展单元n a n d 4 x 4x 6 版图一4 7 图5 3 1 扩展单元n a n d 4 x 4x 6 非线性延时模型4 9 图6 1 1 半定制物理实现流程一5 3 v i l 浙江大学硕士学位论文 图6 1 2 乘法器布图规划。5 3 图6 1 3 乘法器版图一5 4 图6 2 1 乘法器模拟验证方案5 5 图6 2 2 乘法器仿真波形1 5 7 图6 2 3 乘法器仿真波形2 5 8 图6 2 4 乘法器随机模拟验证5 9 图6 2 5 乘法器形式验证一5 9 图6 3 1 乘法器性能比较一6 0 v m 浙江大学硕士学位论文 表目录 表3 1 1 改进的b o o t h 编码( 1 ) 1 7 表3 1 2 改进的b o o t h 编码( 2 ) 1 8 表3 3 1c s a 压缩器真值表2 2 i x 浙江大学硕士学位论文 1 绪论 1 1 背景及意义 随着微电子技术的飞速发展，集成电路工艺已经步入到深亚微米( v d s m ， v e r y d e e ps u b m i c r o ) 阶段。在各种新技术的推动之下，特征尺寸减小到3 2 r i m 以 下，t s m c2 8 r i m 工艺已经达到量产标准，而i n t e l 早已进行2 2 n m 的技术研究。 代表着半导体行业核心技术的微处理器则随着工艺技术的发展实现了性能的突 飞猛进。从1 9 7 1 年i n t e l 公司推出第一款4 位微处理器4 0 0 4 至今，微处理器 技术得到了长足的发展，如今3 2 n m 工艺i n t e lc o r ei 73 9 6 0 xe x t r e m ee d i t i o n 处理器已经上市。相对于4 0 0 4 微处理器仅集成2 2 5 0 个晶体管、主频0 7 4 m h z 而言，c o r ei 73 9 6 0 x 处理器采用六核心十二线程，它集成了2 2 7 亿个晶体管， 主频达3 2 g h z ，性能提升8 0 0 0 倍。即使是对功耗要求很高的嵌入式处理，如今 的性能也早已达到服务器标准，2 0 r i m 基于c o r t e x a 1 5 的m pc o r e 处理器已成功 流片。可见，高性能的处理器成为未来发展的趋势。这一趋势一方面基于技术驱 动，另一方面基于需求驱动。如今，高清数字电视、3 d 高清影视具有广阔的市 场和应用前景，这对海量数据计算和处理都提出了很高的要求，需要系统中硬件 设备具有快速数据处理能力 乘法器是高性能处理器、数字信号处理器的重要组成部件。事实上，乘法器 成为如今高性能处理器和s o c 性能提升的瓶颈。由于乘法运算需要消耗较多的 硬件资源，并且该运算本身的速度相对较慢；而对于一个计算机系统而言，其性 能并非由最快的运算部件决定，相反，系统的性能取决于最慢的运算部件。因此， 乘法器的性能在很大程度上决定了系统的性能在广泛采用流水线技术的c p u 及d s p 中，常常要求乘法运算在一个周期中完成，以保证流水线的正常工作， 这使得乘法器处于关键延时路径中。可见，设计高性能乘法器可以大大提升微处 理器和s o c 的性能。 传统上为了提升系统的性能，通常采用全定制设计方法，通过精确设计晶体 管的长宽比实现快速的晶体管，通过精确地布图布线设计实现较短的走线，减小 互联线寄生电容但是如今，该方法无法满足实际的需求。这一方面由于激烈的 市场竞争，另一方面由于芯片的规模和复杂程度。如今，半导体市场的竞争愈加 1 浙江大学硕士学位论文 激烈，由传统的p c 、服务器领域转到移动终端领域提升竞争力很重要的一点 在于快速推出具有竞争力的产品。这一特点加速了产品的上市进程，从而要求设 计者尽量缩短设计时间。而全定制设计方法尽管能实现最优性能，但是需要大量 的人力成本和时间成本，无法满足激烈竞争的市场的要求与此同时，基于市场 多样的性能要求，芯片的规模和复杂程度显著增大，显然，全定制设计方法无法 适应如今高集成度和复杂度的芯片特点。 如今，为了兼顾系统的性能和设计时间，数字集成电路常采用基于标准单元 库的半定制设计方法。这种方法依托于f o u n d r y 提供的标准单元库和e d a 厂商 提供的e d a 工具，可以实现设计自动化。但是这种方法受限于单元库中标准单 元有限的驱动能力，无法实现最短路径延时。基于此，本课题针对t s m c9 0 n m 超深亚微米工艺，采用半定制设计流程，并探索该流程中可以完善的地方，提出 标准单元库扩展的方法，设计快速的1 7 位整数乘法器部件。 1 2 国内外相关研究 由于乘法器在如今的微处理器、数字信号处理器以及其他各种应用中扮演者 非常重要的角色，因此，国内外对乘法器从不同的角度做了很多研究工作。 乘法器的架构一直成为研究工作的重要组成部分。乘法运算本质上是移位加 法运算，具体而言，乘法运算通常分为三个【1 1 2 1 3 1 ：部分积生成、部分积压缩、 以及最终加法运算。对于两个二进制数x 和y ，设被乘数x 为r n 位，记为x m 1 x m - 2 x o ，乘数y 为n 位，记为y n 1y n - 2 y o ，则积为m + n 位，记为z 咖1 z 咖- 2 z o 。通常，将m 位被乘数x 与n 位乘数y 的每一位进行与运算，可以 得到n 项位数为m 的部分积，用加法器阵列将n 项部分积相加，得到积z 。 从乘法器性能提升角度来看，为了实现高性能的乘法器，要求生成较少的部 分积，使用较快的部分积压缩算法，并且使用快速的加法器来完成最终的加法运 算。 关于减少部分积这个课题，b o o t h 通过采用一种新的算法巧妙地将部分积压 缩到原来的一半，这就是b o o t h 编码算法1 4 。传统上，若乘数y 的位数为1 1 ，则 通过简单地与运算，将乘数的每一位与被乘数x 的所有位进行与运算，得到n 项部分积，且每一项部分积仅有x 和0 两种数值，记为 x ，0 ) 但是b o o t h 引 2 浙江大学硕士学位论文 入一种新的编码方式，将乘数的连续两位进行编码，并用此两位产生一项部分积， 则部分积的数目会减小至原来的一半通过有效地减小部分积的个数，并进而减 小部分积的压缩时间，可以很大程度提升乘法器的性能。引入b o o t h 编码之后， 部分积由传统的 x ，0 ) 变成了 2 x ，x ，0 ，x ，2 x 5 种取值情况这种编码方 式会引入新的硬件资源，即编码电路，同时还要求压缩阵列能执行减法操作( 当 部分积取值为2 x 和x 时) ，这些都会增加设计开销。目前，用的更多的是改进 的b o o t h 编码算法( m o d i f i e db o o t h sr e c o d i n g ) ，或基4 的改进的b o o t h 编码【5 1 。 它将乘数的三位作为一组重新编码，且每连续的两组重叠一位，同样，部分积的 数目减少到原来的一半，且每项部分积可能取值情况为 - 2 x ，x ，0 ，x ，2 x 。 为了将部分积的数目将至更低，基数更高的编码也一度成为研究的热，点, t 6 j 基数 更高的编码方式对乘数的更多位进行编码，这样可以得到更少的部分积，但这增 加了编码电路的复杂程度，并且使部分积可能取值情况变得更多，进而增加部分 积压缩阵列的复杂度，这会抵消乘法器因部分积数目减少导致的性能提升。本课 题采用基4 改进的b o o t h 编码算法来生成部分积。 部分积压缩这一课题同样得到大量研究移位相加算法1 7 ( 或串行乘法器) 消耗极少的硬件资源，它仅使用一级加法器，在时钟的控制下，每一个时钟周期 完成一次加法，并减少一项部分积，这样对于n 项部分积，需要n 1 个周期才完 成一次乘法运算。通过不断复用加法器资源实现乘法运算。这种算法尽管硬件开 销很少，但是速度很慢，在如今高性能数字系统中很少使用。相对于移位相加， 阵列乘法器可以有效提升乘法器性能。对于n 项部分积，阵列乘法【8 】使用n - 1 级 加法器，这样每一项部分积可以作为一级加法器的输入，在一个时钟周期下，n 项部分积被压缩成为一项，从而得到乘法运算的积值。阵列乘法器的硬件开销是 移位相加乘法器的n 1 倍，但是完成一次乘法运算为移位相加乘法器的( n 1 ) 分之一，性能提升了n - 1 倍，这也体现了性能与硬件资源的折中 由阵列乘法器的压缩过程可知，其延时与部分积个数成线性关系，并且，阵 列乘法器的版图十分规则，每一级加法器与部分积成对应关系，通过将部分积简 单地映射为加法器就可以得到乘法器的版图。版图规则这一特性使得乘法器很容 易实现设计自动化，这可以由e d a 工具自动完成，也可以由设计者通过脚本定 制乘法器的版图 为了更快速地压缩部分积，一些设计者提出了树形压缩算法，其中最著名的 3 浙江大学硕士学位论文 是w a l l a c e 树【9 】在关键路径中，由于高位的计算结果需要用到低位的进位，所 以阵列乘法器本质上是一种串行压缩但是，通过积极探索部分积压缩过程中的 并行性，减少压缩过程中高位计算结果对低位进位的依赖性( d e p e n d e n c y ) ，通 过使用一级加法器阵列，原来的三项部分积可以压缩成为两项以9 项部分积为 例，如图1 2 1 所示，其中p p l ，p p 2 ，p p 3 ，p p 4 ，p p 9 表示部分积，c s a ( c a r r y - s a v ea d d e r ) 表示进位保留加法器阵列。经过第一级c s a 阵列，9 项部分 积压缩成六项部分积；经过第二级c s a 阵列，6 项部分积压缩成4 项部分积； 经过第三级c s a 阵列，部分积被压缩成为三项；经过最后一级c s a 阵列，部分 积最终被压缩成为两项，作为最后快速加法器的输入由于c s a 输入3 项部分 积，输出两项部分积，因此又被称为3 2 压缩器。与阵列乘法器n - 1 级加法器， 或者8 级加法器相比，w a l l a c e 树形乘法器仅使用4 级加法器，这就大大的缩短 了部分积压缩时间，提升了乘法器的性能。且阵列乘法器的延时与部分积数目成 一次线性关系，设部分积数目为n ，则阵列乘法器延时为o ( n ) ，而w a l l a c e 树形 乘法器的延时与部分积数目成对数关系，记为o ( 1 0 9 3 2 ( n ) ) 。当n 越大，则树形结 构对乘法器的性能提升越明显。 图1 2 1w a l l a c e 树形压缩结构 尽管树形结构可以有效提升乘法器性能，但是其版图极不规则，而且走线也 十分复杂，不便于进行定制设计。树形乘法器使用版图不规则性换取性能提升， 考虑到不规则的版图结构需要消耗更大的面积，因此，这也反映了性能与面积的 折中 针对w a l l a c e 树形乘法器不规则的版图结构，d a d d a 提出了4 ：2 压缩结构1 们 4 浙江大学硕士学位论文 4 ：2 压缩结构输入4 项部分积，输出2 项部分积与w a l l a c e 树形乘法器相比， 4 ：2 压缩结构乘法器的版图更规则，并且，压缩时间与部分积数目成底数为2 的 对数关系，记为o ( 1 0 9 2 ( n ) ) 乘法器性能提升方面也有其他一些研究工作。为了优化w a l l a c e 树形乘法器 的路径延时，o k l o b d z i j ae ta 1 将其扩展为三维树结构f 1 1 】。在乘法器物理实现方 面也有很多研究。n i i c h ii t o h 等针对5 4 x 5 4 b i t 、w a l l a c e 树型结构的乘法器进行 优化，提出了一种较为规则的版图结构【1 2 】而在乘法器功耗研究领域，p c h m e i e r ，r a r u t c n b a r ，以及l r c a r l e y 对乘法器的功耗问题进行了研究【1 3 】。除 此之外，一些研究者还从设计方法学角度探索乘法器设计和优化方案。与传统的 基于门延时模型的设计方法学不同，s h u oz h o u 等提出了综合的逻辑和版图设计 方案，使在逻辑设计阶段就考虑互联线延迟因素【1 4 1 1 3 半定制设计方法研究 目前，数字集成电路通常采用半定制设计方法一方面，数字系统的规模越 来越大，复杂程度也越来越高，逻辑门数目数以百万计，晶体管的数目则达到亿 的数量级，如果考虑到互联线，则全定制该数字系统成了一项不可能完成的任务。 另一方面，激烈的市场竞争则要求产品尽早上市，这也缩短了设计时间。因此， 如今超大规模数字集成电路很难采用传统的全定制设计方法实现，它们更多采用 半定制设计方法。 在半定制设计流程中，先要经过一系列的诸如市场需求分析、市场调研、可 行性研究、论证等步骤形成项目任务书，然后进行总体设计，这包括确定设计目 标、明确芯片功能、确定接口特性等等。总体设计过程中，使用高级程序语言， 例如c + + ，对各项规格说明进行描述以实现用来验证的参考模型，这种模型被称 为黄金模型 总体设计完成之后，需要进行详细设计，这一过程中会用到“综合”和层次 的概念。由于设计的规模很大、功能很多，需要对设计进行不同层次的描述。使 用硬件描述语言，例如v e r l l o g ，对设计进行行为级描述，使用高级综合工具 将其综合成寄存器传输级( r t l ) ；或者使用硬件描述语言直接对整个设计进行 r t l 级描述之后，需要对r t l 代码进行全面的功能性验证。一种普遍的方法 5 浙江大学硕士学位论文 是编写测试平台( t e s t - b e n c h ) 测试平台也是一段v e r i l o g 代码，它实例化整 个设计，对设计施加一系列测试激励向量，得到响应结果将响应结果与用于参 照的预期结果进行比较：如果响应结果与预期结果相同，表明功能正确；如果响 应结果与预期结果不同，则表明功能不正确。这里用于参照的预期结果是由黄金 模型得到。 r t l 代码经过功能验证之后，需要对其进行逻辑综合。逻辑综合是在设计者 给定的约束条件之下( 该约束条件包括时钟定义、时序、面积要求、负载、最大 转换时间、最大扇出等等) ，在单元库的支持下，使用e d a 工具将r t l 代码转 换、映射、优化最终得到门级网表的过程。逻辑综合要求有单元库的支持，单元 库通常由f o u n d r y 提供，包含有一些d 核以及标准单元。标准单元是经过精细 设计的，并在速度、功耗、面积等方面经过优化 门级网表生成之后，需要对其进行物理设计首先对整个设计进行物理层面 的布图规划( f l o o r p l a n ) ，布图规划包括各种模块的摆放，端口位置的确定、供 电网络的设计等等；接着对设计布局布线( p l a c e & r o u t e ) ，进而得到版图。 为了精确地评估设计的性能，需要考虑互联线的延时，这在深亚微米集成电 路中尤其重要；为此，从版图中提取寄生电阻，寄生电容、寄生电感等寄生参数 信息，将该寄生参数信息反标至门级网表，并进行静态时序分析最后，需要对 版图进行物理验证，物理验证包括天线效应检查( a n t e n n ae f f e c tc h e c k ) 、设计规 则检查( d r c ，或d e s i g nr u l ec h e c k ) 和版图逻辑图检查( l v s ，或l a y o u tv e r s u s s c h e m a t i c ) 等 1 4 课题主要研究工作 本课题基于t s m c9 0 n m 工艺标准单元库扩展，设计并实现了1 7b i t 1 7b i t 带符号二进制乘法器模块。本课题主要从架构、逻辑优化、物理设计、功能验证 四个方面对乘法器进行研究，选择合适的乘法器架构，利用标准单元库扩展的研 究思路，并对所选的乘法器架构的关键路径建立一阶r c 模型，通过数学分析的 方法对其进行逻辑优化，并最终完成乘法器的版图设计。论文的研究内容如下- ( 1 ) 乘法器结构设计 分析不同类型乘法器的结构，从提高乘法器的性能的角度出发，采用改进的 浙江大学硕士学位论文 b o o t h 编码算法生成部分积，采用树形压缩算法对部分积进行压缩，并采用快速 加法器实现最终加法运算 ( 2 ) 乘法器逻辑优化 针对乘法器的总体结构，通过时序分析工具找出乘法器的关键路径。由于关 键路径延时为所有门延时之和，采用逻辑功效模型对每一个逻辑门的延时进行建 模，并进而对关键路径延时建模，从而得到路径延时最短的条件。 ( 3 ) 标准单元库扩展 结合逻辑功效分析乘法器的关键路径得出的结论，引入单元库扩展的设计方 法，通过对标准单元库进行扩展，实现驱动能力更大且更完备的单元集合，从而 使设计得到更好的优化。对标准单元库中同种类型的任意两个单元进行拼接得到 扩展单元，提取扩展单元的寄生参数，将寄生参数反标到扩展单元的s p i c e 网 表中，使用仿真工具计算扩展单元的延时特征信息，对扩展单元进行特征化，得 到包含有延时、面积、功能等信息的扩展单元库，使用扩展单元库实现乘法器关 键路径中每一级门功效相等，从而得到最短路径延时。 ( 4 ) 乘法器版图实现 版图乘法器最终的实现形式本课题采用w a l l a c e 树形压缩算法实现快速乘 法器，一方面由于乘法器版图不规则，且该数字集成电路规模较大，不便于进行 定制设计，另一方面，为了缩短设计周期，因此本课题采用物理综合工具i c c o m p i l e r 实现乘法器的版图。对乘法器的版图进行寄生参数提取，并反标到乘法 器的门级网表中，使用时序分析工具对乘法器进行静态时序分析，得到乘法器的 延时信息为了使所设计的乘法器满足设计规则，对乘法器进行物理验证物理 验证包括天线效应检查( a n t e n n ae f f e c tc h e c k ) 、设计规则检查( d r c ，或d e s i g nr u l e c h e c k ) 和版图逻辑图检查( l v s ，或l a y o u t v e l s l i ss c h e m a t i c ) 。 ( 5 ) 乘法器功能验证 在功能验证方面，采用了模拟验证和形式验证两种方案。通过对乘法器建立 测试平台并编写测试用例以完成模拟验证。同时对乘法器进行形式验证，形式验 证无需测试用例，它从数学推理的角度验证设计的等效性。通过全面的验证保证 了乘法器能正常工作。 浙江大学硕士学位论文 1 5 论文章节安排 本论文针对t s m c9 0 r i m 超深亚微米工艺，采用半定制设计流程，并探索该 流程中可以完善的地方，提出标准单元库扩展的方法，设计快速的1 7 位整数乘 法器部件论文章节组织如下： 第一章为绪论，阐释了课题的背景意义、国内外关于乘法器的研究现状，介 绍了基于单元库的半定制设计方法，以及课题研究工作和章节安排。 第二章讨论了乘法器的结构设计，分析了不同类型乘法器的结构，并针对本 课题选取了合适的乘法器结构。 第三章讨论了乘法器子模块的设计和实现，包括部分积生成模块、部分积压 缩模块，并且讨论了符号位处理方案。 第四章讨论了乘法器的关键路径以及逻辑功效模型，并引出标准单元库扩 展。 第五章具体讨论了标准单元库扩展，并用扩展的单元库对乘法器进行优化 第六章讨论了乘法器的版图实现和功能验证。 第七章为结束语，对本文工作进行总结，并对未来工作进行展望。 浙江大学硕士学位论文 2 乘法器结构设计 2 1 乘法器原理 二进制乘法器实现二进制数的乘法运算它将两个二进制数x 和y 作为输 入，将乘法运算的积z 作为输出设被乘数为m 位，记为x m 1x m 2 x o ，乘 数为1 1 位，记为y n 1y n 2 y o ，则积为m + n 位，记为z 咖1z 咖2 z o 。将 m 位被乘数x 与n 位乘数y 的每一位进行与运算，可以得到n 项位数为m 的部 分积，用加法器阵列将1 1 项部分积相加，得到积z 。 由于乘法运算本质上是一系列累加运算假设被乘数是5 位无符号数，记为 x 4 x 3 x 2 x l x o ，乘数是5 位无符号数，记为y 4 y 3 y 2 y 1 y o 。当x 4 x 3 x 2 x 1 x o = 11 0 0 1 ， y 4 y 3 y 2 y l y o = 1 0 1 1 1 时，其运算如图2 1 1 所示： 图2 1 1 乘法器原理图 部 分 积 最直接的实现方法是：将被乘数的每一位与乘数的每一位进行“与”运算， 这样可以得到5 个位数为5 的项，这些项称作部分积。如图1 所示，箭头指向的 均是部分积。当乘数的位是l 时，部分积为被乘数；当乘数的位是0 时，部分积 为0 显然，在不考虑其他因素的情况下，部分积数目越少，接下来累加运算所用 的时间就越少，实现的乘法器的速度就越快。有以上的分析可知，乘法器的具体 实现分为三个步骤：部分积生成、部分积压缩、最终加法由于最终加法运算通 常由快速加法器实现，而关于加法器的研究工作相对比较成熟，因此，下面主要 从部分积生成和部分积压缩的角度出发，讨论乘法器的结构设计 9 io l o o l l o o o l l o o l l l o 0 l o o o li 浙江大学硕士学位论文 2 2 乘法器结构类型 2 2 1 阵列乘法器 阵列乘法器【1 5 】【1 叼最主要的优势在于其规则的版图，但是它的速度较慢，因 此，在一些对性能要求不高的领域，仍可采用阵列乘法器结构。在阵列乘法器中， 每一项部分积通过将被乘数与乘数的一个位进行与运算得到，与运算可以通过与 门实现。部分积然后根据乘数中该b i t 的顺序移位相加，移位可以通过将部分积 按特定位置对齐实现。 5b i tx5b i t 的阵列乘法器如图所示。乘数最低位y 0 与被乘数的所有位进行 与运算得到一项部分积，记为p p 0 ，其他位y 1 ，y 2 ，y 3 ，y 4 则产生部分积p p l ， p p 2 ，p p 3 ，p p 4 。将p p 0 与p p l 相加，所得到的值再与p p 2 相加，如图2 2 1 所 示1 7b i tx1 7b i t 的阵列乘法器可以用相同的方式实现。 图2 2 1 阵列乘法器 2 2 2 改进的b o o t h 编码乘法器 在乘法器实现中，改进的b o o t h 编码算法是减少部分积数目的有效方法【1 7 1 部分积减少的数目取决于对乘数的多少位进行重新编码。编码时所选取的乘数的 位数越高，可以得到数目更少的部分积，但同时会增加编码电路的复杂度和相应 1 0 浙江大学硕士学位论文 的硬件如果对乘数的连续3 位进行编码，即基4 改进的b o o t h 编码，那么部分 积的数目会减少到原来的一半，部分积压缩所用的时间大大减少采用改进的 b o o t h 编码算法的结构如图2 2 2 所示图2 2 2 中乘法器采用基4 改进的b o o t h 编码算法，乘数的连续3 位经过b o o t h 编码电路产生控制信号，该控制信号作为 移位选择电路的输入与被乘数x 生成部分积【1 8 1 ，图2 2 2 中p p l ，p p 2 ，p p 3 等 表示部分积。对于基4 改进的b o o t h 乘法器，部分积可能的取值为 - 2 x ，x ，0 ， x ，2 x 将生成的部分积输入到部分积压缩模块和快速加法器可以得到乘法运 算的积。 图2 2 2 改进的b o o t h 编码乘法器 2 2 3 树形乘法器 前面阐释了阵列乘法器结构，并得出结论，阵列乘法器的延时与部分积的个 数( 或者被乘数与乘数的位数) 成线性关系因此，当部分积的个数很多时，阵 列乘法器的延时就很大。究其原因，阵列乘法器的高位结果的产生来源于低位结 果的进位，因此，阵列乘法器并未充分挖掘乘法运算中的并行性对此，提出了 一种速度更快的乘法器，即树形乘法器。树形乘法器充分探索乘法运算中的并行 性，将所有的部分积同时进行压缩。因此，相比于阵列乘法器，它有效地提升了 运算速度。树形乘法器的延时与部分积的个数成对数关系。 树形乘法器中，最著名的是w a l l a c e 树形结构，该种乘法器大量采用全加器 进行压缩【1 9 1 全加器具备3 输入2 输出，将3 项部分积同时输入到一组全加器阵 浙江大学硕士学位论文 列中，则输出2 项部分积，因此，全加器又被称为3 2 压缩器。显而易见，对于 n 项部分积，经过一级全加器阵列，可以得到( 2 3 ) n 项部分积；经过第二级全加 器阵列，可以得虱j ( 2 3 ) 2 n 项部分积；经过第三级全加器阵列，可以得到( 2 3 ) 3 n 项部分积以这种压缩算法，直至将部分积压缩到最终两项。可见，w a l l a c e 树形乘法器的延时与部分积的个数成以3 2 为底的对数关系 2 0 1 ，表示为o ( 1 0 9 3 2 ( n 1 ) 以1 7b i tx1 7b i t 二进制数字乘法器为例，采用与门实现部分积：将乘数的每 一位与被乘数进行与运算，可以得到1 7 项部分积，记为p p l 、p p 2 、p p 3 p p l 7 ， 如图2 2 3 所示。经过第一级3 2 压缩器阵列，得到1 2 项部分积，注意这里第一 级压缩阵列含有5 组c s a 阵列，经压缩前面1 5 项部分积，而将p p l 6 和p p l 7 直接作为第二级3 2 压缩阵列的输入第二级3 2 压缩阵列包括4 组c s a 阵列， 这样，部分积被压缩成为8 项。第三级和第四级压缩阵列均包括2 组c s a 阵列， 经过这两级压缩阵列之后，部分积被压缩成为4 项。经过五级压缩阵列之后，部 分积被压缩成为3 项；再经过最后一级压缩阵列，部分积被压缩成为最终两项。 这两项直接作为最终快速加法器的输入，可以得到乘法运算的积值。可见， w a l l a c e 树形乘法器经过6 级c s a 镇流就可以将部分积压缩至两项 图2 2 3w a l l a c e 树形压缩结构乘法器 图2 2 3 中c s a 表示进位保留加法器，一组c s a 阵列表述如图2 2 4 所示 其中虚线框表示一个c s a 加法器，虚线框中包括3 个小正方形表示一个c s a 加 法器的3 个输入，对于只有2 个小正方形的的虚线框可以用一个半加器替代c s a 1 2 浙江大学硕士学位论文 全加器一个3 输入c s a 加法器产生一位和( s l l m ) 和一位进位( c o u t ) ：跚 位权重与加数的权重相同，c o u t 位权重比加数高一级。这里c o u t 位不用直接传 递到同一级c s a 阵列的高位进行加运算，而是保留下来作为下一级c s a 阵列的 输入，如图中的箭头表示这样w a l l a c e 树形乘法器的一级压缩阵列的延时就等 于一个全加器的输入到输出的延时 r 。一一：一：一 i i 口口口口口口口口口口+ 口口口口口：；口口 ；口口口口口口口口口口口口口口：口：口i 口 口口口口口口口口口口口口口口口口+ 口i ： 图2 2 4c s a 阵列示意图 比较进位保留阵列乘法器与w a l l a c e 树形乘法器的性能。1 7b i tx1 7b i t 的进 位保留阵列乘法器的部分积压缩部分的延时等于1 6 级c s a 的延时；而1 7b i t x1 7 b i t 的w a l l a c e 树形乘法器部分积压缩部分的延时等于6 级c s a 的延时。w a l l a c e 树形乘法器大大减少部分积压缩延时，提升了乘法器的性能而且，由于w a l l a c e 树形乘法器的压缩延时与部分积的个数成对数关系，因此，当乘法器的位数越高， 部分积的个数越多，w a l l a c e 树形压缩算法对乘法器的性能提升更加明显。 w a l l a c e 树形压缩结构通过利用乘法运算中的并行性提升乘法器的速度，但 与阵列乘法器相比，这种方法改变了乘法运算中的数据流( d a t af l o w ) 。在w a l l a c e 树形乘法器中，高位结果的生成并不完全依赖来自低位的进位，在低位的进位产 生之前，就可以得到高位的部分信息。这种“过分”利用并行性的方法使得w a l l a c e 树形乘法器的版图十分不规则，而且走线十分复杂，不便于进行定制设计。 针对