基于Goldschmidt算法的高性能双精度浮点除法的开发

　0 引言
　　在科学计算、通信和图像处理等应用中，浮点除法运算是常用的基本操作之一。大部分通用处理器中都实现了浮点除法，如Intel Core i7、IBM Power6和AMDK7[1]等。相对于浮点加、减、乘运算，处理器运算除法更为复杂，所耗时间更长，因此设计并实现高性能的浮点除法器是十分必要的。
　　目前，除法的硬件实现算法中提出了一种改进的Goldschmidt算法，使商值的收敛速度以立方的速度增长，但其实现结构非常复杂。就运算速率而言，基于Goldschmidt算法实现的除法器较基于Newton Raphson算法实现的除法器更具优势。因为Newton Raphson算法每次迭代需要顺序的运算两次乘法，而在Goldschmidt算法中每次迭代需要运算的两次乘法可以并行，这样就缩短了单次迭代时间。实现基于Goldschmidt算法的除法器，需要解决的主要问题包括如何控制迭代过程中产生的误差，如何设计面积尽可能小的迭代初值倒数查找表以及如何调度整个迭代过程使其充分利用硬件资源。
　　1 Goldschmidt算法及误差分析
　　Goldschmidt算法[2-3]是计算除法的一种函数迭代算法，这种算法可以使商的精度随迭代次数呈指数增长，每次迭代需要计算两个并行的乘法，需要较大的硬件开销。在除法器设计中，这种算法更适合作高速率、高精度的除法运算。如果用Goldschmidt算法计算A/B，那么运算过程如图1所示。
　　商Ni的精度随迭代次数呈指数增长。迭代次数k的取值由1/B的初始精度pi和运算结果所要达到的目标精度pt共同决定k=lb （pt/pi）。
　　在Goldschmidt算法迭代计算过程中，需要对中间计算结果进行舍入处理，这种舍入处理会影响运算结果的精度。为了控制误差在目标精度可以接受的范围之内，需要根据目标精度来确定迭代初值的精度、迭代次数以及中间结果舍入位数。
　　计算双精度浮点除法时，根据IEEE（Institute for Electrical and Electronic Engineers）754标准[5]浮点运算结果精度的误差要控制在±0.5ulp（unit of least precision）以下，即相对误差P（N）<2-54。运算过程中Ni-1Fi-1的结果向零舍入赋给Ni，Di-1Fi-1的结果向零舍入赋给Di，2-Di的结果向零舍入赋给Fi。舍入时产生的相对误差分别为m′、n′、 f′。考虑舍入误差之后的迭代计算如下。
　　通过对结果误差控制来确定迭代过程中的舍入位数。对于双精度浮点数，结果尾数的目标精度要达到53位，综合性能和面积的考虑，本文设计采用具有14位精度的迭代初值，迭代次数k取2。根据文献[6]中的结论，为了确保计算结果达到目标精度，控制迭代过程中的误差，乘法器的位宽需大于58位，迭代运算中用到的加法器位宽需大于57位。
　　2 浮点除法器结构
　　2.1 整体结构
　　实现基于Goldschmidt算法的高性能双精度除法器，将其流水化可以提高除法器运算吞吐率。浮点除法器整体结构如图2所示，其中迭代运算单元是一个整体，查倒数查找表确定迭代初值要在迭代计算前完成，在运算首末要进行数据预处理、规格化及异常判断。流水站划分的时候需要考虑给输入输出延时预留时间，所以第一  本文由WwW. 提供，第一 论 文 网专业写作教育教学论文和毕业论文以及发表论文服务，欢迎光临站和最后一站的逻辑尽量少些。根据以上分析，本文对双精度浮点除法器流水站作如下划分：
　　1）E1站。数据输入及预处理。在E1站接收以IEEE754标准表示的被除数与除数数据，并解析这两个输入操作数以分离出尾数、指数和符号位。
　　2）E2站。求出除数尾数的倒数近似值，用倒数查找表求解，本文设计使用的倒数查找表为双查找表[7]，求解相同精度的倒数近似值，双查找表较直接查找表[8]面积更小，并且双查找表中的两个表可以同时查询，速度更快。
　　3）E3站。实现Goldschmidt算法迭代单元。Goldschmidt算法的迭代过程中，每次迭代要计算两次乘法和一次减法。乘法计算需要两个并行的乘法器，减法运算需要使用补码加法器，用状态机控制迭代过程。
　　4）E4站。规格化。在E3站后规格化模块将尾数相除结果与指数相减结果按IEEE754浮点标准执行规格化操作。对指数相减结果规格化时，通过检测尾数相除结果的最高位是否为1，来确定指数相减结果是否借位。另外这一站还包括例外数据判断操作。
　　2.2 关键硬件实现
　　2.2.1 倒数查找表
　　为了得到Goldschmidt算法运算的迭代初值，需要构造14位精度的倒数查找表。采用双倒数查找表算法[7]，需要分别构造P表和N表，联合查找这两个表确定迭代初值。
　　倒数查找表的构造方法如下：
　　构造输入3y+g+1位输出3y+g-1位的查找表。其中y取整数，g取值为0，1，-1。3y+g+1位输入操作数1.b3y+gb3y+g-1…b3b2b1b0此处的操作数“1.”表示什么含义，书写是否正确？请明确。回复：这里的1是输入操作数的整数部分，因为浮点数的尾数都是1点多的（二进制表示）。的小数部分被分为三部分：Xh=b3y+gb3y+g-1…b2y+g是y+1位高位索引部分，Xm=b2y+g-1b2y+g-2…by是y+g位中间位索引部分，Xl=by-1by-2…b0是y位低位索引部分。三个部分Xh，Xm，Xl分别以y+1位，y+g位和y位的数表示。将输入操作数的小数部分编码为[Xh|Xm|Xl]这种形式后，再根据下面给出的算法分别构造出P表和N表。[Xh|Xm]作为P表的2y+g+1位的输入索引，输出3y+g+1位。[Xh|Xm]作为N表的2y+1位的输入索引，输出y+1位。
　　算法1   本文由WwW. 提供，第一 论 文 网专业写作教育教学论文和毕业论文以及发表论文服务，欢迎光临中点倒数算法。
　　输入：整数i≥1， j&g e;1。
　　返回：i位输入j位输出的有限精度中点倒数值。
　　运算：recipmid（Xi）=RN（2i+j+1/此处的表达式正确吗？是否少了一个“/”？请明确。（n+1/2））。
　　2.2.3 补码加法器
　　对没有进行舍入的中间运算结果，按位取反，得到1的补码。将得到的补码加1就得到Goldschmidt迭代算法中的Fi←2-Di的运算结果。根据最后一次迭代运算结果的范围在[0.5，1）还是[1，2）确定指数无偏量是-1还是0。　2.2.4 乘法器
　　乘法器[9]设计采用Radix4的Booth编码算法形成部分积，部分积通过42压缩器进行压缩，整体设计为三站流水结构。为了准确地用Goldschmidt算法计算出结果，需要把计算过程中的误差来源考虑到最终结果中。迭代过程中乘法计算结果舍入会产生的误差，为了达到目标精度，乘法器位宽设置为64×64位。
　　2.2.5 状态机控制器
　　状态机控制器设计包括两种状态：空闲状态（Idle）和计算状态（Div_cal）。当状态机处于Idle状态时，如果接收到除法有效信号，则状态从Idle变化到Div_cal。在Div_cal状态期间，用时钟计数器（Cnt_div_cal）记录迭代计算时钟点，根据迭代时钟点控制迭代计算正常执行。如乘法器运算一次需要3个时钟周期，当Cnt_div_cal为4的时候进行第2次迭代运算。当Cnt_div_cal所记录的时间刚好可以完成本次除法所需的全部迭代计算时，状态就从Div_cal变化到Idle。通过这种控制方式可以控制Goldschmidt算法迭代过程顺利执行。在迭代过程中，乘法器每运算一条乘法需要3个周期，为了达到要满足的目标精度，需要迭代运算3次，这样迭代计算共延迟9个周期，而乘法器在这期间并没有被充分利用，图4展示了这期间乘法器的流水线填充情况。
　　如果在迭代过程中能够充分利用乘法器，除法器的运算吞吐量则会大幅度提高。为此本文对上述的状态机作了相应改进，使其允许连续三次请求除法运算。当状态机处于Idle状态时，如果检测到除法工作信号有效，就开始获取迭代初值（Init_v）并将Init_v送入乘法器。除法工作信号被锁存两拍之后，状态从Idle变化到Div_cal，处于此状态期间，每次迭代送入乘法器的数值Reg_v为上一次迭代计算结果舍入后的数值。迭代次数计数器（Cnt_state）锁存两拍之后加1。Cnt_state达到目标迭代次数并锁存两拍之后，就完成了一条除法的迭代运算，状态从Div_cal变化到Idle。表1显示了迭代过程中状态与迭代运算数值的随时钟周期的变化关系。在这种控制下3条连续的除法就可以顺序的流水执行，间隔6个时钟周期可以继续送入3次连续的除法请求。这样流水执行平均运算每条除法仅需要3个时钟周期。
　　3 实验结果  本文由WwW. 提供，第一 论 文 网专业写作教育教学论文和毕业论文以及发表论文服务，欢迎光临与性能分析
　　使用Verilog硬件编程语言实现了上文所描述的双精度浮点除法器设计，并实现了迭代初值8位的内部乘法器非流水执行结构和迭代初值8位内部乘法器流水执行结构的除法器设计，比较这几种不同配置的除法器性能、功耗、面积。
　　采用40nm标准单元库，在“Typical”典型常温常压（1V，25°C）条件下对除法部件进行综合。时序约束时钟周期450ps的条件下，综合频率可以达到2.2GHz，在相同实验环境下对4种不同配置的双精度浮点除法器综合的结果如表2所示。实验结果表明，流水结构较非流水结构在作大量数据运算时，运算速度更高。14位迭代初值流水结构相比8位迭代初值流水结构运算速度提高了32.73%，而面积仅增大5.05%。综合性能和面积的考虑，确定14位精度的迭代初值以及全流水的结构设计为相对最优设计。
　　在NC仿真环境下对设计进行模拟验证以检验除法器功能正确性和异常处理能力。选取特定功能点操作数及随机操作数，将NC运行的结果与黄金模型的运算结果对比。通过这种方式分别进行了符号位验证、指数运算验证、特殊操作数验证及尾数除法验证。验证结果表明本文设计可以准确并高速计算双精度浮点除法。图5为一组测试激励在NC上仿真出来的部分波形，图5中显示了浮点除法运算过程中关键信号的变化情况，其中信号FDIV_Src1为被除数，FDIV_Src2为除数，FDIV_Dst为除法运算结果，Fnew、Dnew、Nnew为参与迭代运算的数据。
　　编写C语言精度测试程序，程序实现的操作为取两个浮点操作数相除，将运算结果作为下一次除法运算的被除数，除数不变，循环这一过程1000次。编写与C语言精度测试程序实现相同运算操作的Verilog测试激励。将C程序运行结果与NC仿真的结果进行对比，两种模式下除法的运算结果完全一致。实验表明本文设计能有效控制误差，确保运算结果达到目标精度。
　　相比常见的用于除法器设计的SRT算法，基于Goldschmidt算法实现除法器的优势在于它可以用更短的时钟周期计算出除法结果。目前基于SRT算法实现的除法器，计算1条双精度除法一般需要20个时钟周期左右，不能通过流水执行大幅度提高运算吞吐率。而本文设计的除法器运算1条除法需要12个时钟周期，流水执行的情况下平均每条除法运算仅需要3个时钟周期。如表3[10-13]所示（其中：吞吐率表示批量执行时每周期执行指令数），本文设计与其他处理器中基于SRT算法实现的双精度浮点除法器相比，运算吞吐率提高了3～7倍；与其他处理器中基于Goldschmidt算法实现的双精度浮点除法器相比，运算吞吐率提高了2～3倍。
  本文由WwW. 提供，第一 论 文 网专业写作教育教学论文和毕业论文以及发表论文服务，欢迎光临　　4 结语
　　本文设计并实现了基于Goldschmidt算法的高性能双精度浮点除法器，提出采用双查找表法确定迭代初值，有效减小了查找表面积开销，降低了关键路径延迟；通过流水执行填充乘法器的空闲周期的方法，提高了除法器运算吞吐率。实验结果证明了本文设计能够准确计算双精度浮点除法，并且运算速度和吞吐率相比其他处理器中的除法器更具优越性。
　　参考文献：
　　[1]OBERMAN S F. Floatingpoint division and square root algorithms and implementation in the AMDK7 microprocessor [C]// Proceedings of the 14th IEEE International Symposium on Computer Arithmetic. Piscataway： IEEE， 1999： 106-115.