（精密仪器及机械专业论文）计算机算术中若干前缀计算问题的研究(精密仪器及机械专业优秀论文).pdf

摘要 计算机算术是一个亘古而恒新的论题。随着微电子技术的飞速进步，以硬件电路 来实现的算术运算种类越来越丰富、运算器的位宽越来越大。但是二进制定点整数加 法始终是通用微处理器、数字信号处理器( d s p ) 和专用集成电路( a s i c ) 等各类集 成电路中最常用和最基础的算术运算。透彻而系统地研究整数加法器以及各种算术运 算单元中的各项处理技术意义重大。 本文以前缀计算的基本概念和图示方法为基础提出前缀计算图的张度、张度空间 等一系列相关概念、定义和定理与推论，完善和丰富了前缀计算的理论体系，为本文 的后续研究和证明提供理论基础。 本文对各种经典加法器的计算原理深入、系统地进行分析和必要的证明，一方面 从逻辑功能的角度将加法器分解成“计算各单个位上的进位条件”、“进位链计算” 和“根据进位情况计算最终和”三部分计算，另一方面将各种加法器的进位链构成方 式统一成四种分块递归扩展组织方式，提出了整数加法器计算和构成的内在统一模型。 本文通过对“根据进位情况计算最终和”这一部分进行演化，指出能够以各种不 同进位链结构的整数加法器为基础而仅以极少量电路逻辑改变“根据进位情况计算最 终和”就实现各种“拓广加法”运算，如双加运算、模加运算和差的绝对值求解。 本文提出并分析、证明“模2 ”一1 加”和“模2 ”+ 1 加”的新算法。对于“模2 ”一1 加”运算，提出了拆环式的新方案，既可以用于1 补码，也可以用于二进制原码和补 码：对于“模2 ”+ l 加”运算，改变了传统的基于缩一码的作法，改为基于原码直接 进行计算，不仅改进了计算性能还减少了为了实现计算而进行的编码转换开销。 本文将构建的前缀计算理论体系和整数加法器的内在统一模型应用于构造三类前 缀计算图：最小深度前缀计算图的规则构造、最小深度前缀计算图的混合结构构造以 及任意深度最小延迟前缀计算图的构造。进一步定义一系列概念( 如计算自由度、可 行区间等) 、提出并证明一系列定理和推论，并以此为基础构造求解算法并对算法的 正确性进行形式证明。 本文将前缀计算理论应用于前导零问题。从前缀计算的角度，提出一系列的定义、 定理，证明了前导零检测算法本质上都可以归结为前缀计算问题，因而适用递归式求 解方法。在此基础之上，给出了前导零的二分递归检测算法，并加以证明；对于前导 零的预测方法，通过对加法运算量做“借位留存”减法，将对两个运算量的预测转换 为对 l ，0 ，一1 数字字符集上的数字串的特征检测问题，从而能够应用二分递归求解方 法；经过细致分析、通过采用了消除连续的“一1 ，串的重编码技术而提出了一种统一 位串形式来预测前导零的位数，并设计出一组位串构成形式的递归判别方法和前导零 位数的递归推断方法，解决了前人预测方案对有些情况有可能存在误差为l 的问题。 本文还进一步将前导零预测的新方法应用于乘法一加法熔合运算单元，提出了加法 与舍入处理相结合的双路径处理设计，对前人的设计作了改进，针对不同类型的运算 数据采用不同的数据通路进行计算，降低了平均节拍数、提高了计算效率。 关键词：计算机算术前缀计算整数加法器模加运算前导零乘法加法熔舍运算 a b s t r a c t c o m p m e ra r i t h m e t i c ，at r a d i t i o n a lr e s e a r c ht o p i c ，i ss t i l l ah o t - s p o tw i t hu n c e a s i n g i m p r o v e m e n t s w h i l et h ep r o c e s sa n ds o , a l eo fi n t e g r a t e dc i r c u i tg e t sd r a m a t i c a l l yp r o g r e s s ， a r i t h m e t i co p e r a t i o n si m p l e m e n t e di nh a r d w a r ec i r c u i t r ya r eb e c o m i n gm o r ea n dm o r e a b u n d a n t , a n dt h eo p e r a n di sb e c o m i n gw i d e ra n dw i d e r h o w e v e r , b i n a r y 血e d p o i n t ( i n t e g e r ) a d d e ri sa l w a y st h em o s tc o l o l o na n df u n d a m e n t a la r i t h m e t i co p e r a t i o ni nk i n d s o f i n t e g r a t e dc i r c u i t s ，s u c ha sg e n e r a l - p u r p o s e dp r o c e s s o r ( g p p xd i g i t a ls i g n a lp r o c e s s o r ( d s p ) a n da p p l i c a t i o n - s p e c i f i ci n t e g r a t e dc i r c u i tf a s i c ) s oi t i sc m c i mt ot h o m u l ya n d s y s t e m a t i c a l l yr e s e a r c hi n t e g e ra d d e r sa n dv a r i o u sp r o c e s s i n gt e c h n i q u e su s e di nk i n d so f a r i t h m e t i ca n i t s b a s e do nt h eb a s i cc o n c e p t sa n di l l u s t r a t i o nm e t h o do fp r e f i xc o m p u t a t i o n ，t h i s d i s s e r t a t i o np r o p o s e sas e r i e so fr e l e v a n tc o n c e p t s ，d e f i n i t i o n s ，t h e o r e m sa n di n f e r e n c e s ， s u c ha ss p a na n ds p a ns p a c eo f p r e f i xc o m p u t i n gg r a p h ，w h i c hi m p r o v ea n de n r i c ht h ep r e f i x c o m p u t a t i o nt h e o r ys y s t e m , t h e r e f o r ep r o v i d et h er a t i o n a l ef o rs u b s e q u e n tr e s e a r c h e sa n d d e m o n s t r a t i o n s t h i sd i s s e r t a t i o na n a l y s e sc o m p u t a t i o np r i n c i p l e so f v a r i o u sc l a s s i c a la d d e r sd e e p l ya n d s y s t e m a t i c a l l y ，a n dp r o v i d e sn e c e s s a r yd e m o n s t r a t i o n s o nt h eo n eh a n d ，t h ea d d e r ，f r o mt h e a s p e c to fl o g i c a lf u n c t i o n ，i sd e c o m p o s e di n t ot h r e es t a g e sf o rc o m p u t a t i o n ：c o m p u t i n go f c a l t yc o n d i t i o no f e a c hb i t , c o m p u t i n go f c a r r yc h a i na n dc o m p u t i n go f f i n a ls u ma c c o r d i n g t ot h er e s u l t i n gc a r r ys i t u a t i o no f c a r r yc h a i n ；o nt h eo t h e rh a n d ，c o n s t r u c t i o nm e t h o d o l o g i e s o fc a r r yc h a i n so fv a r i o u sa d d e r sa r eu n i f i e dt of o u rk i n d so fb l o c k - b a s e dr e c u r s i o n e x p a n s i o no r g a n i z a t i o n s ，h e n c et h eu n d e r l y i n gu n i f i e dm o d e lf o ri n t e g e ra d d e r si sp r e s e n t e d b ye v o l v i n gt h el a s tc o m p u t i n gs t a g e ，c o m p u t i n go ff i n a ls u ma c c o r d i n gt ot h e r e s u l t i n gc a r r ys i t u a t i o no fc r i t yc h a i n ”，t h i sd i s s e r t a t i o ni n d i c a t e st h a tb a s e do ni n t e g e r a d d e r sw i t hv a r i o u sc a r r yc h a i ns l r u c t u r e s ，v a r i o u s e x t e n d e d a d d i t i o no p e r a t i o n s ，s u c ha s d u a la d d i t i o n ，m o d u l oa d d i t i o na n da b s o l u t eo fd i f f e r e n c e , c a nb ei m p l e m e n t e dw i t hm i n o r l o g i cm o d i f i c a t i o nt ot h el a s tc o m p u t i n gs t a g eo f a d d e r s i nt h i sd i s s e r t a t i o n ，n o v e ls c h e m e sf o rm o d u l o2 n 一1a d d i t i o no p e r a t i o na n dm o d u l o 2 ”+ 1a d d i t i o no p e r a t i o nr e s p e c t i v e l ya r ep r o p o s e d ，a n a l y z e d ，a n dd e m o n s t r a t e d a sf o rt h e m o d u l o2 ”- - 1a d d i t i o n o p e r a t i o n , l o o p d e m o l i s h e da p p r o a c hi sa d o p t e d ，w h i c hi s a p p l i c a b l ef o r1 - c o m p l e m e n tr e p r e s e n t a t i o n , 2 - c o m p l e m e n tr e p r e s e n t a t i o na n du n s i g n e d b i n a r yc o d e ；a sf o rt h em o d u l o2 ”+ 1a d d i t i o no p e r a t i o n ，t h ep r o p o s e dn o v e ls c h e m ei s d i r e c t l yb a s e do nu n s i g n e db i n a r yi n s t e a do f t r a d i t i o n a ld i m i n i s h e d 一1n u m b e rr e p r e s e n t a t i o n ， n o to n l yi m p r o v e st h ec o m p u t i n gp e r f o r m a n c eb u ta l s or e m o v e st h eo v e r h e a df o rc o d e t r a n s f o r m sb e t w e e nu n s i g n e db i n a r yc o d ea n dd i m i n i s h e d - 1r e p r e s e n t a t i o n p r e f i xc o m p u t a t i o nt h e o r ys y s t e ma n du n d e r l y i n gu n i f i e dm o d e lo fi n t e g e ra d d e r ， c o n s 仃u c t e db yt h i sd i s s e r t a t i o n ，a r ea p p l i e dt oc o n s t r u c tt h r o et y p eg r a p h so fp r e f i x c o m p u t a t i o n ：t h er e g u l a rc o n s t r u c t i o no fm i n i m a l - d e p t hp r e f i xc o m p u t a t i o ng r a p h 、h y b r i d s t r u c t u r eo fm i n i m a l - d e p t hp r e f i xc o m p u t a t i o ng r a p ha n ds t r u c t u r eo fm i n i m a l - l a t e n c y a r b i t r a r y - d e p t hp r e f i xc o m p u t a t i o ng r a p h a n dt h e nas e r i e so fc o n c e p t s ，s u c ha sc o m p u t i n g f r e ed e g r e s s ，v i a b l ei n t e r v a l ，e t c ，a r ed e f i n e d ，a n da r eu s e dt od e m o n s t r a t eas e r i o u so f t h e o r e m sa n di n f e r e n c e s ，m o r e o v e rb a s e do i lw h i c h ，t h es o l u t i o na l g o r i t h mi sc o n s t r u c t e d a n dt h ec o r r e c n t e s so f t h ea l g o r i t h mi sf o r m a l l yd e m o n s t r a t e d i nt h i sd i s s e r t a t i o n ，p r e f i xc o m p u t a t i o nt h e o r yi sa l s oa p p l i e dt os o l v el e a d i n g - z e r o s p r o b l e m f r o mt h ea s p e c to fp r e f i xc o m p u t a t i o n ，as e r i e so fd e f i n i t i o n sa n dt h e o r e m sa r e p r o p o s e da n du s e dt od e m o n s t r a t et h ef a c tt h a tl e a d i n g - z e r o sd e t e c t i o na l g o r i t h mc a l l e s s e n t i a l l yb ec o n c l u d e da so n et y p eo fp r e f i xc o m p u t a t i o n , s ot h a ti ti sa p p l i c a b l ef o r r e c u r s i o na p p r o a c h e s b a s e do nt h i sf a c t ，t h eb i n a r yr e c u r s i o nd e t e c t i o na l g o r i t h mo f l e a d i n g - z e r o si sp r e s e n t e da n da l s od e m o n s t r a t e d f o rt h el e a d i n g - z e r o sa n t i c i p a t i o n ，b yo n c eb o r r o w - s a v es u b t r a c t i o no f t h et w oa d d i t i o n o p e r a n d s ，t h ea n t i c i p a t i o np r o b l e mt o w a r d st w oo p e r a n d si sc o n v e r t e di n t ot h ep r o b l e mo f c h a r a c t e r i s t i cd e t e c t i o nt o w a r d st h ef i g u r es t r i n g sr e p r e s e n t e di nt h er e d u n d a n td i g i ts e to f 1 ，0 ，l ，s o t h a t b i n a r yr e c u r s i o n a p p r o a c hc a n b ea p p l i e d a f t e rd e t a i l e da n a l y s i s ，b ya d o p t i n gt h er e c e d i n gt e c h n i q u et oe l i m i n a t ec o n s e c u t i v e “一1 ”s t r i n g ，au n i f i e db i tp a t t e r nt oe x a c t l ya n t i c i p a t et h eb i tn u m b e r so fl e a d i n g - z e r o si s p r e s e n t e d ，a n d8r e c u r s i o nd i s t i n g n i s h m e n tm e t h o df o ras e to fb i ts t r i n gf o r m sa n da r e c u r s i o nd e d u c t i o nm e t h o da r ep r e s e n t e dt o o ，r e s o l v i n gt h ep r o b l e mo f e r r o rp o s s i b i l i t yo f1 u n d e rc e r t a i nc o n d i t i o nb ya p p l y i n gp r e v i o u sa n t i c i p a t o r ya p p r o a c h i nt h i s d i s s e r t a t i o n ，t h en o v e le x a c tl e a d i n g - z e r o s a n t i c i p a t i o n i su s e di n m u l t i p l y 。a d d - f u s e du n i t an o v e lt w o - p a t hs c h e m eo fm u l t i p l y a d d - f u s e du n i ti sp r e s e n t e d ， w h i c hc o m b i n e sa d d i t i o na n dr o u n d i n g ，i m p r o v e st h e p r e v i o u sd e s i g nb ya d o p t i n gt w o d a t a p a t h sf o rc o m p u t a t i o na c c o r d i n gt ot h er e l a t i o n s h i po fo p e r a n d s t h et w o - p a t hs c h e m e d e c r e a s e sa v e r a g eb e a t sa n di n c r e a s e se f f i c i e n c yo f c o m p u t a t i o n k e y w o r d s ：c o m p u t e ra r i t h m e t i c ，p r e f i xc o m p u t a t i o n ，i n t e g e ra d d e r , m o d u l oa d d i t i o n o p e r a t i o n ，l e a d i n g - z e r o s ，m u l t i p l y - a d d - f u s e do p e r a t i o n 插图清单 图2 - 10 次和1 次前缀计算的图示法 图2 - 2 前缀表达式p c 6 d ) 的两种不同计算结合过程 图2 _ 3 前缀表达式c ) ( 6 d ) ) 的两种不同计算过程1 1 图2 _ 4 全加器示意图1 4 图2 _ 6 行波进位加法器进位计算的前缀计算图2 0 图2 _ 7b r e n t - k u n g 加法器进位计算的前缀计算图2 0 图2 8s k l a n s k y 加法器进位计算前缀计算图2 2 图2 - 9 k o g g e - s t o n e 加法器进位计算前缀计算图。2 3 图2 1 0h a r t - c a r l s o n 加法器进位计算前缀计算图2 4 图2 1 1s n i r 的前缀计算结构分治构造法：减半式递归构造2 5 图2 1 2 整数加法运算的逻辑分解2 5 图2 1 3 一级进位跳跃加法器原理图2 7 图2 1 4 一级进位跳跃加法器进位传递最坏情况示意图2 9 图2 1 5 一级进位跳跃加法器进位前缀计算图3 0 图2 _ 1 6 曼彻斯特进位链加法器示意图3 1 图2 _ 1 7 多级进位跳跃加法器示意图3 l 图2 _ 1 8 进位选择加法器原理示意图3 2 图2 _ 1 9 进位链前缀计算图的递归构造：块的并列式扩展单级补缀方案3 6 图2 - 2 0 进位链前缀计算图的递归构造：块的并列式扩展的一般形式3 7 图2 _ 2 14 位进位链补缀计算块的几种不同方案( 未列全) 3 7 图2 _ 2 2 进位链前缀计算图的递归构造：块的级联式扩展3 8 图2 _ 2 3 进位链前缀计算图的递归构造；块的减数式扩展3 9 图2 _ 2 4 进位链网络的功能拓展：复合加法器4 l 图2 - 2 5 进位链网络的功能拓展：模2 ”一1 加运算电路“ 图2 _ 2 6 进位链网络的功能拓展：基于珂+ 1 位原码的模加2 ”+ l 运算 图2 _ 2 7 差的绝对值：基于进位链网络的末级求和单元 图3 - 1 在同一行中只采用一种共用系数的最小深度前缀计算图 帖 记铂 图3 _ 2 在同一行中采用若干种共用系数的最小深度前缀计算图。6 3 图3 - 3 可扩展区间和扩展点的递归扩展7 3 图4 - 1浮点数编码的i e e e 标准格式，。8 l 图4 _ 2 前导零位数的两种求解策略一8 2 图4 - 3 前导零位数的递归式检测算法8 7 图4 _ 4 前导零位数的递归式预测算法应用示例9 3 图5 - 1乘法珈法熔合运算单元功能框图：常规方案9 6 图5 - 2 乘法- j j t l 法熔合运算单元中的对阶移位示意图9 7 图s - 3 乘法_ 力1 2 法熔合运算单元功能框图：加法与舍入相结合的方案9 8 图5 _ 4 乘法力口法熔合运算单元功能框图：加法与舍入相结合的双路径方案1 0 0 图5 5 乘法- 力口法熔合运算单元之加法与舍入相结合的双路径方案的路径结构1 0 0 表格清单 表3 - ! 1 6 位加法器采用不同共用系数序列所使用的计算资源( 黑色格点) 数6 l 表4 _ l 数字串的重编码表9 0 独创性声明 本人声明所呈交的学位论文是本人在导师指导f 进行的研究： 作及取得的研究成果。据我 所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究 成果，也不包含为获得 佥壁王些盔堂 或其他教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：j l 、翕本签字日期：加u 。年，- 月g 日 学位论文版权使用授权书 本学位论文作者完全了解盒世王些盔堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的夏印件和磁盘，允许论文被查阅和借阅。本人授权盒匿王堡 烂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：j 、，晶戽 签字日削： 一6 年，2 月占日 学位论文作者毕业去向 i ：作单位 通讯地址 导师签名 舞陀、 签字日期：知缉，2 月臼 电话 邮编 1 1研究动机 第一章绪论 计算机算术是一个亘吉而恒新的研究论题。且不表中国古老的算盘实质上采用了 混合进制的位置记数法，仅电子计算机问世以来，计算机算术得到了持久而长足的发 展，人们不断提出各种记数法( n u m b e r r e p r e s e n t a t i o n ) ，如对于整数有原码、2 补码、 l 。补码、缩1 码、余数记数法、冗余数字集记数法等不而足；并针对各种记数方式 不断提出各种新颖的算术运算器设计方案。时至今日，计算机领域的重要权威刊物( 如 i e e e 计算机会刊等) 仍不断地刊出计算机算术方面的最新研究成果。 随着微电子技术飞速进步，集成电路的特征尺寸、工作频率和器件容量得到了极 大的提高。这一方面促成微处理器技术得到长足发展，微处理器的字长不断拓宽，目 前已有速度超过1 0h z 的6 4 位微处理器芯片；另一方面，随着微处理器计算能力的极 大提升，人们的计算需求空前高涨，科学计算、数字信号处理、3 维图像处理、天气 预报等应用促使人们直接用电路硬件去实现越来越多种类的算术运算。而微电子技术 的飞速进步，使得这一切成为可能，不仅浮点数加法、乘法运算通过硬件电路直接实 现，而且近些年来人们越来越多地开始讨论一些复杂运算和复合运算，如方根运算、 浮点乘法动口法熔合运算等等。 然雨，在这一切背后，二进割整数加法( 亦稼为定点加法) 仍是最重要的算术运 算，它不仅是各类微处理器中最常涉及的运算( 包括运算指令和地址形成单元) 和浮 点数运算的基础，而且它还是其他各种记数法实现计算的基础，这是由于数字电路目 前只有0 和l 这两种状态的现实所决定的。 整数加法器的设计不断推陈出薪、其他复杂运算亦是如此，让人眼花缭乱。各种 不同计算结构的整数加法器之间是否存在着某种相近、相通的内在联系? 不同种类的 计算机算术运算的计算环节之间是否存在着内在一致的联系和设计思路? 因此，研究如何有效地实现二进制整数加法以及各种整数加法器的内在机理是集 成电路设计中的重大问题；将其内在的数学原理卓有成效地用于复杂的计算机算术运 算的某些计算环节，对设计人员而言也将是一种挑战。 2合肥工业大学博士学位论文 1 2相关工作 1 2 1 整数加法器 笔者认为：整数加法器的各种设计方案基本上可以划分成两太类。 第一类是基础性的设计，仅仅讨论加法的计算过程，也可以认为是讨论加法的进 位计算过程( 下文亦称为进位计算结构) ，而不讨论如何结合( 晶体管) 电路技术( 如 动态电路技术) 实现计算，如行波进位加法器、进位跳跃加法器、多级进位跳跃加法 器、进位选择加法器、超前进位加法器等，笔者也将这一类设计称为“结构设计”。 第二类是在结构设计基础之上，再结合具体的( 晶体管) 电路技术而实现的改进 方案，笔者将这一类设计称为“电路设计”。如，k s c h o n g 等人【i 】和c - j ，f a n g 等人 嘲都利用动态电路技术实现了行波进位加法器；l i n g 算法加法器 3 1 基于发射极耦合逻辑 电路，而文献 4 1 尝试采用c m o s 逻辑电路实现l i n g 算法加法器。 为了更好地揭示整数加法器的计算过程和计算结构，本文将避开各种( 晶体管) 电路技术而着重研究各种结构设计以及它们的内在机理。 在文献记载的各种结构设计中，有单一结构方式的设计，也有采用混合结构方式 的设计。譬如，为了提高进位跳跃加法器的运算时间。m c h a 等人哪将原有的第一组 的行波进位结构改为超前进位结构；而n b u r g e s s t 6 _ i 则通过将最后一组改为进位选择结 构来提高进位跳跃加法器的运算速度。 为了找寻某种结构的最佳工作点参数，p ，k c h a r t 等人f 卅和v k a n t a b u t r a 9 1 采用程 序求解的方法来确定单级进位跳跃加法器的最优分块方法，v k a n t a b u t r a t ”】还采用程序 求解的方法来确定两级进位跳跃加法器的最优分块方法。 还有不少文献也讨论了通过程序求解某种特定的单一结构或者特定方式混合的混 合结构的最优加法器结构求解。 前人在提出各种结构设计时，不论是单结构方式的结构设计，还是混合结构方 式的结构设计，都仅仅论述了所提出的结构在某方面占据优势，而并没有分析各种结 构设计的内在一致性，自然没有可以用于构造任意结构的加法器的手段。 1 2 2 前导零问题 前导零问题的求解方法有两类：检测型方法和预测型方法。各种高效的预测性方 法普遍可能存在误差。这两类求解方法最终都是依靠二分递归的方法计算得出的。但 是为什么二分递归的方法能够有效求解，人们普遍没有加以理性分析。 第一章绪论 1 3 研究目标 根据上述介绍，本文将研究以下内容： ( 1 ) 对前缀计算理论进行扩充，增加度量方面的概念和相关定理、推论，为定量 证明和推导奠定基础； ( 2 ) 以前缀计算理论为工具，系统地分析各种整数加法器的计算原理，寻求它们 内在的统一模型，包括计算过程和进位链的组成结构两方面的情况； ( 3 ) 研究如何根据整数加法器的进位链计算结果来实现更多种类的算术运算，如 双加运算、模加运算等； ( 4 ) 以扩充后的前缀计算理论体系和所提出的整数加法器内在统一模型为理论基 础，研究编程求解满足特定要求的进位链结构的方法，并证明算法的正确性： ( 5 ) 从前缀计算的角度，洞察前导零问题求解可以采用二分递归求解方法的原因； 讨论前导零检测算法；并设计出精确的前导零预测方案； ( 6 ) 将前导零精确预测方案应用于浮点乘法一加法熔合运算单元设计，提出浮点 乘法一加法熔合运算单元的改进设计。 1 4 本文的内容组织 为了实现上述研究目标，本文各章的内容安排如下： 第二章将从前缀计算的角度研究整数( 定点) 加法器的计算原理，力图为各种可 能的整数加法器形式建立统一的计算和构成模型。首先扩充前缀计算理论，然后通过 系统分析各种经典加法器和必要的证明，建立整数加法器构成的内在统一模型；最后 讨论如何对加法器进行改进、根据进位链的结果求解各种“拓广加法”运算，分析双 加器的计算原理，并针对模加运算和模加运算提出新算法。 第三章将第二章所构建的前缀计算理论体系和整数加法器的内在统一模型，应用 于构造三类前缀计算图：最小深度前缀计算图的规则构造、最小深度前缀计算图的混 合结构构造以及任意深度最小延迟前缀计算图的构造。对于每一类前缀计算图构造算 法均将给出正确性证明。 第四章将从前缀计算的角度研究前导零问题i 将提出一系列的定义、定理证明和 分析前导零检测算法和预测算法都可以采用二分递归方法的原因：论述前导零检测算 法；通过细致分析提出用于精确预测前导零位数的统一位串形式，并给出相应的递归 识别和推断方法。 ! 鱼! 坚些查兰苎圭兰垡堡壅 一 第五章将讨论乘法一加法熔合运算单元的设计。首先考察乘法一力口法熔合运算单元 整体架构的常规方案和j i d b r d g e r a 和t l a n g 提出的加法与舍入相结合的方案，然后 提出性能得到改进的加法与舍入相结合的双路径方案。 第六章为论文的结论和展望。 第二章整数加法器内在的前缀计算模型 本章将从前缀计算的角度研究整数( 定点) 加法器的计算原理，力图为各种可能 的整数加法器形式建立统一的计算和构成模型。 将首先在第2 2 节和第2 3 节引入前缀计算的基本概念和图示方法、并以此为基础 提出相关的概念、定义和得到证明的定理与推论，如前缀计算图的张度、张度空间等 等，完善前缀计算的理论体系，为本章和后续章节中的形式证明提供理论基础。 将在第2 4 节和第2 5 节对各种经典加法器的计算原理深入、系统地进行分析和必 要的证明，一方面从逻辑功能的角度将加法器分解成“计算各单个位上的进位条件”、 “进位链计算”和“根据进位情况计算最终和”三部分计算，另一方面为第2 6 节提 出进位链的分块递归组织策略提供必要的准备。 第2 6 节将各种加法器的进位链构成方式统一成四种分块递归扩展方式，一方面 提出了进位链构成的统一模型，另一方面为第三章构造各类满足不同约束的加法器最 优求解算法提供必要的理论准备。 最后在第2 7 节通过对“根据进位情况计算最终和”这一部分进行演化，能够以 各种整数加法器为基础，仅仅以极少量电路逻辑改变“根据进位情况计算最终和”来 实现各种“拓广加法”运算，如双加运算、模加运算和差的绝对值求解。将提出并分 析、证明“模2 ”一l 加”和“模2 ”+ 1 加”的新算法。对于“模2 ”1 加”运算，提出 了拆环式的新方案，消除了前人“尾部进位循环”方案的各项弊端、降低了计算迟滞： 对于“模2 ”+ 1 力口”运算，改变了传统的基于缩码的作法，改为基于原码直接进行 计算，不仅改进了计算性能还减少了为了实现计算而进行的编码转换开销。 2 1 引言 数字电路只有o 和1 这两种状态，因此计算机算术运算器中所采用的各种记数法 本质上都根源于二进制表示法。二进制表示法减少了运算中每一位上可能出现的数值 状态，看上去各种算术计算理应非常容易实现。但是，各种记数法都并没有因为其根 源于二进制而从根本上使得计算机算术的实现得以简化。 6 合肥工业大学博士学位论文 与此相反的是：由于运算量位宽的提高，源于纸笔手工演算( p e n c i la n dp a p e r ) 的 逐位计算方法，如行波进位加法器( r i p p l e - c a r r ya d d e r ，r c a ) ，由于最高位的计算结 果依赖于运算量最低位相加所产生的进位，因此进位的逐位传播将导致长位宽的算术 运算器数据通路的关键路径时滞( 1 a t e n e y ) 过长，从而导致系统运行速度很低。 为此，需要从数学模型上去讨论二进制加法及进位的内在实质和解决进位链问题 的根本方法。 2 2 前缀计算模型 前缀计算理论是一种在并行计算中应用得相当广泛的数学模型i ”一o l 。如( 在多处 理器系统俩络上) 求解线性递归、多项式插值和泛h o m e r 表达式的计算、排列和装箱 问题，数据压缩、处理器分配、负载均衡、a t m 交换管理、路由、循环并行化的指令 调度以及其他许多问题最终都可以归结为前缀计算。 但是由于不同的前缀计算问题所面l 临的资源约束条件【“”“，“，2 6 - 2 8 , 3 1 1 不同，如对计 算总时间和并发度( 即同一时刻可以进行的前缀计算次数) 的约束不同，以及各种不 同的前缀计算问题中前缀算符自身又可能具有某些特殊性质，因此它们的解决方法不 仅不尽相同，甚至还相当悬殊。本文的研究目标是前缀理论在计算计算术中的应用。 2 2 1 前缀计算的一些基本概念 定义2 1 若定义在论域d 上封闭的二元算符“”满足结合律，则称该二元算符 “”为在论域d 上的前缀算符。 定义2 2 若在论域d 上定义了前缀算符“”，则通过有限次( 即0 次或更多次) 使用该前缀算符和括号所构成的表达式称为前缀表达式。具体而言，在论域 d 上按照以下递归规则构造出来的表达式是论域d 上的前缀表达式： ( i ) 对于v x d ，则表达式x 为论域d 上的前缀表达式i ( i i ) 若七为论域d 上的前缀表达式，则表达式( x ) 为论域d 上的前缀表达 式： ( i i i ) 若和恐是论域d 上的前缀表达式，则表达式五乇为论域d 上的前 缀表达式。 第二章整数加法器内在的前缀计算模型 7 性质2 3 前缀表达式中的括号关系只改变整个前缀表达式的运算次序，而不会 改变整个前缀表达式的运算结果。 性质2 3 是由前缀算符自身满足结合律决定的。即，对于论域d 上的任意前缀表 达式一、屯和x 3 ，则而而= b ) x 3 = 五k 而) 。而对于论域d 上的任意 前缀表达式x ，则( ( x ) ) = ( x ) ) 一一0 ) = x 。 一j r r 定义2 4 前缀计算是针对论域d 上长度为”的序列x 0 ，矗q 使用前缀算符 “”计算出序列y o ，儿，n - 1 的过程，序列x o ，x m 和序列 ，儿，儿一l 之间的关系为： r o 、，、 儿。l 薯i 。【而j ，；o n = ( 主墨) = “ 胪卜2 x l x o ) = ( 蔓葺) = k - ，o x n - 2 x i + 1 x 1 o x i _ 1 x 1o x o ) 。 称儿是k 次使用前缀算符所得到的计算结果，其中j = o ，1 ，n - 1 。 2 2 2 前缀计算的图示方法 根据定义2 1 、定义2 2 及性质2 3 ，由于前缀算符“”满足结合律，因而前缀表 达式的计算结合过程不是惟一的。出于直观和便于对比各种计算结合过程的需要，引 入以下图示方法及定义。 8 合肥工业大学博士学位论文 定义2 5 对于0 次前缀计算= x o 和1 次前缀计算m = x 1 可以分别图示为 白色格点( 如图 l ( a ) 所示) 和黑色格点( 如图2 - 1 ( b ) 所示) 。其中，称而、 x l 为格点的输入；称、m 为格点的输出。 萝，扩 定义2 6 根据定义2 5 所绘制的用于表示前缀表达式肌= 墨的计算结合过程 i = o 的矩形格点图称为前缀计算图。每一列对应于一个输入和输出。前缀计算图 。第f 行从右往左数第，个格点记为 。( 行号j 和列号，均从0 开始计数) 。 前缀计算图9 的列数聆称为宽度，记为国( 。) ：其行数( 第一行输入格点不 计入在内) 称为深度，记为占( 。) 。 定义2 7 对于前缀计算图 ，其格点o 。的扇入是指射向该格点的弧线数日， 记为矗，而扇出是该格点射出的弧线数目，记为鹿，。 定义2 8 前缀计算图格点的