兼容Ｘ８６指令的３２位乘法器的分析與設計

摘要：通過研究X86指令手冊中各種乘法指令，分析其可能需要的微指令類型，結合龍騰C2的微體系結構，對執行部件以及譯碼部件工作作出權衡，同時又考慮到旁路設計的需求，設計出適應不同乘法指令類型及結果時機需求的三級流水32位有符號、無符號混合樹型乘法器結構。使用基4布斯編碼，對操作數的高位進行分析，將傳統的17個部分積轉變為16個部分積，減少了乘法部件的面積，同時在邏輯上給出了關斷開關，盡量減少電路的翻轉頻率，有效地降低了電路的功耗。

關鍵詞：X86指令； 微指令； 乘法器； 旁路邏輯； 低功耗

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2008)04－1264－04

0引言

開發具有自主版權并與國外廣泛應用的微處理器指令級兼容的微處理器，是目前提高國內微處理器設計和開發能力的一種有效途徑[1]。西北工業大學航空微電子中心自主設計研究的龍騰C2微處理器是一款面向嵌入式應用領域的低功耗32位CISC微處理器，與Intel 486DX2完全兼容，工作頻率133MHz，規模約100萬門，功耗小于1W。在微處理器的設計中，乘法器是其中一個重要的部件。乘法器在早期由于工藝及成本的限制，主要采用順序乘法器，使用迭代的方法，通過移位累加的形式經過多個時鐘周期完成運算。由Intel 486手冊得知，一條32位的乘法最多要消耗42周期才能完成[2]，可以推測它采用的就是此種方案。但是隨著計算機技術的發展和計算密集型應用需求的大量出現，快速乘法器的重要性得到越來越多的體現。目前，快速乘法器構建主要注重于電路、結構和算法改進，以求得在速度、功耗、面積上的優化[3]。但是這些乘法器在內嵌于微處理中加以使用時，往往不能充分發揮原有的效果。如果不結合微處理器的微體系結構進行綜合考慮，采用不合適的乘法器結構反倒會加重寄存器文件、指令分派追蹤等部件的負擔，比如會導致要求寄存器文件支持多端口寫、數據相關鏈表項的增加，以及寄存器旁路邏輯的復雜化。本文從分析X86乘法指令需求出發，結合龍騰C2微指令的形式及流水線的特點，論述了微處理器乘法器功能部件在設計時需要考慮的問題，以使其與其他各部件匹配融合，達到速度、功耗及單位面積計算效率各方面的要求。

1乘法指令分析

在Intel的X86指令手冊[4]中，關于乘法總共有兩類指令，即無符號乘法指令MUL和有符號乘法指令IMUL。經過分析，可以發現兩類乘法指令在格式上有很大的不同。如果不論操作數的尺寸，無符號乘法只包含單操作數一種格式；而對于有符號乘法指令來說，它包含三種格式是：只含單操作數、包含雙操作數和含有三操作數。為了分析方便，只考慮操作數尺寸在32位時的情況。這樣，無符號乘法的指令格式為 MUL r/m32。其含義是: 一個32位寄存器操作數或一個32位的存儲器操作數與EAX中的值進行無符號乘法運算，將結果的低32位存置于EAX中，高32位置于EDX中。有符號的乘法指令中，單操作數的格式為IMUL r/m32。其含義是：一個32位的寄存器操作數或一個32位的存儲器操作數與EAX中的值進行有符號乘法運算，將低32位結果置于EAX中，高32位結果置于EDX中。雙操作數的格式為IMUL r32，r/m32。其含義是將一個32位寄存器操作數與另外一個32位的寄存器操作數或存儲器操作數進行有符號乘法運算，將結果的低32位結果置于32位的寄存器中，而將高32位結果舍棄。三操作數格式為IMUL r32， r/m32， imm8。其含義是將8位的立即數符號擴展，與一個32位的寄存器或存儲器操作數進行有符號乘法運算，將其低32位結果置于一個32位的寄存器中，而高32位結果舍棄。這幾種指令格式在形式上可以簡單地歸納為三類：OPcode A、OPcode A B和OPcode A B C，分別對應于單操作數、雙操作數和三操作數指令形式。

2微指令的分析

在現代微處理器設計中，CISC型微處理器由于指令長短不一致，復雜的指令用硬件實現時復用度不高，內部采用一組RISC指令序列來實現一條復雜的CISC指令，從而將CISC指令轉換為具有RISC特性的微指令。微指令具有固定的長度，而且各個微指令域盡量做到正交，從而可以減小譯碼器工作量。考慮到Intel指令特性，其一般格式為OPcode A B。其含義為兩個源操作數A和B操作，最后結果仍然置于A中，也就是說，A既作為其中一個源地址，又作為目的地址。因而，為了盡量保持形式上的統一，龍騰C2中的微指令也采用同樣的格式：microcode A B。比如一個加法微操作，A和B相加，結果最終寫回A。為了資源的充分利用，乘法器應同時完成有符號乘和無符號乘運算。對于微指令，它應該最少包含一個有符號乘mul，以及無符號乘imul。對于單操作數的指令，可以在微指令中，將其隱含的操作數EAX在微指令中指明。但是由于其運算結果為64位，需要寫回兩個不同的32位寄存器中，在判斷寫回寄存器時只看目的寄存器編號，則只能寫回其中一部分結果。除非寄存器變成雙端口寫，并且寫回時需要對當前的操作再作譯碼，通常采用的邏輯為：if(microcode==mul)， then EAX←Mul_result[31∶0]， EDX←Mul_result[63∶32]。這樣會造成寫回寄存器時邏輯的不規整，加重寫回邏輯負擔。對于有符號乘法的單操作數指令形式也可以采用相同的處理方法。但是對于有符號的雙操作數以及三操作數，這樣處理是不可行的。因為它們的結果只取低32位，而對高32位結果舍棄。這樣如果要求一次寫回全部結果，僅有兩條微指令mul和imul還是不足，最少應該加上一條imult微指令，以便解決運算結果僅取低32位的情況。

3相關化解分析

典型的微處理器采用流水線結構，主要階段有取指、譯碼、取數、執行并寫回。指令執行時出現的數據相關而引起的流水線阻塞會極大地影響流水線性能的發揮。按序執行流水線中會出現寫后讀數據相關。考慮下面一段X86程序：

從表面形式上分析，并不能得到數據相關，但是如果指出其中隱含的操作數，就會發現任意兩條連續的指令均存在寫后讀相關。MUL EBX，隱含的另一個源操作數是EAX，而EAX是第一條MOV指令的目的操作數，其寫回結果是EDX和EAX，與第三條加法指令的兩個源操作數都相關。在龍騰C2的微處理器設計中，這種寄存器型指令之間的數據相關用數據前推技術來解決，依靠bypass通路將第n條指令的結果直接送到第n+1條指令執行時使用。但是有些32位乘法運行一次產生兩個32位結果，如果一次寫回這兩個結果，對旁路的設計時也同樣要求對微指令譯碼，下一條微指令中的兩個操作數都要與EDX以及EAX作比較以確定是否存在數據相關。進一步考慮，如果采用寄存器重命名技術來支持亂序執行，會引起體系結構寄存器保留站及標簽判斷復雜，公共結果總線位寬增加而利用率降低，這些都會增大對時序的壓力。因而需要考慮分時寫回兩次結果。圖1給出了一次寫回兩個和一個結果時分別對寄存器及旁路的要求，可以看到一次寫回一個結果時寄存器及旁路的邏輯簡單許多。



4微指令形式的確定

從上面分析得知，寫回寄存器時應避免一次寫回兩個。這就要求在乘法器設計中，應該盡量將結果分兩次寫回，也就是說最少應該兩拍完成一個乘法指令。但是由于存在IMUL A B C這種類型的乘法指令，B和C相乘結果不是寫回B而是放置于A中，這樣在第一拍中，必須指明參與運算的兩個操作數B和C，而一條龍騰C2的微指令只有兩個操作數域，無法指明在這一拍要寫回的目的地址A。所以微指令應該至少再加上一拍，這一拍用來指明參與運算的兩個操作數，從而最少三拍來完成一條乘法指令。這樣微指令的內容也就基本上確定了：第一拍讀入兩個操作數，第二拍可以寫回低32位結果，第三拍寫回高32位結果。此外，在別的復雜指令中也會用到乘法微操作，經過統計其形式為mul A，B，也就是A和B相乘結果置于A中，且只需低32位的結果，即只需兩條微指令，因而一個乘法操作應具有一定的彈性，以滿足不同的乘法結果需求的時機，如果用狀態機來控制乘法執行的階段就不大適合。所以僅使用微指令來控制乘法的不同階段，這就要求易于區分是第幾拍指令。結合微指令格式，有一個寫回位WB(write back)，在流水線第一個節拍寫回位為0，表明不寫回任何結果。第二拍和第三拍要寫回結果，寫回位WB應該為1。聯想到乘法指令結束之后還需要更新標志寄存器，可以使用更新標志寄存器位flag，在第二拍使flag為0，第三拍為1就區分了這兩個執行階段。同時，采用這種方法只需在對應的操作數域內填入正確的寄存器編號，就可以只用兩個微操作碼MUL和IMUL來表示所有類型的乘法指令，避免了增加微指令的位寬的可能性。這樣一條乘法運算所對應的微指令如下（以MULEBX為例）：

5乘法器的結構

經過上面分析可以得知，采用三拍來完成一個32位乘法操作最合適。有符號乘法和無符號乘法的操作數性質不一致，可以采用的處理也是多樣的。一種是將有符號乘法的兩個操作數取其絕對值，用無符號乘法統一處理。但是由于要求在第二拍將低32位結果寫回，不應該在得到絕對值乘積之后再對結果進行處理。在龍騰C2處理器內部，所有參與有符號運算的操作數都以補碼形式表示，而對補碼表示的二進制數據，擴展其最高位，表示數值不變。為了便于運算，將無符號數乘法兩個源操作數向高位擴展一個0，對于有符號的兩個源操作數按符號位也擴展成33位，這樣就統一為兩個33位的有符號乘法相乘。用基4布斯編碼來控制生成部分積，然后用4－2壓縮器組成的樹型結構來實現部分積的求和，最終產生的兩個結果用選擇進位加法器來求和。利用布斯編碼產生部分積，縮減了運算量；而用樹型結構來求和，加快了運算速度。其整體結構圖如圖3所示。

對booth編碼來說，有一個前提條件，就是乘數A的位寬為偶數。但是由于將有符號乘和無符號乘統一以后，按符號擴展乘數A的位寬是33，這就需要將A再擴展一位，也就是變為34位。 這樣，得到的部分積會有17個，而乘法器在得到部分積以后，會使用4-2壓縮器來加快求和速度，這就要求盡量使得部分積為4的倍數。因此需要將部分積減少到16個。對booth編碼進行分析，如果將乘數A擴展為34位寬，則對于IMUL來說，A33、A32、A31只有兩種可能：全是0或者全是1。對照表1，可發現，這兩種情況的部分積都是0。而對MUL來說，A33、A32、A31也只有兩種可能：000或者是001，對照表1可發現，在000時部分積也為0，只有001時，部分積為被乘數，又因為這時i=16，也就是說這一部分積只對最終乘法結果的高32位有影響。考慮到前面提到的要在第二拍寫回低32位結果，而在第三拍寫回高32位結果，因而可以將這一部分在最后一拍時才加到最終結果的高32位上，這樣得以保證只產生16個部分積，減少4-2壓縮器的數量，也可以緩和前兩拍的時序壓力。

5．2樹型壓縮結構

在生成16個部分積以后，需要將這16個部分積全部求和，較快的結構采用多個4-2壓縮器并行求和。4-2壓縮器的結構規整，利用VLSI實現。4-2壓縮器的壓縮單元如圖6所示。其中：L1、L2、L3、L4是四個輸入位；CIN是上一位的進位；輸出S是運算結果；COUT是給下一位的輸入進位；CARRY是壓縮器的第二個輸出。在圖6中，COUT在輸入位有效后經過兩級門延遲后生成，而計算也是在兩級門延時以后才需要CIN，因此多組四個加數可以同時進行加法運算。每四個部分積需要用多組4-2壓縮器來得到兩組輸出，經過第一級4-2壓縮之后，可以得到八組輸出，再經過一級后，得到四組輸出，經過第三級壓縮后，得到兩組輸出。整體框圖如圖7所示。

5．3合理插入寄存器

由于三拍要完成兩個32位操作數的乘法操作，需要合理分配三個不同周期完成的邏輯功能，但是有一個前提是要在第二拍能完成低32位的運算，第三拍完成高32位的運算。由于主要的時延是低位向高位的進位，低32位的計算結果是一定會比高32位提前完成。經過考慮之后，將第一級寄存器置于第二級4-2壓縮器之后，并將第二級寄存器置于將第三級4-2壓縮產生的兩組輸出用選擇進位加法器相加之后。這樣，在乘法的第一個周期，需要完成符號擴展、部分積的生成以及前兩級4-2壓縮，而第二個節拍完成第三級4-2壓縮并產生64位乘法結果，第三個節拍判斷是否要在高32位上加被乘數以得到最終乘法結果，并根據乘法結果設置相應的標志位。其中在每一級邏輯結構前加一個使能信號。三級使能信號是由微操作碼以及flag和wb位共同決定，用于決定是否運行該級操作以及是否要將中間結果打入寄存器中。采用邏輯開關方法可以有效地控制所有邏輯電路的翻轉頻率，從而明顯地降低了乘法器的動態功耗。

6乘法器功耗分析

構建的乘法器主要通過SYNOPSYS公司prime power工具來分析其功耗。將整個處理器設計的RTL代碼作為DC(design compiler)的輸入，在SMIC的.18工藝庫下進行綜合。DC綜合后產生了整個微處理器的門級網表，同時也生成sdf(standard delay file，延時文件）。由于.18工藝的靜態功耗所占總功耗的比例較低，著重分析乘法器的動態功耗。采用的分析方式是將VCS(verilog compiler simulator)反標sdf標準延時信息后的門級網表作為設計輸入，運行測試程序；然后將所有節點的波形都dump出來并保存為VCD文件，再用prime power工具結合門級網表對VCD文件進行分析，最終得到乘法器及微處理器的功耗信息。為使其他部件對功耗的影響降至最低，在分析功耗時微處理器處于一個穩定的工作狀態，且乘法器處于一個滿負荷的工作狀態。選取的乘法指令包括了除有存儲器操作數參與的各種32位有符號、無符號的乘法運算指令，選取的測試激勵包括了最大、最小的正負數、零以及一般數的各種配對形式，并且讓微處理器不間斷地循環運行這些指令。在執行程序過程中，隨機抽取了15個運行段，每段記錄了10us的波形文件，由prime power分析了相應功耗，其結果如圖8所示。從圖中來看，在滿負荷工作情況下，乘法器在執行過程中，消耗的功耗非常穩定，微處理器消耗功耗約為0.289 2W，乘法器的功耗約為3.32×10-3W，平均功耗占微處理的12%不到。



7結束語

本文通過一種全正向的設計思路來構建適用于龍騰C2微體系結構的乘法器。從系統級觀點來綜合考慮執行部件的設計，從而避免單一從功能上著手的執行單元設計而造成的與體系結構不匹配的弊端。所設計的乘法器對系統結構寄存器保留站及標簽判斷、公共結果總線位寬等壓力較小。確定微指令后，采用最佳的三級流水線來滿足不同時機需求的各種乘法操作。同時對擴充符號位的有符號、無符號32位操作數基4的布斯編碼部分積的生成從17個簡化為16個，不僅減少了乘法器的結構，也有效地降低了乘法延時。最終所設計的乘法器結構緊湊，面積、功耗及性能均滿足了龍騰C2的既定目標。

參考文獻：

［1］朱霞.線程級并行的硬件技術研究[D].西安：西北工業大學，2003: 56-60.

[2］Embedded Intel486TM processor family developer’s manual[S]. [S.l.]:Intel Corporation，1997.

[3］孫旭光.高性能算術運算單元的研究與實現[D].哈爾濱:哈爾濱工業大學，2003:1-5.

[4］IA－32 Intel architecture software developer’s manual volume 2:instruction set reference[S].[S.l.]:Intel Corporation， 2003.

[5］HENNESSY J L， PATTERSOB D A. Computer architecture: a quantitative approach[M]. 3rd ed. [S.l.]:Elsevier Science Pte Ltd， 2003:A.13-A.23.

[6］WALLACE C S.A suggestion for a fast multiplier[J]. IEEE Computer，1964，13(1):14-17.

[7］VUILLEMIN J E.A very fast multiplication algorithm for VLSI implementation[J].VLSI Journal，1983，1(1):39-52.

[8］RABAEY J M， CHANDRAKASAN A， NIKOLIC B. Digital integrated circuits: a design perspective[M].2nd ed. [S.l.]:Pearson Education，2003:586-594.

[9］WESTE N H E， HARRIS D. CMOS VLSI design: a circuits and systems perspective[M].3rd ed. [S.l.]:Pearson Education， 2005:693-706.

[10]SHEN J P， LIPASTI M H. Modern processor design fundamentals of superscalar processors[M].[S.l.]:McGraw－hill Companies，2003:17-20.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”