《基于srt算法的单精度浮点除法器》由会员分享,可在线阅读,更多相关《基于srt算法的单精度浮点除法器(7页珍藏版)》请在金锄头文库上搜索。
1、基于 SRT 算法的单精度浮点除法器 暨南大学基于基于 SRTSRT 算法的单精度浮点除法器算法的单精度浮点除法器作者:郑观东作者:郑观东单位:暨南大学固体电子技术与单位:暨南大学固体电子技术与集成电路设计实验室集成电路设计实验室基于 SRT 算法的单精度浮点除法器 暨南大学摘摘 要要采用 Verilog HDL 语言,在 FPGA 上实现了单精度浮点除法器的设计,通过采用 SRT 算法、SD 表示法、常数比较法以及飞速转换法,进一步提高电路的运算速度。本文使用 NCsim 和 Maxplus2 仿真软件进行前仿真和后仿真,使用 Synplify 进行逻辑综合,采用的器件是 EPF10K40R
2、C208-3,对除法器进行了仿真。关键词:除法器;SRT;数字循环法;仿真基于 SRT 算法的单精度浮点除法器 暨南大学1引言 在语音通信、图象处理等领域中,系统往往涉及大量的数据处理,而且数据计算的精度和实时 性要求很高,需要很高的浮点处理能力来提高系统的执行效率。Soerquist 等人1指出,在四种基 本浮点运算中,浮点除法的执行速度是最慢的,处理器执行浮点加法和浮点乘法一般需要 2 到 3 个 机械周期,而浮点除法则需要 8 到 60 个机械周期。然而,浮点除法占的比例较小, Oberman 和 Flynn 认为2在所有浮点指令中,浮点加法指令占 55%,浮点乘法大约占 37%,浮点除
3、法大约占 3%,和浮点加法和浮点乘法相比,浮点除法的比例很小。但是,这并不表示浮点除法对处理器性 能的影响很小,在因为浮点指令阻塞等待而引起的处理器性能下降的因素中,浮点除法指令大约占 40%,浮点加法大约占 42%,浮点乘法大约占 18。由此可见,浮点除法虽然出现的频率较低,但 对处理器整体性能有较大的影响,设计一种执行效率较高的浮点除法结构对处理器性能的提高起到 很重要的意义。2SRT 算法的优点 在处理单精度浮点数的时候,处理除法器的算法主要有两种:函数迭代法以及数字循环法。由 于函数迭代法所提供的商的最低位不准确,导致四舍五入操作无效,不能满足 IEEE 754 标准对精 度的要求,而
4、且它不产生余数,循环部分的执行复杂性程度很高。Oberman 和 Flynn 的研究2表明 数字循环算法可以取得较好的延时和面积平衡。数字循环算法是以加法和减法运算为基础的算法, 需要多个循环周期,但是,该算法的实现比较简单,所需的硬件面积比较小,功耗也比较小,非常 有利于芯片的设计。 该算法的实现主要有三种方法:恢复余数算法,不恢复余数算法以及 SRT3 (Sweeney,Robertson and Tocher)算法。传统的除法器都采用恢复余数算法或者不恢复余数算法, 但是这两种算法的运算速度较低,每次循环仅能够产生一位的商数字,需要较多的循环次数才能达 到需要的指标。在每次循环的时候,恢
5、复余数算法都需要将被除数或部分余数与除数进行比较,如 果除数较大的话,还需要将部分余数恢复到上一次循环的数值;不恢复余数算法虽然不需要将部分 余数恢复到原来的数值,但是商的数字集会出现负值,最后需要额外的加法器,将商的正数部分与 负数部分相减。SRT 算法是不恢复余数算法的扩展,具备了不恢复算法的优点,而且每次循环可产 生 log2r 位结果(r 为基数) ,大大减少了循环的次数。基于 SRT 算法的优点,以及考虑到本除法器 应用在自动语音编码,本文所设计的除法器采用 SRT 算法进行除法运算。 SRT 算法由下面的表达式来确定商和余数:dPr dqPrPjjj 011d 表示除数;Pj+1表
6、示第 j 次循环后的部分余数;r 表示 SRT 算法的基;qj+1表示第 j 次循环得到的商,qj+1的值由除数和部分余数组成的商数字选择函数决定。最后的商为,最后 nii jrqq1的余数如下:。0, 0,)( nn nnn nprp prdpremainder3单精度浮点除法器的设计 本文是针对 IEEE 754 单精度浮点数据格式进行的浮点除法器设计。IEEE 754 单精度浮点格式:,s 表示符号位,E 表示偏移码,E-127 表示阶码,M 表示尾数。 12721EsMA除法器运算操作分 3 步进行。 (1) 确定结果的符号,对被除数和除数的符号位做异或操作。基于 SRT 算法的单精度
7、浮点除法器 暨南大学(2) 计算阶码,两数相除,结果的阶码是被除数的阶码与除数的阶码的相减。 (3) 尾数相除,采用 SRT 算法进行尾数相除,被除数和除数的实际尾数都是 24 位数,即尾数 实际为 1.M,最高位 1 是隐藏位。 (4) 结果格式化,将结果整合为单精度浮点格式的标准。 在进行尾数部分处理的时候,虽然被除数和除数的实际尾数均为 24 位,但考虑到最后格式化 以及商的数值的要求,实际上需要进行处理的位数为 26 位,因此,根据 SRT 算法的公式,要使得 循环次数减少,并且面积适中,必须选择适合的基数。而且每次循环的时候都需要与除数进比较, 26 位数进行比较,延时较大,必须选择
8、位数较少的数值代替 26 位的除数。为了适应自适应语音编 码对速度的需求,本文针对上述两个需要进行时序改善的地方,设计了基 4 的 SRT 算法的除法器结 构,如图 1 所示。商选择常数选择MUX寄存器加法器飞速转换商调 整除数被除数商余数图 1 基于 SRT 算法的除法器结构3.1 基数的选择 考虑到部分余数以及基数实现的简单性,本除法器选择 SRT 算法的基数为 2 的幂次方。基数 大小和所需的循环次数成反比,基数越大,实现除法所需要的循环次数越少,但是基数增加,会导 致商数字选择函数的复杂性的提高,而且商数字选择函数往往处在关键路径上,其复杂度的增加无 疑增加了每次循环的时间延迟。另外,
9、大基数使得产生所有可能商的乘积的硬件电路变得复杂,增 大每个循环周期。因此,在实际应用中,SRT 算法的基数一般限制在 2 或 4。相比较而言,基 4 的 性能较优,每次循环产生的位数为基 2 的两倍,Oberman 的研究4表明基 4 除法的速度几乎是基 2 除法速度的 2 倍,而且更有利于进一步优化,降低整体的时间延迟。因此,在平衡面积和速度方面, 本除法器的 SRT 算法选取基 4,这样可以以较小的面积消耗换取较快的速度。3.2 商数字集由于 SRT 算法的基数选择了 4,因此,商的数字集不再是0,1,而是。在传统的非冗3 , 0 L余表示法中,商的每一位仅由一个正确的有效值表示,因此在
10、确定每一位商数字的时候,需要将部 分余数和除数进行完整的比较,即是 24 位数的比较,效率较低。为了进一步提高除法器的运算速基于 SRT 算法的单精度浮点除法器 暨南大学度,本除法器采用 Avizienis5介绍的冗余商数字集 SD,它是一种对称的冗余表示法,商数字集表示为,冗余因子,。在确定每位, 1, 1 , 0 , 1, 1,aaaaqjLL12rar 1ra 1 ,21(商数字的时候,仅需要将部分余数和除数进行大约的比较,不要求当前循环确定的商准确,可由下 次循环来修正,商的选择余地较大,而且产生的所有可能商的乘积的数目较少,可以简化商数字选 择函数。对于基 4 来说,商数字集只有两种
11、选择,最小冗余和最大冗余,2 , 1 , 0 , 1, 23 , 2 , 1 , 0 , 1, 2, 3 Oberman 的研究4表明采用最大冗余商数字集的商数字选择函数速度比最小冗余的快 20%,而且面积 小 50%,因此本除法器采用的商数字集的最大冗余表示法。3.3 商数字选择函数 商数字选择函数的功能是从商数字集中有效地选择出正确的商数字,它是除法器的核心。由于 商数字集选择了最大冗余,因此商数字选择公式如下:, 如果 ,d 是除数3 , 2 , 1 , 0 , 1, 2, 31kqj) 1() 1(kdjrpkd在基 4 最大冗余的 Robertson 图6可见(如图 2 所示) ,部
12、分余数的有效区域总共分 8 个小区域, 相邻区域有部分区域重叠,每个商数字都有两个区域与之对应,就是说允许商数字有两个选择,不 正确的可通过下次循环进行纠正。但是,有效地判断部分余数所在的区域,选择比较接近的商数字, 可以提高商数字选择函数的执行效率和实现的简单性,因此必须选取合适的区域分界点。传统的做 法是通过 PD 曲线法来求得各区域的分界点,但是需要将部分余数和除数进行比较,24 位数的比较 产生的时延比较大,而且商数字选择函数的实现比较复杂。为了简化商数字选择函数,提高除法器 的运算速度,本除法器采用常数选择法,用常数来代替除数进行比较,将所需要进行比较的位数缩小,降低这部分引起的时间
13、延时,而且实现起来比较简单。其主体思想是把分解成若干个小区 1 ,21域:,然后判断除数的合适区域,再确定比较常数,每一位商数12)(2log,21,21,211 adddddiiii字所对应的区域,最后确定根据部分余数确定每一位商数字,常数选择法如图 37所示:, 1,11imrpimkqkjkj)(),(min()()(),(max(1111ikiKkikikdUdUimdLdLdkLdkUkk,图 2 基 4 最大冗余的 Robertson 图 图 3 di,di+1)的常数选择根据最大冗余基 4 的商数字集,区域可以分成两个小区域:,相应的比较常数集 1 ,21 1 ,41,41,21
14、分别为-3/2,-1,-1/2,1/2,1,3/2和-2,-1,-1/2,1/2,1,2,这些比较常数就是每位商数字所对应区域的分界 点。由所得到的两个比较常数集可以知道,在确定商数字的时候,仅需要比较部分余数的高三位,基于 SRT 算法的单精度浮点除法器 暨南大学而不需要比较 24 位,产生的延时较小,而且硬件实现比较简单。 3.4 飞速转换 SD 表示的商数字集可以简化商数字选择函数的实现,但是商数字集会出现负值,最后需要一 个加法器,将商的正数部分与负数部分相减,24 位数的相减,位传递产生的时延比较大。而且由 于商数字的选取的空间比较大,会出现最后余数为负的现象,需要对其进行修正,同时,商也需要 进行操作,效率较低。效率较好的转换方法是飞速转换法8,它采用移位的方法来完成 SD 表示的 商数字集的转换,而不采用相减的方法,这样就不存在借位的问题,效率较高,可以降低时间延时。其转换公式如下: 。00, |( ,11111iiiiiiqqqq qrqmiq001, |)1(,11111 iiiiiiqqqq qrqmiqm当完成最后一次转换后,需要根据最后余数的符号来选择正确的商,如果最后余数为负的话, 则商选择 qmi+1,否则商选择 qi+1,则最后