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

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