（物理电子学专业论文）双精度64位浮点除法运算单元的设计与实现.pdf

中南大学硕士学位论文 摘要 摘要 浮点数可以表示高精度以及非常大的数值，同时，高精度计算、 图形加速、数字信号处理等应用对浮点处理的要求也越来越高，浮点 运算单元成为当代微处理器中一个重要组成部分。浮点除法因其特殊 性与实现的难度，仍有不小的优化空间，研究表明，浮点运算中除法 运算效率的浮动会导致处理器性能的大幅度浮动，虽然其出现频率较 低，但对处理器整体性能有较大的提高。所以，设计一种执行效率较 高的浮点除法结构对处理器性能的提高可以起到很重要的作用。n i o s 是一种基于哈佛结构的采用流水线技术的软核r i s c 处理器，基于 s o p c 的思想设计，且专门针对a l t e r a 的可编程逻辑器件做了相应优 化。作为一种可配置的通用r i s c 处理器，它可以与用户自定义逻辑 结合构成s o c 系统并下载到a l t e r a 的可编程器件中去。浮点运算单 元是为处理器服务的，所以将浮点除法运算单元与n i o si i 软核处理 器相结合，既能很好的验证运算单元的正确性，又具有很好的实用性。 本文对微处理器中双精度6 4 位浮点除法运算单元的算法与实现进行 了深入的研究。在充分分析现有的各种除法算法，包括n e w t o n r a p h e s o n 、g o l d s c h m i d t 、恢复余数迭代法和s r t 等算法的基础上， 针对微处理中浮点“位除法运算还存在可进一步优化的技术特点， 对s r t - 4 算法的关键部分商数字选择函数进行了优化，并提出了基于 优化后的s r t - 4 算法的双精度浮点除法的改进方案。该方案符合 i e e e - 7 5 4 浮点格式标准，采用误差的就近舍入策略，并采用v h d l 硬件描述语言完成了除法运算单元的设计，用s o p cb u i l d e r 工具将 运算单元通过a v a l o n 互联架构与n i o si i 处理器相结合，在基于 c y c l o n ef p g a 硬件平台上得以实现。同时，对除法运算单元进行了 模块测试与整体验证，结果表明改进的除法运算单元达到了正确性的 设计要求，且具备较快的运行速度，从而具备很好的实用性。 关键字：浮点除法运算单元，s r t 算法，i e e e - 7 5 4 ，s o p c ，n i o si i 中南大学硕士学位论文 f l o a t i n g - p o i n tc a ne x p r e s s e sh i g h - p r e c i s i o na n dv e r yl a r g ev 批 m e a n w h i l eg r a p h i c sa c c e l e r a t i o na n dd i g i t a ls i g n a li ns c i e n t i f i cr e s e a r c h a n de n g i n e e r i n ga p p l i c a t i o n s ，t h ed e m a n do ff l o a t i n gp r o c e s si sb e c o m i n g m o r ea n dm o r ce x i g e n t , f l o a t i n gp o i n tu n i th a sb e c o m ea ni m p o r t a n t c o m p o n e n t i nm o d e mm i c r o p r o c e s s o r t h e r ei ss t i l lb i go p t i m i z a t i o n s p a c ef o rf l o a t i n g - p o i n td i v i s i o nd u et ot h es p e c i a ln a t u r ea n dt h e d i f f i c u l t yt o a c h i e v e a sai n f r e q u e n to p e r a t i o ni n & a 衄gp o i n t c o m p u t a t i o n , at i n yi m p r o v e m e n tt od i v i s i o nm a yr e s u l ti nb i gc h a n g e st o t h ew h o l ep e r f o r m a n c eo ft h ep r o c e s s o r t h e r e f o r e , d e s i g naf l o a t i n g p o 缸d i v i s i o nc o m p u t a t i o ns t r u c t u r e 。w h o s oi m p l e m e n t a t i o ni sm o r c e f f i c i e n t , c a nm a k eg r e a ti m p m v e m e n tt ot h ep e r f o r m a n c eo f 湖s o r n i s oi ip r o c e s s o ri sar i s ce p uw h i c hb a s e so nh a r v a r da r c h i t e c t u r e a n du 瞄p i p e l i n e dt e c h n o l o g y , i ti so p t i m i z e dt oa l t e r a sp r o g r a m m a b l e l o g i cc h i pa n dt h et h i n k i n go fs y s t e mo np r o g r a m m a b l ec h i p a sa c o n f i g u r a b l eg e n e r a l - p u r p o s er i s cp r o c e s s o r , i tc a l lb eb u i l ta sas o c s y s t e mw h i c hi sc o m b i n e dw i t hu s e r - d e f i n e dl o g i c ，a n dt h ew h o l es y s t e m c a nb ed o w n l o a d e dt o a l t e m sp r o g r a m m a b l ed e v i c e f p us e n ，i c e s c p u , s oi fw ec o m b i n et h ef l o a t i n gp o i n td i v i s i o nu n i tw i t hn i o si is o f t p r o c e s s o r , i tw o u l db ea p p r o p r i a t ef o rv a l i d a t i n gc o e s so ft h eu n i t a n da l s oh a sg o o du t i l i t y i nt h i sp a p e r , t h et h e o r yo fv a r i o u sc u r r e n t d i v i s i o na l g o r i t h mi n c l u d i n gn e w t o nr a p h e s o n , g o l d s c h m i d t ，r e s t o r i n g d i g i t 黼e n c e ，n o n - r o s t o r i n gd i g i tr c c n r r e n c ea n ds r ta l g o r i t h ma r c a n a l y s e d , t h es p e e da n de f f i c i e n c yo ft h e s ea l g o r i t h mi se v a l u a t e d a n d t h eb a s i c 也e o r ya n dk e yc h a r a c t e r i s t i c so fs r t a l g o r i t h ma r ef o c u s e d ； a i m i n gt oi e e e - 7 5 4f l o a t i n gp o i n ts t a n d a r d , ad e s i g no fd o u b l ep r e c i s i o n f l o a t i n gp o i n td i v i s i o nw h i c h i sb a s e ds r t _ 4 a l g o r i t h mi sp r e s e n t e d t h e o p e r a t i o nu n i t i s c o m p l e t e db yu s i n gv h d lh a r d w a r ed e s c r i p t i o n l a n g u a g e a n di ti s c o m b i n e dw i t hn i o si ip r o c e s s o rt h r o u g ha v a l o n s w i t c hf a b r i cb yu s i n gs o p cb u i l d e r , a n dt h ew h o l es y s t e mi s i m p l e m e n t e db a s e do nc y c l o n ef p g ah a r d w a r ep l a t f o r m m e a n w h i l e , t h eo p e r a t i o nu n i tp 弱s e sb l a c k - b o xt e s ta n dw h i t e - b e xt e s t , i tp r o v e st h a t 中南大学硕士学位论文 a b s t r ( t t h es c h e m ei sc o r r e c t l yd e s i g n e d ，a n dh a v eaf a s t e rs p e e d ，t h u sp o s s e s s g o o dp r a c t i c a l 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 nu n i t , s r ta l g o r i t h m , i e e e - 7 5 4 ， s o p c ，n i o s n i l i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。论文主要是自己的研究所得，除了已注明的地 方外，不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的 同志对本研究所作的贡献，已在论文的致谢语中作了说明。 作者签名： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文，允许学位论文被查阅和借阅；学校可以公 布学位论文的全部或部分内容，可以采用复印、缩印或其他手段 保存学位论文；学校可根据国家或湖南省有关部门的规定，送交 学位论文。对以上规定中的任何一项，本人表示同意，并愿意提 供使用。 作者签名：丑鱼j 一导师签名：盟日期；t 1 1 z 年二月鲨日 i 中南大学硕士学位论文 第一章绪论 1 1 研究背景 第一章绪论 随着科技的进步和社会的发展，计算机已经在我们的日常生活、工农业生产 和科学研究中被广泛应用c p u ( c e n t r a lp r o c e s s i n gu n i t ) 是计算机的核心，c p u 的性能决定着计算机的性能，从而决定着整个系统的性能真正意义的c p u 出 现是在1 9 7 1 年( 玳1 e l 的4 0 0 4 处理器) ，从它诞生之日起到今天，已经过去了 3 6 年3 6 年是历史的一瞬问，但c p u 发展的这3 6 年却改写了历史，带给了社 会巨大的进步和文明，是充满创新和激情的3 6 年 如今，作为信息处理核心的c i u 已渗透到通信、家电、商务处理等与人们 日常生活密切相关的各行各业，尤其深刻地影响着武器装备、航空、航天、航海 等国防领域。然而，由于各种历史原因，我国的微处理器的许多核心技术与产品 仍然依赖于国外高科技公司，经济、国家安全等都面临受制于人的尴尬局面。为 使国家经济、国防安全得到保证，必须发展具有自主版权的微处理器，必须研究 微处理器设计领域所涉及的各项核心技术 c p u 所处理的数据主要有两种表示方法：定点数和浮点数其中定点数表 示范围小，但其实现简单。而浮点数可以表示高精度的数值以及非常大的数值 在当代的微处理器设计中，通常使用专用部件也即浮点运算单元( f p u 。 f l o a t i n g - p o i n tp r o c e s su n i t ) 来进行浮点计算同时，由于在语音通信、图象处理 等领域中，系统往往涉及大量的数据处理，而且数据计算的精度和实时性要求很 高，需要很高的浮点处理能力来提高系统的执行效率，浮点运算单元成为当代微 处理器中的一个重要组成部分，如何提高f p u 的性能已成为微处理器设计领域 的一个重要的研究课题。 通常意义上的浮点运算指浮点格式的加法、减法、乘法以及除法这四种基本 运算。其中加法、减法与乘法在浮点运算单元中的实现，研究者们倾注了大量的 精力，取得了显著的成效而浮点除法因其特殊性与实现的难度，仍有不小的优 化空间。s o e r q u i s t 等人【l 】指出，在四种基本浮点运算中，浮点除法的执行速度是 最慢的，处理器执行浮点加法和浮点乘法一般需要2 到3 个机器周期，而浮点除 法则需要8 到6 0 个机器周期。同时，浮点除法占的比例较小，o b e r m a n 和f l y n n 2 1 认为在所有浮点指令中，浮点加法指令占5 5 浮点乘法大约占3 7 ，浮点除法 大约占3 ，和浮点加法和浮点乘法相比，浮点除法的比例很小但是，这并不 表示浮点除法对处理器性能的影响很小，在因为浮点指令阻塞等待而引起的处理 器性能下降的因素中，浮点除法指令大约占4 0 ，浮点加法大约占4 2 ，浮点 中南大学硕士学位论文 第一章绪论 乘法大约占1 8 p i s o e t a l l 2 】的研究亦表明，浮点运算单元中除法与开方运算效 率浮动1 将导致处理器的性能表现浮动2 0 n , 4 1 而浮点除法器设计上的一个设计 瑕疵更将带来严重的后果，比如1 9 9 4 年i n t e l 曾因其在p e n t i u m 处理器浮点除 法中的b u g 而损失了4 7 5 亿美元【3 1 。由此可见，浮点除法虽然出现的频率较低， 但对处理器整体性能有较大的影响，设计一种执行效率较高的浮点除法结构对处 理器性能的提高有着很重要的意义 n i o si i 是一种采用流水线技术、单指令流的软核r i s c ( r e d u c e di n s t r u c t i o n s e tc o m p u t i n g ，精简指令集1 处理器，基于s o p c ( s y s t e mo np r o g r a m m a b l ec h i p ， 片上可编程系统) 的思想设计，且专门针对a l t e f a 的可编程逻辑器件 c p l d ( c o m p l e xp r o g r a m m a b l el o g | cd e v i c e ) 或f p g a ( f i e l dp r o g r a m m a b l eg a t e a r r a y ) 做了相应优化。作为一种可配置的通用r i s c 处理器，它可以与用户自定 义逻辑( 嘣l o g i c ) 结合构成s o c ( s y s t 锄o nc h i p ) 系统并下载到a l t e x a 的可编 程器件中去。浮点运算单元是为处理器服务的，所以如果将浮点除法运算单元与 n i c ei i 软核处理器相结合，既能很好的验证运算单元的正确性，又具有很好的实 用性本文专注于基于i e e e - 7 5 4 标准【4 】的双精度( 6 4 位) 浮点除法运算的研究与 实现。 1 2 国内外研究现状 浮点除法器是浮点运算单元的一部分，浮点运算单元随着c p u 的发展而发 展以最典型的瑚t e l 处理器为例 1 9 7 8 年i n t e l 推出8 0 8 6 8 0 8 8 微处理器的时候就充分认识到浮点处理能力的 重要性。紧接着1 9 8 0 年推出了8 0 8 6 ，8 0 8 8 的浮点处理扩展8 0 8 7 ，它不能与 1 9 8 5 年公布的i e e e 7 5 4 浮点标准完全兼容【卯。1 9 8 3 年推出8 0 2 8 6 的协处理器 8 0 2 8 7 ，亦没有与i e e e 7 5 4 标准兼容【6 】。 1 9 8 5 年，曾任职于i n t e l ，并参与8 0 8 7 协处理器开发的数值分析专家 w i l l i a mk a h a n 教授所完成的浮点数格式设计，被i e e e 采用，并形成了i e e e 标 准浮点格式：i e e e - 7 5 4 。 1 9 8 6 年，i n t e l 推出8 0 3 8 6 的协处理器8 0 3 8 7 ，总线接口由原来的1 6 位扩 大为3 2 位，且与i e e e - 7 5 4 标准兼容。之后，i n t e l 继续推出了8 0 3 8 7 d x 、8 0 3 8 7 s x 和8 0 3 s 7 s l t n 。虽然3 8 7 系列比以往的x 8 7 协处理器功能要强很多，但总的说来， 由于x 8 7 系列协处理器与c p u 之间的通信开销比较大，限制了数据传输的速度， 因而效率不高。 2 中南大学硕士学位论文 第一章绪论 图1 - i 除法算法分类 1 9 8 9 年i n t e l 推出的4 8 6 d x 标志着浮点处理器发展的一个飞跃。在功能上包 含一个c p u 和一个片上f i u ( 增强3 8 7 ) 由于片上f i u 削除了昂贵的c i u 与 f l u 通信开销，而且可以利用片上c a c h e 和高度流水部件，使f l u 能以硬件允 许的最大速度工作嗍。 处理器 所用算法所耗周期 随着半导体技术的飞速发展，f p u 的各种运算也在飞速发展。加法、减法成 功的解决了进位传递带来的关键路径延时过长的问题，出现了超前进位加法器、 进位选择加法器( c a r r y - s e l e c t a d d e r ) 、进位跳跃加法器( c 觚y - 蛳删以及条 件加法器( c o 础6 0 n a la d d e r ) 等f g 州【l l 】。乘法运算由于其应用的广泛性，亦取得 了显著的发展。而除法运算和开方运算，由于其在程序中出现的频率比较低，起 3 中南大学硕士学位论文 第一章绪论 初并没有获得重视。随着处理器的加法、减法和乘法运算性能的显著提高，除法 与开方运算的延时显得越来越大【1 2 1 ，这种性能差距限制了微处理器的发展，使 除法和开方运算逐渐成为了算术领域研究的热点，诞生了大量提高运算速度的算 法。 总的说来，除法主要分为两种类型：基于函数( f u n c t i o n a l ) 的除法算法与 基于数字迭代( d i g i tr 鲫珊m 嘲的除法算法【1 3 】。如图1 1 所示近现代c p u 的除 法、开方运算( 3 2 位) 的性能表现如表1 1 所示。显然，各个c p u 的除法运算的 性能是有差别的，需要指出的是，并非运算速度越快就越好，f p g a a s i c 的设 计是速度与面积的均衡，所以无需一味的追求运算速度。以r a d i x - 4s r t 算法为 例，如果改为r a d i x - 2 5 6s r t 实现，理论上运算速度将提高4 倍，然而除法运算 单元所耗用的硬件资源亦将扩大4 倍或更多 1 3 论文研究内容及结构 本文分析了当前各种除法算法，包括n e w t o nr a p h e s o n 、g o l d s c h m i d t 、恢复 余数迭代法以及s r t 等除法算法的原理，并从速度、功耗等方面进行了分析比 较，着重分析了s r t 算法的基本原理和关键特性；提出了对传统s r l 4 算法进 行优化的方案；针对i e e e - 7 5 4 浮点格式标准，提出了基于s r = i 珥算法的双精度 浮点除法运算单元的实现方案；采用v h d l ( v h s i ch a r d w a r ed e s c r i p t i o n i m g u a g e ) 硬件描述语言完成了运算单元的设计，并使用s o p cb u i l d e r1 - 具将运 算单元通过a v a l o n 互联架构与n i mi i 处理器相结合，基于c y c l o n ef p g a 硬件 平台实现了整个系统；同时对运算单元进行了模块测试与整体验证，证明了本方 案达到了正确性的设计要求，且具备较快的运行速度，从而具备很好的实用性。 本论文共分为六章，简述如下： 第一章绪论，介绍处理器领域的核心技术对国家经济发展和国防安全的重 要性，浮点运算单元尤其是除法算法在处理器中的地位，浮点运算单元的历史与 发展概况，近现代处理器中除法算法的性能表现，以及本论文的研究内容与意义。 第二章除法算法概述，将除法算法分为函数迭代型与数字迭代型，较详细 的介绍、分析近现代处理器较常用的除法算法，并分析其优缺点。 第三章s r t 除法算法，深入剖析s r t 除法算法，重点介绍了s r t 除法算法 的“迭代基的选择”、“商的冗余表示”与“商选择函数”这三个关键部分，分析 讨论如何利用o n - t h e f l y 技术提高s r t 算法的性能，并详细讨论了如何在传统 的s r l 珥算法基础上进行改进与优化。 4 中南大学硕士学位论文第一章绪论 第四章讨论了m e e 7 5 4 浮点格式标准，并与本设计相结合概要介绍了其舍 入策略，较详细地讨论了就近舍入策略的原理；重点讨论了方案中对输入操作数 的规格化、结果的舍入与规格化等，这些都是运算单元实现的基础。 第五章从e d a l e c t r o n i cd e s i 驴a u t o m a t ) 技术的发展着手，讨论了 s o p c 及其相关技术的要点较详细的介绍了面向f p g a 的e d a 开发与v h d l 硬件描述语言，重点分析讨论了n i n 处理器核的特典，以及a 、词总线架构 的优点。 第六章基于s r t 珥的6 4 位浮点除法运算单元的设计与实现，提出将6 4 位 浮点除法运算单元与优秀的n i o s h 处理器核结合的方案，探讨了其意义和可行 性；详细阐述了系统中关键模块的设计思路与实现方式，主要是a v a l 总线接 口模块、控制与计数模块以及s 砌4 运算单元；编写了相应的驱动程序，给出并 分析了其中的关键代码：使用v h d l 硬件描述语言实现了s r t 4 运算单元，并 将优化后的方案与传统算法进行了对比，且规划出了系统的测试验证方法，做了 充分的测试验证工作。 第七章总结与展望，总结了论文的工作，并对基于论文的工作进一步开展 做了介绍。 中南大学硕士学位论文第二章除法算法概述 第二章除法算法概述 函数迭代与数字迭代是除法运算最主要的两个实现方法。函数迭代除法以乘 法为核心运算操作；数字迭代除法以加减法为核心运算操作，辅之以可通过移位 操作完成的乘法运算。数字迭代除法非常类似于传统的手工计算除法的方法。在 某些文献中，函数迭代除法被称之为除法的乘算法( m u l t i p l i c a t i v ea l g o r i t h m s ) ，数 字迭代除法被称之为除法的加减算法( 刚，仃a c c i v ea l g o r i t h m s ) 。 2 1 函数迭代除法 函数迭代除法主要有n e w t o n - r a p h s o n 算法与g o l 凼c h m i d t 算法【1 6 1 ，这两 个算法的主要特点是并非直接计算出商的准确值，而是采用逼近的方法。 设q 、x 与d 分别为商、被除数与除数。则除法运算可表示为 g=(2-d 9 2 i 著名的牛顿迭代法的基本公式为 怒 g q 分析除法运算( 2 - 1 ) 可知，求商也即求除数的倒数与被除数的乘积( 三d 工) ， 所以可以先通过牛顿迭代法求出除数的倒数( ) ，为此构造一个函数 4 厂o ) ：三一d ；0 ， ( 2 - 3 ) 将( 2 3 ) 式代x ( 2 2 ) 式 胪y ，一怒= 乃一! - - m t 4 啡嘞) f 咄”川2 川 1 j y i 2 6 中南大学硕士学位论文 第= 章除法算法概述 肼2 ( 1 - ( d 1 ) l + ( d + 1 ) 2 x i + ( d 一1 ) 。) o + ( d 1 ) 2 ) ( 2 - s ) 该式但满足三s d l 时收敛于孝； 姆乃2 而1 丽。i 1 ( 2 固 经过若干次迭代得到三的较精确的近似值后，由 92i砧(2-7) 求出商的值 显然，n e w t o n - r a p h s o n 算法的每次迭代需两次乘法和一次减法且余数无 法直接得到，需通过，= 工一d x 口求得。 g o l d s c h m i d t 算法基于如下思想：为了计算孝，可以对除数与被除数同时乘 以一个数m 胝 曩2磊(2-81 如果使m d * 1 ，则撒即为商q 的近似值构造迭代过程； 1 ) 将除数d 规划化至三s d l ； 2 ) 设善( 0 = x ，d ( o ) = d ； 3 ) 迭代直至礤) 足够靠近q ，迭代的伪代码如下： l o o p i = o ，1 2 ， m ( i ) = 2 一d ( i ) x ( i + 1 ) = m ( i ) ) 【( i ) d ( i + 1 ) = m ( i ) d ( i ) e n d l o o p 迭代n 次后，运算中将累计有2 1 q 次乘运算，n 次减运算。乘运算的次数比 较高，是限制g o l d s c h m i d t 算法运算速度的主要因素 7 中南大学硕士学位论文第二章除法算法概述 2 2 数字迭代除法 除法的数字迭代算法主要分为两类：恢复余数( r e s t o r i n g ) 与不恢复余数 ( n o n - r e s t o r i n g ) 。本文采用的s r t 算法本质上属于不恢复余数的迭代算法。 2 3 1 基本原理 考虑了余数的除法运算定义如下 工= + m ( 2 - 9 ) 且 | ，刊 p 陋且啦刀( m ) = s 劬( 功( 2 - 1 0 ) 其中，x 是被除数，d 是除数，q 是商，衄是余数，u l p ( u n i ti nt h eh 或p o s i t i o n ) 是除数d 的最低有效位的权值，u l p 以及q 的取值遵循如下准则： i 如果t 勿= l ，那么商q 是整数 2 设i t 为操作数( x a q ) 的进制基( 如2 进制、l o 迸制等) ，n 为商q 的有效 数字位数，如果“扫= ，一，那么商q 是小数。 浮点数由三部组成：符号位、指数和尾数。两个浮点数相除，商的指数为被 除数的指数减去除数的指数所得到的值，尾数为被除数的尾数除以除数的尾数所 得到的商i e e e - 7 5 4 浮点数标准中，尾数是以小数形式表示的，本文为保证精 度和简化操作，x 与d 都以小数形式表示，且通过移位操作保证x 与d 的取值范 围为【去，1 ) ，即保证二进制表示的x 与d 的小数点后的第一个数字为i 。且由于浮 二 点除法中符号位已另外处理，所以尾数除法是非负小数的除法运算。i e e e - 7 5 4 浮点格式标准在第四章中有详细的分析与研究。 数字迭代除法由n 次迭代实现，每次迭代产生一个商数字( 一位或者多位， 取决于迭代基r 的值) ，其中高有效位在前【埘。i 次迭代后的商记做q d + l 】，即 窖【_ ，+ l 】_ g ，r - j ( 2 1 1 ) l = l 从而，最终的商是 g = 吼，l 】= q f r 。 ( 2 1 2 ) 中南大学硕士学位论文第二章除法算法概述 由除法的定义，商的准确值为言，经过n 次迭代后，求得的商的误差需满 足如下的约束条件： o s & 2 言一q ，( 2 - 1 3 ) 显然，不仅仅是迭代结果需满足此约束，迭代的中间步骤也需满足类似的约束， 以第( j + 1 ) 次迭代为例，设商q j + 1 j e , u + 1 1 ，则 岛u + l 】= d j + 1 1 订圳( 2 - 1 4 ) 第( i + 1 ) 次迭代的言一g 【_ ，+ 1 】不同于最终的言一q ，因为如果是不恢复余数的迭代 算法，该式是可以取负值的，所以仅需满足绝对值不超过，制即可不恢复余 数的数字迭代除法在第2 2 3 节中有详细分析。 在( 2 - 1 4 ) 式两边同乘以d ，并引入一个新值部分余数( p i t , p a r t i a l r c m a i n d = ) ，记为w u + 1 ，表示第j + 1 次迭代产生的部分余数，其中w 的初始值 w 【o 】= x ， u + l 】= ，川o 一匈u + l 】)( 2 一1 5 ) 经适当变换后可得 m _ ，+ l 】= 州刀一由m( 2 - 1 6 ) 式( 2 - 1 6 ) 是数字迭代算法的核心方程式，几乎所有的数字迭代算法都由此方程式 演变而来由( 2 1 4 ) 式至( 2 - 1 5 ) 式的推导过程可知，部分余数w d + l 】需满足 一d s 町+ l 】 d ( 2 1 7 ) 称为w d + l 】的有边界性从而求商的过程转交为在第( j + 1 ) 迭代中，确定q 【j + l 】的 值以满足式( 2 - 1 7 ) ，也即由w l i - 与d 的值确定q j + l q j * l2s e l ( w j , d ) ( 2 1 8 ) 称为商数字选择( q u o t i e n td i g i ts e l e c t i o n ) 商数字选择在数字迭代算法中扮演着非 常重要的角色，几乎所有的算法优化都围绕着商数字选择来进行，本文对s r t 算法的优化也不例外。 由式( 2 - 1 6 ) 可得出数字迭代算法的基本迭代过程，如图2 1 所示 9 中南大学硕士学位论文第二章除法算法概述 图2 - 1 敷字遮代算法的基本步骧“” 2 2 2 恢复余数的数字迭代除法 恢复余数迭代除法与手工计算除法的原理是一致的。商数字可取的值是一个 非负的集合 0 ，l ，2 ，, r - 1 ) ，称为。商数字集”( q u o t i e n td i g i ts e t ) 。第a + i ) 次迭代 产生的部分余数必须满足 o s ，+ l 】 d ( 2 1 9 ) 商数字选择函数s e l ( t j ，d ) 定义为 q m = 】 ，如果d k s ，刀 d ( 七+ 1 ) ，其中| e o ，1 ，2 ，r - 1 ) ( 2 - 2 0 ) 迭代过程用伪代码描述如下 f o rk = o ，l ，( r _ 1 ) w d + l 】= r w j - k d i f w d + 1 】 1 ) ，则该数字集称为过冗余( o v e r f e d i m d a n o 例洲 表3 - 1 十进制数字2 3 的冗余表示。a = 7 中南大学硕士学位论文 第三章s r t 除法算法 表3 1 与表3 2 为冗余数字集的两个例子 表3 - 2 基r - 2 ，4 或8 时可能的冗余数字集“” ra数字集 p 类型 2lf l , o j l最大冗余和最小冗余 42 2 卿 最小冗余 4 3 百，j ，i , o , l ，2 3 l最大冗余 44 西，一3 ，一2 ，一1 , 0 , 1 ，2 , 3 ，4 ) 仍过冗余 83 压j ，i 舯，2 渤 3 ，7无冗余 84矗j ，一2 ，一1 。o j 2 & 4 4 7最小冗余 87 - ，毛；，- j ，j ，i , o j ，2 ，3 ，4 , 5 ，6 7 l最大冗余 冗余有符号数字系统的吸引人之处在于其“无进位”加法的性质在普通的 加法中，进位可能从最低数位一直传播到最高数位跚。在冗余表示法中，加法 可以在与操作数字长w 无关的恒定时间内完成 2 4 1 。 3 2 s r t 算法 s r t 算法是d s w e e n e y l 2 5 1 ，丁e r o b e r t s o n 2 6 和t d t o c h 一2 7 1 三人几乎同时发 现的，他们当时各自提出了对基2 的不恢复余数的数字迭代法的一种改进方法， 目的是加速运算过程，主要的改进是在商数字集里引入了“0 ”： j1 ，如果2 w j 】 厶2 d ( k 一以以2 d + 力 ( 3 1 1 ) 睁d ( k 一力s r w u 】d ( 七+ 力，其中七；口 ( 口一1 ) , - k l ，0 ( 3 1 2 ) ( 3 1 2 ) 式定义了商数字的选择区间，选择区间的连续性条件意味着不管r 刀取 r 点到，否之间的何值，商数字都应该能取商数字集中的某一个值。换句话说， r h 刀的任意一个可取值必须至少属于一个选择区间，这可以表示为 u k _ l 丘 ( 3 1 3 ) 而由厶与【k i 的定义可知 u h 一厶= d ( k 一1 + 力一d ( k 一力= ( 2 p 一0 , ( 3 一t 4 ) 对于p 丢和d o ，咋。一丘 o ，连续性条件是满足的。 3 5 商数字选择函数 商数字选择函数是s r t 算法最关键的部分，是基于s r t 算法的除法电路中 延时最大( 或称最长) 的逻辑运算路径，即临界路径( c r i t i c a lp a t h ) 。而整个电 路的延时取决于关键路径的延时，所以商数字选择函数是影响除法运算电路性能 的关键，商数字选择函数的优化设计是至关重要的。 s r t 算法的商数字选择函数定义如下： q ，+ l = k 和，口一1 ，l ，0 ，1 ，a - 1 ，4 ) ，如果d ( k 一力s ，m 刀s d ( 七+ 力( 3 - 1 5 ) 对应的r o b e r t s o n 图表示如图3 - 1 所示。 除r o b e r t s o n 图外，p d 图也常用于表示商数字选择函数【1 3 】。p d 图中，n v l i 】 表示为p ，d 表示为d ，由前面的推导可知 一p 蕾s m ，+ l 】户d - p u = ( 一p + k ) d ， 眦= ( p + 七) d ( 3 - 1 6 ) 1 6 中南大学硕士学位论文第三章s r t 除法算法 如图3 2 所示 图3 - 1 商数字选择函数的r o b e r t s o n 图表示“ 上“1 巩 1 2 图3 - 2 商选择函数的p d 图表示咖 显然，相邻的两个选择区问存在着重叠区域，重叠区域的大小由冗余因子p 与除 数d 决定。在重叠区域【厶，以。) 内，q j + t = k 或者g = k - i 都是正确的取值 所以，在迭代中无需知道每次r , c t j 】的准确值，无需进行全精度模式下的 a ( k - p ) s ，d 】与，h d 】 a ( k p ) 的比较操作。且重叠区间越大，比较操作中所 需精度越小所以，重叠区间的存在简化了商数字选择函数的复杂性，从而提高 了其运算效率嘲 有限精度模式下的商选择函数，通常有基于p d 图和基于选择常数n 叼两种 实现方式，后者出现较晚且更易于实现。 首先，将除数d 【砉，1 ) 划分成长度为2 。的小区间【t ，t 。) ，且 1 7 中南大学硕士学位论文 第三章s k i 除法算法 d l = 去，d “l = d l + 2 。( 3 1 7 ) 这样，区间就用除数的前艿位小数来表示此外，在小区间哺，“。) 里，商数字 选择函数用选择常数来描述 q l + l = j ，如果d e 瞄，如i ) 且s 州刀 m “l ( 0 ( 3 - 1 8 ) 选择常数巩定义如下 m 觚以( 4 ) ，丘( “- ) ) ( o m i n 似- t “，) ，【k - “i ) ) ( 3 1 9 ) 用p d 图表示如图3 - 3 所示： 三 西如l1 2 图3 - 3 选择常数的取值呻 选择常数以区间的形式表示，所以对于部分余数r w t j ，同样无需进行全精 度的比较操作。设选择区间的最小长度为2 一，那么对于 q ，+ i = | e 和，a l ，1 ，0 , 1 , - - , a - 1 ，4 ，选择常数可表示为： m 。= 4 ( 0 2 一，其中4 为整数( 3 2 0 ) 由( 3 1 7 ) 式、( 3 1 9 ) 式与( 3 - 2 0 ) 式可知，商选择函数必须满足如下条件 ( 吐+ 2 。) 以( 0 2 u t _ l “，) ，如果m u 】o ；( 3 - 2 1 a ) 厶( t ) a k ( f ) 2 一。s 以- 1 ( d j + 2 5 ) ，如果r w j 】 0 ( 3 2 1 b ) 1 8 中南大学硕士学位论文 第三章s r t 除法算法 使用不同位数的有限精度除数( p ) ，) 和有限精度的移位后部分余数 ( 九刀) 。) ，设计的难题在于如何确定选择常数和除数区间使得c 和艿都达到最 小但是由p d 图可知两者之间的关系是互斥的，一方的减少会导致另外一方的 增大。一种可能的优化选择是使c + 8 的和达到最小，从而使得商选择函数的输 入操作数的总位数达到最小 显然，j 值的选择必须保证能够取值，也即必须满足( 3 - 2 1 ) 式。相当于 乏援嚣捌乏：翥鬈：爱0 工i ( t ) s 【，0 i ( 4 + 2 。) 如果七 一。7 将厶与的表达式( 3 1 1 ) 代) k ( 3 - 2 2 ) 式，得 俨( 1 - k 卯- p 一) 2 笼( 2 叫p - 办1 ) d 妻i 善 ) 。s ，当七 o 【研，+ l 】+ ( g 川一1 ) 2 2 m 如果m ，+ l 】s o o - 2 6 b ) 可见，其中不存在算术操作，且无进位借位的传递问题在除法运算的最 后一步迭代完成后，二进制补码形式表示的商值即保存在a 寄存器中。 3 7s r t - 4 算法优化 s r t 运算模块是整个运算单元的核心所在传统的s r t 算法中，依据冗余 数字集的定义( 第3 1 节) ，基4 的s r t 算法