新闻中心

EEPW首页 > 嵌入式系统 > 设计应用 > 利用重叠扫描方法改进单片机乘法运算

利用重叠扫描方法改进单片机乘法运算

作者:时间:2012-02-08来源:网络收藏

引 言

本文引用地址:http://www.eepw.com.cn/article/172157.htm

1946年,第一台电子计算机的诞生开创了计算机发展的新纪元。随着计算机科学技术的迅速发展,计算机的应用领域越来越广泛,并逐渐形成科学发展中的一个新的分支。在计算机的主要工作中,处理大量的数据是其一项基本功能;因而数据是必不可少的。于是人们设法在硬件设计与数据结构方面努力进行工作[1],使计算机的速度不断提高。

十几年前,单片微型机脱颖而出,逐渐应用于微型计算机的各个领域,它不仅适用于一般的自动控  制,而且还可以承担高精度的数据处理工作。诚然,在许多系统中近来采用DSP来提高微机的数据处理能力,以便完成复杂的图像处理、音频处理、网络通讯等功能,而且是一个趋势;但在这些系统中仍不可忽视程序的执行速度,因为好的算法可以大大提高程序的执行效率[2]。同时,考虑到目前8BITMCU的主导地位及某些系统不适合配置DSP来进行数据处理[3]。因此,这里仍有必要对高精度高速度的浮点多字节进行进一步研究。

1 浮点多字节标准

普通的计算机都采用标准的加法-移位技术来实现,Mowle曾经对这些基本的算法和问题作了详细的描述[4]。对于二进制数A,B来说,设其数值为AV,BV

53.jpg

由此原始矩阵乘法产生了标准的移位加算法[5,6]。一般的标准浮点乘法运算分为阶码运算与尾数运算两部分,其主要部分为尾数运算。标准尾数相乘是采用边乘边相加的办法(即加法-移位)来实现的,即乘数向左移位,产生中间结果,中间结果被加至积区的;在整个过程中,积也与乘数一起移位。此过程如图1所示。上述对于两个n位二进制尾数的相乘结果,即乘积为2n位,也就是部分积要点n位,在运算过程中,这2n字节都有可能要有相加的操作,需2n个字节加法器。对于标准算法,相当于进行了8n次2n字节的移位,还有55.jpg次2n字节的加法。其中Pj(bj)为其每个bit位的布尔取值,其为1则取1,反之则为0。

56.jpg

为了节省运算时间,标准乘法应用标准右移乘法以便减少加法器的数量,有关这方面的具体论述请参见文[2]。

2 乘法的基本原理

在执行乘法指令时,如果每个周期所检查的乘数位多于一位,乘法的速度便可以加快。例如,每次检查二位,那么加法移位周期的总数就可以减半。这些逐次的位组可以是分离的,也可以是的。这里先简述一下分离的原理。对于乘数来讲是以字节为单位的,其字长按二进制BIT来计是偶数,设被乘数A=(AX),乘数B=(MR);则在扫描了最低一对乘数位(MR1,MR0)后,有四种可能的动作,如图2所示。对于m=(MR1,MR0)2来说,被乘数A的倍数m×A被加到当前的部分乘积上,用来生成下一个部分积。上述原理可以推广到任意大小的扫描位组,其具体实现方法和分析结果请参见文[2],这里不再叙述。

57.jpg

以上所描述的是分离扫描的情况,下面再介绍多位扫描的情况。一般在乘数中bj为0的个数越多,则程序运行的时候对为0的情况仅仅是移位越过,而不用作加法的运算,在此种情况下的运算相对加快。因此希望对乘数的bj能否进行适当的操作,使这之在bj为1的区域也能使运算时间减少。

现考虑乘数中有一串k个连续的1,如下
  列的位置…,i+k,i+k-1,i+k-2,…,i,i-1,…
  列的内容…,0,1,1,…,1,0,… (2) 

58.jpg

按常规,在移位加时,被乘数A与部分积要进行k次加法操作,但是存在
2i+k-2i=2i+k-1+2i+k-2+…+2i+1+2i  (3)

因此可以用下面的数符串来代替k个连续的1
  列的位置…,i+k,i+k-1,i+k-2,…,i,i-1,…
列的内容…,1,0,0,…,-1,0,… (4)

上面的-1表示执行一次减法。这种乘法再编码的方法,只要在数字串开始时作一次加法,结束时作一次减法,使这能够代替原来的k次连续加法。显然,当k很大时,能节省大量的加法时间。

为了方便扫描,乘数位仍按二位一组分成许多组,但一次扫描三位,二位来自现在的组,第三位来自下一次高次组的低位,实际上每一组的低位被检测了二次。为了与右移算法取得一致,假定扫描乘数从右端到左端,和非重叠两种扫描模式表示见图3。

59.jpg

设扫描组XR=[Xi+1,Xi]2;下一扫描组XR′=[Xi+3,Xi+2]2;每三位一组检测后的动作说明见图4。其指出了每个机器周期或执行一次单纯的移位,或者执行一次加法,或者执行一次减法,这里只需要倍数2A或4A。当下一对的低次位xi+2为0时,三位中最左边的1经常指示一串1的左端(结束)。依式(3)所描述的特性,在具有非零的乘数位时应该执行加法。另一方面,当xi+2=1 时,即意味着是一串1的右端(开始)或中心,按照串特性需要作一次减法,在每个加法周期中,部分乘积每次要右移二位。这就使部分乘积比它应该具有的数值少了4倍被乘数(-4A)。这可以用在下一步扫描中加上所需被乘数的倍数与4倍数的差值来校正。倍数2A或4A进入加法器的地点是重要的。如果一对的尾数是 0,那么所得到的部分乘积是正确的,而且下一次的操作是一次加法。如果一对的结尾是1,则所得到的部分乘积太大,所以下一次操作将是一次减法。

65.jpg

3 重叠扫描乘法运算的实现

从以上原理可知,针对二位一组的情况需要五个被乘数的倍数,其数值可取为0,±2A,±4A。由于其每移二位至多操作一次加减法,在多字节的运算中对提高执行效率有很大的益处;不过考虑到8BITMCU的移位操作并没有二位一移的指令,对这种扫描算法有很大的障碍,必须重新考虑扫描运算如何在微型机上进行实施。

根据文[2],MCU对字节与半字节操作的指令较强,因此可以在扫描算法的基础上扩展其扫描位组,这样在每个加法周期中的运算变得很复杂,因此首先必须研究清楚这种情况。

将乘数位按4BIT分成一组,一次扫描五位;设本组为BMi=[Xi+3,Xi+2,Xi+1,Xi],下一次要扫描的BMi′的低位为Xi+4;这样在扫描过程中的情况与文[3]所介绍的情况有类似之处,但这里进行运算的次数不但与BMi有关,同时下一次扫描的低位对本算法也有重大的影响作用。假定在运算数中0,1的概率出现机会均等,对4位一组的扫描进行分析。  根据重叠扫描算法的原理,BMi′低位为0时(如图5所示),组中最左端的1指示一串1的左端(结束)。依据式(3),很容易得到每次扫描部分积所要加的被乘数倍数(见图5),可以得到其倍数,即相加的倍数
Pj={BMi-2G[BMi/2]}A+BMi.A  =2(BMi-G[BMi/2])A (5)

其中G[]为取整函数。Pj实质上均与2A有关,这一点从图中可以看到。如果一组的结尾是零,那么所得到部分乘积是正确的,按正常操作;如果一组的结尾是1,那么所得的部分积同上一次扫描有关;所以此时只是在扫描第一组时做一下记录,在最后完成时针对它在最尾端减一次A即可。这一点对于BMi′低位为1时也成立。其部分积加的情况如图6所示。

60.jpg


上一页 1 2 下一页

评论


相关推荐

技术专区

关闭