（微电子学与固体电子学专业论文）高性能cpu中除法器的设计.pdf

摘要 摘要 c p u 的核心功能之一是实现基本算术运算。在四则基本运算中，除法在技术 实现上具有较高的复杂性，所以硬件除法器的设计一般会成为c p u 设计中的重点 与难点。对于嵌入式c p u 来说，其设计目标更加关心成本的降低，使得其算术运 算单元在性能设计指标上需要有较大的灵活性，从而使硬件占用较小的面积。 本文以国家8 6 3 项目为依托，根据项目的实际需求并结合除法器设计领域新的理 论与实践进展，实现了两种实用的整数除法器。第一种以低成本简约化设计为 着眼点，采用最基本的基数2 算法，以标准加法器作为核心部件，辅以最低限度 的硬件逻辑构成数据通道，实现除法功能；第二种在前一种设计所采用的基本 算法中引入中间数据的冗余表示形式，极大地提高了中间运算的处理速度，使 得一周期内能做两次基数2 ) 1 1 法的中问运算，从而形成一种基数4 算法。与传统 的以r o m 或p l a 等存储部件实现的基数_ 4 除法器相比，这种以基数拆分的方式 实现的基数4 除法器在不损失性能的前提下大幅降低了硬件结构的复杂度。本文 尾部的章节在两种除法器设计的基础上加入传统的基数4 除法器作为参照，对三 者的运算性能、运行速度等做了分析与比较。另外，本文在实现过程中还介绍 了与除法器设计有关的一些设计方法，这些设计方法与除法器本身一样具有实 用价值。 关键词：除法器，基本除法算法，基数- 4r n s 算法，时序展开 a b s t r a c t a b s t r a c t a r i t h m e t i cc o m p u t a t i o ni sak e yf u n c t i o no fc e n t r a lp r o c e s s o ru n i t ( c p u ) a m o n gb a s i ca r i t h m e t i co p e r a t i o n ，d i v i s i o ni st h em o s td i f f i c u l to n et oi m p l e m e n t t h e r e f o r et h ed e s i g no fd e d i c a t eh a r d w a r ed i v i d e ri su s u a l l yt h ev i t a lp a r ti nc p u d e v e l o p m e n t s i n c et h ed e s i g no fa ne m b e d d e dc p u i sm o r ec o n c e r n e da b o u tc o s t r e d u c t i o n 。i t sa l u d e s i g nu s u a l l ye m p h a s i z e so nf l e x i b i l i t yr a t h e rt h a np e r f o r m a n c e t h i so r i e n t a t i o nd e m a n d ss o l u t i o n st h a tc o n s u m em i n i m u md i ea r e a t 1 l i sd i s s e r t a t i o n d e s c r i b e st h ed e s i g na n di m p l e m e n t a t i o no ft w ot y p e so fi n t e g e rd i v i d e r s t h ef i r s t o n ei sa1 0 w - c o s tr a d i x - 2d i v i d e rb a s e do na6 4 - b i ts t a n d a r da d d e ra n dm i n i m u m c o m p l e m e n t a r yl o g i c t h e s e c o n do n ei m p r o v e sp e r f o r m a n c er e m a r k a b l yb y e m p l o y i n gr e d u n d a n t n u m b e rs y s t e m ( r n s ) t h i sa l g o r i t h me n a b l e st h er e a l i z a t i o n o far a d i x - 4d i v i d e rt h r o u g ht w oc a s c a d e dr a d i x 一2r n sk e r n e l c o m p a r i n gt oa t r a d i t i o n a lr a d i x - 4s r td i v i d e rb a s e do nl a r g es t o r a g ea r r a y , t h i sd e s i g ns i g n i f i c a n t l y r e d u c e st h eh a r d w a r es t r u c t u r ec o m p l e x i t yw i t h o u tp e r f o r m a n c el o s s u s i n gar a d i x - 4 s r td i v i d e rd e s i g na sa r e f e r e n c e ，c h a p t e r4c o m p a r e st h r e ed i f f e r e n td e s i g n si nt e r m s o fa l g o d t h m e t i ce f f i c i e n c ya n dt i m i n g d e l a y e f f i c i e n t i cb a c ke n dd e s i g n m e t h o d o l o g y , w h i c he n s u r e sc h i pp e r f o r m a n c e ，i sd i s c u s s e da l o n gw i t ht h ed i v i d e r s k e yw o r d s ：d i v i d e ru n i t ，b a s i cd i v i s i o na l g o r i t h m ，r a d i x 4r n sa l g o r i t h m ，h a r d w a r e l o o pu n r o l l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版：在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月 日 望 v 、伊n1 轹挑别，月 利了 作 年 艾， 论电 位汐鬻 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名去霉 劢叼年3 月功日 第1 章引言 第1 章引言 1 1 计算机算术理论在c p u 设计中的地位 尽管在电路层级上提高系统的运行速度面临越来越大的困难，但过去二十 年来计算机系统结构的发展仍然使计算机硬件的性能获得巨大提升，这种趋势 还将持续下去。如果没有对计算机内部结构在理论上的深入研究与实践，这种 进步是不可能实现的，而计算机算术( c o m p u t e ra r i t h m e t i c ) 又是这些研究与 实践中至关重要的部分。 c p u 的设计者要实现设计目标：设计出结构简易紧凑，高性能，低功耗、低 成本的芯片，对计算机算术的理解是其中的关键之一。计算机算术是计算机系 统结构( c o m p u t e ra r c h i t e c t u r e ) 领域中历史最久的组成部分，并且一直在评 测计算机功能和性能的标准中占据重要地位。 c p u 的主要设计目标是高效性和通用性，所以c p u 一般在内部配备独立的硬 件运算单元实现基本算术运算。近年来，计算机技术的实际应用对计算速度和 精度的要求不断提高。另外，一些计算性能评测标准如s p e c m a r k s 等在业界的 使用也越来越广泛，这些都使得c p u 的设计者对运算单元的设计投入越来越多 的精力。 基本算术运算包括加、减、乘、除四种，分别以硬件加减法器、乘法器和 除法器来实现。回顾一下近年来c p u 设计的改进，可以发现，为了提高性能所 做的大部分努力都花在设计更快的加减法器和乘法器上，除法器设计相对来说 所受的关注较少。一般来说，加减法操作所耗费时间的典型值是l 到4 个周期， 乘法操作是2 到8 个周期，而除法操作则是从少于8 周期到多于6 0 周期不等。 软件设计者一般认为除法是一种较少用到的操作，不需要较高的优先级。但是， 研究显示，如果忽视除法操作的实现，在一些应用环境中会造成显著的性能降 低嘲。实现除法操作的技术复杂度高于实现加法或乘法，部分原因是因为从算法 到硬件实现细节上可能的选择都比较多，而具体设计一个怎样的除法器，则应 根据c p u 的定位及性能的需求来决定。 第1 章引言 1 2 算术运算单元的设计所面临的挑战 算术运算单元的设计作为c p u 设计的核心组成部分的地位近几十年来一直 没有改变。在这几十年内，无论是计算机体系结构理论还是半导体制造工艺都 有了突飞猛进的发展，这给在新的系统与工艺条件下设计算术运算单元带来了 挑战。由于计算机系统主频不断地提高，流水线结构被广泛运用并具有深化的 趋势，流水线的一级所能容纳的逻辑深度越来越小，致使一些在计算机算术学 科发展的早期所提出的一些复杂的算法和逻辑结构不再适用；另外，在器件工 艺进入深亚微米和超深亚微米级别的条件下，物理器件表现出一些特殊的行为 特性，与较大尺寸工艺相比，器件的工作速度相对来说不是在加快，而是在减 馒，这种情况在1 0 0 纳米以下工艺中表现尤为明显，上述两种情况都要求算术 运算单元的设计者不断研究新的算法和实现方式，新的研究应以以下目标为努 力的方向：算法更加易于理解和验证，在日渐庞大的设计规模中能有效地节省 资源并保证设计的正确性；逻辑结构更加简单，逻辑深度能有效地降低，易于 后端实现：结合后端工艺的新进展，采用符合最新工艺的器件类型；以及在此 前提下，不断地提高算法与系统的性能。 1 3 本文所依托课题的背景介绍 本文所依托的项目“6 4 位高性能嵌入式c p u 设计”是同济大学微电子中心 在c p u 设计领域的发展规划中的重要一环。通过该项目的研究实践，微电子中 心将完成c p u 设计由3 2 位到6 4 位，以及主频超过1 g h z 的跨越，并为更高阶 段的设计目标傲技术积累。项目所设计的c p u 拥有自主知识产权，使用先进的 9 0 纳米工艺，处理器主频能达到1 g 以上。该产品将有望满足国内市场对自主产 权微处理器的巨大需求，可广泛应用于国民经济各个部门，尤其是在电子政务、 通讯信息行业和计算机行业等。6 4 位c p u 可使用在机顶盒、数字高清、路由器、 n c 服务器等产品中。 该项目将使用目前国内领先的全定制设计流程。使用全定制方法可以使芯 片上的功能块布局更加紧凑，有利于进一步的功能扩展；让内部连线更短，易 于实现系统集成；使功耗更小，延迟更短，连线串扰得到进一步的抑制，从而 实现更高的工作速度，使芯片性能、质量和成本都达到最优。 2 第1 章引言 1 4 本文的内容及安排 本文的内容安排把设计和具体实现的过程放在最重要的位置。为了避免理 论与实现内容的脱节，本文没有把除法算法方面的内容单独分出介绍，而是与 具体实现相结合，按照所实现的除法器的类型统一划分内容。文中以算法的基 本要素作为切入点，步步深入做分析与介绍，各部分内容的逻辑联系紧密。 本文第一章为引言，第二章介绍基本除法器的原理与实现。首先介绍d i g i t r e c u r r e n c e 算法的基本理论，包括算法的数学表述、基数、商取值与部分余数的 收敛等。2 2 节是对基本除法算法的具体分析。在算法的核心部分之外，为了具 体实现又增加了商的实时转换和结果调整等内容。在介绍基本除法器的具体实 现之前，2 3 节先介绍了一些后端设计方法，这些设计方法贯穿后面介绍的所有 设计过程，2 4 节与2 5 节介绍了基本除法器的具体实现，包括电路设计与物理 设计。 第三章与第二章的结构大致相同。其内容以数据的冗余表示形式为切入点， 在前一章理论部分的基础上通过逐步分析介绍算法的各种基本要素，最终展现 了一种新的算法基数2r n s 算法的全貌，并通过使算法核心在一周期内串 行的方式，实现了基数- 4r n s 除法器。本章在硬件设计部分初步分析了基数_ 4 r n s 除法器在系统速度方面相对传统的基数4 算法所具备的优势。作为比较的 参照之一，第三章还介绍了基数- 4s l i t 算法以及它的传统的实现方式。 第四章介绍除法器的验证、仿真并对结果进行了较深入的分析和比较，通 过实际数据进一步说明了不同的设计之阅的差异。 第五章对全文内容及工作做了总结。 1 5 本文的主要创新点 商选择逻辑是除法算法的核心部分，它的设计与实现方式决定了除法器的 主要特性。本文针对基数2r n s 算法设计了一种新的算法核心和它的实现方式 ( 见3 1 3 小节) ，并且通过在一周期内串联两个基数- 2r n s 运算核心而实现一 种基数4r n s 除法器( 见3 3 1 小节) 。与传统的基数- 4s r t 算法的商选择逻辑 相比，这种算法核心的形式简单，容易验证，从而大大降低了在保证设计正确 性方面所面l 临的风险，同时又保持了基数- 4 算法的运算性能( 见4 1 节) 。 3 第1 章引言 在硬件设计方面，本文从设计的观点除法分析了基数2r n s 算法的商选择 逻辑的细节，在此基础上设计了一种十分简洁的硬件结构( 见3 3 3 小节) 。在 基数- 4r n s 除法器中采用这种商选择逻辑结构能完全发挥3 2 加法器速度快的 优点，而传统的基数一4s r t 除法器的商选择逻辑一般是基于复杂的存储阵列来 实现。与其相比，本文设计的硬件结构在逻辑延迟方面具有明显的优势( 见4 2 节) 。 另外，在文中作者结合自己的经验与相关理论知识，介绍了与后端设计有 关的一些设计方法( 见2 3 节) 。这些方法的内容与除法器的设计紧密结合，有 较强的针对性，并在其后大部分的硬件设计过程中得到体现。但是，这些方法 并不仅适用于本文所介绍的除法器设计，它们又具有普遍性，其本身与除法器 设计一样具有实用价值。 4 第2 章基本除法器的设计 第2 章基本除法器的设计 2 1 d i g i tr e c u r r e n c e 算法基本理论 2 1 1 综述 如果不考虑实现细节，仅从算法层面上来划分，除法算法大致可以分为两 类：d i # tr e c u r r e n c e 算法和f u n c t i o n a li t e r a t i o n 算法。 d i g i tr e c u r r e n c e 算法是类似于笔算形式的，以循环加，减作为中间运算，每 次循环产生一位( d i g i t ) 商算法，它的特点是形式以及对应的硬件结构比较简 单，容易实现。通过采用不同的算法参数( 如基数、商冗余度等) 和实现方式， 可以使算法的性能在很大的范围内浮动，具有较大的灵活性，可以满足不同定 位的硬件设计需求。从历史上看，d i g i tr e c u r r e n c e 算法也是被采用最多的一种 算法，设计实例中既包括低端的嵌入式c p u ，也包括高端的桌面式通用c p u 。 f u n c t i o n a li t e r a t i o n 算法则采用形式完全不同的迭代函数，以乘法作为中间 运算，使得操作数( 被除数) 在迭代过程中逐渐趋近于结果( 商) 例如如下形 式的迭代函数： q 。三。缝：盐 ( 2 1 ) d 啦。j x ( i ) - - - x ( _ “， 在式( 2 1 ) 中，z 为被除数，d 为除数，q 为商。如果能找到一系列的因 子o ) ) + 1 ) ，使得除数d 与这些因子相乘而结果逐渐趋近于1 ( 即式( 2 1 ) 的分母部分趋近于1 ) ，那么式( 2 1 ) 的分子部分就将趋近于商q 。为了达至ul - _ 述目的，可以令： f d ( f “) i d 鼍o ) t 1 ) ， 哦d ) i 矗； z ) z x ( o 1 ) ” 孙) - z ； ( 2 2 ) i ) 一2 - d ( f ) 式( 2 2 ) 是这种算法的循环形式表达。在具体实现中，硬件电路不断执行 5 第2 章基本除法器的设计 式( 2 2 ) 所表示的循环。当z “+ 1 ) 与q 之间的误差足够小时，就可以认为得到 了正确的商结果。 f u n c t i o n a li t e r a t i o n 算法的主要特点是所需的循环次数较少。以上面所介绍 的算法为例，计算出q 所需的典型的循环次数是l o g ：k 次，k 为被除数的位宽。 相对来说，d i g i tr e c u r r e n c e 算法一般需要j r _ ( r 为基数，k 为被除数位宽) j 0 9 2 r 个循环周期。但是f u n c t i o n a li t e r a t i o n 算法实现起来具有d i g i tr e c u r r e n c e 算法所 不可比拟的复杂度。由于以乘法作为中间运算，所以需要设计快速的乘法电路， 而乘法电路内部结构复杂，关键路径比较长，一般会成为整个系统速度上的瓶 颈。另外，实现f u n c t i o n a li t e r a t i o n 算法也需要耗费较大的面积。这一类算法一 般应用在高端的桌面式c p u 架构中，例如a m d 。的k 7 架构。对于成本较低， 性能设计指标有针对性的嵌入式c p u 来说，采用d i g i tr e c u r r e n c e 算法是比较 普遍的选择，本文所实现的两种算法都属于这一类。由于d i g i tr e c u r r e n c e 算法 具有很强的共性，另外，先了解d i g i tr e c u r r e n c e 算法的基本理论也是进行技术 实现的前提，所以在本节先对这些基本理论进行介绍。 2 1 2 数学表述 纯数学意义上的整数除法公式可以写成如下形式： f z q d ；r 悯 o 式( 2 3 ) 中，z 是被除数，d 是除数，q 是商，r 是余数。根据整数除法 的定义，余数r 需要满足两个条件：1 、绝对值小于除数；2 、与被除数同号( 0 除外) 。在实际的运算过程中，商q 是逐位产生的，不妨把q 与z 写成各位相加 的形式： 其中q k 。，q k 一：q o 就是在运算过程中逐个产生的商位( d i g i t ) ，为基数 ( r a d i x ) 。把式( 2 4 ) 代入式( 2 3 ) ，就得到： 6 d2 吼 + + 7 丫 气吼 + + 吣心 轧 + + 4 以 一” d 4气吼 一 霉 z q 第2 章基本除法器的设计 瓴- l 一1 + 钆一，+ z 。) ( 2 5 ) 一( 吼- l r 一+ q k 一2 r 一24 - - + 鼋l r + q o ) d t r 式( 2 5 ) 可以进一步改写为如下形式： “( ( z i l q k l d ) 。r + 2 一吼一2 d ) ，+ + 毛- q l d ) ，+ z o q o d 暑r ( 2 6 ) 式( 2 6 ) 具备了循环迭代的形式，如果再设置一个中间变量m j 】，那么式( 2 6 ) 又可以改写成： 式( 2 7 ) 反映了d i 醇r e c u r r e n c e 算法的一种实现方式，它显示了被除数通 过多轮的减法中间运算最终得到余数，并在中间运算中逐位产生商的过程。式 中的中间变量。是部分余数，它是被除数( 输入) 与余数( 输出) 之间的中间 形式。d i i s i tr e c u r r e n c e 算法大体上都具有式( 2 7 ) 的形式。对于不同的实现可 以选取不同的参数，例如基数r ，商位q ，的取值范围，等等。这些参数不同时， 循环需要的次数k 也不同。下图以十进制( r ；1 0 ) 除法的形式标示了式( 2 7 ) 中的各个量。图中显示的除法过程是按照平常习惯进行笔算时的过程，不是硬 件电路中的运算过程： 7 q阵 d d 碧础 第2 章基本除法器的设计 2 1 3 基数 除数d ；1 2 1 2 葡蕊0 1 0 2 8 - - - - * 商饭q 除= 数1 0 2 2 8 ：1 2 3 4 5 嫂 0 1 ，i 4 1 4 1 0 1 2 一一，1 4 l r + z 3 。1 2 0 1 2 一吼d 。1 2 0 0 0 + i 3 】= 0 0 0 0 3 0 0 0 0 0 0 0 3 - - - - * w 1 2 l 5 3 0 0 0 3 4 幽 0 0 0 1 0 _ w t l l = 1 0 0 0 0 1 0 5 幽迦堑 伽0 0 0 9 - + 余数r w t0 1 。9 图2 1d i g i tr e c u r r e n c e 算法实现过程示意图 对于以r 进制形式表示的整数来说，各个位上的数值是。啊，厅。， 并且= 一1 r ”1 + n 。一2 r ”2 + + n 1 r + n o ，其中的r 就是基数。在除法算法的 具体实现中，数据总是以二进制形式来表示的，所以对d i g i tr e c u r r e n c e 算法来 说，基数大小就代表每次循环能产生多少位二进制商值。下图显示了对相同的 操作数( 二进制) 分别做基数2 除法和基数4 除法的过程： 图2 1 基数一2 除法与基数一4 除法过程示意图 8 =i甲i由|o i 珂三 r ：|呷副赵驾 第2 章基本除法器的设计 图2 2 中使用的是计算机算术中常用的圆点示意图( d o tn o t a t i o n ) 。图中每 个圆点表示一位数值。由于只是用来示意算法，所以不用关心它的值具体是什 么。图2 2 中的实心圆点表示一位二进制数值，空心圆点表示一位四进制数值， 当它转化为二迸制形式后需要以两位来表示。可以看到，基数2 除法运算过程 的循环次数是基数一4 除法的两倍。 2 1 4 商取值与部分余数的收敛 根据整数除法的数学定义，余数的绝对值应该小于除数，算法的具体实现 必须保证这一点，普遍使用的办法就是使循环过程中产生的每一个部分余数的 绝对值都满足这个要求，即：满足k c 蚓( 在具体实现时可以认为l m 一一川也 满足要求，只要最后对结果做必要的调整) 。这叫部分余数的收敛。部分余数的 收敛需要由适当的商值选取规则来保证。回顾图2 1 所示的除法过程，当部分余 数嘶：】一3 时，m 2 1 * + z i 一3 4 ，此时需要取商值统一2 ，才能保证下一轮部分余 数h 。一1 0 c 】d i 。一般来说，取商的最大值为，一1 ，再加上正确的商选择规则， 可以满足部分余数收敛的要求。例如在十进制整数除法里，商的最大取值为9 。 在图2 1 所示的除法过程中，商取值范围为q e 0 , 9 】，这完全符合人们笔算时的 习惯。在以硬件电路实现时，也可以有完全不同的商取值范围，例如允许商取 负值。本章后面所介绍的基本除法器，商的取值范围就是鼋， 一1 ，1 ) 。在实际实 现中，商选择逻辑一般是d i g i tr e c u r r e n c e 除法器中所耗用面积较大，时延较长 的部分。特别是对于高基数算法( 基数r 2 ) 的除法器来说，设计面积小、速 度快的商选择逻辑是整个除法器设计的核心。 2 2 基本除法算法 本章中所设计的基本除法器实现的基本除法算法是d i g i tr e c u r r e n c e 算法中 基数2 算法的一个特例。它以全进位加法作为中间运算，并且不对操作数进行 预移位处理，也不对中间产生的部分余数进行检测。基数2 算法一般都具有相 近的运算周期数，本文所列的参考文献一脚介绍的就是采用基数一2 算法的除法 9 第2 章基本除法器的设计 器实现。 当被除数的位宽为“位时，基本除法算法的运算过程包含“次循环。这 种算法是d i g i tr e c u r r e n c e 算法中最基本的一种。它的优点在于结构简单，不需 要专门设计复杂的商选择逻辑，所有的硬件都可以采用标准器件( 如寄存器、 数据选择器、加法器等) 拼接完成，可以极大地缩短设计周期。从实现成本上 来看，基本除法器也是结构非常紧凑的一种除法器，仅一个6 4 位进位传播加法 器就占了总面积的大部分。基本除法器是d i g i tr e c u r r e n c e 算法实现的基础，也 是本文所依托的项目所实际采用的除法器设计。 2 2 1 综述 在本文的设计所关涉到的c p u 架构中，算术运算部分的操作数都是以2 的 补码佗sc o m p l e m e n t ) 形式表示的。对于负数来说，2 的补码是以 一m ( 肼，0 ，k 为数据的位数) 来表示一j | l f ，例如，对于4 位二进制数0 0 1 1 来说， 对应的十进制数是3 ，一3 就以2 4 0 0 1 1 = 1 1 0 1 来表示。由于基本除法算法在运算 开始莳不对操作数进行预移位处理，所以当被除数为负数时，要先求补变为整 数再进行运算。下面是用基本除法算法实现四位数除法一6 + 3 的过程： 1 0 第2 章基本除法器的设计 嵋4 4 化仃纷 除法( 一6 ) ( + 3 ) 的过f 、! ： 1 ，1 0 1 0 0 ，0 i 0 1破除数求补 、漉茹 0 ，0 0 0 0 ，1 1 0 、蒜羔一 l ，1 0 1 1 ，1 0 、蒜芸一 q 4 = 1 移位 r 4 为止， 禽贫 i n 工t 减 q 3 = o i t e r r 3 为负，肌i q 2 = 0 1 ，1 1 0 1 ，0 i t e r 怖1 、蒜茹一二嚣一 0 ，0 0 0 0 i t e r o、豢 + ，1 1 0 1 + ) 0 ，0 0 1 1 + ，0 0 0 0 + ，1 1 1 1 + 0 ，0 0 0 1 ，0 0 0 0 ，1 1 0 1 + ) 0 ，0 0 0 1 + ，1 1 1 0 减 一q 0 = 0 余数渊枢， f i n l 加除数的绝x , t f i 。 余数纷i j 搿整， r a f 求； j j 蔡致：0 一 q 3 q 2 q l q 0 ) r s a l 新渊蝗，求仆 j j 赢，二， q a 一完成一 ( ”+ ”农，j j j e f l l 4 - 欠，d ， 艘什f i m m 篮保仃伯吁化) 图2 3 基本除法算法的执行过程 图2 3 表示了基本除法算法在硬件电路中的实际执行过程。在运算开始前对 操作数进行了符号扩展，使它们交为5 位数，这是为了兼容无符号数的格式。 在运算过程中，符号位与其它位一样需要用硬件保存。因为被除数 0 图2 4r a d i x - 2 写回算法的商值选取规则 图2 4 既表示了商值的选取规则，又解释了这种商选取规则如何保证部分余 数的收敛。图中横坐标轴m r + 2 h 表示前一轮部分余数嘶，】移位( 乘以基数) 后再补上被除数的一位以后的值，就是准备用来试商的值，纵坐标轴w 【_ 1 1 表示 试商后的结果，就是本轮的部分余数。由于两者之间具有如下关系： 嘶j - l l - w f 7 + 。h 一日j - l d ( 见式2 1 7 ) ，所以图2 4 中就以两条粗线分别表示本 轮的商值q 分别取0 和1 时的情形。当m f l ，+ 2 h 0 图2 5r a d i x - 2 非写回算法的商值选取规则 同样，非写回算法也是按照除数d ，0 进行运算，把符号留在运算结束后处 理。当w 【i 1 ，+ 2 j l o 时取鼋- 1 w i 1 r + z 卜1 o 时取鼋- - 1 。这样，部分余数m j 一1 】 就有可能为负值，像图2 3 显示的那样。它的取值范围是【一，d 】，仍然满足 1w l 门i - i d i 的条件，所以部分余数仍然是收敛的。 1 3 第2 章基本除法器的设计 需要说明的是l m n i - j d i 的情况，这种情况只有当m m l = o 时才会出现。因为 按照2 的补码格式，0 的符号位与正数一样，也是0 ，所以o 与正数做同样处理。 这种情况不影响后面运算过程中部分余数的收敛，唯一的问题是出现，、；0 而 i l i = 川的情况，就像图2 3 显示的那样，这是个特例，这种情况可以靠最后的 结果调整来解决，见2 2 4 小节。 与写回算法相比，非写回算法不需要“试商”的过程，仅根据部分余数的 符号位就可以决定商值，所以采用非写回算法可以使硬件逻辑达到最简化。两 种算法在数学意义上是等价的，它们的结果转换成同样的表示形式后完全相同。 2 2 3 商的实时转换 按照c p u 架构定义对内部数据格式的要求，运算单元的输出应该和输入一 样，也是以2 的补码的形式表示，所以采用非写回算法时，以 一1 ，q 表示的商需 要转换成以 o ，1 表示的标准形式。如果这种转换需要耗费多余的硬件逻辑和周 期，那么非写回算法相对来说就不具备明显的优势。实际上，这种格式转换可 以和商的产生同时进行，即商的实时转换( o n t h e f l yc o n v e r s i o n ) ，并且不需要耗 费多余的硬件。它的原理如下： 随意给出一个以 一1 ，1 表示的二进制数，如：1 1 1 - 1 1 1 1 1 ，与它等价的 2 的补码格式是1 0 0 0 1 0 1 1 。把两个数放在一起就可以看出转换的规则： 冗余表示形式：1111111 1 2 的补码形式： 1 0 00 1 011 图2 6 基本除法算法商格式转换的原理 图2 6 中的两个箭头表示冗余格式中所包含的借位链，消除冗余格式中的借 位链之后就可以得到标准形式。借位链是由各个位中的“1 ”( 或一连串的“一1 ”) 造成的。要消除借位链，只要将一连串“1 ”中的最后一个换成“1 ”，其余的换 成“0 ”，再将这串“1 ”前的一个“1 ”换成“0 ”即可。容易看出转换前后两种 形式的数是等值的。由于所有位的数值都由“1 ”和“1 ”构成，一连串的“一1 ” 1 4 第2 章基本除法器的设计 造成的借位一定可以被前面的一个“1 ”吸收而不会一直传播下去，所以这种形 式转换规则非常简单。 上述转换规则只要稍微改动一下，就可以得到用于硬件实现的更加简单的 规则，如下图所示： 冗余表示形式 2 的补码形式： ，1000 1011 舍弃 图2 7 商格式转换的硬件实现原理 气 补1 图2 6 所示的关键，在于使两种格式的商产生的时间错开一个周期，这样两 种格式各个位的数值就完全对应起来，“1 ”对应“1 ”，“1 ”对应“0 ”，而唯一 的特例是运算的开头和结尾。在运算的开头，当对被除数进行符号调整完毕后， 最高位的商就产生了( 图2 3 中的q 4 ) ，由于调整后的被除数为正，所以这一位 商值一定是1 ，但是这位商要被舍弃，如图2 3 所示的那样。在运算的过程中， 如果按照冗余格式应该商1 ，按照标准格式就仍然商1 。如果按照冗余格式应该 商1 ，实际就商0 。在运算结束之后，要在商的最后再补上一个1 ，如图2 6 所 示。可以看出，在具体实现时，只要将每一次循环所求得的部分余数的符号位 取反就可以得到相应的商值，这种商选择逻辑非常简单而易于实现。 回顾图2 3 所示的过程，首轮产生的商值日。被舍弃了，但是运算过程的最后 一轮( 图中的f i n l ) 并没有补1 ，而是仍然按照中间过程的规则取商。实际上， 补1 的操作被放到商调整周期( 图中的q a 周期) 处理了，这样是为了保持商选 择逻辑的简单性和一致性。另外，把补1 放到后面处理也不会使商调整周期的 逻辑更加复杂，见2 2 4 小节。 2 2 4 结果调整 运算周期后面的三个周期( 图2 3 中的r a 、r s a 和q a 周期) 是结果调整 周期，这三个周期对求得的最后一轮部分余数和商值进行调整，得到最终的余 数和商。结果需要调整的原因有三个：1 、按照整数除法的数学定义，余数需要 与被除数同号。因为基本除法算法是把被除数变为正数进行运算，所以最后一 轮部分余数应该为正。算法的商选取规则并不能保证这一点，所以如果出现最 1 5 第2 章基本除法器的设计 后一轮部分余数为负的情况，需要加上除数的绝对值，相应地商也应该减1 ( 商 选取规则认为除数d 同样是正数，见2 2 2 小节) 。2 、由于将被除数变为工f 数进 行运算，另外除数也有正、负两种情况，所以需要根据情况对余数和商的符号 做调整。3 、由于前面所叙述的原因( 由于商格式转换造成的末位补1 和由于余 数调整造成的减1 ) ，商还需要另外的调整。结果调整的规则如下： 余数调整( 图2 3 中的r a 周期) ：当最后一轮部分余数w f 。i ( 图2 3 中的r 0 ) 小于0 时需要做余数调整，将w t 。加上除数的绝对值使它变为正数，相应地商需 要减1 。 余数符号调整( 图2 3 中的r s a 周期) ：当被除数为负数时需要做余数符号 调整，将余数调整的结果再求补变为负数。 商调整( 图2 3 中的q a 周期) ：当被除数与除数异号时需要做商调整，将 运算周期中逐位得到的商求补。 对于商调整的规则必须做如下说明：回顾2 2 3 小节，由于商的格式转换而 需要在末位补1 ，所以最后一轮的商值( 即图2 3 中的吼) 必须为l 。如果因w 【。】，0 而导致- 1 ，这种情况不会有问题。如果因w t 。lt 0 而导致吼= 0 ，那么商需要 加1 。但是。】t0 刚好又是需要做余数调整的条件，而余数调整需要商减1 ，两 者的作用刚好抵消，结果就是，商调整只跟两个操作数的符号有关。 2 2 5 逻辑归纳 本节前面的部分已经把基本除法算法的各方面都做了介绍与分析。为了清 楚起见，可以在这些分析的基础上把基本除法算法的时序列成一张表： 1 6 第2 章基本除法器的设计 表2 1 基本除法器的时序归纳列表 周期描述操作 l n | t初始化( 被除 如果被除数0 ，执行以下步骤： 数调整)1 被除数求补变为正； 2 扩展为1 2 9 位( 含符号位) ，高位补0 ，高6 5 位为 首轮部分余数w 1 6 4 1 ；除数扩展为6 5 位。 3 左移一位，原b n ，2 7 移入符号位。 如果被除数 0 ，只执行步骤2 、3 。 r r e r 循环 ( 6 3 ) 1 若上一轮部分余数w 【j + l l 与除数同号则以w t ，+ 1 】2 + z ，减去除 数，否则加上除数- 结果为本轮部分余数w l ：i - 2 若叶门 0 则本轮商1 ，否则商0 - 3 w l l 左移一位( 符号位舍弃) 末位补上2 i 卜1 i ，得到 w t 2 + 。，- 1 。 f i n l最后一轮循环 o l 不再移位，其它同i t e r 。 r a余数调整 如果需要，w t o l 加上除数的绝对值 r s a 余数符号调整如果需要，将r a 的结果求补得到余数。 q a 商调整 如果需要，把q n 吼 求补得到商 表2 1 说明了基本除法器的时序。在i n i t 周期中，为除数和调整后的被除 数增加一位符号位是为了兼容无符号格式。符号扩展后所有数据都变为有符号 格式，这样在后面的运算过程中就可以根据符号位来进行逻辑判断。 1 7 第2 章基本除法器的设计 表2 2 基本除法器调整周期的情况列表 情况被除数符号除数符号 w 【o l 符号 余数调整余数符号调 商调整 ( r a )整( r s a )( o a ) 1+ 否否否 2+ 是否否 3+ 否是是 4+ 是是是 5+ 否否是 6+ 是否是 7+否 是 否 8是 是 否 表2 2 说明了结果调整周期的情况。表中“是”表示需要，“否”表示不需 要。在具体实现中，如果不需要某种调整，那么相应的周期就不做任何操作， 将输入直接传递到下一周期。 另外，需要说明的是：硬件并没有真正产生m j l 2 + z ，。，而是将w i 2 + z i 。 的符号位预先舍弃了( 见图2 3 ) 。实际的做法是叶1 左移一位后末位补上z 。， 原符号位舍弃并将数据部分的最高位填入符号位。这样不会造成问题，因为商 选择逻辑保证了m 门2 + z h 与- q 卜一异号，所以m 门2 + z - q j _ f l 的数值不会溢 出，结果总是正确的，即使操作数为无符号格式时也是如此。 2 3 一些后端设计方法介绍 在介绍基本除法器的后端实现( 包括电路设计和物理设计) 之前，本节先 对后端设计所关涉到的一些设计方法进行介绍。这些设计方法是作者在自身实 践的基础上结合一些理论知识加以总结得到的。在设计过程中注意运用这些方 法可以达到事半功倍的效果。 1 8 第2 章基本除法器的设计 2 3 1 电路并行结构的设计方法 并行是电路结构设计的关键议题之一，在一周期内，如果使不同的硬件逻 辑在同一时间段内并行处理，就可以提高系统的运行速度。所以，设计出高度 并行的电路结构是达到高速度、低成本的设计目标的捷径。但是，硬件逻辑的 并行度并不是可以无限提高，因为并行度取决于内部数据之间的相关性。所以， 并行度实际上是由算法决定的，并行结构设计的目标也就是在面积等成本一定 的条件下，尽量将算法中所包含的并行度加以利用。 下面的例子说明了硬件逻辑的并行以及数据的相关等概念。 对于一个简单的算法：s - a x b + c x d + e + f + g ，如果要以加法单元和 乘法单元作为基本部件来进行硬件实现，那么下面三种实现方法有明显的区别： a b c d a b c d a b c d e f s 图2 8 电路并行结构的设计 1 9 s s 第2 章基本除法器的设计 图2 8 所示的三种实现方法中每一种都使用了两个乘法单元和四个加法单 元。也就是说，它们的面积应该是近似相等的。但对系统的运行速度来说，第 一种最慢，它的时延是气+ 4 t ( t 与f 分别是乘法单元与加法单元的时延) ；第 二种是气+ 3 t + ；第三种最快，时延是t 。+ 2 f + 。 第三种实现之所以达到了最短的时延，在于它最大限度地利用了算法所包 含的并行度。它的硬件逻辑中出现了如下几个中间数据：z ；彳b ，瓦c x d ， 五一e + f ，瓦= 互+ e ，疋= e + g ，如下图所示： 图2 9 中间数据的相关性 s 可以看出，瓦，乏，五是第一级逻辑的输出，它们的输入之间没有交集，所以夏、 互、五是不相关的，以它们作为输出的硬件逻辑之间可以并行。，五与互之间也 一样。 上面的例子说明了组合逻辑的结构优化对于系统设计的重要性。这种分析 与优化的方法也适用于其它算法的系统设计，在后面除法器的实现过程中将会 用到。 2 3 2 硬件时序结构的优化方法 因为实用的除法算法都是以“循环迭代”的方式完成中间运算，所以除法 器硬件整体上呈现循环结构。在介绍除法器的后端实现之前，专门讨论一下对 硬件循环结构在并行度方面进行优化的方法是必要的。 硬件循环结构中一定包含时序部件，例如寄存器等，用来对时序加以划分。 对于算法上连续的运算过程，具体实现时可以有不同的时序划分方法，而不同 的时序划分方法往往导致不同的系统工作效率。下面的例子可以说明这一问题： 第2 章基本除法器的设计 i n l l n 2 0 u t l 图2 1 0 循环结构算法示意图 图2 1 0 是一个循环形式算法的示意图，最初的输入为i n l 与i n 2 ，中间的处 理过程是由两个函数n 与f 2 构成的k 轮循环，最终产生输出o u t l 与o u t 2 。如 果直接以硬件实现上述算法，可以得到如图2 1 l 所示的硬件结构： i n li n 2 0 u t l 0 u t 2 图2 1 1 算法的硬件实现方式1 图2 1 1 中的n 、f 2 分别表示实现两个函数的硬件模块。可以看到，在一个 循环周期内，n 和f 2 的处理过程是串行的，像算法中所表示的那样。如果要对 这种硬件实现在并行度上进行改进，可以先把算法在时序上展开，从全局角度 2 1 第2 章基本除法器的设计 重新考察： 图2 1 2 循环形式算法的时序展开 图2 1 2 对图2 1 0 所示的算法在时序上展开，虚线表示不同的时序划分方 法。可以看到，按照图中第二种方式划分时序，可以使n 与f 2 的处理过程并行， 这导致如图2 1 3 所示的硬件结构： 图2 1 3 算法的硬件实现方式2 2 2 第2 章基本除法器的设计 图2 1