一種基于循環(huán)減法原理除法器的加速方法.doc

文庫下載 免費(fèi)文檔下載/本文檔下載自文庫下載網(wǎng)，內(nèi)容可能不完整，您可以點(diǎn)擊以下網(wǎng)址繼續(xù)閱讀或下載：/doc/8d7a0cae8762caaedc33d41e.html一種基于循環(huán)減法原理除法器的加速方法沈航數(shù)電課程設(shè)計(jì)-BCD 碼除法器 ,所需材料 ,報(bào)告?26卷?第12期2009年12月微電子學(xué)與計(jì)算機(jī)MICROELECTRONICS&COMPUTERVol.26?No.12December2009一種基于循環(huán)減法原理除法器的加速方法宣淑巍,李曉江,馬成炎(中國科學(xué)院微電子研究所,浙江杭州310053)摘?要:通過分析一般除法器的原理,提出了一種基于移位循環(huán)減法原理除法器的普遍加速方法,并給出了關(guān)鍵電路的設(shè)計(jì)和仿真比較結(jié)果.該方法適用于無符號(hào)數(shù)除法,對(duì)于有符號(hào)數(shù)除法可以先取絕對(duì)值再進(jìn)行運(yùn)算.與傳統(tǒng)的除法器相比,特別是當(dāng)除數(shù)絕對(duì)值相對(duì)于被除數(shù)絕對(duì)值比較大時(shí),能顯著縮短除法器所用時(shí)鐘周期;而對(duì)于所有被除數(shù)絕對(duì)值小于除數(shù)絕對(duì)值的情況,只需一個(gè)時(shí)鐘周期就能完成,極大提高了運(yùn)算效率.雖然只分析結(jié)果為整數(shù)的除法,但對(duì)于任意定點(diǎn)循環(huán)減法除法,都有相同的加速效果.關(guān)鍵詞:移位;循環(huán)減法;對(duì)齊操作;首0計(jì)數(shù)器中圖分類號(hào):TN402?文獻(xiàn)標(biāo)識(shí)碼:A?文章編號(hào):1000-7180(2009)12-0012-04AnAcceleratedMethodofCircularSubtractionDivisionXUANShu-wei,LIXiao-jiang,MACheng-yan(InstitutionofMicroelectronics,ChineseAcademyofScience,Hangzhou310053,China)Abstract:Acommonacceleratedmethodofcircularsubtractiondivisionwaspresentedbasedonanalyzingtheprincipleofdivision,andthekeycircuitwasdesigned.Simulationresultsweregivenforcomparingthetimethedivisionused.Thismethodwasappliedto/doc/8d7a0cae8762caaedc33d41e.htmlunsigneddivision,butitcouldalsobeusedtothesignedafterchangedtotheirabsolutevalue.Comparedwithtraditionaldivision,especiallywhentheabsolutevalueofdivisorwaslargetothedividend,thecyclesofclockwereshortenedobviously,andwhentheabsolutevalueofdividendwassmallerthanthedivisor,itjusttookoneclocktofinishtheoperation,sotheefficiencyofthedivisionwasimprovedverywell.Thispaperonlyanalyzedintegrald-ivision,butithadthesameacceleratedeffecttoallfixpointcircularsubtractiondivision.Keywords:shift;circularsubtraction;alignmentoperation;first?zero?scounter1?引言隨著現(xiàn)代信息處理技術(shù)的迅猛發(fā)展,除法器作為微處理器的一個(gè)重要運(yùn)算部件在一些高性能應(yīng)用場合的使用越來越頻繁,對(duì)除法器的性能要求越來越高,除法器的硬件實(shí)現(xiàn)有多種,除法器陣列可在一個(gè)時(shí)鐘周期內(nèi)做完整個(gè)除法運(yùn)算,但是硬件面積大,邏輯延時(shí)長,往往只能工作在比較低的頻率;用乘法器實(shí)現(xiàn)是先通過求除數(shù)的倒數(shù),然后相乘,這種方法主要應(yīng)用在浮點(diǎn)運(yùn)算中,是一種近似算法,運(yùn)算精度受到一定限制;循環(huán)相減的多周期除法器是面積和運(yùn)算時(shí)間的一個(gè)折中,主要有不恢復(fù)余數(shù)法和恢復(fù)余數(shù)法兩種算法,現(xiàn)在大多數(shù)通用除法器都基于這收稿日期:2008-11-15兩種基本算法原理開發(fā),文中的加速方法就是針對(duì)這種除法器提出的1.2?除法器基本原理除法器的本質(zhì)其實(shí)就是在做減法運(yùn)算/doc/8d7a0cae8762caaedc33d41e.html和移位運(yùn)算.在除法進(jìn)行過程中,要判斷部分被除數(shù)是否夠除數(shù)減,如果不夠減,則在該位上商0,同時(shí)補(bǔ)充被除數(shù)的下一位(即移位操作),組成更大的數(shù);如果夠減,則該位商1,在部分被除數(shù)中減去除數(shù),所得結(jié)果再補(bǔ)充被除數(shù)的下一位.直至被除數(shù)的每一個(gè)位都使用為止.那么怎樣判斷部分被除數(shù)是否夠減呢?一種是采用專門的比較器,再根據(jù)比較結(jié)果采取相應(yīng)的操作;第二種是不管是否夠減,先減了再說.當(dāng)?第12期宣淑巍,等:一種基于循環(huán)減法原理除法器的加速方法13夠減時(shí),這種方法就不僅判斷了是否夠減,還完成了減法操作2.基于上述原理的有兩種基本算法:恢復(fù)余數(shù)法和不恢復(fù)余數(shù)法.它們的不同之處就在于當(dāng)完成減法操作之后,如果發(fā)現(xiàn)不夠減,就存在是否要把除數(shù)加回到產(chǎn)生的差,以恢復(fù)原來的部分被除數(shù)上.最后再根據(jù)有符號(hào)數(shù)運(yùn)算的法則對(duì)結(jié)果進(jìn)行處理,得到有符號(hào)數(shù)結(jié)果.在恢復(fù)余數(shù)法中,如果余數(shù)P為負(fù)數(shù),即不夠減,則需要加上除數(shù)B,恢復(fù)成原來的余數(shù),即P B.然后,余數(shù)P和被除數(shù)A聯(lián)合左移1位.此時(shí)余數(shù)為2(P B) ai,其中ai為被除數(shù)A中的一位被移入P中.隨后,進(jìn)入下一步運(yùn)算,即從余數(shù)中減去除數(shù)B.有(2(P B) ai)-B=2P B ai這樣,就提供一種方法,當(dāng)在某一步中,判斷余數(shù)P為負(fù)數(shù),無需在該步驟中加上除數(shù)B恢復(fù)成原來的余數(shù),只需在下一步中把恢復(fù)余數(shù)算法中的減去除數(shù)B改成加上除數(shù)B,這種算法就叫做不恢復(fù)余數(shù)法.不恢復(fù)余數(shù)法的問題是如果最后一步中得到的余數(shù)為負(fù),需要加上除數(shù)B來恢復(fù)余數(shù).m表示被除數(shù)前面無效的0個(gè)數(shù).圖1?傳統(tǒng)移位操作圖2?改進(jìn)后的移位操作接下來還是從判斷被除數(shù)和除數(shù)的大小入手.因?yàn)榇藭r(shí)被除數(shù)和除數(shù)都是正數(shù),其有效位的多少就決定了兩者的大小,而且已經(jīng)得到了被除數(shù)的有效位(n-m),假設(shè)除數(shù)的有效位為k,那繼續(xù)要做的就是讓補(bǔ)充到余數(shù)中的部分被除數(shù)至少達(dá)到k位.還是以上面的4位除法為例,除數(shù)有效位為2,算法演示如下所示.改進(jìn)后的移位/doc/8d7a0cae8762caaedc33d41e.html操作流程,如圖3所示.3?基于循環(huán)減法的除法器加速原理和具體實(shí)現(xiàn)3.1?加速原理的算法分析既然一般除法器的本質(zhì)3是減法運(yùn)算,那么要加快除法器的運(yùn)算就必須減少減法運(yùn)算的次數(shù).一些改進(jìn)算法的核心就是如何實(shí)現(xiàn)循環(huán)減法,又兼顧硬件的復(fù)雜度,例如SRT算法.但是文中要提出的是一種普遍的加速方法,不管采用哪種算法,只要是以循環(huán)減法為基本原理的,都能部分縮短計(jì)算時(shí)間,因此,把焦點(diǎn)放在操作數(shù)的預(yù)處理上.例如一個(gè)4位二進(jìn)制除法運(yùn)算0011?0010,通過第2節(jié)的算法分析,發(fā)現(xiàn)只要被除數(shù)前面有0,那么補(bǔ)充到初始余數(shù)(余數(shù)初始值為0)的值就是0,這時(shí)候去減除數(shù)肯定不夠減(商0),因此白白浪費(fèi)了2個(gè)時(shí)鐘周期用于移位操作.因此作如下改進(jìn):一般移位操作,其中HI用于存放余數(shù),LO初始用于存放被除數(shù),當(dāng)被除數(shù)左移補(bǔ)充HI0后LO0用于存放新產(chǎn)生的商X,參見圖1.改進(jìn)后的移位操作見圖2.即忽略掉被除數(shù)前面無效的0,直接把最高有效位補(bǔ)充到了余數(shù)寄存器,LO的低位用0填補(bǔ),因?yàn)樯虨?.至此,把除法,圖3?改進(jìn)的移位方法改進(jìn)后的一步移位算法,如圖4所示.圖4?一步移位操作這樣又縮短了k-1次減法,總的減法次數(shù)縮小到n-m-k 1=n-(m k) 1次,而m k越大,表示除數(shù)相對(duì)與被除數(shù)越大,此時(shí)的除法運(yùn)算也越快.3.2?加速算法的具體實(shí)現(xiàn)這種加速算法的核心就是通過一步移位實(shí)現(xiàn)部14微電子學(xué)與計(jì)算機(jī)2009年分被除數(shù)和除數(shù)的對(duì)齊操作,即有效位數(shù)相等.對(duì)齊操作的移位位數(shù)num由兩部分組成,包括被除數(shù)的無效0個(gè)數(shù)m和除數(shù)的有效位數(shù)k,而除數(shù)的有效位數(shù)又等于除法位寬減去除數(shù)的無效0個(gè)數(shù),即k=n-l(l為除數(shù)無效0個(gè)數(shù)),所以移位位數(shù)有num=m (n-1)=n-(l-m)(1)式中,l-m為被除數(shù)和除數(shù)無效0個(gè)數(shù)/doc/8d7a0cae8762caaedc33d41e.html之差.當(dāng)l-m?0時(shí),計(jì)算結(jié)果沒問題;但當(dāng)l-mn,這時(shí)可通過判斷l(xiāng)-m的最高位是1還是0,來選擇num是等于式(1)的計(jì)算結(jié)果還是n.現(xiàn)在需要一個(gè)專用電路來計(jì)算操作數(shù)的無效0個(gè)數(shù),稱之為首0計(jì)數(shù)器.簡單起見,下面給出一個(gè)四位首0計(jì)數(shù)器的設(shè)計(jì)方法,更高位數(shù)的首0計(jì)數(shù)器可由相同原理得到或由低位數(shù)首0計(jì)數(shù)器組合而成:本例中操作數(shù)為A3:0,掃描結(jié)果為P2:0四位首0計(jì)數(shù)器的真值表如表1所示.表1?4位首0計(jì)數(shù)器真值表A310000A2x1000A1xx100A0xxx10P200001P100110P001010具體仿真結(jié)構(gòu)如圖5所示.圖5?仿真結(jié)構(gòu)第一種情況被除數(shù)大于除數(shù),例如1118208?272=4111,余16,仿真結(jié)果如圖6所示.圖6?除法器仿真結(jié)果a根據(jù)真值表可得到以下邏輯表達(dá)式:P0=A3A2 A3A2A1A0P1=A3A2A1 A3A2A1 A0P2=A3A2A1A0至此,被除數(shù)和除數(shù)的無效0個(gè)數(shù)都已得到,再經(jīng)過加減運(yùn)算,就能算出首次移位位數(shù),然后再經(jīng)過一個(gè)左移移位器,進(jìn)行一步對(duì)齊操作.可以看到從start信號(hào)開始到實(shí)際除法運(yùn)算結(jié)束,一共花費(fèi)14個(gè)時(shí)鐘周期.當(dāng)把兩個(gè)操作數(shù)都擴(kuò)展為32位時(shí),被除數(shù)首0個(gè)數(shù)為8個(gè),除數(shù)為20個(gè),因此根據(jù)式(1)對(duì)齊操作所需移位位數(shù)為20,比原來只是按部就班左移1位,縮短了19個(gè)時(shí)鐘周期.所以所需時(shí)鐘周期數(shù)為32 1-19=14,加1是因?yàn)榭吹絪tart信號(hào)后,把操作數(shù)載入HI/LO寄存器需要1個(gè)時(shí)鐘周期.這與仿真結(jié)果一致.也可得到實(shí)際運(yùn)算花費(fèi)時(shí)鐘數(shù)為S=32 1-(num-1)=34-num./doc/8d7a0cae8762caaedc33d41e.html繼續(xù)增大除數(shù),改為1118208?65808=16,余65280.可得仿真結(jié)果,如圖7所示.4?加速算法仿真結(jié)果文中提出的是一種普遍加速算法,并不針對(duì)某種具體的循環(huán)減法除法器,因此采用一個(gè)經(jīng)過充分驗(yàn)證的32位普通循環(huán)減法除法器Verilog模型進(jìn)行仿真,所用仿真工具為Synopsys公司的VCS,所要做的只是把經(jīng)過對(duì)齊操作的被除數(shù)和商放入結(jié)果寄存器(HI/LO),然后讓除法器開始工作,觀察計(jì)算結(jié)束所用時(shí)鐘周期比原來提高了多少.這個(gè)普通循環(huán)減法除法器的運(yùn)算周期是固定的,因?yàn)槊?bit都要移位補(bǔ)充至部分被除數(shù),所以對(duì)于任意操作數(shù)都需要32個(gè)時(shí)鐘周期.下面根據(jù)操.4-5圖7?除法器仿真結(jié)果b可見,隨著除數(shù)增大,除法運(yùn)算周期越來越短.?第12期宣淑巍,等:一種基于循環(huán)減法原理除法器的加速方法15S=34-num=34-28=6,與仿真結(jié)果一致.第二種情況被除數(shù)等于除數(shù),例如1048592?1048592=1,余數(shù)0,如圖8所示.推導(dǎo)出一種基于數(shù)據(jù)預(yù)處理的普遍加速算法,該方法在除數(shù)比較大時(shí)效果尤為明顯.由于增加了首0計(jì)數(shù)器、移位器和移位位數(shù)的計(jì)算,增加了不少延遲,所以當(dāng)工作頻率比較快時(shí),建議額外增加一個(gè)時(shí)鐘周期來單獨(dú)進(jìn)行數(shù)據(jù)預(yù)處理,然后在下一個(gè)時(shí)鐘周期開始除法運(yùn)算.這樣,最壞情況下除法運(yùn)算周期反而多了一個(gè)時(shí)鐘周期,但是就平均而言,該方法能很大程度上提高運(yùn)算速度.這種方法基于數(shù)據(jù)預(yù)處理,因此不會(huì)增加除法器本身的復(fù)雜度,有利于IP的復(fù)用.圖8?除法器仿真結(jié)果c參考文獻(xiàn):1DavidAP,JohnLH.Computerorganization&design:thehardware/softwareinterfaceM.2nded.SanFransisco:MorganKaufmannPublishers,/doc/8d7a0cae8762caaedc33d41e.html1998:202-209.2朱子玉,李亞民.CPU芯片邏輯設(shè)計(jì)技術(shù)M.北京:清華大學(xué)出版社,2005:113-131.3劉杰.高速整數(shù)除法器的實(shí)現(xiàn)及其仿真J.福建電腦,2007,16(10):162-163.4周珍艮,郭立.固定延遲的流水線雙精度浮點(diǎn)除法電路J.微電子學(xué)與計(jì)算機(jī),2008,25(5):84-87.5黃秀蓀,葉青,仇玉林.高速除法器設(shè)計(jì)及ASIC實(shí)現(xiàn)J.微電子學(xué)與計(jì)算機(jī),2008,25(2):133-135.S=34-num=34-32=2,與仿真結(jié)果一致.第三種情況被除數(shù)小于除數(shù),例如4096?1048848=0,余數(shù)4096,如圖9所示.作者簡介:圖9?除法器仿真結(jié)果d宣淑巍?男,(1983-),碩士.研究方向?yàn)閷Ｓ眉呻娐吩O(shè)計(jì)和應(yīng)用.李曉江?男,(1972-),碩士生導(dǎo)師.研究方向?yàn)閷Ｓ眉呻娐吩O(shè)計(jì)和應(yīng)用.馬成炎?男,(1963-),博士生導(dǎo)師.研究方向?yàn)榧?