【文章內(nèi)容簡介】 。wj，l與d′的實(shí)際值所在的“不確定區(qū)域”不能同時(shí)越過重疊區(qū)域的上、下邊界。圖中的每個(gè)“網(wǎng)格”代表存儲(chǔ)陣列中的一個(gè)單元，對(duì)應(yīng)的地址信號(hào)是網(wǎng)格左下角的頂點(diǎn)坐標(biāo)，如下圖所示：(第一象限) 4wj與d′實(shí)際值的“不確定區(qū)域”如圖所示，當(dāng)4wj與d′的高位近似值為圖中某一點(diǎn)時(shí)，其實(shí)際值可能位于這一點(diǎn)右上方“不確定區(qū)域”內(nèi)的任何位置。因?yàn)?wj以進(jìn)位保留形式表示而d′以標(biāo)準(zhǔn)形式表示，所以不確定區(qū)域沿縱軸方向占據(jù)兩個(gè)最小單位。通過觀察不難發(fā)現(xiàn)，為了滿足前面所述的規(guī)則，即:分界線應(yīng)該位于重疊區(qū)域之內(nèi)并且“不確定區(qū)域”不能同時(shí)越過重疊區(qū)域的上、下邊界，網(wǎng)格需要有一定的密度，這個(gè)密度是由對(duì)4wj與d′的近似程度，也就是由取它們的高幾位作近似來決定的。以往的研究結(jié)果顯示，對(duì)于商取值為最小冗余度的情況，4wj應(yīng)該至少取高7位，而d′應(yīng)該至少取高5位[4]。也就是說，存儲(chǔ)陣列中一共包含2725個(gè)存儲(chǔ)單元。由以上分析可知，對(duì)于基數(shù)4SRT算法的直接實(shí)現(xiàn)來說，每次循環(huán)只需進(jìn)行一次進(jìn)位保留加法，就可以得到一位四進(jìn)制商值。但是它的商選擇邏輯比較復(fù)雜。2725的存儲(chǔ)陣列會(huì)占用比較大的面積，另外，存儲(chǔ)陣列的地址解碼邏輯也會(huì)造成較長的時(shí)延。本節(jié)內(nèi)容介紹的是基數(shù)4SRT算法的直接實(shí)現(xiàn)，其特點(diǎn)是以地址信號(hào)輸入一個(gè)完整的存儲(chǔ)陣列從而直接得到商值。以往的研究資料中也提出過一些類似的實(shí)現(xiàn)方法[4] [5]。除了直接實(shí)現(xiàn)之外，還有其他一些途徑可以實(shí)現(xiàn)基數(shù)4SRT算法。本文所列的參考資料[6] …[11]介紹了不同的實(shí)現(xiàn)方式，其中應(yīng)用到的技術(shù)包括操作數(shù)移位、商值預(yù)測、查找表拆分、基數(shù)拆分等。 NewtonRaphson 除法算法NewtonRaphson 除法算法（以下簡稱為牛頓迭代算法）的基本思想是用乘法代替除法運(yùn)算，例如，a/b=a*(1/b)?，F(xiàn)在代問題是不用除法，如何計(jì)算出1/b，這也是牛頓迭代算法代核心所在。假設(shè)我們有函數(shù)f(x),如何找出X，使得f（X）=0。，我們猜測x0，由f(x)在該點(diǎn)處的切線方程y f(x0)=f′ (x0)（x x0）,找出使y=0的新的一點(diǎn)x1，則x1更加接近X。一般地，y f(xi)=f′ (xi)（x xi） 令y=0，我們有新的一點(diǎn)xi=1xi+1=xif(xi)/f′（xi） NewtonRaphson 除法算法重復(fù)上述過程，一直到xn足夠精確為止。令f（x）=1/xb,則在x=1/b處f（x）=0。應(yīng)用牛頓迭代公式：x i+1= x i （1/ x ib）/(1/x i2)= x i+ x i x i2b= x i (2 x i b)。這樣，我們 能夠用下述步驟實(shí)現(xiàn)a/b：（1）把b移位，使其滿足1≤b＜2，即，b=…。使用b高若干位查表，得到1/b的近似值x0 。（2）迭代xi+1= x i（2 x i b），直到xn足夠精確為止。（3）計(jì)算axn，把結(jié)果反向移位以消除第一步造成的影響。查表可通過ROM（只讀存儲(chǔ)器）來完成。事先把1/b的近似值存放在ROM中，用b的高若干位作為地址來訪問它。由于b的最高位總是1，地址可以不用它。問題是ROM中存放多少為才合適。這將影響到使用多少位地址來訪問它，以及需要多少次迭代才能使xn足夠精確?？梢詫懸粋€(gè)簡單的程序，求最少需要多少位地址才能區(qū)分出ROM中的p位精確位。從ROM中直接得到1/b所有的精確位是不實(shí)現(xiàn)的，它需要太大容量的ROM。設(shè)x i精確到p位，這意味著︱（x i1/b）（1/b）︱=2p。下面的推導(dǎo)過程說明︱（xi+11/b）（1/b）︱=22p，即，迭代一次，精度是原來的兩倍。︱（xi+11/b）（1/b）︱=︱（x i（2 x i b）1/b）/(1/b)︱=︱(2 x i/b x i2(1/b)2)/ (1/b)2︱=︱( x i1/b)2/ (1/b)2︱=2p牛頓迭代算法具有“自我修正”的能力，在運(yùn)算過程中的舍入誤差是沒有關(guān)系的。下次的迭代總是有所改進(jìn)的（精度大約是原來的兩倍）。在介紹基本除法器的后端實(shí)現(xiàn)(包括電路設(shè)計(jì)和物理設(shè)計(jì))之前，本節(jié)先對(duì)后端設(shè)計(jì)所關(guān)涉到的一些設(shè)計(jì)方法進(jìn)行介紹。這些設(shè)計(jì)方法是作者在自身實(shí)踐的基礎(chǔ)上結(jié)合一些理論知識(shí)加以總結(jié)得到的。在設(shè)計(jì)過程中注意運(yùn)用這些方法可以達(dá)到事半功倍的效果。并行是電路結(jié)構(gòu)設(shè)計(jì)的關(guān)鍵議題之一，在一周期內(nèi)，如果使不同的硬件邏輯在同一時(shí)間段內(nèi)并行處理，就可以提高系統(tǒng)的運(yùn)行速度。所以，設(shè)計(jì)出高度并行的電路結(jié)構(gòu)是達(dá)到高速度、低成本的設(shè)計(jì)目標(biāo)的捷徑。但是，硬件邏輯的并行度并不是可以無限提高，因?yàn)椴⑿卸热Q于內(nèi)部數(shù)據(jù)之間的相關(guān)性。所以并行度實(shí)際上是由算法決定的，并行結(jié)構(gòu)設(shè)計(jì)的目標(biāo)也就是在面積等成本一定的條件下，盡量將算法中所包含的并行度加以利用。下面的例子說明了硬件邏輯的并行以及數(shù)據(jù)的相關(guān)等概念。對(duì)于一個(gè)簡單的算法:S=AB+CD+ E+ F+ G，如果要以加法單元和乘法單元作為基本部件來進(jìn)行硬件實(shí)現(xiàn)，那么下面三種實(shí)現(xiàn)方法有明顯的區(qū)別: 。也就是說，它們的面積應(yīng)該是近似相等的。但對(duì)系統(tǒng)的運(yùn)行速度來說，第一種最慢，它的時(shí)延是+4(與分別是乘法單元與加法單元的時(shí)延)。第二種是+3。第三種最快，時(shí)延是+2。第三種實(shí)現(xiàn)之所以達(dá)到了最短的時(shí)延，在于它最大限度地利用了算法所包含的并行度。它的硬件邏輯中出現(xiàn)了如下幾個(gè)中間數(shù)據(jù):=AB， =CD，=E+F，，如下圖所示: 中間數(shù)據(jù)的相關(guān)性可以看出，、。是第一級(jí)邏輯的輸出，它們的輸入之間沒有交集，所以、是不相關(guān)的，以它們作為輸出的硬件邏輯之間可以并行。與之間也一樣。上面的例子說明了組合邏輯的結(jié)構(gòu)優(yōu)化對(duì)于系統(tǒng)設(shè)計(jì)的重要性。這種分析與優(yōu)化的方法也適用于其它算法的系統(tǒng)設(shè)計(jì)，在后面除法器的實(shí)現(xiàn)過程中將會(huì)用到。 硬件時(shí)序結(jié)構(gòu)的優(yōu)化方法因?yàn)閷?shí)用的除法算法都是以“循環(huán)迭代”的方式完成中間運(yùn)算，所以除法器硬件整體上呈現(xiàn)循環(huán)結(jié)構(gòu)。在介紹除法器的后端實(shí)現(xiàn)之前，專門討論一下對(duì)硬件循環(huán)結(jié)構(gòu)在并行度方面進(jìn)行優(yōu)化的方法是必要的。硬件循環(huán)結(jié)構(gòu)中一定包含時(shí)序部件，例如寄存器等，用來對(duì)時(shí)序加以劃分。對(duì)于算法上連續(xù)的運(yùn)算過程，具體實(shí)現(xiàn)時(shí)可以有不同的時(shí)序劃分方法，而不同的時(shí)序劃分方法往往導(dǎo)致不同的系統(tǒng)工作效率。下面的例子可以說明這一問題: 循環(huán)結(jié)構(gòu)算法示意圖，最初的輸入為In1與In2，中間的處理過程是由兩個(gè)函數(shù)f1與f2構(gòu)成的k輪循環(huán)，最終產(chǎn)生輸出Out1與Out2。如果直接以硬件實(shí)現(xiàn)上述算法，:、f2分別表示實(shí)現(xiàn)兩個(gè)函數(shù)的硬件模塊?？梢钥吹剑谝粋€(gè)循環(huán)周期內(nèi)，f1和f2的處理過程是串行的，像算法中所表示的那樣。如果要對(duì)這種硬件實(shí)現(xiàn)在并行度上進(jìn)行改進(jìn)，可以先把算法在時(shí)序上展開，從全局角度重新考察：，虛線表示不同的時(shí)序劃分方法。可以看到，按照圖中第二種方式劃分時(shí)序，可以使f1與f2的處理過程并行，:，fl與f2的處理過程是并行的。如果f1與f2處理時(shí)間相仿，并且忽略寄存器和數(shù)據(jù)選擇邏輯所造成的延遲，理論上一周期內(nèi)的運(yùn)行速度能達(dá)到接近100%的提升，而在硬件面積上卻不會(huì)有顯著差別。上述算法結(jié)構(gòu)是作者參與過的另外一個(gè)項(xiàng)目:DES加/解密模塊設(shè)計(jì)所采用的算法結(jié)構(gòu)。DES算法是七十年代提出并成為標(biāo)準(zhǔn)的一種對(duì)稱加/解密算法，至今在數(shù)據(jù)加密領(lǐng)域仍被廣泛運(yùn)用。，In2為密鑰。f2為密鑰處理函數(shù)，f1為主加密函數(shù)。密鑰經(jīng)f2函數(shù)處理后再與明文做加密運(yùn)算，構(gòu)成算法中的一個(gè)循環(huán)體。原始的DES算法包含16輪循環(huán)。，循環(huán)次數(shù)越多，理論上性能提升的比例就越高。所以，對(duì)于硬件循環(huán)結(jié)構(gòu)來說，有時(shí)分屬不同周期的邏輯之間存在并行度以時(shí)序展開的辦法對(duì)算法進(jìn)行全局角度的考察有助于發(fā)現(xiàn)這種并行度。在一定條件下，可以通過改變系統(tǒng)結(jié)構(gòu)，調(diào)整邏輯的時(shí)序劃分來達(dá)到并行的目的。作者把這種方法叫做“時(shí)序展開法”。在對(duì)包括除法算法在內(nèi)的循環(huán)結(jié)構(gòu)算法進(jìn)行分析和結(jié)構(gòu)優(yōu)化時(shí)，這種方法能起到一定作用。另外值得指出的是，本節(jié)中的小節(jié)敘述的組合邏輯優(yōu)化一般可以借助綜合工具完成，而本小節(jié)所述的時(shí)序分析與優(yōu)化還需要設(shè)計(jì)者來做，因?yàn)槟壳暗木C合工具時(shí)序優(yōu)化功能上有所欠缺，一般不會(huì)改變由輸入代碼所描述的系統(tǒng)時(shí)序結(jié)構(gòu)。對(duì)設(shè)計(jì)者來說，系統(tǒng)時(shí)序的優(yōu)化方法相對(duì)更加重要。 由于本文所介紹的基本除法器在后端采用全定制設(shè)計(jì)，所以本小節(jié)討論針對(duì)全定制設(shè)計(jì)的版圖結(jié)構(gòu)設(shè)計(jì)方法。與自動(dòng)化設(shè)計(jì)流程相比，全定制設(shè)計(jì)能針對(duì)具體的邏輯結(jié)構(gòu)對(duì)電路和版圖布局布線進(jìn)行優(yōu)化，所以在系統(tǒng)的面積、運(yùn)行速度上都具有優(yōu)勢，但劣勢也比較明顯，就是:設(shè)計(jì)周期長，需要投入較多人力，產(chǎn)品的可升級(jí)性與可維護(hù)性較差。究其原因，在于全定制設(shè)計(jì)的版圖結(jié)構(gòu)十分復(fù)雜，手工繪制和修改版圖十分不易。如果繪制版圖時(shí)能夠采用系統(tǒng)的方法減低手工繪制的復(fù)雜度，就可以相對(duì)減小全定制設(shè)計(jì)的劣勢，也就可以使全定制設(shè)計(jì)方法在總體上更具備競爭力。注重全定制版圖的層次化和模塊化設(shè)計(jì)就是有效的方法之一。與系統(tǒng)設(shè)計(jì)一樣，全定制版圖設(shè)計(jì)也是按照由低層到高層的順序進(jìn)行，由基本部件拼接成功能模塊，再拼接成全系統(tǒng)。每完成一級(jí)，都要做后端驗(yàn)證DRC、LVS以保證正確性。但是，在拼接高層模塊的時(shí)候，由于布局或布線安排上的矛盾經(jīng)常導(dǎo)致原來己通過驗(yàn)證的低層模塊需要修改，從而破壞了它們的完整性，像下圖顯示的那樣:，在版圖模塊拼接成整個(gè)系統(tǒng)之前，每個(gè)模塊一定是已經(jīng)通過后端驗(yàn)證的，但由于拼接過程中修改了原有模塊，導(dǎo)致了雖然最后系統(tǒng)的版圖能通過后端驗(yàn)證，但是將各個(gè)模塊重新提取出來后卻通不過驗(yàn)證的結(jié)果。這種現(xiàn)象在全定制版圖設(shè)計(jì)中非常普遍。它不利于系統(tǒng)的升級(jí)維護(hù)，甚至對(duì)快速完成系統(tǒng)版圖本身也有影響。因?yàn)楫?dāng)高層模塊在后端驗(yàn)證上遇到問題時(shí)，就無法通過重新驗(yàn)證低層模塊來快速查找并排除這些問題。所以，在進(jìn)行全定制版圖拼接時(shí)，應(yīng)該注意版圖模塊的完整性與獨(dú)立性。版圖模塊的完整性與獨(dú)立性是相對(duì)于后端驗(yàn)證而言的。如果一個(gè)版圖模塊從系統(tǒng)版圖中分離出來后，自身仍能通過后端驗(yàn)證DRC、LVS，那么它就是完整的，如下圖所示:當(dāng)碰到系統(tǒng)需要升級(jí)或其它情況，系統(tǒng)中的一個(gè)模塊需要做修改時(shí)，如果只需要修改相應(yīng)的版圖模塊(而不需要改動(dòng)系統(tǒng)版圖的其它部分)，將修改后的模塊替換到原版圖中就能得到符合要求的新的系統(tǒng)版圖，那么，相應(yīng)的模塊就是獨(dú)立的，如下圖所示:顯而易見，這種方法能極大地提高全定制版圖設(shè)計(jì)的效率。雖然在設(shè)計(jì)過程中保持低層版圖模塊的完整與獨(dú)立需要花費(fèi)一定時(shí)間，但是與解決高層模塊和全系統(tǒng)驗(yàn)證遇到的問題所花費(fèi)的時(shí)間相比，這些無疑是值得的。全定制版圖的層次結(jié)構(gòu)完全是由設(shè)計(jì)者決定的，對(duì)于一個(gè)復(fù)雜的系統(tǒng)來說，其版圖設(shè)計(jì)可能具有多達(dá)十幾級(jí)結(jié)構(gòu)，要保持每一級(jí)模塊的完整與獨(dú)立并不現(xiàn)實(shí)，一般只要使整個(gè)系統(tǒng)下面的一級(jí)或者兩級(jí)保持就可以了。按照下面所介紹的兩種方法進(jìn)行設(shè)計(jì)可以保持版圖模塊的完整性與獨(dú)立性。比較簡單而省時(shí)的一種方法是使用專門的連接模塊，當(dāng)需要對(duì)低層版圖模塊進(jìn)行拼接時(shí)，先將它們擺放到一起，然后其內(nèi)部就不再改動(dòng)，它們之間的連接(一般是通過金屬層)全部在新建的連接模塊內(nèi)進(jìn)行，如下圖所示:當(dāng)然，連接模塊內(nèi)還可以有子模塊，:連接模塊內(nèi)有三個(gè)子模塊，分別用來連接1與2，1與3，2與4。由于原有的低層版圖模塊不被改動(dòng)，所以它們自然是完整的。但是當(dāng)其中某個(gè)模塊需要修改時(shí)，與它相關(guān)的連接模塊也需要修改，這種方法可以看作是部分保持了模塊的獨(dú)立性。另一種方法是在原有模塊內(nèi)部進(jìn)行連接。當(dāng)模塊1需要與模塊2連接時(shí)，在相關(guān)的各個(gè)模塊內(nèi)分別添加相應(yīng)的連接金屬，使它們在模塊邊界上對(duì)準(zhǔn)。這樣，模塊就在邊界上形成接口。只要保持這些接口的形態(tài)不變，就可以方便地對(duì)模塊進(jìn)行替換。這種方法稍微費(fèi)時(shí)一些，因?yàn)樽鲞B接時(shí)需要改動(dòng)相關(guān)的多個(gè)模塊，但它所形成的版圖結(jié)構(gòu)比較好地保證了模塊的完整性與獨(dú)立性，非常有利于大規(guī)模系統(tǒng)版圖的設(shè)計(jì)與升級(jí)維護(hù)。3. 32位不恢復(fù)替代算法除法器設(shè)計(jì) Verilog HDLVerilog HDL 是一種硬件描述語言，用于從算法級(jí)、門級(jí)到開關(guān)級(jí)到多種抽象設(shè)計(jì)層次到數(shù)字系統(tǒng)建模。被建模的數(shù)字系統(tǒng)對(duì)象的復(fù)雜性可以介于簡單的門和完整的電子數(shù)字系統(tǒng)之間。數(shù)字系統(tǒng)能夠按層次描述，并可在相同描述中顯式地進(jìn)行時(shí)序建模。Verilog HDL 語言具有下述描述能力：設(shè)計(jì)地行為特征、設(shè)計(jì)地?cái)?shù)據(jù)流特性、設(shè)計(jì)的結(jié)構(gòu)組成以及包含響應(yīng)監(jiān)控和設(shè)計(jì)驗(yàn)證方面的時(shí)延和波形產(chǎn)生的機(jī)制。所以這些都使用同一種建模語言。此外，Verilog HDL語言提供流編程語言接口，通過該接口可以在模擬、驗(yàn)證期間從設(shè)計(jì)外部訪問設(shè)計(jì)，包括模擬的具體控制和運(yùn)行。Verilog HDL 語言不僅定義流語法，而且對(duì)每個(gè)語法結(jié)構(gòu)都定義了清晰的模擬、仿真語義。因此，用這種語言編寫的模型能夠使用Verilog 仿真器進(jìn)行驗(yàn)證。語言從C編程語言中繼承了多種操作符和結(jié)構(gòu)。Verilog HDL提供了擴(kuò)展的建模能力，其中許多擴(kuò)展最初很難理解。但是，Verilog HDL語言的核心子集非常易于學(xué)習(xí)和使用，這對(duì)大多數(shù)建模應(yīng)用來說已經(jīng)足夠。當(dāng)然，完整的硬件描述語言是以對(duì)從最復(fù)雜的芯片到完整的電子系統(tǒng)進(jìn)行描述。由于Verilog HDL的標(biāo)準(zhǔn)化，可以很容易地把完成的設(shè)計(jì)移植到不同廠家的不同芯片上去，并在不同規(guī)模應(yīng)用時(shí)可以較容易地修改。采用Verilog HDL最大的優(yōu)點(diǎn)是與工藝的無關(guān)性。這使得工程師在功能設(shè)計(jì)、邏輯驗(yàn)證階段，可以不必過多的考慮門級(jí)及工藝實(shí)現(xiàn)的具體細(xì)節(jié)，只需要利用系統(tǒng)設(shè)計(jì)時(shí)對(duì)芯片的要求，施加不同的約束條件，即可設(shè)計(jì)出實(shí)際電路[12]。本文通過使用Modelsim SE 。Mentor公司的ModelSim是業(yè)界最優(yōu)秀的HDL語言仿真軟件，它能提供友好的仿真環(huán)境，是業(yè)界唯一的單內(nèi)核支持VHDL和Verilog混合仿真的仿真器。它采用直接優(yōu)化的編譯技術(shù)、Tcl/Tk技術(shù)、和單一內(nèi)核仿真技術(shù)，編譯仿真速度快，編譯的代碼與平臺(tái)無關(guān)，便于保護(hù)IP核，個(gè)性化的圖形界面和用戶接口，為用戶加快調(diào)節(jié)提供強(qiáng)有力的手段，是FPGA/ASIC設(shè)計(jì)的首選仿真軟件。 主要特點(diǎn)：RTL和門級(jí)優(yōu)化，本地編譯結(jié)構(gòu)，編譯