Design of Double-Precision Floating-Point Division and Square Root Based on SRT Algorithm

In the process of scientific computing, digital signals processing, communication and image processing, division and square root are the widely used basic operation. This article designs a unit of floating-point division and square root based on SRT4 algorithm. It reduces the iterative division and square root calculation delay by using parallel processing of quotient and residue addition and the on-the-fly conversion technology. At the same time, it reduces hardware resources and saves area by adopting reuse the lookup table and the adder. Experiments show that the cell area is 9812.3087um, the power is 10.7854mW, the cycles per division instruction is 31, the cycles per square root instruction is 28, comprehensive frequency up to 2.5GHz with 40nm technology library and the timing constraint 400ps. Key words—SRT4, floating-point division and square root, on-the-fly conversion 基于 SRT算法的双精度浮点除法和平方根运算的设计 陈际阳 彭元喜 雷元武 邓子椰 国防科技大学计算机学院,长沙,湖南,中国 摘 要 在科学计算、数字信号处理、通讯和图像处理等应用中,除法和平方根运算是常用的基本操作。本文基于SRT4算法,设 计一个同时支持IEEE-754标准的双精度浮点除法和平方根的部件。首先提出商选择和余数加法的并行处理方法,通过商飞速转换技术, 来降低除法/平方根的计算延时,同时复用查找表和加法器,减少硬件资源开销,节省面积。综合表明,在40nm工艺、时序约束400ps 的条件下,本设计综合频率可达2.5GHZ,cell面积为9812.3087 um,功耗为10.7854mW,除法运算计算延时为31拍,平方根运算计算 延时为28拍。 关键词 SRT4,浮点除法/平方根,商飞速转换 1.引言 浮点除法和平方根运算是科学计算、数字信号处理、 通讯和图像处理等应用中的基本操作。高性能浮点除法/平 方根部件对处理器性能的提高越来越重要。SRT 作为一种 主要的浮点除法/平方根算法,已经广泛使用在现代微处理 器中, 比如 Intel Pentium CPUs[1]、ARM 处理器[2]和 IBM FPUs[3]采用 SRT4 算法,Intel Core2 处理器[1]采用 SRT16 算法。同时,各种应用的处理器对计算速度、芯片面积以 及功耗大小的要求也对 SRT 算法的实现提出了挑战。本文 设计并实现高性能低开销的浮点除法/平方根部件以解决 除法/平方根计算周期长、硬件开销大的问题。 目前对 SRT4 算法的研究已取得许多成果。文献[4]在 航天科学基金(项目号:2013ZC88003) 国防科技大学科研计划项目(项目号:JC120201) 协处理器 LSC87 中提出串行除法和平方根计算,最大限度 利用通用数据路径完成 SRT 算法实现,但工作频率低,不 适合高速处理器的实现;文献[5]分别用基 4 和基 16 算法实 现了 SRT除法/平方根,基 4算法通过比较器预测下一商值, 面积消耗较大,一种基 16 的算法通过单纯扩大查找表实 现,但这样硬件复杂度会急剧增加,另一种基 16 方法由两 个 SRT4 算法在一个时钟周期内迭代而成,但这样的方法 容易引起时序紧张;文献[6]采用牛顿迭代来计算平方根, 采用 Goldschmidt 来计算除法,虽然将两种运算集成在一个 部件中,却无法实现硬件复用,面积较大。 本文基于 SRT4 算法,设计了一种高性能低开销的双 精度浮点除法 /平方根运算模块,在一个部件中支持 IEEE-754 标准的除法和平方根运算。在深入研究 SRT4 算 法的基础上,提出商查找选择和余数加法的并行处理方法, International Conference on Computer, Communications and Information Technology (CCIT 2014) © 2014. The authors Published by Atlantis Press 355 降低关键路径延时,并通过比较商的冗余表示和商的飞速 转换,选用周期较短的商飞速转换来降低迭代的计算延时, 提高频率。另外本文将除法和平方根运算集成在同一个部 件中,可复用查找表和加法器,减少硬件资源开销,节省 面积。 本文将从以下结构对文章进行阐述:第 2 节, SRT 算 法及分析;第 3 节,介绍除法和平方根算法的总体结构; 第 4 节,比较商冗余表示和商飞速转换的结果,比较单独 除法、单独平方根和除法/平方根算法的结果,比较其他处 理器与本设计的除法/平方根部件的频率、延时;第 5 节, 得出结论。 2.SRT算法及分析 SRT[7]算法是一种数字循环算法,当它以 r=2k为基时, 每次迭代可产生非冗余二进制结果的 k 位,同时生成相应 的部分余数。SRT 算法的关键是基数的大小,它决定了每 次循环可以得到的商的位数,每次迭代得到的位数越多则 需要迭代的次数就越少,运算所需的周期就越少,从而提 高算法性能。但是增大基数会增加设计的硬件复杂度,同 时也会增加部件的延迟和面积。 i r n i i q q     1 (1) 迭代主要由移位加操作实现,计算结果采用冗余数表 示,结果数值位 1 }, , 1 , , 1 , 0 , 1 , 1 , {            r a a a a a qi 。采用冗余 数的优点是可用截短的输入值来估计结果值中对应数位, 从而简化设计,缩短操作时间;而且当本次迭代的结果位 qi有 1 位误差时,可通过冗余在下一次迭代中修正。本文 SRT 算法基值为 4,所以选择 a=2(如选择 a=3,对除数 d 生成 3d不易实现)[4]。根据 IEEE754标准[8],单精度浮 点数的尾数为 23 位,双精度浮点数的尾数为 52 位。假如 采用基数为 4 的 SRT 算法,实现单精度浮点数的除法至少 需要 23/log24=12 个指令周期,而实现双精度浮点数的除 法至少需要 52/log24=26个周期。 2.1 SRT除法算法及分析 2.1.1 商数字集合和选择区间 为得到高速算法,我们使用一个对称的集合表示商数 字的取值范围,即: } , 1 , , 1 , 0 , 1 , 1 , { 1 a a a a k q j            数字集合的冗余由冗余因子 ρ 的值决定,定义冗余因 子 ρ: 2 1 , 1      其中 r a (2) 在除法运算中,x、d 为被除数和除数的尾数,并定义 部分余数 p[j]=rj(x-dQ[j]),其中 j 为迭代序数,Q[j]为第 j 步迭代出的商值,p[j]为第 j 次迭代的部分余数,则迭代公 式为: 1 * ] [ 4 ] 1 [      j q d j p j p (3) 余数边界为: d j p  ] [ (4) 设 Uk、Lk为当 qj+1=k且保证下次循环的部分余数在选 择范围时,部分余数相应的最大值和最小值,qj+1的选择区 间为: d k L d k U k k ) ( , ) (        (5) 2.1.2 商选择函数 商选择函数部件位于除法算法设计的关键路径上,该 部分实现会影响到整个设计的时间延迟。 在除法计算中,首先将除数 d 划分成长度为   2 的小区 间 ) , [ 1 i i d d  ,且 2 / 1 1  d ,      2 1 i i d d 。这样,区间就 用除数的前 位小数表示。在小区间 ) , [ 1 i i d d  里,如果 ) ( ) ( 1 i m rP i m k j k    ,则 k q 1 j   。设选择常数 mk的最小 长度为 2,则 c k k i A i m   2 ) ( ) ( ,其中 ) (i Ak 为整数,mk 定 义如下: