（电子科学与技术专业论文）x处理器浮点除法部件的研究与实现.pdf

国防科学技术大学研究生院硕士学位论文 a b s t r a c t t h eu n i to f f l o a t i n gp o i n td i v i s i o ni so n eo ft h em o s to ft h ec o r ec o m p o n e n t so fh i g h p e r f o n t l a n c em i c r o p r o c e s s o r ，a n di t ss p e e du s u a l l yb e c o m e st h eb o t t l e n e c ko fa m i c r o 。p r o c e s s o r sp e r f o r m a n c e s ot h er e s e a r c ha n dd e s i g no fh i g hp e r f o r m a n c e m i c r o - p r o c e s s o r sf l o a t i n gp o i n td i v i s i o nu n i th a v eg r e a ta n di m p o r t a n tv a l u ei nr e a l a p p l i c a t i o n s t h er e s e a r c hr e s u l t so ft h i sp 印e rm a i n l yc o n t a i ns e v e r a lp o i n t s 1 a n a l y z eh i g hp e r f o r m a n c ea l g o r i t h mf o rf l o a t i n gp o i n td i v i s i o no p e r a t i o n ； d e s i g na n di m p l e m e n t4 - r a d i xs r tf l o a t i n gp o i n td i v i s i o nc o m p o n e n tw h i c h f i t si nw i t ht h en e e do fx p r o c e s s o r 2 t h e p a t h o fe x p o n e n tu s e st i m e - d i v i s i o nr e u s ep r e a d d i n g12 b i t s c a r r y 1 0 0 k a h e a da d d e rt oc a l c u l a t en u m b e r si n c l u d i n gt h ed i f f e r e n c eb e t w e e nt h e d i v i s o ra n dd i v i d e n d ，d e c r e a s i n gt h ed i f f e r e n c e ，a n di n c r e a s i n gt h ed i f f e r e n c e a n da f t e rt h i s ，c h o o s et h ee x p o n e n tf o r mo ft h ed i v i s i o n sr e s u l ta c c o r d i n gt o t h en o r m a lf o r mo ft h eq u o t i e n t 3 o p t i m i z et h ef l o a t i n gp o i n td i v i s i o nc o m p o n e n t ，u s ef a s tc o n v e r s i o nm e t h o d i n t ox m i c r o - p r o c e s s o ra n dc o n v e r tt h eq u o t i e n to fs i g n e ds e tt ot h es t a n d a r d b i n a r yc o m p l e m e n t 4 u s ep r i m a r ys p e c i a ld a t a ，b o u n d a r yd a t a ，i e e ec c 7 5 4s t a n d a r dt e s tv e c t o rs e t a n de n o r m o u sr a n d o m l ys e l e c t e dd a t at o t e s tt h ew h o l ed e s i g ns u c c e s s f u l l y ， w h i c hv e r i f yt h ev a l i d i t yo ft h ed e s i g n t h i sf l o a t - d i v i s i o nc o m p o n e n tn e e d s14c l o c k st oc a l c u l a t es i n g l ep r e c i s i o n f l o a t i n g p o i n td i v i s i o n ，a n d2 9c l o c k s t od o u b l ep r e c i s i o n u s i n gt h e0 13 脚c m o s t e c h n o l o g y ，t h ef r e q u e n c yo fac l o c ki sm o r et h a n7 0 0 m h z m yr e s e a r c hi sp a r to ft h e ”h i g hp e r f o r m a n c exp r o c e s s o r ”p r o j e c t ，a n dt h i sd e s i g nh a sa l s ob e e nu s e di nt h e p r o j e c ts u c c e s s f u l l y k e yw o r d s ：f l o a t i n g - p o i n td i v i s i o n ，s r ta l g o r i t h m ，n e w t o n r a p h s o n a l g o r i t h m ，g o l d s c h m i d i ta l g o r i t h m ，o n t h e - f l yr o u n d i n g 第i i 页 国防科学技术大学研究生院硕十学位论文 表目录 表1 1各浮点表示格式的参数2 表1 2 典型数据各舍入方式下的结果4 表1 3 舍入方式归并4 表2 1自定时电路分类1 9 表2 2 不同除法算法性能【5 。2 2 表2 3 双精度浮点除法算法常用配置的延迟1 5j 2 2 表2 4 主流算法的商业应用2 3 表3 1 基2s r t 演算过程2 6 表3 2 基一4 ( q i 一3 ，3 ) 飞速变换演算3 1 表3 3 基一4 ( q k 一3 ，3 ) ) 改进飞速变换演算3 l 表3 4 接近舍入操作3 3 表4 1基2 商选择函数真值表3 9 表4 2 单字节前导0 计数4 0 表4 38 字节前导o 计算真值表4 2 表4 4 单字节前导1 计算4 2 表4 58 字节前导1 真值表4 4 表5 1 浮点除法初级测试激5 1 表5 2 浮点除法边界测试激励5 2 表5 3 综合结果。5 6 第l l i 页 国防科学技术大学研究生院硕士学位论文 图1 1 图1 2 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 1 图3 1 2 图3 1 3 图3 1 4 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图目录 3 2 位单精度浮点格式3 6 4 位双精度浮点格式3 循环组件架构8 基2 恢复余数法的r o b e r t s o n 图9 基2 不恢复余数法的r o b e r t s o n 图10 牛顿迭代收敛图。12 自定时电路环【1 。7 1 19 q d i 自定时电路4 相握手信号和双轨编码1 1 7 】2 0 自定时环迭代除法器电路架构图【1 6 】2 0 基2s r t 算法伪状态机【3 2 1 2 5 基2 飞速转换状态机2 6 基2s r t 算法r o b e r t s o n 图2 6 基rs r t 算法商选择函数p d 图2 8 基rs r t 算法的r o b e r t s o n 图2 8 基4s r t 算法商选择函数p d 图2 9 常规飞速转换的实现3 0 基一r 飞速转换状态机【”j 3 0 基于飞速转换的舍入3 3 低基s r t 除法器堆叠获取高基除法器3 4 硬件复制无交叠3 4 p r 交叠1 5 6 j 3 5 o s 交叠3 6 o s 与p r 交叠【4 2 1 3 6 浮点除法框图3 7 基4 s r t 商选择函数架构3 8 基2 商选择函数逻辑电路。3 8 基4 商选择函数逻辑电路3 9 整数预处理部件模型4 0 单字节前导0 逻辑电路架构4 l 4 字节前导o 逻辑电路架构4 1 8 字节前导o 逻辑电路架构4 2 单字节前导l 逻辑电路架一4 3 第1 v 页 国防科学技术大学研究生院硕士学位论文 图4 1 0 图4 1 l 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 4 字节前导l 逻辑电路架构4 3 8 字节前导1 逻辑电路架构4 4 6 4 位8 选1 多路复用器4 5 两级6 4 位移位4 5 飞速转换逻辑电路架构4 6 商数舍入逻辑电路4 6 验证中的恢复路径。4 8 不确定状态下的恢复路径4 8 等效性检查的恢复路径4 8 模型检查的恢复路径4 9 功能验证的恢复路径4 9 测试验证模型5 0 边界测试波形5 3 延迟与约束一5 4 面积与约束一5 4 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特另4 加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 茎丛垄墨翌。叁险洼叠住鲍盟童生塞理 学位论文作者签名：逮壅日期：榭年，上月j 节日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名： 作者指导教师签名： 缘 日期：删年工月7 日 日期：姗占年，三月节日 国防科学技术大学研究生院硕七学位论文 第一章绪论 1 1 课题研究背景 伴随工作站以及工业等诸多方面对于数字信号处理以及图像处理需求的日益 增长，浮点运算扮演的角色越加显得重要；特别是在高性能计算领域，浮点单元 ( f p u ) 的性能成为当前衡量处理器性能的一个重要指标。与定点数相比，浮点数据 拥有更大的动态范围与更高的精密度，因而更具运算上的优越性。随着集成电路 生产工艺的进步，工艺特征尺寸的缩小，单芯片面积的增大，使得单芯片的集成 度有了空前的提高，因此，实现算法更复杂的高性能浮点运算单元成为可能。 当前应用广泛的浮点运算包括：浮点加法、浮点乘法、浮点除法以及浮点平方 根。通常情况下，浮点加法延迟为2 - - - 4 个时钟周期；浮点乘法延迟为2 - - 8 个时 钟周期；但当前双精度浮点除法延迟却需要8 - - 6 0 个时钟周期【l 】；而同时典型的浮 点应用程序中常用浮点运算比例为：加法4 5 ，乘法4 5 ，除法5 ，平方根3 。多年以来研究及工程人员更多关注高速浮点乘法和加法，浮点除法以及浮点 平方根的性能则少人问津。与浮点乘法和加法相比，浮点除法和平方根使用频率 低；但对于某些应用而言，浮点除法部件则成为制约系统性能提高的瓶颈。高性 能浮点加法、乘法算法、熔合乘加算法以及其实现技术已经相当成熟，而高速浮 点除法器的设计与实现仍然存在严峻挑战。浮点除法算法种类众多，但鉴于设计 参数多样性，如：硬件成本、设计复杂度、运算精度、运算速度等等，各种算法 在实现中各有所长，所以其实现与优化的空间仍然相当大。 浮点除法以及基本函数功能部件设计经历了近五十年的发展，相继提出了多种 不同的算法以及改进方案。这些算法和实现方案主要有以下两方面的不同：第一， 实现除法和基本函数功能部件基于不同的基本算法操作类型加法、加法以及 乘法。第二，实现除法和基本函数功能部件算法的收敛速度不同；基于加法和减 法实现操作的算法以线性收敛速度逼近最终计算结果；而基于乘法操作的算法以 二次方收敛速度逼近计算结果；同时对于基于乘法操作的算法而言，循环开始时 的初始化精度决定了得到最后计算结果所需要的循环次数。 伴随着我国信息化进程的不断加快和深入，在信息安全方面提出了更高的要 求；特别是高端计算机领域的安全尤其重要，具有自主知识产权的微处理器可为 信息安全提供基础保障，因此我国正在大力发展具有自主知识产权的高性能微处 理器。本论文正是基于国内对高性能微处理器的需求，以高性能6 4 位x 处理器的 浮点运算部件的研究与设计为背景，对高性能浮点除法运算进行深入研究，具有 一定的理论价值和较强的现实意义。 第l 页 国防科学技术大学研究生院硕士学位论文 1 2i e e e 7 5 4 浮点标准 由于浮点指令的语义不如其他指令那么不明确，因此最初浮点操作在不同体 系结构计算机之间的转换存在很大问题，如分配给阶码和有效数字的位数、阶码 的范围、如何舍入以及上溢和下溢等异常如何处理等等。1 9 8 5 年推出的i e e e 7 5 4 2 j 标准规定了浮点运算的操作数格式、精度、舍入方式以及异常处理等内容：其已 成为计算机工业中使用最广泛的浮点标准；其支持浮点加、减、乘、除、平方根 等多种操作，因此也是设计实现浮点部件的基础。该标准与以前浮点表示方法的 主要区别在于： 1 ) 当待舍入数据位于两个可表示数中间时，就近舍入选择其中的偶数； 2 ) 规定特殊值n a n ( n o tan u m b e r ) ，+ o o ； 3 ) 使用非规格化数表示其值小于1 0 2 的数据； 4 ) 按缺省方式进行舍入，同时支持其他三种舍入方式； 5 ) 方便地处理异常情况。 1 2 1 浮点数的表示 i e e e 7 5 4 标准定义了四种浮点数表示格式：单精度、扩展单精度、双精度以及 扩展双精度。四种格式的各参数的范围如表1 1 所示。 表1 1 各浮点表示格式的参数 格式 参数 单精度扩展单精度双精度扩展双精度 字宽 3 24 3 6 47 9 指数宽度 8 11 l l 1 5 尾数宽度 2 3 3 1 5 2 6 3 指数最大值瓯“ + 1 2 7 + 1 0 2 3 + 1 0 2 3 + 1 6 3 8 3 指数最小值瓦t 。 1 2 6 1 0 2 2 1 0 2 2 1 6 3 8 2 指数偏移量 + 1 2 7 未指定 + 1 0 2 3 未指定 指数个数 2 5 4 未指明 2 0 4 6 未指明 精度 2 2 32 3 12 5 22 - 6 3 1 2 1 1 单精度浮点及特殊操作数 3 2 位单精度浮点格式如图1 1 所示，根据各域的不同，其数值v a l u e 的计算方 法为： 第2 页 国防科学技术大学研究生院硕+ 学位论文 2 1 3 ) 4 、 图1 13 2 位单精度浮点格式 若p = 2 5 5 并且f 0 ，则不论符号位j 为何值，v a l u e 为n a n 数，非数又 分为两种，一种为s n a n ，一种为q n a n 。当q n a n 作为操作数时，不 触发异常，运算结果直接为q n a n ；如果操作数中出现多个q n a n 数， 其优先级由设计者决定。当s n a n 作为操作数时，触发无效操作数异常。 若p = 2 5 5 并且f = 0 ，则v a l u e = ( 一1 ) 5 0 0 。 若0 p 2 5 5 ，则v a l u e = ( 一1 ) 。2 e - 1 2 7 ( 1 厂) 。 若e = 0 并且厂0 ，则v a l u e 为非规格化数( d e n o r m a l i z e dn u m b e r s ) ，且 v a l u e = ( 一1 ) 5 2 叫趵( 0 ) 。 5 ) 若e = 0 并且厂= 0 ，, 贝l j v a l u e = ( - 1 ) 5 0 。 1 2 1 2 双精度浮点及特殊操作数 图1 26 4 位双精度浮点格式 6 4 位双精度浮点格式如图1 2 所示，根据各域的不同，其数值v a l u e 的计算方 法为： 2 ) 3 ) 4 、 5 ) 若e = 2 0 4 7 并且厂0 ，则不论符号位s 为何值，v a l u e 为非数肌w ，非数 又分为两种，一种为s n a n ，一种为q n a n 。当q n a n 作为操作数时， 不触发异常，运算结果直接为q n a n ；如果操作数中出现多个q n a n 数， 其优先级由设计者决定。当s n a n 作为操作数时，触发无效操作数异常。 若e = 2 0 4 7 并且厂= 0 ，则v a l u e = ( 一1 ) 5 0 0 。 若0 e 2 0 4 7 ，则v a l u e = ( 一1 ) 2 - 1 0 2 3 ( 1 f ) 。 若e = 0 并且厂0 ，则v a l u e 为非规格化数( d e n o r m a l i z e dn u m b e r s ) ，且 v a l u e = ( 1 ) 52 - 1 0 2 2 ( 0 厂) 。 若e = 0 并且厂= 0 ，贝0v a l u e = ( 一1 ) 5 0 。 1 2 2 浮点舍入方式 由于计算机表示浮点数的字长有限，因此无限精度的浮点运算结果需要舍入以 符合浮点表示格式。i e e e 7 5 4 标准定义了四种舍入方式： 第3 页 国防科学技术大学研究生院硕士学位论文 1 ) 就近舍入( 偶数) r n e ：无限精度的运算结果舍入到最接近实际数值，如果 存在两个这样的值，则选择最低位有效数字为o 的那个( 即为偶数的那个) ， 1 最大误差为= i t 三船( l e a s ts i g n i f i c a n tb i t ) 。该舍入方式为默认的舍入方式。 r 2 2 ) 正无穷舍入：所有值向正无穷方向舍入到下一个可表示值( 负数的多余位被 截去) ；所以舍入结果大于或等于无限精度的运算结果。 3 ) 负无穷舍入：所有值向负无穷方向舍入到下一个可表示值( 正数的多余位被 截去) ；所以舍入结果小于或等于无限精度的运算结果。 4 ) 零舍入( r z ) ：即截断舍入，直接将无限精度运算结果的多余位截掉，得到 舍入结果；其最大误差为+ l s b 。 为了达到精确地舍入的结果，i e e e 7 5 4 标准建议设立附加位。在最低尾数的右 边附加一个保护位( g u a r db i t ) ，一个舍入位( r o u n db i t ) 以及一个粘合位( s t i c k yb i t ) 。该 粘合位的引入减少了附加位的个数；如果运算结果的粘合位之后( 包括粘合位在内) 的任意一位有1 ，则粘合位置l ，；否则，其置o 。 表1 2 给出了几种典型数据在不同舍入方式下的舍入结果，其将1 0 位舍入为 7 位。分析表1 2 可得，正无穷舍入和负无穷舍入可被归并到零舍入和无限舍入， 如下表1 3 所示。由此，i e e e 7 5 4 规定的四种舍入方式被归并为三种：就近舍入( 偶 数) r n e 、零舍入以及无限舍入。其中就近舍入( 偶数) r n e 为默认的舍入方式；其 目的在于：把无限精度浮点数舍入到距离其最近的可表示数；如果需舍入的数据 位于两个可表示数的中点，则舍入到最低位为偶数的可表示数( 对于二进制数而言， 末位为o ) 。 表1 2 典型数据各舍入方式下的结果 数值就近舍入正无穷舍入负无穷舍入 零舍入 1 1 0 1 1 0 1 0 0 11 1 0 1 1 11 1 0 1 1 11 1 0 1 1 0 1 l o l l 0 1 1 0 1 1 0 1 0 0 1。1 1 0 1 1 11 1 0 1 1 01 1 0 1 1 1一1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 11 1 1 0 0 01 1 1 0 0 11 1 1 0 0 01 1 1 0 0 0 一1 1 1 0 0 0 0 1 1 11 1 1 0 0 0一1 1 1 0 0 01 11 0 0 0 11 1 1 0 0 0 10 0 0 0 0 0 0 0 01 0 0 0 0 0 1 0 0 0 0 01 0 0 0 0 0 1 0 0 0 0 0 表1 3 舍入方式归并 舍入方式符号归并后舍入方式 正无穷舍入 + 无限舍入 正无穷舍入零舍入 负无穷舍入 + 零舍入 负无穷舍入 无限舍入 1 2 3 浮点异常处理 第4 页 围防科学技术大学研究生院硕十学何论文 i e e e 7 5 4 标准定义了五种浮点异常操作： 1 ) 无效操作数异常 当浮点运算的源操作数在其运算环境中为标准规定的某些情况时，发生无 效操作数异常，通常情况下其运算结果被强制置为q n a n 。 i e e e 7 5 4 标准规定的触发无效操作数异常的情况有以下几种： 任意源操作数为s n a n 的浮点运算。 加、减运算的源操作数包括无穷数。 乘式为0 x o o 。 除式为0 0 或o o o o 。 x 对y 的求余运算x y ，y 为非规格化数或x 为无穷数。 平方根运算中操作数小于0 。 在浮点数转化整数或者十进制数操作中，当操作数出现无穷、n a n 或 者是操作结果上溢，以致结果的数据格式不能真实表示原值。 一些不支持无序比较的比较操作数中出现n a n 数。 2 ) 除o 异常 在浮点除法操作中，如果除数为零且被除数为有限非零数，则其结果为符 号位确定的无穷数，同时触发除0 异常。 3 ) 上溢出异常 当待舍入浮点数的指数超越目标浮点格式所能表示的最大幅度时，产生上 溢异常操作。如果没有陷阱发生，其结果由舍入模式和中间结果的符号决 定。就近舍入将其舍入为无穷以及中间结果的符号；零舍入将其舍入为该 浮点格式下的最大有限数以及中间结果的符号；负无穷舍入将正上溢舍入 到该浮点格式下的最大有限数，将负上溢舍入到负无穷；正无穷舍入将负 上溢舍入到该浮点格式下的最负有限数，将正上溢舍入为正无穷。 4 ) 下溢出异常 有两种相关的情况可能导致下溢，一种是产生一个+ _ 2 e i 之间的非规格化 数，因为该数非常小，所以在以后的运算中可能导致其它异常，如除法运 算中作为除数导致上溢。另一种是当该数用非规格化数表示时在取近似值 时会丢失精度。当下溢陷阱没执行或没有使能时，只有当小的数值和丢失 精度同时被检测到时才触发下溢异常；当下溢陷阱被执行或被使能时，只 能检n n d , 的数值就产生下溢异常。 5 ) 非精确异常 若舍入结果不精确或溢出但没有溢出陷阱，那么发生不精确异常。 第5 页 国防科学技术大学研究牛院硕士学位论文 1 3 论文结构 本文的结构为：第一章绪论，阐述了论文的研究背景，简述了i e e e 7 5 4 浮点 标准，介绍了整篇文章的组织结构；第二章浮点除法算法分析，简述各浮点算法 的思想，并对其面积和时序进行比较；第三章x 处理器s r t 浮点除法器研究与设 计，演绎s r t 算法，并根据算法发展搭建最优s r t 浮点除法器架构：第四章x 处 理器s r t 浮点除法器实现，对设计中的关键部件进行详细分析介绍；第五章x 处 理器浮点除法器的验证与综合，介绍了浮点除法部件的验证方法、验证过程及结 果，综合的策略、方法和结果等。第六章结束语总结现有工作，并展望工作内容。 第6 页 国防科学技术大学研究生院硕士学位论文 第二章浮点除法算法分析 m i c h a e lj f l y n n 与s t u a r tf o b e r m a n 按照硬件操作的不同将浮点除法算法分为5 大类【2 1 ：数值循环法( 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 ) 、高基数法 ( v e r yh i g hr a d i x ) 、查找表法( t a b l el o o k u p ) 以及可变延迟法( v a r i a b l el a t e n c y ) 。而当前 实际的浮点除法部件并不是单纯采用某一类方法，而是汲取了几种方法的长处， 采用合理的配置以提高浮点除法运算的效率。例如高性能的浮点除法算法采用查 找表得到准确的初始化倒数表，使用函数迭代可以二次方加速商的收敛等等。 2 1 数值循环法 数值循环法是历史久远的高速浮点算法，其是最简单且应用最广泛的除法算 法。该浮点除法又可分为恢复余数与不恢复余数两大类。除法运算如式2 1 所示， x = q d + r e i n 其中i 陀m l u l p ) 以及以下的规则 所决定： 如果u l p = l ，则商数为整数。 如果u l p = ，一，其中n 是商数的位置，r 是表示所有输入数据以及结果的基数， 所以商数为小数。 数值循环法需要通过n 次循环过程来获取商数，每次循环产生一位基r 的商数位， 各个商数位根据产生的顺序权值逐级递减，所以，+ 1 次循环产生的商数可写成式 2 2 的形式。所以经过i 1 次循环之后，除法运算将得到最终的n 位商数( 如式2 3 所示) 。而其计算结果的误差如式2 4 所示。商数位的误差不仅仅制约最后的商数 结果，而且在每次迭代之后都需要满足式2 5 所示的要求。但是循环过程中，如果 qj】_盯叫(2-2) q = g m = q ，叫 ( 2 3 ) 0 s 口= 号- q ，叫 ( 2 - 4 ) s 。 + 1 】= f 言- q 【，+ l 】i q d s ) 。循环过程中所需要的运算部分架构如图2 1 所示，最终获得余数( 式2 8 ) 。 ，p 垅：1 w 胛1 ，一：、。圹w 【胛 o ； (28，1，p 垅2 ( w i l l + d ) ，一n cw 以】 0 2 8 2 1 1 恢复余数法 图2 1 循环组件架构 恢复余数法的除法算法类似于普通的手算除法，其要求商数q 的选择应当属 于一个非负的数字集 o ，1 ，2 ，一1 ) 。这就需要严格的约定部分余数的范围必须满足 0 w j + 1 】 d 。因此恢复余数的商选择函数定义为： q j + l = 七，i f 出, w i j d ( k + 1 ) ，k 0 ，1 ，2 ，r 一1 ) ( 2 9 ) 该算法需要比较r w ，1 与除数d 的倍数。通常情况下，该商选择函数有两种实 现方式：并行比较器和串行比较器。并行比较器的方式可以获得更高的性能，但 是伴随的除法基数的增加，比较器的数量即硬件面积的需求也同时指数倍的增长。 为了避免大量比较器的使用，可以通过尝试性的从部分余数中重复的减去被除数， 直到其结果为负数为止。然后将最终减为负数的部分余数加上被除数，存入部分 余数寄存器中，从而获得本次循环过程最终正确的部分余数。伴随着基数的增加， 第8 页 所需要的尝试性操作、回退操作变得十分的耗时，j 司时其硬件实现代价也迅速的 增长。所以实现高基的恢复余数的数值循环法的除法器是不和实际情况的。对于 基2 的恢复余数法除法的商选择函数如式2 1 0 所示。该商选择函数也可以通过 r o b e r t s o n 图的形式来表示( 如图2 2 ) 。对于n 位的被除数和除数，为了计算最终 的商数需要n 次减法移位和平均昙次恢复余数的操作。其中，该恢复余数的操作 可以通过加上被除数d 或者保存之前的余数两种方式来实现。但是由于不断的恢 复余数需要花费大量的时间以及硬件资源，所以该方法并不是实现浮点除法器的 优化算法。设计者在实际的设计过程中也基本上不使用恢复余数法设计实现浮点 除法器。 “。：f o2 w j 等 (2l 2l i fd l u t ) ； 表格中初始化近似数据的精度增大可以加速收敛过程。如果非零作为第一步近 似的结果，然后可得式2 1 5 和2 1 6 。将式2 1 3 代入式2 1 2 可得到函数迭代的近 似倒数形式( 如式2 1 7 所示) ，其误差因子如式2 1 8 所示。由式2 1 7 可得，每次迭 代需要两个乘法和一个减法运算。减法操作通常采用二进制补码的形式设计实现。 第11 页 国防科学技术大学研究生院硕士学位论文 最终的商则需要将该倒数与被除数作乘法。综上，在一次迭代过程中，两个相关 的乘法操作和一个二进制补码操作是必须的。 x j x i + 1 x i + 2 图2 4 牛顿迭代收敛图 厂( x ) ：! 一6 ：0 “，弘一篇 川= 等 l ( x o ) 2 吼= 确一篇叫壬_ c 2 - b xx ， s f + l = s f 2 ( 6 ) 2 2 2g o l d s c h m i d t 法 ( 2 一1 7 ) ( 2 一1 8 ) g o l d s c h m i d t 法也称为级数展开法。级数表示形式如式2 1 9 所示。应用于倒数 迭代的直接有效的方法是m a c l a u r i n 级数形式( 式2 2 1 ) 。假如有两个n 位的输入 数据a 和b ，且其满足l 口，d 2 ( 其为规格化的浮点数) 。为了计算式2 2 0 ， 第1 2 页 刁 q $ 回 l l l l l 二 二 二 二，l，l，、 国防科学技术大学研究生院硕士学位论文 g o l d s c h m i d t 算法连续的查找序列k l ，k 2 ，k 3 ，从而状得r j = d k l k 2 k 无限逼近常 数1 。将2 2 1 带入式2 2 0 可得级数展开法的运算雏形( 式2 - 2 2 ) ，基于迭代以及 硬件设计规格化的要求，经化简可得式2 2 3 ，其可通过式2 2 4 完成最终的循环迭 代过程。其中m 和口是第i 次循环迭代的分子与分母。当d j 收敛到l 时，i 向商 收敛。由式2 2 3 可得，每次迭代为商增加一个( 1 + y 2 。) 的修正因子。这便是 g o l d s c h m i d t 算法的核心思想。与n e w t o n r a p h s o n 算法相似，需要一系列的扩展运 11 算来计算被除数的导数。由于计算在x = 0 处的结果比计算二在x = 1 处的结果 l + xx 容易。问题最终变成使式2 2 0 收敛到善，这就需要如式2 2 3 所示的一些乘法操作 l 来获取最终的商数。 咖心( 咖( j ，刊g ( 卅哮鼬) + + 咩烈卅 g = i a = 口g ( y ) 1 g ( y ) = = 1 一y + y 2 一y 3 + y 4 l - i - 1 ， g = 口丁；i 軎二i 了= 口歹1 = 口( 1 一y + y 2 一y 3 ) q = a ( 1 一少) ( 1 + 少2 ) ( 1 + y 4 ) ( 1 + y 8 ) 】 n 吼2 方 2 3 高基数法 与高基除法相比，数值循环法适用于低基的浮点除法，随着基数的增加，其硬 件设计变得相当的复杂，同时面积和时间也指数倍的增加。为了兼顾高基除法的 优势，又可接受的面积、时间以及舍入精度，高基除法算法应运而生。高基算法 就是通过减少商位选择的规模和加快倍数的处理来实现面积和延迟的缩小，从而 达到可以接受的设计要求。其算法主要包括一下几种：精确商近似1 9 j 、短倒数l l o j 以及预缩放与舍入【l 卜1 3 j 。精确商近似法以操作数的高位从查找表中索引近似商， 利用多个乘法部件和加法部件参与辅助运算，实现商数的近似求解；短倒数法由 d w o n g 提出，与精确商数近似法近似，其仅仅是产生倒数的形式有所不同；舍入 并预缩放法则有e r c e g o v a c 和l a n g 提出，其首先获得除数倒数的精确近似值，然 后通过缩放对除数和被除数做近似处理，最后采用乘法和加法部件对商数舍入和 第1 3 页 9 0 l 2 3 4 2 2 2 2 2 2 2 2 2 2 2 国防科学技术大学研究生院硕七学位论文 余数减少做多次迭代，最终获墩浮点除法的商数。其每次迭代的位数u j 入于1 0 。 2 3 1 精确商近似法 这种高基算法由d e r e kc w o n g 和m i c h a e lj f l y n n 提出【9 1 。假设被除数x 和除 数y 都是符合i e e e 7 5 4 的规格化浮点数，该数尾数部分的有效位数为q 位。x 的 1 最高p 位与x 存在2 p 的误差；x 存在于一个连续的区间 一，掣一一，0 0 0 0 ，_ 一，一2 一p 111 l i ：即x 的最小值为一，_ 一：一，0 0 0 0 ，x 的最大值为一寸一p l1 1 l 。采用类似的方法，获得y 的最高m 位；则y 位于 区间 一寸一一p o o o o ，一- 彳一儿一p 1 1 1 1 之间。因此将x 的最高p 位定义为 咒= x q i _ 2 一p 0 0 0 0 ( 2 - 2 5 ) 虼= 儿一l y q 2 ”均一，111 1 ( 2 2 6 ) 舣= x 一也 ( 2 2 7 ) a y = y k( 2 2 8 ) 鼍( 如式2 - 2 5 ) ；将y 的最高m 位定义为k ( 如式2 2 6 ) 。如式2 - 2 7 和2 - 2 8 分别定义a x 和a y ；它们分别为x 和y 与也和虼的修正值。仔细分析似和a y 的定义可得：似始终为非负数，而】，则始终为非正数。倘若可以得到軎的结果， 很显然其将小于或等于三y ，而且使得专的结果始终小于或是等于事。因此可以 将精确商近似法的算法表述如下【5 】： 1 ) 初始化阶段，将商数q 的初始化数据和变量j 设定为0 。然后使用y 的最 高m 位通过查表获得軎的最佳逼近值。由于y 是符合i e e e 7 5 4 标准的浮点 数，其前导1 被隐藏，所以需要m 一1 位实现表格的索引。同时并行执行乘 法计算以】，； 2 ) 通过倒数近似的方法同时截断被除数和第一步中所产生的乘积。为了提高 运算性t i ，这就需要两个并行计算的乘法器，分别计算歹1 xy 和 专( 以】，) 的乘积结果。其中专】，= l ，在之后的循环过程中并不改变， 所以只需要计算这一次。此后的循环只需要一个乘法器完成y 最，其中e 第1 4 页 国防科学技术大学矽f 究生院硕士学位论文 1 1 是当前截断后的部分余数。p hx 歹1 的结果则是本次循环后的商；乞古y 则是被除数的近似值； 3 ) 执行一次循环所得到的下次循环的部分余数为：尸= 尸一最軎y ，其 中p o = x 。因为所有的数据已经准备就绪，所以只需要完成一次减法操作； 4 ) 计算新的商数：q ，- q + 乏专= g + 最专歹1 ，本次循环之后的商数可 以通过把得到的軎移位后加到上一次循环后得到； 5 ) 本次循环后的部分余数尸，需要将所有的前导0 删除，即进行规格化处理。 该算法保证本次循环后的部分余数前面有m 一2 个0 。移位索引变量i 修正 为j = j + m 一2 ； 6 ) 调整所有的变量：j = ，o = q ，p = p ； 7 ) 重复完成步骤2 到6 ，直到，q ； 8 ) 完成所有的循环之后，q 的最高n 位便是最后舍入前的商数。同时，该算 法可以直接通过右移p 值一g 位的方法获得最后的余数，而该余数是假定 得到q 的所有位数皆为最终的商数而获得的。假如只将q 前n 位当作商 数，则最后的余数为q 】，+ p ，其中q 为q 去掉前n 位而剩下的低位部 分。 综上，精确商近似法每次循环减少部分余数q 的m 一2 位【9 1 ，对于q 位商数则 需要i 1 次循环。对于大多应用而言，为了减少除法运算的迭代次数，就需要 i 聊一zi 增加倒数表的尺寸；在高级的设计中，精确的倒数表可以在2 个甚至1 个循环完 成除法操作。其关键思想在于较低的评估商数，同时通过加法来实现商数的调整； 而并不是按位求得商数位。该方法实现的除法器比n e w t o n r a p h s o n 法快很多。 2 3 2 短倒数法 短倒数法与精确商近似法十分的类似，其仅仅在产生倒数的方式上有所不同。 短倒数法则利用n e w t o n r a p h s o n 公式将从倒数表中索引的精度不高的倒数值进一 步进行优化，从而获得更高的精度近似倒数；这种方法极大的减小倒数表的尺寸； 同时也简化的倒数表译码电路的时间需求，进而大大的提高了表的索引速度。对 于初始化倒数的调整以及转换将使得该倒数落入一定的需要精度范围之内，其转 第1 5 页 国防科学技术入学研究生院帧十学位论文 换公式如式2 2 9 所示。由该式很显然可以得到：n e w t o n r a p h s o n 算法每循环一次 就需要两个乘法操作和一个减法操作。c y r i x 8 3 d 8 7 协处