高速低功耗乘法器的對稱分割算法及電路結構的製作方法
2023-04-23 19:58:16 2
專利名稱：高速低功耗乘法器的對稱分割算法及電路結構的製作方法
技術領域：
本發明屬於微電子學領域的高速低功耗集成電路設計，特別是指一種高速低功耗乘法器的對稱分割算法及電路結構。
背景技術：
乘法運算在數位訊號處理過程中使用非常頻繁，乘法器在專用集成電路(ASIC)、通用數位訊號處理器(DSP)和先進的微處理器(CPU)中均有廣泛使用。用硬體來實現乘法運算通常有移位累加的陣列乘法器和採用Booth算法、Wallace樹型壓縮結構的快速乘法器等幾種類型。並且為了達到更快的速度，通常都使用多級流水線技術在多個時鐘周期內完成乘法運算。
乘法運算在流水線指令處理器中(DSP、CPU)中，通常位於時序的關鍵路徑上，是流水線平衡的瓶頸。通過多級同步時鐘流水線來實現乘法運算，可以大大提高乘法運算的速度，平衡各級流水線，提高流水線效率，但同時，一個乘法運算需要在多個時鐘周期內完成，在流水線指令處理機中造成很多衝突，包括數據相關和結構相關衝突。由此，一方面，對於處在關鍵路徑上的乘法運算，要求執行速度越快越好；另一方面，為了提高整個流水線處理機的執行效率，要求乘法運算儘可能少的佔用流水線級，最好在一個時鐘周期內完成，減少衝突；這兩方面是一對矛盾。
隨著市場對數位化產品需求的不斷增加，不光對數位訊號處理的速度提出了更高的要求，同時對數據的處理能力也提出了更高的要求。新開發的CPU已達到64位水平，其中包括64位的乘法電路。未來的數字處理必將要求更高位數處理能力的乘法器。現有的基於Booth和Wallace Tree快速算法的乘法器要達到64位以上的運算非常困難，速度、功耗和面積各方面都無法滿足未來技術的要求。
發明內容
本發明的目的在於，提供一種高速低功耗乘法器的對稱分割算法及電路結構，其可實現高位數甚至超高位數乘法的快速運算。
本發明一種高速低功耗乘法器的對稱分割算法，其特徵在於，包括如下步驟步驟S1N位的兩個乘法運算操作數送入乘法器的兩個輸入端；步驟S2兩個N位乘法運算操作數對稱分割為原位寬的一半，即N位的操作數分割成N/2位高位和N/2位低位進行運算；步驟S3兩個乘數的高N/2位與高N/2位相乘、低N/2位與低N/2位相乘；步驟S4按照從左到右的順序，高位乘積的結果之後拼接低位乘積結果，形成2N位的初步運算結果，並保存備用；步驟S5兩個乘數的高N/2位與低N/2位交叉相乘；
步驟S6交叉相乘得到的兩個N位部分積結果相加；步驟S7兩個N位部分積加運算結果的最低位，與步驟S4得到的拼接結果右起第N/2位對齊，兩數相加，得到最終的乘法結果；步驟S8在時鐘控制下，最終的乘法運算結果輸出；本發明的算法採用操作數對稱分割之後，再進行小位數乘法的運算方式，使用多步驟實現高位數的乘法運算，本發明對應的電路結構可以在一個全局時鐘周期內完成所有步驟的操作。
本發明一種高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中包括一自定時控制系統，該自定時控制系統是高速低功耗對稱分割算法乘法器電路所需的外部埠為時鐘信號、復位信號和兩個N位乘法操作數輸入埠；一N位自定時對稱分割算法乘法器電路，該N位自定時對稱分割算法乘法器電路與自定時控制系統的時鐘信號及控制信號連接。
其中N位自定時對稱分割算法乘法器電路包括乘法運算模塊、部分積重組模塊、部分積求和模塊，該乘法運算模塊、部分積重組模塊、部分積求和模塊之間用多選器連接。
其中N位自定時對稱分割算法乘法器電路中有兩個N/2位乘法器，對稱分割算法運算所需的乘法器位數是普通乘法器操作數位數的一半；在運算的兩個流水線級中，由多選器選擇不同的兩套N/2位的乘數分別送入兩個N/2位乘法器中運算，來完成分割後的操作數高位與高位、低位與低位及高位與低位交叉相乘運算；
乘法器包括各種電路結構形式實現的有符號數/無符號數乘法器，其輸出端與多選器相連，由多選器選擇送入部分積重組模塊。
其中部分積重組模塊電路包括N位的拼接電路，其完成的功能是在流水線第一級，將兩個乘法器高位與高位、低位與低位乘積的N位結果拼接成2N位，送入2N位的加法器運算；其輸出通過多選器與2N位的加法器相連；在流水線第二級，拼接電路不工作；N位的加法器，在流水線第二級，用來完成分割的操作數高位與低位交叉相乘後得到的部分積的累加運算；在流水線第一級，該加法器不工作；部分積重組模塊輸出包括2N位拼接電路輸出和N+1位加法器輸出，與多選器相連，作為 部分積求和模塊的輸入信號。
其中部分積求和模塊電路包括2N位傳輸總線，用來將拼接電路的輸出結果直接送入結果寄存器，在流水線的第一級，多選器選擇2N位拼接電路的結果直接送入結果寄存器中保存，流水線第二級，該總線不使用；2N位加法器，用來完成最終部分積求和運算，以得到最終的乘法運算結果；流水線第二級，多選器選擇結果寄存器的反饋值，送入2N位加法器一個輸入端，選擇N位加法器的結果拼接N/2位常數零送入2N位加法器的另一端完成加運算，並得出最終結果；部分積求和模塊的輸出與結果寄存器通過多選器相連。
其中自定時控制系統電路包括兩相時鐘產生電路，外部輸入的時鐘經過兩相時鐘產生電路產生互不交疊的同頻率兩相時鐘，兩個時鐘輸出信號與控制信號產生電路輸入端相連；控制信號產生電路，兩相時鐘信號的上升沿先後到達控制信號產生電路，觸發控制信號狀態的翻轉；其輸出的控制信號連接乘法器內各個模塊輸入端所連接的多選器，控制多選器選擇不同的信號送入模塊中進行運算。
為進一步說明本發明的技術特徵，以下結合實施例及附圖對本發明作一詳細的描述，其中圖1是高速低功耗乘法器對稱分割算法流程圖。
圖2是N位自定時高速低功耗對稱分割算法乘法器電路結構圖。
圖3是N位自定時高速低功耗對稱分割算法乘法器局部自定時流水線控制部分電路結構框圖。
具體實施例方式
請參閱圖2和圖3，本發明一種高速低功耗對稱分割算法乘法器的電路結構，其中包括一自定時控制系統30，該自定時控制系統30是高速低功耗對稱分割算法乘法器電路所需的外部埠為時鐘信號、復位信號和兩個N位乘法操作數輸入埠；一N位自定時對稱分割算法乘法器電路20，該N位自定時對稱分割算法乘法器電路20與自定時控制系統30的時鐘信號及控制信號連接。
其中N位自定時對稱分割算法乘法器電路20包括乘法運算模塊21、部分積重組模塊22、部分積求和模塊23，該乘法運算模塊21、部分積重組模塊22、部分積求和模塊23之間用多選器24連接。
其中N位自定時對稱分割算法乘法器電路20中有兩個N/2位乘法器211，對稱分割算法運算所需的乘法器位數是普通乘法器操作數位數的一半；在運算的兩個流水線級中，由多選器24選擇不同的兩套N/2位的乘數分別送入兩個N/2位乘法器211中運算，來完成分割後的操作數高位與高位、低位與低位及高位與低位交叉相乘運算；乘法器211包括各種電路結構形式實現的有符號數/無符號數乘法器，其輸出端與多選器24相連，由多選器24選擇送入部分積重組模塊22。
其中部分積重組模塊22電路包括N位的拼接電路221，其完成的功能是在流水線第一級，將兩個乘法器高位與高位、低位與低位乘積的N位結果拼接成2N位，送入2N位的加法器運算；其輸出通過多選器與2N位的加法器相連；在流水線第二級，拼接電路不工作；N位的加法器222，在流水線第二級，用來完成分割的操作數高位與低位交叉相乘後得到的部分積的累加運算；在流水線第一級，該加法器不工作；部分積重組模塊22輸出包括2N位拼接電路輸出和N+1位加法器輸出，與多選器24相連，作為部分積求和模塊的輸入信號。
其中部分積求和模塊23電路包括2N位傳輸總線，用來將拼接電路的輸出結果直接送入結果寄存器，在流水線的第一級，多選器選擇2N位拼接電路的結果直接送入結果寄存器中保存，流水線第二級，該總線不使用；2N位加法器231，用來完成最終部分積求和運算，以得到最終的乘法運算結果；流水線第二級，多選器24選擇結果寄存器的反饋值，送入2N位加法器231一個輸入端，選擇N位加法器222的結果拼接N/2位常數零送入2N位加法器的另一端完成加運算，並得出最終結果；部分積求和模塊的輸出與結果寄存器通過多選器相連。
其中自定時控制系統30電路包括兩相時鐘產生電路，外部輸入的時鐘經過兩相時鐘產生電路產生互不交疊的同頻率兩相時鐘，兩個時鐘輸出信號與控制信號產生電路輸入端相連；控制信號產生電路，兩相時鐘信號的上升沿先後到達控制信號產生電路，觸發控制信號狀態的翻轉；其輸出的控制信號連接乘法器內各個模塊輸入端所連接的多選器，控制多選器選擇不同的信號送入模塊中進行運算。
本發明的乘法運算對稱分割算法，是將N位的乘法運算對稱分割，使用兩個N/2位的乘法器運算。其算法基於以下公式設A，B分別為乘數和被乘數A=(AN-1...AN/2AN/2-1...A1A0)2=A^12N2+A^0---(1)]]>B=(BN-1...BN/2BN/2-1...B1B0)2=B^12N2+B^0]]>其中A^1=(AN-1...AN/2)2---A^0=(AN/2-1...A0)2]]>B^1=(BN-1...BN/2)2---B^0=(BN/2-1...B0)2]]>由此得出乘法表達式可寫為AB=A^1B^12N+2N2(A^1B^0+A^0B^1)+A^0B^0---(2)]]>由公式(2)可以看到，對於一個N位數的乘法運算，如式中的A·B，可以由位數為N/2的 四個數，通過組合完成 的四次相乘運算，並經過簡單的移位累加而得到最終的乘法結果。當乘法運算的位寬N較大時，經過優化的N/2位分割乘法器的兩次運算從速度上快於N位普通快速乘法器；面積上，N位快速乘法器的面積不是簡單的N/2位乘法器的兩倍，是三倍甚至四倍，而且N越大，倍數越高，本發明用兩個N/2位的乘法器實現N位乘法運算，並且控制電路簡單，可以大大縮小晶片的面積；同樣，N位乘法器功耗一般達到N/2位乘法器的四倍到五倍，N越大，倍數越大，因此發明的乘法器功耗相比普通快速乘法器要小得多。
本發明運算過程使用的是自定時異步流水線，在兩個局部時鐘周期內完成一個多位數乘法運算，但仍然是在一個全局時鐘周期內實現。異步流水線是由事件驅動流水線的推進，由於異步電路的優點，兩級異步流水線時序上不存在平衡問題，前一級事件完成後自動啟動第二級流水線工作，可以達到流水線的最高效率。對於異步流水的事件驅動機制，常用的方法有加入運算冗餘位產生事件、利用虛電路單元模擬執行延遲產生事件，而本發明的乘法器使用全新的事件驅動機制，利用時鐘產生技術產生兩相不交疊時鐘，不交疊時鐘再通過控制信號狀態翻轉電路產生控制異步流水線推進的事件驅動信號。異步電路的事件驅動機制決定了這種電路對於控制信號的毛刺非常敏感，有可能造成運算結果錯誤，本發明中的局部異步流水線控制特別設計為單根信號線雙狀態轉換，完全避免了不必要的毛刺產生。
本發明在一個全局時鐘內採用異步流水線完成了高位數乘法運算的快速實現，為實現流水線處理機關鍵路徑上的乘法運算實現提供了很好的解決方法，解決了乘法運算速度和流水線執行效率的矛盾。
圖1是高速低功耗乘法器對稱分割算法流程圖。
本發明一種高速低功耗乘法器的對稱分割算法，包括如下步驟步驟S1N位的兩個乘法運算操作數送入乘法器的兩個輸入端；步驟S2兩個N位乘法運算操作數對稱分割為原位寬的一半，即N位的操作數分割成N/2位高位和N/2位低位進行運算；步驟S3兩個乘數的高N/2位與高N/2位相乘、低N/2位與低N/2位相乘；步驟S4按照從左到右的順序，高位乘積的結果之後拼接低位乘積結果，形成2N位的初步運算結果，並保存備用；步驟S5兩個乘數的高N/2位與低N/2位交叉相乘；步驟S6交叉相乘得到的兩個N位部分積結果相加；步驟S7兩個N位部分積加運算結果的最低位，與步驟S4得到的拼接結果右起第N/2位對齊，兩數相加，得到最終的乘法結果；步驟S8在時鐘控制下，最終的乘法運算結果輸出；本發明的算法採用操作數對稱分割之後，再進行小位數乘法的運算方式，使用多步驟實現高位數的乘法運算，本發明對應的電路結構可以在一個全局時鐘周期內完成所有步驟的操作。
請再參閱圖1，圖中左右兩部分代表兩個流水線級，左邊部分的流程在第一個流水線級中執行，包括兩個N/2位的乘法運算並行執行和接下來的拼接運算，運算得到的結果送入寄存器。
具體實施方式
為設An-1...A0和Bn-1...B0分別為兩個乘法操作數，在運算開始時，S1，兩個操作數進入輸入乘法器；S2，兩個操作數分別對稱分割為An/2-1...A0和An-1...An/2、Bn/2-1...B0和Bn-1...Bn/2；S3，在第一個流水線級中，分割後的操作數，高位與高位相乘，即An-1...An/2與Bn-1...Bn/2相乘，低位與低位相乘，即An/2-1...A0與Bn/2...B0相乘，結果分別為P2n-1...Pn和Pn-1...P0；S4，由拼接電路按照高位相乘產生的部分積在高位，低位相乘產生的部分積在低位的順序，將乘運算結果組合成P2n-1...P0，保存在寄存器中備用。
圖中右邊部分為流水線級的第二級，所完成的運算是將分割的另一半乘法操作數進行乘法運算，得到的部分積相加，並與流水線第一級的結果累加。依照同樣設定，具體實施方式
為S5，分割的乘法操作數，高位與低位交叉相乘，即An-1...An/2與Bn/2-1...B0相乘，An/2-1...A0與Bn-1...Bn/2相乘，得到的運算結果分別為，P3n-1...P2n和P4n-1...P3n；S6，P3n-1...P2n和P4n-1...P3n兩個部分積相加；S7，相加所得結果的最低位再與流水線第一級的結果P2n-1...P0的Pn/2-1位對齊，並進行累加；S8，此時得到的結果便是整個乘法運算最終結果。
圖2是N位高速低功耗對稱分割算法乘法器電路結構圖，是圖1所示的算法流程的電路實現。如圖所示，電路的連接關係為兩個操作數輸入埠分別連接輸入寄存器1和寄存器2，輸入寄存器連接多選器241，多選器241將需要的操作數送入其連接的兩個乘法器221的輸入端，乘法器的輸出總線作為多選器242的輸入端，多選器242的輸出與加法器222和拼接電路相連，其後是多選器243，其功能是將加法器222、拼接電路和常數「零」及輸出寄存器反饋回來的數據選擇送入加法器231或者直接送入結果寄存器3中保存，多選器244連接在結果寄存器之前，作用是控制結果寄存器的輸入。控制信號是由電路中的自定時控制系統產生的，其產生的控制信號包括一個局部時鐘信號和一個一位控制信號，局部時鐘信號12分別和輸入寄存器1、2和輸出寄存器13相連，控制信號13和多選器241、242、243、244相連。整個電路具體的實施方式為乘法運算的操作數Bn-1...B0和An-1...A0分別在局部時鐘信號12的上跳沿分別存入N位寄存器1和寄存器2中，由自定時控制系統發出的控制信號13的電平決定了電路處在流水線第一級，在控制信號13的作用下，多選器241將An/2-1...A0與Bn/2-1...B0、An-1...An/2與Bn-1...Bn/2分別送入兩個乘法器211，在這兩個N/2位的乘法器中完成乘法運算，同樣，控制信號13控制圖中的多選器242將乘法器結果通路與拼接電路的兩個輸入端連接，將兩個N位的乘法結果拼接成2N位的二進位數送出，由於處在流水線的第一級，圖中的多選器243和多選器244將2N位拼接電路輸出結果直接送入結果寄存器寄存器3的輸入端，在時鐘信號的下跳沿，結果存入寄存器3中。
寄存器3保存了流水線第一級的結果之後，圖中的自定時控制系統30適時翻轉控制信號的電平，電路進入流水線第二級工作。控制信號控制多選器241將An-1...An/2與Bn/2-1...B0、An/2-1...A0與Bn-1...Bn/2分別送入圖中的兩個乘法器211，得到運算結果P3n-1...P2n和P4n-1...P3n，多選器242將這兩個部分積送入N位的加法器222相加後，多選器243又在控制信號的作用下，將加法器222的輸出端，與來自寄存器3的部分積結果反饋值送入2N位加法器231中運算，這裡多選器243需要將加法器222的最低位後補齊N/2位的常數零，再送入加法器231中。最後運算的結果由多選器244選擇送入結果寄存器輸入端，在下一個時鐘上跳沿，送入結果寄存器3中。這樣，一個完整的乘法運算就完成了。
圖3所表示的是乘法器局部自定時流水線控制系統電路結構圖。其中包括兩相不交疊時鐘產生電路和控制信號產生電路。不交疊時鐘發生電路可以由外部輸入的時鐘信號產生時鐘信號11和時鐘信號12的同頻率不交疊時鐘。電平翻轉電路由不同時間到來的時鐘信號11和時鐘信號12的上升沿觸發控制信號產生電路的輸出電平反覆翻轉，這個反覆翻轉的電平控制整個異步流水線的狀態控制。
權利要求
1.一種高速低功耗乘法器的對稱分割算法，其特徵在於，包括如下步驟步驟S1N位的兩個乘法運算操作數送入乘法器的兩個輸入端；步驟S2兩個N位乘法運算操作數對稱分割為原位寬的一半，即N位的操作數分割成N/2位高位和N/2位低位進行運算；步驟S3兩個乘數的高N/2位與高N/2位相乘、低N/2位與低N/2位相乘；步驟S4按照從左到右的順序，高位乘積的結果之後拼接低位乘積結果，形成2N位的初步運算結果，並保存備用；步驟S5兩個乘數的高N/2位與低N/2位交叉相乘；步驟S6交叉相乘得到的兩個N位部分積結果相加；步驟S7兩個N位部分積加運算結果的最低位，與步驟S4得到的拼接結果右起第N/2位對齊，兩數相加，得到最終的乘法結果；步驟S8在時鐘控制下，最終的乘法運算結果輸出；本發明的算法採用操作數對稱分割之後，再進行小位數乘法的運算方式，使用多步驟實現高位數的乘法運算，本發明對應的電路結構可以在一個全局時鐘周期內完成所有步驟的操作。
2.一種高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中包括一自定時控制系統，該自定時控制系統是高速低功耗對稱分割算法乘法器電路所需的外部埠為時鐘信號、復位信號和兩個N位乘法操作數輸入埠；一N位自定時對稱分割算法乘法器電路，該N位自定時對稱分割算法乘法器電路與自定時控制系統的時鐘信號及控制信號連接。
3.根據權利要求2所述的高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中N位自定時對稱分割算法乘法器電路包括乘法運算模塊、部分積重組模塊、部分積求和模塊，該乘法運算模塊、部分積重組模塊、部分積求和模塊之間用多選器連接。
4.根據權利要求3所述的高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中N位自定時對稱分割算法乘法器電路中有兩個N/2位乘法器，對稱分割算法運算所需的乘法器位數是普通乘法器操作數位數的一半；在運算的兩個流水線級中，由多選器選擇不同的兩套N/2位的乘數分別送入兩個N/2位乘法器中運算，來完成分割後的操作數高位與高位、低位與低位及高位與低位交叉相乘運算；乘法器包括各種電路結構形式實現的有符號數/無符號數乘法器，其輸出端與多選器相連，由多選器選擇送入部分積重組模塊。
5.根據權利要求3所述的高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中部分積重組模塊電路包括N位的拼接電路，其完成的功能是在流水線第一級，將兩個乘法器高位與高位、低位與低位乘積的N位結果拼接成2N位，送入2N位的加法器運算；其輸出通過多選器與2N位的加法器相連；在流水線第二級，拼接電路不工作；N位的加法器，在流水線第二級，用來完成分割的操作數高位與低位交叉相乘後得到的部分積的累加運算；在流水線第一級，該加法器不工作；部分積重組模塊輸出包括2N位拼接電路輸出和N+1位加法器輸出，與多選器相連，作為部分積求和模塊的輸入信號。
6.根據權利要求3所述的高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中部分積求和模塊電路包括2N位傳輸總線，用來將拼接電路的輸出結果直接送入結果寄存器，在流水線的第一級，多選器選擇2N位拼接電路的結果直接送入結果寄存器中保存，流水線第二級，該總線不使用；2N位加法器，用來完成最終部分積求和運算，以得到最終的乘法運算結果；流水線第二級，多選器選擇結果寄存器的反饋值，送入2N位加法器一個輸入端，選擇N位加法器的結果拼接N/2位常數零送入2N位加法器的另一端完成加運算，並得出最終結果；部分積求和模塊的輸出與結果寄存器通過多選器相連。
7.根據權利要求3所述的高速低功耗對稱分割算法乘法器的電路結構，其特徵在於，其中自定時控制系統電路包括兩相時鐘產生電路，外部輸入的時鐘經過兩相時鐘產生電路產生互不交疊的同頻率兩相時鐘，兩個時鐘輸出信號與控制信號產生電路輸入端相連；控制信號產生電路，兩相時鐘信號的上升沿先後到達控制信號產生電路，觸發控制信號狀態的翻轉；其輸出的控制信號連接乘法器內各個模塊輸入端所連接的多選器，控制多選器選擇不同的信號送入模塊中進行運算。
全文摘要
本發明是一種高速低功耗高位數乘法器的算法及其實現結構，這種乘法器基於高位數乘法運算的分割算法，將多位乘法運算分割後用低位數的乘法器來實現，並採用多相時鐘技術構成局部自定時系統在一個時鐘周期內完成整個運算。該乘法器經仿真驗證，算法可靠，對於高位數和超高位數乘法運算的快速實現，提出了全新的解決辦法。同時，由於分割後採用低位數乘法器，相比於傳統多位數乘法器的實現方法，具有高速度，低功耗，小面積的特點。本發明可廣泛應用於通用和專用高性能數位訊號處理集成電路中。
文檔編號G06F7/48GK1553310SQ0313822
公開日2004年12月8日 申請日期2003年5月28日 優先權日2003年5月28日
發明者李鶯, 陳杰, 李 鶯 申請人:中國科學院微電子中心