新聞中心

EEPW首頁 > 嵌入式系統(tǒng) > 設(shè)計應(yīng)用 > 利用重疊掃描方法改進單片機乘法運算

利用重疊掃描方法改進單片機乘法運算

作者: 時間:2012-02-08 來源:網(wǎng)絡(luò) 收藏

引 言

本文引用地址:http://m.butianyuan.cn/article/172157.htm

1946年,第一臺電子計算機的誕生開創(chuàng)了計算機發(fā)展的新紀元。隨著計算機科學(xué)技術(shù)的迅速發(fā)展,計算機的應(yīng)用領(lǐng)域越來越廣泛,并逐漸形成科學(xué)發(fā)展中的一個新的分支。在計算機的主要工作中,處理大量的數(shù)據(jù)是其一項基本功能;因而數(shù)據(jù)是必不可少的。于是人們設(shè)法在硬件設(shè)計與數(shù)據(jù)結(jié)構(gòu)方面努力進行工作[1],使計算機的速度不斷提高。

十幾年前,單片微型機脫穎而出,逐漸應(yīng)用于微型計算機的各個領(lǐng)域,它不僅適用于一般的自動控  制,而且還可以承擔高精度的數(shù)據(jù)處理工作。誠然,在許多系統(tǒng)中近來采用DSP來提高微機的數(shù)據(jù)處理能力,以便完成復(fù)雜的圖像處理、音頻處理、網(wǎng)絡(luò)通訊等功能,而且是一個趨勢;但在這些系統(tǒng)中仍不可忽視程序的執(zhí)行速度,因為好的算法可以大大提高程序的執(zhí)行效率[2]。同時,考慮到目前8BITMCU的主導(dǎo)地位及某些系統(tǒng)不適合配置DSP來進行數(shù)據(jù)處理[3]。因此,這里仍有必要對高精度高速度的浮點多字節(jié)進行進一步研究。

1 浮點多字節(jié)標準

普通的計算機都采用標準的加法-移位技術(shù)來實現(xiàn),Mowle曾經(jīng)對這些基本的算法和問題作了詳細的描述[4]。對于二進制數(shù)A,B來說,設(shè)其數(shù)值為AV,BV

53.jpg

由此原始矩陣乘法產(chǎn)生了標準的移位加算法[5,6]。一般的標準浮點乘法運算分為階碼運算與尾數(shù)運算兩部分,其主要部分為尾數(shù)運算。標準尾數(shù)相乘是采用邊乘邊相加的辦法(即加法-移位)來實現(xiàn)的,即乘數(shù)向左移位,產(chǎn)生中間結(jié)果,中間結(jié)果被加至積區(qū)的;在整個過程中,積也與乘數(shù)一起移位。此過程如圖1所示。上述對于兩個n位二進制尾數(shù)的相乘結(jié)果,即乘積為2n位,也就是部分積要點n位,在運算過程中,這2n字節(jié)都有可能要有相加的操作,需2n個字節(jié)加法器。對于標準算法,相當于進行了8n次2n字節(jié)的移位,還有55.jpg次2n字節(jié)的加法。其中Pj(bj)為其每個bit位的布爾取值,其為1則取1,反之則為0。

56.jpg

為了節(jié)省運算時間,標準乘法應(yīng)用標準右移乘法以便減少加法器的數(shù)量,有關(guān)這方面的具體論述請參見文[2]。

2 乘法的基本原理

在執(zhí)行乘法指令時,如果每個周期所檢查的乘數(shù)位多于一位,乘法的速度便可以加快。例如,每次檢查二位,那么加法移位周期的總數(shù)就可以減半。這些逐次的位組可以是分離的,也可以是的。這里先簡述一下分離的原理。對于乘數(shù)來講是以字節(jié)為單位的,其字長按二進制BIT來計是偶數(shù),設(shè)被乘數(shù)A=(AX),乘數(shù)B=(MR);則在掃描了最低一對乘數(shù)位(MR1,MR0)后,有四種可能的動作,如圖2所示。對于m=(MR1,MR0)2來說,被乘數(shù)A的倍數(shù)m×A被加到當前的部分乘積上,用來生成下一個部分積。上述原理可以推廣到任意大小的掃描位組,其具體實現(xiàn)方法和分析結(jié)果請參見文[2],這里不再敘述。

57.jpg

以上所描述的是分離掃描的情況,下面再介紹多位掃描的情況。一般在乘數(shù)中bj為0的個數(shù)越多,則程序運行的時候?qū)?的情況僅僅是移位越過,而不用作加法的運算,在此種情況下的運算相對加快。因此希望對乘數(shù)的bj能否進行適當?shù)牟僮鳎惯@之在bj為1的區(qū)域也能使運算時間減少。

現(xiàn)考慮乘數(shù)中有一串k個連續(xù)的1,如下
  列的位置…,i+k,i+k-1,i+k-2,…,i,i-1,…
  列的內(nèi)容…,0,1,1,…,1,0,… (2) 

58.jpg

按常規(guī),在移位加時,被乘數(shù)A與部分積要進行k次加法操作,但是存在
2i+k-2i=2i+k-1+2i+k-2+…+2i+1+2i  (3)

因此可以用下面的數(shù)符串來代替k個連續(xù)的1
  列的位置…,i+k,i+k-1,i+k-2,…,i,i-1,…
列的內(nèi)容…,1,0,0,…,-1,0,… (4)

上面的-1表示執(zhí)行一次減法。這種乘法再編碼的方法,只要在數(shù)字串開始時作一次加法,結(jié)束時作一次減法,使這能夠代替原來的k次連續(xù)加法。顯然,當k很大時,能節(jié)省大量的加法時間。

為了方便掃描,乘數(shù)位仍按二位一組分成許多組,但一次掃描三位,二位來自現(xiàn)在的組,第三位來自下一次高次組的低位,實際上每一組的低位被檢測了二次。為了與右移算法取得一致,假定掃描乘數(shù)從右端到左端,和非重疊兩種掃描模式表示見圖3。

59.jpg

設(shè)掃描組XR=[Xi+1,Xi]2;下一掃描組XR′=[Xi+3,Xi+2]2;每三位一組檢測后的動作說明見圖4。其指出了每個機器周期或執(zhí)行一次單純的移位,或者執(zhí)行一次加法,或者執(zhí)行一次減法,這里只需要倍數(shù)2A或4A。當下一對的低次位xi+2為0時,三位中最左邊的1經(jīng)常指示一串1的左端(結(jié)束)。依式(3)所描述的特性,在具有非零的乘數(shù)位時應(yīng)該執(zhí)行加法。另一方面,當xi+2=1 時,即意味著是一串1的右端(開始)或中心,按照串特性需要作一次減法,在每個加法周期中,部分乘積每次要右移二位。這就使部分乘積比它應(yīng)該具有的數(shù)值少了4倍被乘數(shù)(-4A)。這可以用在下一步掃描中加上所需被乘數(shù)的倍數(shù)與4倍數(shù)的差值來校正。倍數(shù)2A或4A進入加法器的地點是重要的。如果一對的尾數(shù)是 0,那么所得到的部分乘積是正確的,而且下一次的操作是一次加法。如果一對的結(jié)尾是1,則所得到的部分乘積太大,所以下一次操作將是一次減法。

65.jpg

3 重疊掃描乘法運算的實現(xiàn)

從以上原理可知,針對二位一組的情況需要五個被乘數(shù)的倍數(shù),其數(shù)值可取為0,±2A,±4A。由于其每移二位至多操作一次加減法,在多字節(jié)的運算中對提高執(zhí)行效率有很大的益處;不過考慮到8BITMCU的移位操作并沒有二位一移的指令,對這種掃描算法有很大的障礙,必須重新考慮掃描運算如何在微型機上進行實施。

根據(jù)文[2],MCU對字節(jié)與半字節(jié)操作的指令較強,因此可以在掃描算法的基礎(chǔ)上擴展其掃描位組,這樣在每個加法周期中的運算變得很復(fù)雜,因此首先必須研究清楚這種情況。

將乘數(shù)位按4BIT分成一組,一次掃描五位;設(shè)本組為BMi=[Xi+3,Xi+2,Xi+1,Xi],下一次要掃描的BMi′的低位為Xi+4;這樣在掃描過程中的情況與文[3]所介紹的情況有類似之處,但這里進行運算的次數(shù)不但與BMi有關(guān),同時下一次掃描的低位對本算法也有重大的影響作用。假定在運算數(shù)中0,1的概率出現(xiàn)機會均等,對4位一組的掃描進行分析?! 「鶕?jù)重疊掃描算法的原理,BMi′低位為0時(如圖5所示),組中最左端的1指示一串1的左端(結(jié)束)。依據(jù)式(3),很容易得到每次掃描部分積所要加的被乘數(shù)倍數(shù)(見圖5),可以得到其倍數(shù),即相加的倍數(shù)
Pj={BMi-2G[BMi/2]}A+BMi.A ?。?(BMi-G[BMi/2])A (5)

其中G[]為取整函數(shù)。Pj實質(zhì)上均與2A有關(guān),這一點從圖中可以看到。如果一組的結(jié)尾是零,那么所得到部分乘積是正確的,按正常操作;如果一組的結(jié)尾是1,那么所得的部分積同上一次掃描有關(guān);所以此時只是在掃描第一組時做一下記錄,在最后完成時針對它在最尾端減一次A即可。這一點對于BMi′低位為1時也成立。其部分積加的情況如圖6所示。

60.jpg


上一頁 1 2 下一頁

評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉