（计算机系统结构专业论文）高性能浮点除法及基本函数功能部件的研究.pdf

摘要 摘要 随着v l s i 技术的发展，针对各个方面应用的处理器相继提出，特别是d s p ，m m p 等专用处理器。这些处理器对性能的要求使得除法和基本函数功能部件作为其中独立的 运算部件成为可能。同时，除法和基本函数功能部件的性能也是影响这些处理器整体性 能的一个重要方面。各种应用的处理器对计算速度，芯片面积以及功耗大小有不同的要 求，这对除法和基本函数功能部件的设计提出了相应的要求。 实现除法和基本函数功能部件的常用算法有两类，其中一类是数字循环方法，另一 类是函数叠代方法。数字循环方法是使用基于减法的循环算法每次产生一个商数字；函 数叠代方法是使用基于乘法方法的循环算法逼近精确结果。 对于数字循环算法来说，实现该算法需要的时间延迟可以决定整个处理器的频率： 实现该算法的计算周期可以影响整个处理器的性能。所以，在算法需要的计算周期不变 的情况下，减小时间延迟；或者在时间延迟增加很小的情况下( 增大后的时间延迟在处 理器整体设计对时间延迟约束的范围内) ，减小算法需要的计算周期，对整个处理器的 性能影响比较大。针对以前s r t 算法的实现方法和结构，本文提出两种改进结构：一种 结构可以减少s r t 关键路径上的时问延迟；另一种结构在增加很少时间延迟的情况下， 能够减少s r t - 4 算法( 该算法是处理器中使用比较多的s r t 算法) 的循环次数。 对于函数叠代算法( 包括n e w t o w r a p h s o n 和g o l d s c h m i d 算法) 来说，决定该算法 性能的主要方面之一就是初始值的位数。如果初始值的位数越长，需要的循环次数就越 少，实现该算法需要的计算周期也越少；如果初始值的位数越短，需要的循环次数就越 多，实现该算法需要的计算周期也越多。得到初始值的方法很多，主要包括两种，一种 是适合于得到较短位数初始值的基于多衷相加逼近方法，另外一种是适合于得到较长位 数初始值的多项式逼近方法。本文给出这两种不同类型的改进方法。对于基于多表相加 逼近方法来说，本文给出的优化方法可以减小查找表需要的位数；对于多项式逼近方法 来说，本文给出的新型方法可以减小需要的面积和时间延迟。对于这些方法，本文给出 了详细的数学分析和严格的实验证明。 最后，本文对采用不同参数设计的处理器中常用的浮点除法部件，其中包括基为4 ， 8 ，1 6 的s r t 算法和初始值位数长度分别为1 3 ，1 6 ，2 4 位的n e w t o n r a p h s o n 算法，在 速度，面积和功耗上进行了详细的比较，并给出了相应的结论。 关键字：浮点除法，基本函数，功能部件，数字循环算法，s r t 算法，函数叠代算法 n e w t o w r a p h s o n 算法，g o l d s c h m i d 算法 a b s t r a c a b s t r a o t w i t hd e v e l o p m e n to fv l s it e c h n o l o g y ，t h ep r o c e s s o r sf o ra l l a s p e c t so fa p p l i c a t i o n s h a v eb e e n p r o d u c e d ，e s p e c i a l l y f o rd s p , m m rt h e s e p r o c e s s o r sr e q u i r e m e n tf o rp e r f o r m a n c e m a k ei t p o s s i b l e t h e e l e m e n t a r yf u n c t i o n a st h e i n d e p e n d e n t l y a r i t h m e t i c c o m p o n e n t m e a n t i m e ，t h ep e r f o r m a n c eo ft h e s ee l e m e n t a r yf u n c t i o nc o m p o n e n t si so n eo ft h ei m p o r t a n t f a c t o r sf o rt h ep e r f o r m a n c eo ft h et o t a lc o m p u t e rs y s t e m a l lt h o s ed i f f e r e n tp r o c e s s o r sh a v e v a r i o u sr e q u i r e m e n t sf o rt h es p e e d ，a r e a ，a n dp o w e r o fc o u r s e ，t h o s er e q u i r e m e n t sc a na f f e c t t h ed e s i g n so ft h e e l e m e n t a r yf u n c t i o nc o m p o n e n t s t h e r ea r et w ok i n d so fc o l n l t l o na l g o r i t h m st oi m p l e m e n tt h ee l e m e n t a r yf u n c d o n s ， w h i c hi n c l u d et h ed i g i t a lr e c u r r e n c e a l g o r i t h m a n dt h ef u n c t i o ni t e r a t i o n a l g o r i t h m t h e d i g i t a lr e c u r r e n c ea l g o r i t h mb a s e do ns u b t r a c t i v em e t h o dp r o d u c e saq u o t i e n tn u m b e re a c h i t e r a t i o n ；a n dt h ef u n c t i o ni t e r a t i o na l g o r i t h mb a s e do nm u l t i p l i c a t i v e m e t h o do b t a i n st h e a p p r o x i m a t i o nv a l u eo ft h er e a lq u o t i e n t f o rt h ed i g i t a lr e c u r r e n c ea l g o r i t h m ，t h ed e l a yo ft h ei m p l e m e n t a t i o n sc a nd e c i d et h e f r e q u e n c yo ft h ep r o c e s s o r s ；a n d t h e c y c l en u m b e rr e q u i r e db yt h ei m p l e m e n t a t i o n s c a n i m p a c t t h ep e r f o r m a n c eo ft h ep r o c e s s o r s s o ，r e d u c i n gt h ed e l a yw i t ht h es a m ec y c l en u m b e r o rd e c r e a s i n gt h eq c l en u m b e ro b v i o u s l ya tt h ee x p e n s eo fal i t t l ed e l a y ( t h et o t a ld e l a y s h o u l db el e s st h a nt h ed e l a yc o n s t r a i n to ft h et o t a lp r o c e s s o r ) ，w i l lc o n t r i b u t et oi n c r e a s l ：t h e p e r f o r m a n c eo ft h ep r o c e s s o r ss i g n i f i c a n t l y a sf o rt l l ep r e v i o u s l yp u b l i s h e dm e t h o d sa n d a r c h i t e c t u r e sf o rs r t a l g o r i t h m ，t h i sd i s s e r t a t i o ng i v e so u tt h et w oo p t i m i z e da r c h i t e c t u r e s - o n ec a nr e d u c et h ed e l a yo ft h em - i t i c a lp a t ho fs r t i m p l e m e n t a t i o n ； h e o t h e rc a nr e d u c et h e c y c l en u m b e r o fs r t - 4 i m p l e m e n t a t i o n w h i c h i so f t e nu s e da st h ea l g o r i t h mf o rt l ed i v i s i o n o rs q u a r er o o tc o m p o n e n ti nt h em o d e m p r o c e s s o r s f o rt h ef u n c t i o ni t e r a t i o na l g o r i t h mi n c l u d i n gn e w t o n r a p h s o na n dg o l d s c h m i d ，t h e v e r yi m p o r t a n ta s p e c tf o rt h ep e r f o r m a n c e o ft h a ta l g o r i t h mi st h el e n g t ho ft h es e e dv a l u e i f t h el e n g t hi sl o n g e r , t h er e q u i r e di t e r a t i o nn u m b e ri sl e s s ；i ft h el e n g t hi ss h o r t e r , t h er e q u i r e d i t e r a t i o nn u m b e ri sm o r en u m e r o u s a sf o rh o wt oo b t a i nt h es e e dv a l u e ，t h e r ea r em a n y m e t h o d s p u b l i s h e dp r e v i o u s l y a m o n gt h o s em e t h o d s ，t h e r e a r em o s t l yt w ok i n d so fm e t h o d s o n e i sb a s e do nt h em u t i ，t a b l e sa d d i t i o nm e t h o d s ，w h i c hi sw h i c h i ss u i t a b l ef o ro b t a i n i n gt h e a p p r o x i m a t i o nv a l u e f o r t h es e e dv a l u ew i t ht h es h o r tl e n g t h ；t h eo t h e ri sb a s e d o n p o l y n o m i a l a p p r o x i m a t i o nm e t h o d s ，w h i c hi s s u i t a b l ef o ro b t a i n i n gt h ea p p r o x i m a t i o nv a l u ef o rt h es e e d v a l u ew i t hl o n gl e n g t h t h i sd i s s e r t a t i o ng i v e so u to u ra p p r o x i m a t i o nm e t h o d sf o rt h o s et w o a b s t r a c t d i f f e r e n tk i r i d so fm e t h o d s f o rt h em e t h o d sb a s e do nm u f f t a b l e sa d d i t i o n 、o u ro p t i m i z a t i o n m e t h o dc a nr e d u c et h es i z eo ft h ei o o k u pt a b i e s ；f o r 出em e t h o d sb a s e do np o l y n o r e d a l a p p r o x i m a t i o n ，o u rn o v e lm e t 1 0 dc a n r e d u c et h ea r e aa n dt h e d e l a yo ft h e t o t a lc i r c u i t s a tl a s t ，f o rt h ef l o a t i n g - p o i n td i v i s i o n ，t h ec o m m o na r i t h m e r i ci nt h em o d e m p r o c e s s o r s ， t h i st h e s i sc o m p a r e st h ed i f f e r e n ti m p l e m e n t a t i o n sf o rt h e1 w om e t h o d si n c l u d i n gs r ta n d n e w t o n r a p h s o n o ns p e e d ，a r e aa n d p o w e r i nd e t a i l a sf o rs r t a l g o r i t h m ，i t sr a d i xi n c l u d e s 4 ，8a n d1 6 ；a sf o rn e w t o n r a p h s o na l g o r i t h m ，t h el e n g t ho fi t ss e e dv a l u ei n c l u d e s1 3 ，1 6 ，2 4 b i t a n dw ed r a wt h er e l a t e dc o n c l u s i o n s 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 ，e l e m e n t a r yf u n c t i o n ，c o m p o n e n t ，d i g i t a l r e c u f r e n c e a l g o r i t h m ，s r ta l g o r i t h m ，f u n c t i o n i t e r a t i o n a l g o r i t h m ，n e w t o n - r a p h s o na l g o r i t h m ， g o l d s c h m i da l g o r i t h m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 作者签名：翻 日期 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采j l l 影f - i 、 缩印或其它复制手段保存该论文。 作者签名；0 7 导师签 毫日期： 致谢 致谢 在计算所五年多的时间里，有很多人给予了我热忱的帮助。首先，我要对我敬爱的 导师一韩承德研究员表示我最真挚的感谢。在这些攻读博士学位的时间里，我得到了他 的悉心关怀和耐，心指导，在此表示深深的谢意。对于论文的设计和最后的修改定稿，韩 老师都倾注了巨大的心血。韩老师严谨的治学态度，渊博的学识，孜孜不倦的工作精神， 平易近人的生活作风给我流下了深刻的印象，将使我终生受益。 本文的主要工作更得到了胡伟武研究员的悉心指导。胡老师科学的思维方法、丰富 的科研经验和无比的工作热情，使我克服了重重困难，找到了正确的科研道路，使我受 益匪浅，相信对我今后的工作也将产生深远的影响。对于论文的选题，设计和最后的修 改定稿，胡老师都一一指导。在此表示我衷心的感谢。另外，感谢师母晋红，感谢她对 我生活，学习和工作的关心和照顾。我还要感谢唐志敏研究员对本文给出了宝贵的建议。 在系统结构室学习和工作的时间里，系统结构室的刘凤琴老师、任丽娇老师和杨欣 老师在工作和生活上给予了我很多支持，在此表示深深的谢意。我还要感谢c p u 课题 组共同努力，共同战斗过的同学和同事：王剑、肖俊华、王海霞、周旭、张珩、李文、 范东睿、李祖松、钟石强、范宝霞、安虹、陈岚、程晓东、范宝峡、冯子军、高燕萍、 葛仁北、郭奕、何立强、贺今朝、解咏梅、李健松、齐子初、沈海华、许彤、尹茂新、 张戈、张同新、张逸激、赵继业、郑保建、郑为民、庄泗华、高翔等，在和他们探讨的 有关问题中受到了很多启发。感谢研究生部的老师们为我付出的辛勤劳动。 特别感谢系统结构室的张福新同学，他的帮助给我节约了很多时间和精力，使我能 够快速地完成论文的工作。 感谢我的父母双亲，他们不遗余力的付出，使我有勇气和动力直面人生，并完成一 次又一次自我超越。几十年来他们为了我的成长操碎了心，我无以回报，只希望这篇论 文能够给他们带来一丝欣慰。 最后感谢所有关心和帮助过我的师长、亲人、同事和朋友，我的每一点成绩都应归 功于他们。 ， 第一章引言 1 1 问题的提出 第一章引言 过去的二十年里，超大规模集成电路v l s i 和集成电路处理技术的发展突飞猛进 s l a t e r 9 6 ，芯片技术的设计也取得了很大的进步。各种适合于不同应用的处理器芯片也 紧随发展起来，其中包括通用处理器，d s p ( d i g i t a ls i g n a lp r o c e s s o r s ) 和m m p ( m u l f i m e d i a p r o c e s s o r s ) 等。这些处理器芯片主要对以下三个方面提出了很高的要求： 计算速度 自处理器发明后，计算速度一直是人们追求的目标。一般来说，处理器的计算速度 主要由两个因素决定；处理器的主频和结构。到目前为止，采用超线程技术的p e n t i u m 4 处理器主频已经达到了3 2 g h z p e n t i u m 4 ，该处理器的性能显然比使用相同结构主频较 低的p e n t i u m 4 处理器要高。此外，处理器的速度还与实现结构密切相关。例如，以运 行s p e c 2 0 0 0 的浮点程序为基准，主频为1 5 g h z 的i t a n i u m 2 处理器浮点处理速度比主频 为3 2 g 的p e n t i u m 4 处理器快得多 p e n f i u m 4 。 芯片面积 处理器芯片面积的大小是决定芯片价格的一个重要因素。因为处理器需要的芯片面 积越大，每个圆晶片能容纳的芯片个数越少；因为芯片面积越大，成品率越低。 功耗 随着集程度的增加，处理器的功耗越来越成为突出的问题，现在通用处理器的功耗 已经达到几十瓦，甚至上百瓦 g e n e r a l 0 1 1 。尤其是，各种移动设备以及嵌入式处理器芯 片对处理器功耗提出了严格的要求。 作为各种处理器的主要组成部分，完成处理器中各种运算的功能部件也面临提高速 度，减小面积以及降低功耗的多重压力，尤其是在d s p ，m m p 等处理器芯片中。处理 器主频的提高对相应功能部件的时间延迟提出了新的条件：处理器体系结构的改进( 如 指令级并行度的提高) 对功能部件的数目和结构提出了新的要求。此外，处理器中功能 部件数目的增加以及处理器面积和功耗的限制也对功能部件的面积和功耗提出了严格 的要求。 功能部件主要包括加法，乘法，除法以及适合于某些特殊应用需求的基本函数功能 论文：高性能浮点除法及基本函数功能部件的研究 部件。在本文中，基本函数功能部件主要指能完成某种特殊运算功能的部件，包括实现 开根，正弦，余弦，倒数，开根倒数，对数，指数等基本函数的运算部件。 除法和基本函数功能部件在各种处理器中起着重要作用。作为处理器的组成部分， 这些功能部件也必须满足整个处理器的速度，面积以及功耗的设计要求。本章将重点介 绍浮点除法以及基本函数功能部件在通用处理器和其它各种处理器中的作用，同时给出 1 0 0 a i r铀nmu f 删ds 椭a 随 m o vc v t ：ln c 计w 图1 1 浮点指令的分布图 图1 2 浮点功能部件因阻塞对c p i 增加的分布 2 o o o (i垦奄呈罂一臣i豆毒。|擞 第一章引言 论文的总体框架。 1 2 浮点除法部件在处理器中的重要性 在针对各种应用的处理器中，浮点除法功能部件的性能直接影响处理器的整体性 能。以下，本章将以介绍浮点除法部件在高性能通用处理器中的作用为例，说明浮点除 法部件在当代各种处理器中的重要性。 1 2 1 计算周期的影晌 浮点除法在实际应用程序中占有一定的比例，用计算周期数较大的硬件实现或软件 模拟浮点除法指令将增加处理器的每条指令需要的周期数，c p i ( c y c l e s p e r c e n t i n s t r u c t i o n ) ，从而降低处理器的整体性能。 在文章 o b e r m a n 9 7 ，1 1 中，作者研究了评估通用处理器性能的基准程序s p e c f p 9 2 【s p e c 9 2 1 中的各种应用程序，得出各种浮点指令包括加法，减法，乘法，除法以及开根 等指令占所有浮点指令中的比例，如图i i 所示( s p e c f p 9 2 中的各个应用程序编译时都 采用0 3 的优化) 。图1 1 中显示浮点加法指令( 在图1 1 中，浮点加法指令包括a d d ，s u b ， m o v e c o n v e r t 指令) 大约占所有浮点指令的5 5 ；浮点乘法大约占3 7 ；浮点除法大约 占3 ；开根指令大约占0 3 3 。和浮点加法和浮点乘法相比，浮点除法的比侧很小。然 而，假如浮点除法运行时间太长的话，会大大影晌处理器整体性能。如果执行一条浮点 除法运算指令需要2 0 个计算周期，浮点加法和浮点乘法指令都只需要3 个计算周期，那 么浮点功能部件因为阻塞时间对增加处理器c p i 的影响如图1 2 。阻塞时间是指下一条指 令因为依赖于上一条未完成的浮点指令结果而被迫等待的时间。图t 2 表明浮点除法指令 大约占医所有浮点指令阻塞等待而引起的整个处理器性能下降的4 0 ，浮点加法大约占 4 2 ，浮点乘法大约占1 8 。浮点除法不同计算周期对c p i 的影响如表1 1 所示。假如处 理器中没有浮点除法运算部件，而采用软件处理的方法，即当执行浮点除法指令时就调 表1 1 浮点除法不同计算周期对c p i 的影响 d w i d e rt v d el a t e n c v ( c y c l e s le x c e s sc p l 1 殖s 只t 4 0( o 5 2 - b i ts r t 2 0 。4 0 1叩1 0 ，0 3 2 1 4 - b 诗s r 覃n 0 。2 0 11 0 _ 0 4 0 ，10 1 8 j ls j ta r i d 1 4 。 0 1膨0 1 ，0 ，0 7 1 s e l f - 可r e e d v e r y h i g h 8 _ 1 6 寸3 2 5 3 如果通过更精确( 即位数更长) 的 初始值，如8 位，那算法只要3 次就可以得到精确值，所以得到精确的初始值是提高计 论文t 高性能浮点除法及基本函数功能部件的研究 算速度的重要方法。一般情况下，初始值可通过查r o m 表得到。但是为了提高初始 值的精度，如果只通过直接查表方法，需要的r o m 表会很大，以致于在处理器芯片难 以实现。论文的部分工作就是致力于优化得到初始值的方法。 从叠代函数的表达式，可以发现每次叠代需要先计算( 2 一b x x ，) ，然后再得到 x ( 2 一b x ，) ，这样就需要两个相关的浮点乘法操作。在最后的叠代得到除数倒数之后， 使用被除数与之相乘可以得出舍入前的商。 以上方法因为每次叠代需要两个相关浮点乘法操作，所以具体实现需要多个计算周 期。为了把每次循环中两次相关的浮点乘法变成无关的操作，除数倒数的叠代表达式可 以由以下表达式表示： = ( 1 十( 1 一扫) + ( 1 一b x x 0 ) 2 十+ ( 1 - b x ) ) i + ( 5 ) 最后的商可表示为 口= “j = “o x ( i + ( i b ) ( x o ) + ( i b x x o ) 2 + 十( 1 - b x x o ) ) ，i _ 忙( 6 ) 得到的商与精确值的误差为 = a l b q = a x 。( 1 b x o ) “ ( 7 ) 其中确为初始叠代值，即为1 b 的初始逼近值。 从该算法的误差表达式也可以明显看出，如果初始值x 。和除数倒数的相差越小，那 么计算( 1 一自j 。) 的幂次数i 就越小，得到正确结果的速度也越快。例如，假如 1 l b i = q ； 8 ) 在完成所有的循环后，q 的最高n 位数形成最后舍入前的商。同时，该算法可以直 接通过右移p 值的j q 位得到最后的余数，该余数是假定得到q 的全部位数为商。 假如只有q 前的n 位用作商，则最后的余数值为q 1 x y + p ，其中q 1 为q 值去掉前 r i 位的低位数。 该算法每次循环可以得到m 2 位商的结果，这样，一个n 位结果的商需要循环1 1 ，( m 2 ) 次。因为m 的大小跟查表相关，如果得到初始值越精确，则循环的次数也越少。 该算法需要的主要硬件如下。需要使用查找表方法得到初始值的电路：需要三个乘 法器：一个大小为( m 十i ) n 的乘法器用于初始的乘法操作( 如步骤1 ) ：另外一个大小 为( m4 - 1 ) x ( m + n ) 的乘法器用于循环计算；另外一个大小为( m + 1 ) x r t l 的乘法器用于计算 商：此外，还需要一些加法电路计算部分余数、商以及余数等。 2 42 短位倒数的方法 利用几乎相同的原理，c y r l x 8 3 d 8 7 算术协处理器使用了一个短倒数算法得到每次循 环可瞄得到1 7 位商结果的除法器( b r i g g s 9 3 l m a t u i a 8 9 j 。在该算术部件牢，不是采用多 个不同大小的乘法器，而只使用了一个1 8 x 6 9 的矩形乘法器。在得到( 1 e ) 的初始值时， c y r i x 处理器使用n e w t o n r a p h s o n 算法得n - - 个1 9 位的逼近值。在该协处理器中，计 算除法总共需要1 5 计算周期，其中6 个计算周期用于得到1 9 位的初始值。如果，能够 提高得到初始值的方法，就能减少得到扔始值的计算周期，从而达到提高除法都件性能 的目的。此外，如果能得到比1 9 位更长的初始值，那也可以减小循环的次数，从而减 小得到计算结果的计算周期。 第二章实现除法和基本函数功能部件的算法概述 2 4 3 极大基数算法小结 与数字循环算法相比，极大基数算法使用适当的面积和时间延迟，每次循环可以得 到位数较多的计算结果，并且可以直接得到余数。由于极大基数算法和函数叠代算法一 样，都是基于乘法的算法，所以需要较大的乘法器，这需要较大的面积。此外，算法叠 代开始时也需要初始值，所以也可阱通过得到更精确的初始值的方法来减少循环次数， 从而提高该算法的性能。 2 5 本章小结 本章主要介绍处理器中实现除法和基本函数功能部件的常用算法，包括数字循环算 法，函数叠代算法以及极大基数算法。其中数字循环算法和极大基数算法是线性逼近计 算结果；而函数叠代算法是二次方逼近计算结果。一般来说，数字循环算法适用于对除 法性能要求比较低的处理器中：而函数叠代算法和极大基数算法适用于对除法性能要求 比较高的处理器中。并且对于函数叠代算法和极大基数算法来说，初始值的精度( 即叠 代开始时的初始值位数) 是决定这些算法性能的重要因素。 在实现功能部件时，不管采用什么算法，都是围绕速度，面积，时间延迟以及功耗 这四个主要指标来考虑具体的设计。论文的工作主要围绕数字循环算法中的s r t 算法和 函数叠代算法展开。对于s r t 算法，论文主要考虑算法的时间延迟和计算速度；对于函 数叠代算法论文主要考虑如何得到初始值，即如何利用较少的面积和时间延迟得到比 较精确的初始值。 第三章减小s r t 除法算法时间延迟的方法 第三章减小s r t 除法算法时间延迟的方法 随着处理器技术的发展，高性能的浮点除法部件对处理器胜能的提高越来越重要 【o b e r m a n 9 7 2 。s r t 作为一种主要的浮点除法算法，已经广泛使用在当代处理器( 女l h n t e l p e n t i u m 、h p p a 8 0 0 0 等 s o d e r q u i s t 9 7 】) 中，提高该算法性能有很重要的意义。 处理器性能的迅速提高，除了因为v l s i 技术的飞速发展外，还有一个重要的原因就 是处理器体系结构的改进。改进处理器体系结构一个重要的方法就是增加流水线深度。 这样，就需要每级流水线的时间延迟迅速下降。对于采用s r t 算法的除法部件而言，希 望在不减小基数的前提下，即不改变每次循环得到的结果位数减小关键路径的时间延 迟来满足整体设计对时间延迟的要求。因为采用s r t 算法的除法部件面积相对于其它功 能部件来说，如浮点乘法，浮点加法等，比较小，同时因为v l s i 技术的发展，所以对面 积的要求相对比较宽松。在这些情况下，希望找出能减d 、s r t 算法时间延迟的新方法， 即使需要增加少量的面积。 根据基数的大小，可以把s r t 算法分为大基数和小基数两种情况。一般情况下，大基 数的结构是由小基数重叠而成的。对大基数来说，关键路径的时间延迟将比较大。减小 大基数时间延迟主要方法是把算法中可以并行的部分尽可能并行执行。s r t 浮点除法算 法的传统优化方法包括 p r a b h u 9 5 f a n d r i a n t 0 8 7 【f a n d r i a n t 0 8 9 】【o b e r m a n 9 8 t a y l o r 8 5 】 q u a c h 9 2 ，这些方法把该算法的基本步骤进行重叠，并行执行以降低时间延迟。本章在 介绍这些传统的优化结构后，给出优化方法。该方法可以进步减d 、s r t 算法传统结构中 关键路径的时间延迟。实验表明，无论是小基数或大基数的s r t 算法，与传统的结构相 比，本章给出的优化方法都可以降低时间延迟。 本章第2 节，简要讨论s r t 除法算法；第3 节，讨论小基数s r t 除法算法的传统实现 结构：第4 节，讨论大基数s r t 除法算法的传统优化方法以及相应的结构；第5 节，针对 小基数s r t 除法算法的传统结构给出优化结构；第6 节，针对大基数s r t 除法算法的传统 结构中时间延迟较短的结构，进行优化；第7 节，针对s r t 除法算法的基4 ，基8 ，基1 6 情况，比较传统结构和优化结构得出时间延迟和面积实验结果；第8 节，给出本章的结 论。 2 l 论文：高性能浮点除法及基本函数功能部件的研究 3 。2s r t 除法算法 3 2