Felix

技术源于积累,成功始于执着! 个人邮箱:justlxy@mail.dhu.edu.cn QQ:1576109464

FPGA定点小数计算(二)——除法运算

0
阅读(1509) 评论(0)

0 引言

在四则运算中,除法最为复杂,在时间上和空间上的开销都比较大。因此很多算法都极力避免进行除法运算,或者采用其他的方案来代替除法运算。但是,除法运算作为基本的四则运算之一,在很多情况下依旧是不可避免的。近年来,陆续出现了很多种除法实现算法,如恢复余数算法(Restoring)、不恢复余数算法(Non-Restoring)、SRT算法、倒数算法和牛顿迭代法等。但是大部分算法都是基于整数除法或者浮点小数除法的,并不太适合进行定点小数计算。下面来简单地介绍一下几种常见除法算法、整数除法与定点小数除法的差异和一种简单的定点小数除法实现。

1 常见的除法算法

恢复余数算法

         恢复余数算法是一种基于移位和减法的算法,比较适合FPGA或ASIC实现。恢复余数算法不能直接进行有符号数的补码运算,而只能采用原码进行运算。基于恢复余数算法的无符号除法器具有如下特征:

1)       各参数的字长:被除数为2nbit,除数,商和余数均为nbit;

2)       被除数的高nbit必须小于除数;

3)       算法主要迭代n次。

该算法的基本运算单元如下图所示:

blob.png

恢复余数算法是一种整数的除法,在计算商的同时还能获得余数,是一种无误差的除法实现方式。

不恢复余数算法

         恢复余数算法中的“恢复”指的是,如果之前的计算中余数出现了负值,要将其恢复到前一次的结果,而不恢复余数算法则不进行此操作。不恢复预算算法除了需要移位和减法运算,还需要加法运算,因此其又被称为加减交替算法。

         该算法的基本运算单元如下图所示:

blob.png

不恢复余数算法也不能直接进行有符号数的补码运算,而只能采用原码进行运算。商的符号位可以通过除数和被除数的符号位的异或运算获得。

SRT算法

         SRT除法器起源于20世纪50年代,其名称是由3个算法提出者名字的首字母组成的。其一般有基2和基4两种,更高的基可以由低的组合来实现。

         SRT算法只用到加法、移位运算,加上低精度的比较或查找表就可以实现。低精度的比较有很大优点,这意味只要少量位数的运算来产生部分余数的高位,参与商选择;完整的部分余数的产生可以与之并行操作。由于SRT算法可以实现高精度的运算,因此被广泛应用于浮点除法运算中,AMD和Intel的CPU设计中也采用了SRT算法来设计浮点除法器。

倒数算法

         倒数算法是一种局限性比较大的算法,常用于处理除数位宽比较小的除法运算,且一般用于整数除法中。该算法的基本思想是,把除数的倒数的所有可能值都放入查找表中,然后将被除数与相应的除数的倒数相乘。

         由于该算法不需要迭代操作,相对于其他的算法,其迟滞(Latency)很小。借助硬件乘法器,基于倒数算法的除法器同样可以运行在很高的频率上。

牛顿迭代法

         牛顿迭代法又被称为Newton-Raphson算法,其基本思想是将非线性方程线性化,以线性方程的解逼近非线性方程的解。采用牛顿迭代法进行除法运算,实际上是先使用牛顿迭代法求得除数的倒数值,然后在和被除数相乘。

         牛顿迭代法有两个重要影响因素:初始值(又称为猜测值)和迭代次数。一个合适的初始值可以减少迭代次数,甚至只进行一到两次迭代操作,却可以实现相同的运算精度。然而这样的初始值却是很难寻找的,所以为了保证运算的精度,一般需要4~6次的迭代操作,这样的开销还是很大的。

注:后续的文章中会介绍一种基于牛顿迭代法的平方根倒数运算,John Carmack提出过一个神奇的猜测值(Magic Number)。采用该猜测值,只需要进行一到两次迭代操作,便可以达到较高的计算精度。

2 整数除法与小数除法的差异

         和乘法不同的是,定点小数的除法并不能直接使用整数除法的IP,主要原因有以下两个方面:

1)       整数除法的输出为商和余数,小数除法的输出为小数表示的商;

2)       整数除法通常是一种无误差的运算,小数除法中结果存在一定的误差;

Lattice提供了一种基于不恢复余数算法的整除除法器IP,并且支持可配置Latency的功能。该除法器的IO框图如下:

blob.png

         虽然定点小数仍然采用的整数的表示方式,但是并不能直接使用整除除法器的IP。如果采用该IP计算定点小数除法,需要最输出的商(Quotient)和余数(Remainder)做进一步处理,已得到小数形式的商。而这些处理会增加额外的时间开销和空间开销。

上面介绍的几种除法算法中,恢复余数算法和不恢复余数算法主要应用于整数除法,而SRT算法和牛顿迭代法主要用于小数除法。倒数法和牛顿迭代法还需要进行乘法运算,在采用FPGA实现时,最好使用硬件乘法器来提高性能。

3 一种简单的定点小数除法实现

定点小数可以采用SRT算法或者牛顿迭代算法,但是这两种算法逻辑都比较复杂,采用FPGA实现时,需要很多的资源。下面介绍一种简单的定点小数除法算法,算法只进行基本的移位和减法操作。该算法的思想基本与恢复余数算法的思想一致,只支持有符号数的原码操作:

1)       首先将nbit的除数扩展为2nbit,被除数保持不变仍然为nbit;

2)       如果被除数大于等于除数,则将被除数减去除数的值重新赋给被除数,并将对应的商的位置置1;

3)       将除数向右移一位;

4)       重复2)和3),直至达到迭代次数w+wf-2次。

其中,w表示整个定点小数的位宽(除符号位外),wf表示的是小数部分的位宽。

虽然该算法耗费的资源相对较少,但是缺点也很显著——需要w+wf-2次迭代,即在时间是开销还是比较大的。如果设计中对精度的要求并不是非常高,可以适当地调整定点小数的位宽,在精度和时间开销上找到一个平衡点。

注:该算法的源码可以在开源网站OpenCore上下载到。