（电子科学与技术专业论文）高性能浮点乘、加部件的研究与实现.pdf

国防科学技术大学研究生院硕士学位论文 a b s t r a c t f l o a t i n g p o i n tm u l t i p l ya n df l o a t i n g p o i n ta d du n i ta r ep a r t so ft h eh e a r to f c o m p u t i n gc o m p o n e n t si nh i g h - p e r f o r m a n c em i c r o p r o c e s s o r s ，a n dt h es p e e dh a sg r e a t e f i f e c t s o nt h e p e r f o r m a n c eo f t h ee n t i r e m i c r o p r o c e s s o r r e s e a r c h e s o nt h e h i g h p e r f o r m a n c ef l o a t i n g p o i n tm u l t i p l i e ra n da d d e ra r eo fi m p o r t a n tp r a c t i c a l s i g n i f i c a n c ea n dv a l u ei na w i d er a n g eo fa p p l i c a t i o n s i nt h i sp a p e r w eh a v em a d es o m er e s e a r c ha n do p t i m i z a t i o no nt h ef l o a t i n g p o i n t m u l t i p l i e ra n da d d e ro ft h exp r o c e s s o r w h i c hi sp a r to ft h em a j o rn a t i o n a lp r o j e c t ”h i g h p e r f o r m a n c ep r o c e s s o r ”t h ea c h i e v e m e n t sw i l lb ed i r e c t l ya p p l i e dt ot h ep r o j e c t t h em a i nr e s e a r c hi sa sf o l l o w s 1 r e s e a r c h e so nt h eh i g h p e r f o r m a n c ef l o a t i n g p o i n tm u l t i p l i e ra n da d d e r ，a n d t h e i rk e yt e c h n o l o g i e s b a s e do nt h i sw ed e s i g n e da n di m p l e m e n t e dh i g h p e r f o r m a n c e f l o a t i n g p o i n tm u l t i p l i e ra n da d d e rt ot h exp r o c e s s o r 2 w eh a v ed e s i g n e dt h el e a d i n gz e r od e t e c t i o n ( l z d ) c i r c u i ti ns u i to ft h ex p r o c e s s o r t h ec i r c u i tc a nn o to n l yd e t e c tl e a d i n gz e r o ，b u ta l s op r e c a l c u l a t et h e n o r m a l i z e ds h i f ta m o u n to fb y t e s ，m a k i n gl z da n ds t a n d a r d i z e dc o a r s e g r a i n e d b y t e s h i f t i n go p e r a t i o np e r f o r mp a r a l l e l ，f u r t h e rr e d u c i n gt h el e n g t ho f t h e c r i t i c a lp a t h 3 w eh a v eo p t i m i z e dt h ef l o a t i n g p o i n ta d d e r ，a p p l y i n gt h et e c h n o l o g yo f r o u n d i n gc o m b i n a t i o nt ot h es i n g l ed a t aa c c e s ss t r u c t u r eo ft h ea d d e r i nx p r o c e s s o r ，s o a st oa d v a n c et h eo p e r a t i o nr u n n i n gp a r a l l e lw i t ht h em a i na d d e ro p e r a t i o n t h i sa r t i c l e h a sp u tf o r w a r dac o m p l e t ed e s i g nb l u ep r i n t 4 t h ee n t i r ed e s i g ni st e s t e dt h r o u g hav a r i e t yo fi n p u t s ，i n c l u d i n gi e e ec c 7 5 4 s t a n d a r dt e s tv e c t o r s ，m a r g i n a ln u m b e r sa n dr a n d o mn u m b e r s ，w h i c hg u a r a n t e et h a tt h e d e s i g ni sc o r r e c t f i n a l l y ，w es y n t h e s i z e da n do p t i m i z e dt h ef l o a t i n g - p o i n tm u l t i p l i e ra n da d d e r t h ef l o a t i n g p o i n tm u l t i p l ya n df l o a t i n g p o i n ta d dc o m p o n e n t sw e r ed i v i d e di n t o5 a n d4 p i p e l i n e si n d i v i d u a l l y i na0 13l a mc m o sp r o c e s s ，t h er e s u l t so fl o g i cs y n t h e s i s s h o wt h a tt h ef r e q u e n c yo ft h ef l o a t i n g p o i n tm u l t i p l i e ra n df l o a t i n g p o i n ta d d e rc a n a l lr e a c h7 0 0m h z w h i c hm e e t st h er e q u i r e m e n t so ft h exp r o c e s s o r k e yw o r d s ：f l o a t i n g - p o i n tm u l t i p l i e r ，f l o a t i n g p o i n ta d d e r ，l z d ， r o u n d i n gc o m b i n e 第i i 页 国防科学技术大学研究生院硕+ 学位论文 表目录 表2 1 浮点格式参数一4 表2 2 一阶b o o t h 编码部分积产生规则表8 表2 3 改进的b o o t h 算法8 表2 4 三阶b o o t h 算法的部分积产生规则9 表2 5 各阶b o o t h 编码复杂性比较( 6 4 位乘法) 一9 表2 - 6 对阶移位和规格化移位的情况1 8 表2 7 一些尾数结果和对应的前导0 计算结果1 9 表3 1 选择开关控制信号真值表2 4 表3 2 选择开关控制信号含义2 4 表3 3 两种方案综合结果比较2 5 表3 4 两种压缩器的面积延时比较( d c 综合，0 1 3 u m 工艺库) 一2 9 表3 5 舍入控制表3 5 表4 12 位f f o 真值表3 8 表4 2 八位f f o 真值表4 1 表4 3 选择开关控制信号含义4 2 表4 4 四种可能尾数结果对应的规格化、舍入需求4 3 表4 5c i n 2 ：0 结果选择表4 6 表4 6 最近偶舍入4 6 表4 7 向正无穷舍入4 7 表4 8 最近偶舍入4 8 表4 - 9 向正无穷舍入4 8 表4 10 最近偶舍入一4 9 表4 1 1 向正无穷舍入5 0 表4 1 2 最近偶舍入5 1 表4 1 3 向正无穷舍入一5 l 表5 1 简单测试激励5 5 表5 2 验证最后阶段数据表5 7 表5 3 综合结果5 9 第1 v 页 国防科学技术大学研究生院硕十学位论文 图目录 图2 1 单精度浮点格式4 图2 2 双精度浮点格式5 图2 34 4 的阵列结构部分积压缩器。1 0 图2 44 x 4 的树型结构部分积压缩器1 1 图2 53 ：2 压缩器逻辑结构图1 1 图2 - 64 ：2 压缩器逻辑结构图1 2 图2 74 ：2 压缩器链结构1 2 图2 8 由3 ：2 压缩器构成的4 ：2 压缩器1 2 图2 9 具有3 个x o r 门延时的4 ：2 压缩器。1 3 图2 1 0 具有1 个x o rf - j + 2 个m u x 延时的4 ：2 压缩器1 3 图2 1 1n 位的行波加法器结构1 3 图2 1 24 位的进位选择模块拓扑结构1 4 图2 1 3 线性进位选择加法器1 5 图2 1 4 平方根进位选择加法器1 5 图2 一1 51 6 位k o g g e s t o n e 超前进位对数加法器原理图1 7 图2 1 6 浮点加法运算流程一1 8 图2 1 7 双通路加法器流程图1 9 图2 18 前导0 检测逻辑l z d 2 0 图2 1 9 前导0 预测逻辑l z a 2 0 图3 1 乘法器原理图2 2 图3 2 并行的部分积产生逻辑2 3 图3 3 基于多级二路选择开关的b o o t h 编码器2 3 图3 4 基于o n eh o t 编码的b o o t h 编码器2 5 图3 5 隐藏的加l 操作2 6 图3 - 6 原始部分积阵列2 6 图3 7 假设部分积符号均为负时的部分积阵列2 7 图3 8i = 2 时的情况2 8 图3 - 9i = k 到k + l 的扩展示意图2 8 图3 1 0 假设部分积符号均为负时的优化部分积阵列2 8 图3 1 1 部分积阵列的最终形式2 9 图3 1 2 部分积压缩树结构3 0 图3 1 3 串行的s t i c k y 值计算原理示意图一3 1 第v 页 国防科学技术大学研究生院硕士学位论文 图3 1 4 本文的并行s t i c k y 值计算原理示意图3 1 图3 1 5s t i c k y 等于0 时a 、b 两数形式3 3 图3 1 65 3 位k o g g e s t o n e 超前进位对数加法器原理3 4 图4 1 浮点加法器总体结构3 6 图4 2 全编码方式的l z d 3 7 图4 3f f o 逻辑3 7 图4 4f f o 仿真波形图3 8 图4 56 4 6 编码器结构3 9 图4 6 改进的l z d 逻辑结构3 9 图4 7 字节编码逻辑4 0 图4 8 字节选择逻辑4 0 图4 9 八位的f f o 逻辑4 1 图4 1 0 传统的规格化、舍入串行结构4 2 图4 1 l 规格化、舍入并行结构一4 4 图4 1 2 进位合并结构4 4 图4 一1 3 实现a + b + 2 的加法器结构4 5 图4 1 4 单通道加法器的进位合并结构4 5 图4 1 5c i n 产生逻辑的详细结构图5 2 图5 1 子模块测试平台5 4 图5 2 基于软件模拟器的测试平台5 6 图5 3 基于逻辑综合的a s i c 设计流程5 7 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目： 壶性能翌直垂：垄垫往的婴究生塞超 学位论文作者签名：整趟日期：二d 0 8 年j2 月岁d 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：壶懂瞧星直丞：趣垫佳鲤盈壅复塞理 学位论文作者签名： 作者指导教师签名： 日期：易鲤年幢月；o 日 日期：) 旷矿年，2 月多矿日 国防科学技术大学研究生院硕士学位论文 1 1 课题研究背景和意义 第一章绪论 目前人类社会的发展己经进入了信息时代，各种信息技术构成了信息时代的 基础，而信息技术的基础是微电子技术。集成电路是电子信息产业的命脉，对国 民经济发展和国防建设都具有十分重大的意义。作为信息处理核心的微处理器 ( m p u ) 已渗透到计算机、通信、交通、金融、家电、商务等与人们日常生活密切相 关的各行各业，尤其深刻地影响着武器装备、航空、航天、航海等国防领域。在 这些领域里，数值计算是不可免除的。 浮点运算在高精度数字的计算中被普遍使用，并且随着数字信号处理和图像 处理需求的增长，其应用也越来越广。与定点数相比，浮点数据拥有更大的动态 范围与更高的精密度，因而更具运算上的优越性。随着集成电路生产工艺的进步， 工艺特征尺寸的缩小，单芯片面积的增大，使得单芯片的集成度有了空前的提高， 因此，实现算法更复杂的高性能浮点运算单元成为可能。现在的许多计算机程序， 如科学计算，3 维图像处理，数字信号处理和系统性能测试程序，使用浮点运算的 频率很高，这些应用的性能往往受浮点硬件速度的限制，因此，研究高性能浮点 单元的设计技术十分重要。 i e e e 一7 5 4 浮点数标准l l 】是目前最广泛使用的浮点数标准。它规定了符合该标 准所需的浮点操作数格式，精度表示，舍入方式以及异常处理等。这些浮点数的 运算主要包括浮点加法、浮点乘法、浮点除法及浮点平方根等运算。s t a n f o r d 大学 的s f o b e r r n a n 和m j f l y n n 在其技术报告【2 j 中指出，在典型的四种浮点运算指令 ( 浮点乘法指令、浮点加法指令、浮点除法及平方根指令) 中，浮点加法与浮点乘 法是最常用的两种浮点指令。浮点加法原理上仅为两个浮点数的和或差，是非常 简单的操作，然而在硬件实现上，由于对阶操作，移位操作，规格化操作以及舍 入操作使得浮点加法变得非常慢，因此，一个快速的浮点加法器对浮点部件显得 非常重要。浮点乘法的使用频率仅次于浮点加法操作，浮点乘法运算比较复杂， 计算过程也比较长，其执行速度对处理器的运算速度影响很大，并且其性能往往 成为浮点部件性能瓶颈，因此设计高速的乘法部件对于高性能的浮点单元也是至 关重要的。 随着我国信息化进程的不断深入，对信息安全提出了很高的要求，高端计算 机领域的安全尤其重要，具有自主知识产权的微处理器可为信息安全提供基础保 障，为此我国正在大力发展具有自主知识产权的高性能微处理器。本论文正是基 于国内对高性能微处理器的需求，以高性能6 4 位x 处理器的浮点运算部件的研究 第l 页 国防科学技术大学研究生院硕士学位论文 与设计为背景，对高性能浮点运算中的乘、加运算进行深入研究，具有一定的理 论价值和较强的现实意义 1 2 国内外研究现状 1 2 1 浮点乘法器的研究现状 大多数现代微处理器都实现了单独的浮点乘法器，浮点乘法运算主要包括部 分积编码、部分积压缩、超长加法器、s t i c k y 计算以及舍入几部分。对于浮点乘法 算法的优化主要是围绕这几部分进行。 部分积编码算法的研究始于a d b o o t h 于1 9 5 1 年提出的一阶b o o t h 编码p j ， 随后o l m c s o r l e y 对其进行了改进并于1 9 6 1 年提出了著名的二阶b o o t h 编码【4 j ， 将部分积数量减少了一半，此后b e w i c k 又提出了一种冗余三阶b o o t h 算法，该算 法可在略多于二阶b o o t h 算法的时间内完成，各种高阶的b o o t h 编码算法也一直是 研究的热剧1 0 1 【l l j 【5 7 】；部分积压缩结构主要有迭代运算、阵列结构以及树型结构三 种，其中树型结构由于能够大大减少关键路径长度以及硬件开销而被广泛使用。 在树型结构的构建上，w a l l a c e 首先提出了3 ：2 压缩器来构建压缩树i z 引，随后d a d d a 提出了( m ，n ) 计数器的概念【3 0 】，将3 ：2 压缩器推广到4 ：2 、5 ：3 、7 ：3 等以获得更高的 压缩比，高压缩比的压缩器结构也是一个研究的焦点问题，各种各样的高阶压缩 器结构被提出【5 】【l l 】【1 5 】【2 0 】；超长加法器是浮点乘法运算性能瓶颈，研究人员提出了 各种结构的加法器，如串行结构的行波进位加法器、进位跳跃加法器1 5 引、进位选 择加法器【2 7 】【2 8 】以及并行结构的s k l a n s k y 加法器【5 引、b r e n t k u n g 加法器【6 0 1 、 k o g g e s t o n e 加法器i 1 等。 除了上述部件外，s t i c k y1 , t 算算法f 2 4 】【2 5 1 1 2 6 1 、符合i e e e7 5 4 标准的舍入问题【6 2 】 也是研究的热点。 1 2 2 浮点加法器的研究现状 浮点加法是运算中出现最频繁的操作【2 j ，浮点加法运算原理上虽然简单，然而 在硬件实现上，需要经过相对复杂对阶操作，移位操作，规格化操作以及舍入操 作等，以至浮点加法器往往成为整个微处理器单元的性能瓶颈，因而减少浮点加 法器运算时间的研究备受关注。 w a s e r 等人总结了浮点加法运算的通用步骤1 35 1 ，此后浮点加法器的研究都围绕 对这些步骤的优化进行。f a r m w a r l d 针对浮点加法的基本算法进行了一系列改进， 提出了双通路浮点加法结构【3 1 1 【3 2 】【3 3 j 【3 8 】，与单通路结构相比，双通路结构具有更高 的并行性以及较小的延迟，其代价是需要消耗更大的硬件开销。目前该算法已经 第2 页 国防科学技术大学研究生院硕士学位论文 在部分商刚处理器的到应用【3 6 j 【”j 。浮点加法运算关键步骤的优化也是一个研究焦 点，如在针对前导o 的计算上，人们提出了各种优化算法，j a v i e rd b r u g u e r a 和 t o m a sl a n g 提出了并行修正模块的构造法【4 7 】，凌智强等【4 8 】【4 9 】对改算法进行了改 进，修正了算法中存在可能引起最后的预测存在一位误差的错误；何威等1 3 9 1 1 4 6 1 提 出了一种基于产生式规则的l z a 算法，g z h a n g 等【5 0 】提出了并行错误检测算法， 将前导o 预测和错误检测并行起来，使得能够更早生成错误指示信号，因而减少 了关键路径长度，提高了整体性能。概括起来，加速浮点加法运算主要包括下面 一些技术：l 根据两个操作数阶差大小将运算分成两条并行的数据通路，最后进行 结果选择。2 前导0 计算和有效操作数相加并行计算m 【4 8 】【4 9 】【5 0 1 。3 规格化和舍入 并行计算。4 操作数交换技术省去减法操作结果的补码还原操作。5 舍入合并技 术【4 1 1 。6 利用注入算法将所有的舍入模式归并为单一的0 舍入模式。 1 3 论文结构 本文的结构安排如下： 第一章为绪论，阐述了论文的研究背景和意义，讨论了浮点乘、加部件的国 内外研究现状，介绍了整个论文的组织结构。 第二章首先简单介绍了i e e e7 5 4 标准，接下来对浮点乘、加算法及其关键技 术进行了深入的研究。 第三章阐述了浮点乘法部件的设计，对乘法器中的一些关键部件的设计进行 了详细的介绍。 “ 第四章阐述了浮点加法部件的设计，对加法器中的一些关键部件的设计进行 了详细的介绍。 第五章阐述了浮点乘、加部件的模拟验证及综合，介绍了浮点乘、加部件的 验证方法、层次、过程和结果，综合的策略、方法和结果等。 第六章结束语总结了现有的工作并对下一步的工作进行了展望。 第3 页 国防科学技术大学研究生院硕士学位论文 第二章浮点乘、加算法的研究 2 1i e e e 7 5 4 浮点标准 i e e e 7 5 4 标准规定了浮点运算的操作数格式、精度、舍入方式以及异常处理 等内容，是现代微处理器中使用最广泛的浮点标准，也是实现浮点运算部件的基 础。本小节将对该标准中涉及的一些关键内容进行简要介绍。 2 1 1 浮点操作数的表示格式 i e e e 7 5 4 标准定义了四种基本格式，分别为浮点单精度格式、浮点扩展单精 度格式、浮点双精度格式以及浮点扩展双精度格式。四种格式的参数范围如表2 1 所示： 表2 - 1 浮点格式参数【1 1 格式 参数 单精度扩展单精度双精度扩展双精度 尾数宽度p 2 4 = 3 25 3 = 6 4 指数最大值e m a x + 1 2 7 = + 1 0 2 3+ 1 0 2 3 = + 1 6 3 8 3 指数最小值e m i n1 2 6 = 1 5 浮点格式宽度 3 2 = 4 36 4 = 7 9 2 1 1 1 单精度浮点数据格式及对应的特殊操作数 i32 3 图2 - 1 单精度浮点格式( j j 3 2 位单精度浮点格式如图2 1 所示，其值v a l u e 根据各域的不同可有下列几种 计算方法： l 若e = 2 5 5 并且厂0 ，则不论符号位5 为何值，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 作为操作数时，触发异常，应报无效操作错误。 2 若e = 2 5 5 并且厂= 0 ，则v a l u e 为无穷o o ，v a l u e = ( 一1 ) 3 。 第4 页 国防科学技术大学研究生院硕十学位论文 3 若0 若e = 0 并且f = 0 ，则v a l u e 为0 ( z e r o ) ，且v a l u e = ( - 1 ) 5 0 。 2 1 。1 2 双精度浮点数据格式及对应的特殊操作数 图2 - 2 双精度浮点格式【1 】 6 4 位单精度浮点格式如图2 - 2 所示，其值v a l u e 根据各域的不同可有下列几种 计算方法： 1 若e = 2 0 4 7 并且厂0 ，则不论符号位s 为何值，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 作为操作数时，触发异常，应报无效操作 错误。 2 若e = 2 0 4 7 并且f = 0 ，则v a l u e 为无穷数+ o o ，v a l u e = ( 一1 ) 5 0 0 。 3 若0 若e = 0 并且f = 0 ，则v a l u e 为0 ( z e r o ) ，且v a l u e = ( - 1 ) 5 0 。 2 1 2 浮点操作 i e e e 7 5 4 标准定义了浮点加、减、乘、除以及余数操作五种算术操作。此外， 还包括平方根操作、浮点类型格式转换、浮点到整数格式转换、将浮点数舍入转 换成整数值、浮点二进制转十进制数以及浮点比较等操作。 2 1 3 浮点舍入方式 由于机器的有限字长限制，需要对无限精度的浮点运算结果进行舍入，以适应 浮点表示格式。舍入操作可能会使得运算结果精度降低。i e e e 7 5 4 标准定义了四 种舍入方式，分别为舍入到最近偶数、向正无穷方向舍入、向负无穷方向舍入以 及向o 舍入。 1 舍入到最近偶数：在这种模式下，需将无限精度的运算结果舍入到与其最 接近的那个值，如果存在两个这样的值，则选择最低位有效数字为0 的那 第5 页 国防科学技术大学研究生院硕十学位论文 个( 即为偶数的那个) 。该舍入方式为默认的舍入方式。 2 向正无穷方向舍入：在这种舍入模式下，舍入结果与无限精度运算结果最 接近，且舍入结果大于或等于无限精度的运算结果。 3 向负无穷方向舍入：在这种舍入模式下，舍入结果与无限精度运算结果最 接近，且舍入结果小于或等于无限精度的运算结果。 4 向0 舍入：即截断舍入，在这种舍入模式下，直接将无限精度的运算结果 的多余位截掉得到舍入结果。 2 1 4 浮点异常处理 i e e e 7 5 4 标准定义了五种浮点操作异常： l 无效操作数异常 当浮点运算的源操作数在其运算环境中为非法操作数时，发生无效操作数异 常，在通常情况下，若运算发生无效操作数异常，运算结果被强制置为q n a n 在i e e e 7 5 4 标准中规定的触发无效操作数异常的情况有以下几种： 任何源操作数包含s n a n 的浮点运算。 浮点加、减法运算操作数中包含无穷数的情况，如( 佃) + ( - o o ) 。 乘法操作中的0 x o o 。 除法操作中的0 0 或o o o o 。 x 对y 的求余运算x y ，y 为0 或工为无穷数。 平方根运算中操作数为负数。 在浮点数转化整数或者十进制数操作中，当操作数出现无穷、n a n 或者是 操作结果上溢，以致结果的数据格式不能真实表示原值。 一些不支持无序比较的比较操作数中出现n a n 数。 2 除0 异常 在浮点除法操作中，若除数为0 而被除数为有限的非0 数，则报除0 异常 且运算结果为带准确符号位的无穷数。 3 上溢出异常 对于浮点操作，若运算结果大于当前浮点精度下所能表示的最大浮点数， 则发生上溢出异常，浮点运算结果与当前采用的浮点舍入模式有关。 4 下溢出异常 对于浮点操作，若运算结果小于当前浮点精度下所能表示的最小浮点数， 则发生下溢出异常，浮点运算结果与当前采用的浮点舍入模式有关。 5 非精确异常 若经过舍入处理后的浮点运算结果为非精确，则报非精确异常。 第6 页 国防科学技术大学研究生院硕士学位论文 2 2 浮点乘法算法的研究 浮点乘法的使用频率仅次于浮点加法，浮点乘法运算比较复杂，计算过程也 比较长，其执行速度对处理器的运算速度影响很大，早期的小型计算机和微型计 算机一般用软件模拟浮点乘法运算，现在绝大多数微处理器都设计了专门的浮点 乘法部件，硬件实现的浮点乘法运算部件的性能往往成为浮点部件性能瓶颈，因 此设计高速的乘法部件对于高性能的浮点单元是至关重要的。 2 2 1 浮点乘法器结构 i e e e 7 5 4 标准将浮点操作数定义为由符号位、指数域以及尾数域三个域组成 的格式。因此，浮点乘法运算一般包括符号位处理，指数相加以及尾数相乘三部 分。指数和符号运算相对简单，符号位经过简单的同或运算就能得到结果的符号； 通过加法运算并根据尾数运算结果进行适当的移位调整后就能得到结果的指数； 而尾数运算比较复杂，涉及到尾数相乘、s t i c k y 位推测以及结果的规格化与舍入操 作，因而尾数数据通路的设计决定了整个浮点乘法运算的性能。尾数相乘实质上 是一个部分积产生和累加的过程，针对这部分电路，人们提出了很多的优化算法， 本节接下来将对浮点乘法的一些关键部件算法进行研究与比较。 2 2 2 部分积编码算法 乘法运算方法与操作数的编码方式密切相关，相比较而言，采用原码较为简 单：两个源操作数符号异或即可得到结果的符号位，两数按绝对值相乘即可得到 两数乘积。原码乘法虽然简单，但由于计算机通常采用补码数据表示方法，若使 用原码进行乘法操作，还需要增加补码转原码的逻辑，增加了运算过程的复杂性 和处理时间，因此，现在的微处理器中多直接采用补码进行乘法运算。本节将对 目前常用的几种部分积补码编码方式进行比较。 2 2 2 1 传统的b o o t h 算法 a d b o o t h 于1 9 5 1 年提出了b o o t h 算法【3 】，该算法有效的解决了有符号乘法运算 中复杂的符号修正问题。与原码乘法不同之处在于，补码乘法中乘数和被乘数的 符号位均需要参加运算，在乘法过程中，被乘数a 需要采用两位符号位的变形补 码，即模4 补码。采用传统的b o o t h 算法，位乘法运算共产生个部分积，每 个部分积均根据乘数b 中的相邻两位( e 小e ) 编码产生，其部分积产生规则如表 2 2 所示： 第7 页 国防科学技术大学研究生院硕十学位论文 表2 - 2 一阶b o o t h 编码部分积产生规则表【3 】 b n b n + l 部分积pp i 00o 0l l a i 仆 l 0i - a i * 1l0 采用传统b o o t h 算法的乘法运算规则如下所述： l 被乘数和部分积取两位符号位，乘数采用一位符号位，并参与操作。 2 乘数末尾增设附加位色+ 。，并将其初值置为0 。 3 鼠和色+ 。构成各步运算的乘数判断位，按表2 - 2 所示的方法进行操作。 4 按补码移位规则，部分积右移时末端触发器补入符号位。 5 按表2 2 所示的方法进行到+ 1 步，但+ 1 步的部分积不再移位。 2 2 2 2 改进的b o o t h 算法 0 l m c s o r l e y 在传统b o o t h 编码的基础上于1 9 6 1 年提出了改进的b o o t h 算法 【4 1 ，改进的b o o t h 算法递推公式如式2 1 所示： + 2 】补 = 2 _ “p + l 】补+ ( 吃一。一e 一，- 1 ) 【彳】补) = 2 - 2 “p 补+ ( 吃小i b 一，) 爿】补+ 2 ( 尾一，一最+ 1 ) 彳】补) ( 2 - 1 ) = 2 - 2 p l h + ( 统一件l 一最一，+ 2 尾一，一2 8 一，一1 ) 【彳】补) = 2 - 2 p 】补+ ( 色一川一色一，一2 8 一_ 1 ) 彳 补) 由式2 1 可知，与传统的b o o t h 算法不同，改进的b o o t h 算法的乘数寄存器在 每计算出一个新的部分积后需要右移两位。这样，判断位b + 。、色一，和院牛。就是 每次移动位后乘数寄存器的最后三位或+ 。、e 和或一。e + i 、色和色一通过译码可 得到八种值，代入式2 1 即得到快速b o o t h 算法的部分积产生规则，如表2 3 所示： 表2 - 3 改进的b o o t h 算法 b n 1b nb n + l部分积pp o000 o0l 【a 】补 olo 【a 】补 oll 【2 a 】讣 loo 【一2 a 】朴 lol 【一a 】 ll 0 一a 】仆 ll l0 第8 页 国防科学技术大学研究生院硕十学位论文 对于改进的b o o t h 算法，其乘数也需增加一个附加判断位院+ ，初值为o 。和 传统的1 阶b o o t h 算法相比，改进的b o o t h 算法能将部分积的数量压缩到原来的一 半，并且所有的部分积都可以通过对乘数的简单左移产生，从而达到速度和面积 的最优化，因而在现代微处理器设计中得到广泛的应用【5 】【6 】【7 1 【8 1 。 2 2 2 3 高阶b o o t h 算法 高阶( 阶数大于二) b o o t h 算法每次扫描连续的更多位乘数，从而形成一个有符 号的部分积来减少乘法中的部分积的数目，随着b o o t h 编码的阶数增加，部分积 会以因子1 n 减少【9 j ，表2 4 是三阶b o o t h 算法的部分积产生规则。更高阶的b o o t h 算法( 如5 阶) 可参考文献i 10 】。 表2 - 4 三阶b o o t h 算法的部分积产生规则 b n 2b n 一1b n b n + l部分积p p ib n 2b n 1b n b n + i部分积pp 1 0000 o loo0 一4 a 】朴 0ool a 】朴 lo0l 一3 a 】补 0 ol0 a 】 l ol 0 【一3 a 】补 00ll 【2 a 】补 l0ll 【- 2 a 】补 olo0 【2 a , b llo0 一2 a 】补 0lol 【3 a 】朴 llol a l 补 ollo 【3 a 】朴 lllo 【一a h olll 【4 a 】补 llll 0 2 2 2 4 各种编码算法的比较 表2 5h o ! 对各阶b o o t h 编码的复杂性进行了比较。 表2 - 5 各阶b o o t h 编码复杂性比较( 6 4 位乘法) 【1 0 1 阶数部分积数量p p g 扇入总的p p g 扇入可能用到的部分积 传统b o o t h ( i 阶)6 4l6 4 0 ，a ，- 4 改进b o o t h ( 2 阶)3 3l3 3 一2 a ，一a ，0 ，a ，2 a 3 阶2 224 4 一4 a ，4 彳 4 阶1 746 8 - 7 a ，7 a ) 5 阶1 381 0 4 - 1 5 a ，1 5 4 基于前面的分析，结合参考文献 1 0 ，可以得到以下几个结论。 1 改进的b o o t h 算法继承了传统b o o t h 算法的优点，此外，和传统的1 阶b o o t h 算法相比，它能将部分积的数量压缩到原来的一半，并且所有的部分积都 可以通过对乘数的简单左移产生，从而达到速度和面积的最优化，此外采 用改进的b o o t h 算法，其部分积产生逻辑( p p g ) 具有更低的扇, 入( f a n i n ) 。 2 理论上说，由于高阶b o o t h 算法可以进一步减少部分积数量，因而越高阶 的b o o t h 算法可能得到更快速的乘法器。然而，对于高阶的b o o t h 算法， 第9 页 国防科学技术大学研究生院硕七学位论文 其部分积产生可能无法h j 简单的左移位来产生( 如三阶b o o t h 算法的3 倍 乘数3 m 是难以产生的部分积) ，从而带来额外的复杂性、面积与延时开 销，此外高阶b o o t h 算法部分积产生逻辑的扇入大大增加。 2 2 3 部分积压缩 部分积压缩实际上是一个多操作数的累加过程，在早期的计算机里，由于硬 件技术的限制，采用软件迭代的方法实现，这样做的好处是电路结构非常简单， 易于实现，然而由于是串行迭代，需要多个周期才能得出压缩结果，因此这种方 法不适合在现代高速处理中使用。 随着集成电路技术的飞速发展，并行部分积累加技术逐渐应用到现代微处理 器中，按照结构上划分，并行累加技术主要包括阵列结构的部分积累加和树型结 构的部分积累加【l5 】两种结构。下面将对这两种结构进行详细阐述。 2 2 3 1 阵列结构的部分累加 图2 3 是一个4 x 4 的阵列结构部分积压缩器【l 7 1 ，该种压缩器结构与部分积阵列 形式非常相似，由全加器( f a ) 和半加器( h a ) 组成的三级阵列将部分积压缩成两级 后再由一级向量合并加法器完成最终的结果，图中灰色标出部分为关键路径。其 关键路径延时如式2 2 所示。 = 叫1 ) + a d d ( 2 - 2 ) 其中：为h a 或f a 的延时，k 趔为向量合并加法器的传播延时。 砑 刚丘首开朋冶嚣 图2 34x4 的阵列结构部分积压缩器【1 7 1 2 2 3 2 树型结构的部分累加 部分积压缩的另一种结构是树型结构，通过许多较小的压缩单元对部分积矩 阵进行“覆盖”以达到同时减少关键路径和所需的加法器单元数目。图2 4 是一个 4 x 4 1 拘树型结构部分积压缩器【1 7 1 。 第1 0 页 国防科学技术大学研究生院硕七学位论文 部分积 第一级 一萋三墼 向量合并加法器 图2 44x4 的树型结构部分积压缩器【1 7 】 2 2 3 3 压缩结构的比较 由图2 3 和图2 4 可以看出，阵列结构的部分积压缩器拓扑结构较规整，易于 版图实现，然而其关键路径延时较长并且版图面积较大鸺】，而树型结构的部分积 压缩器相比之下关键路径延时明显降低，并且明显减少了实现所需的硬件，其缺 点是非常不规整，这使得后面高质量的版图设计任务