鬼佬大哥大
  • / 14
  • 下載費用:30 金幣  

一種利用窮舉法的三值FPRM電路功耗優化方法.pdf

摘要
申請專利號:

CN201510524262.2

申請日:

2015.08.25

公開號:

CN105205214A

公開日:

2015.12.30

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06F 17/50申請日:20150825|||公開
IPC分類號: G06F17/50 主分類號: G06F17/50
申請人: 寧波大學
發明人: 汪鵬君; 厲康平; 張會紅
地址: 315211 浙江省寧波市江北區風華路818號
優先權:
專利代理機構: 寧波奧圣專利代理事務所(普通合伙) 33226 代理人: 方小惠
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510524262.2

授權公告號:

||||||

法律狀態公告日:

2017.09.29|||2016.01.27|||2015.12.30

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

本發明公開了一種利用窮舉法的三值FPRM電路功耗優化方法,首先將三值FPRM電路采用p極性下的三值FPRM邏輯函數進行表示,然后分解三值FPRM邏輯函數中含有的多輸入運算,得到p極性下的多個二輸入模3加門和多個二輸入模3乘門,將二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,構建得到三值FPRM電路的功耗估計模型,最后采用窮舉法對三值FPRM電路進行功耗最佳極性搜索,搜索得到三值FPRM電路的最小功耗和功耗最佳極性;優點是可實現三值FPRM電路的功耗優化;隨機采用13個MCNC?Benchmark電路進行仿真驗證,本發明搜索到的最佳極性與0極性比較,模3加門數量平均節省54.94%,模3乘門數量平均節省46.89%,功耗平均節省72.72%,功耗優化效果顯著。

權利要求書

權利要求書
1.  一種利用窮舉法的三值FPRM電路功耗優化方法,其特征在于包括如下步驟:
①建立三值FPRM電路的功耗估計模型:
①-1將三值FPRM電路采用三值FPRM邏輯函數表示為如下形式:
fp(xn-1,xn-2,...,x0)=⊕Σi=03n-1ai*Πj=0n-1x·jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用n位三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,⊕表示多輸入模3加運算,∑為累加符號,符號“*”表示乘號,i=0,1,2,…,3n-1,i用n位三進制形式表示為in-1in-2…i0,ij∈{0,1,2},ai為FPRM系數;ai∈{0,1,2};∏表示多輸入模3乘運算,的展開式為:Πj=0n-1x·jij=x·n-1in-1x·n-2in-2...x·0i0,]]>其中x·j=(xj⊕pj),]]>x·j0=1,x·j1=x·j,x·j2=x·j*x·j,]]>極性p和下標i決定變量的表示形式;
①-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入 模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
①-3將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
①-4根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1‐P1(k)u‐P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1‐Q1(g)o‐Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
①-5根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函 數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量;
②采用窮舉法對三值FPRM電路進行功耗最佳極性搜索,得到三值FPRM電路的功耗最佳極性和該功耗最佳極性下三值FPRM電路的最小功耗。

2.  根據權利要求1所述的一種利用窮舉法的三值FPRM電路功耗優化方法,其特征在于所述的步驟②中采用窮舉法對三值FPRM電路進行功耗最佳極性搜索的具體步驟為:
②-1采用三值FPRM電路的功耗估計模型計算最大極性下的三值FPRM電路功耗,將最大極性作為最佳極性,將最大極性下的三值FPRM電路的功耗作為最小功耗;
②-2依極性由大到小的順序用三值FPRM電路的功耗估計模型逐一計算其余3n-1個極性下的三值FPRM電路功耗;
②-3根據當前值小于最小值即更新的原則,以三值FPRM電路的功耗大小為評判依據,不斷更新最小功耗和最佳極性,得到最后一次更新后的三值FPRM電路的最小功耗和最佳極性;
②-4將最后一次更新后的三值FPRM電路的最小功耗和最佳極性作為三值FPRM電路的最小功耗和功耗最佳極性。

說明書

說明書一種利用窮舉法的三值FPRM電路功耗優化方法
技術領域
本發明涉及一種三值FPRM電路功耗優化方法,尤其是涉及一種利用窮舉法的三值FPRM電路功耗優化方法。
背景技術
隨著集成電路規模和集成度的不斷發展,數字電路必定會遭遇功耗、面積與速度等問題。傳統的數字電路大都采用二值邏輯,但是二值信號信息含量低已成為制約集成電路發展的主要因素。而多值邏輯電路增加了單線攜帶信息的能力,能有效提高空間或時間的利用率,減少數字系統的連線,節省電路面積與成本。基數為3的三值邏輯在多值邏輯代數系統中基數最小,容易實現,具有代表性。
任意邏輯函數均可以用布爾邏輯和Reed-Muller(RM)邏輯來表示,與傳統的布爾邏輯電路相比,基于RM邏輯的電路具有以下三個方面的優勢:首先,在某些功能電路(如通信電路、奇偶校驗電路、運算電路等)中,用RM邏輯表示的電路在功耗、面積和速度等方面體現出了巨大的優勢;其次,用RM邏輯表示的電路可測性強;最后,用RM邏輯表示的電路結構更加緊湊。RM邏輯函數通常采用固定極性(Fixed-polarityReed-Muller,FPRM)和混合極性(Mixed-polarityReed-Muller,MPRM)兩種表達方式。在n變量的三值FPRM邏輯函數中有3n個固定極性,3n個固定極性對應有3n個不同的三值FPRM表達式,三值FPRM表達式的簡單與否由其對應的極性決定,而三值FPRM表達式的簡單與否直接決定了三值FPRM電路的功耗和面積等性能指標,因此,極性對FPRM電路的功耗、面積等性能指標產生很大的影響。
由于多值邏輯和RM邏輯的諸多優點,國內外許多專家學者對多值RM邏輯進行了研究。然而國內外專家學者主要集中研究多值RM邏輯電路極性轉換技術,對于多值RM電路的功耗優化技術未進行研究。
鑒此,設計一種利用窮舉法的三值FPRM電路功耗優化方法,對三值FPRM電路 功耗優化具有重要意義。
發明內容
本發明所要解決的技術問題是提供一種利用窮舉法的三值FPRM電路功耗優化方法。該優化方法利用窮舉法實現三值FPRM電路的最佳極性搜索,由此實現三值FPRM電路的功耗優化,功耗優化效果顯著。
本發明解決上述技術問題所采用的技術方案為:一種利用窮舉法的三值FPRM電路功耗優化方法,包括如下步驟:
①建立三值FPRM電路的功耗估計模型:
①-1將三值FPRM電路采用三值FPRM邏輯函數表示為如下形式:
fp(xn-1,xn-2,...,x0)=⊕Σi=03n-1ai*Πj=0n-1x·jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用n位三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,表示多輸入模3加運算,∑為累加符號,符號“*”表示乘號,i=0,1,2,…,3n-1,i用n位三進制形式表示為in-1in-2…i0,ij∈{0,1,2},ai為FPRM系數;ai∈{0,1,2};∏表示多輸入模3乘運算,的展開式為:Πj=0n-1x·jij=x·n-1in-1x·n-2in-2...x·0i0,]]>其中x·j=(xj⊕pj),x·j0=1,x·j1=x·j,x·j2=x·j*x·j,]]>極性p和下標i決定變量的表示形式;
①-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸 入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
①-3將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
①-4根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1‐P1(k)u‐P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1‐Q1(g)o‐Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
①-5根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量;
②采用窮舉法對三值FPRM電路進行功耗最佳極性搜索,得到三值FPRM電路的功耗最佳極性和該功耗最佳極性下三值FPRM電路的最小功耗。
所述的步驟②中采用窮舉法對三值FPRM電路進行功耗最佳極性搜索的具體步驟為:
②-1采用三值FPRM電路的功耗估計模型計算最大極性下的三值FPRM電路功耗,將最大極性作為最佳極性,將最大極性下的三值FPRM電路的功耗作為最小功耗;
②-2依極性由大到小的順序用三值FPRM電路的功耗估計模型逐一計算其余3n-1個極性下的三值FPRM電路功耗;
②-3根據當前值小于最小值即更新的原則,以三值FPRM電路的功耗大小為評判依據,不斷更新最小功耗和最佳極性,得到最后一次更新后的三值FPRM電路的最小功耗和最佳極性;
②-4將最后一次更新后的三值FPRM電路的最小功耗和最佳極性作為三值FPRM電路的最小功耗和最佳極性。
與現有技術相比,本發明的優點在于首先將三值FPRM電路采用p極性下的三值FPRM邏輯函數進行表示,然后分解三值FPRM邏輯函數中含有的三輸入運算,得到p極性下的多個二輸入模3加門和多個二輸入模3乘門,將二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,構建得到三值FPRM電路的功耗估計模型,最后采用窮舉法對三值FPRM電路進行最佳極性搜索,搜索得到三值FPRM電路的最佳極性及該最佳極性下的最小功耗,實現三值FPRM電路功耗優化;本發明的方法通過建立的三值FPRM電路的功耗估計模型結合窮舉法來實現三值FPRM電路的最佳極性搜索,從而得到三值FPRM電路的最小功耗,實現三值FPRM電路的功耗優化;隨機采用13個MCNCBenchmark電路進行仿真驗證,本發明搜索到的最佳極性與0極性比較,模3加門數量平均節省54.94%,模3乘門數量平均節省46.89%,功耗平均節省72.72%,功耗優化效果顯著。
具體實施方式
以下結合實施例對本發明作進一步詳細描述。
實施例一:一種利用窮舉法的三值FPRM電路功耗優化方法,包括如下步驟:
①建立三值FPRM電路的功耗估計模型:
①-1將三值FPRM電路采用三值FPRM邏輯函數表示為如下形式:
fp(xn-1,xn-2,...,x0)=⊕Σi=03n-1ai*Πj=0n-1x·jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用n位三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,表示多輸入模3加運算,∑為累加符號,符號“*”表示乘號,i=0,1,2,…,3n-1,i用n位三進制形式表示為in-1in-2…i0,ij∈{0,1,2},ai為FPRM系數;ai∈{0,1,2};∏表示多輸入模3乘運算,的展開式為:其中極性p和下標i決定變量的表示形式;三值FPRM電路的三值FPRM邏輯函數可以采用現有技術中成熟的三值FPRM極性轉換技術得到;
①-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所 有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
①-3將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
①-4根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1‐P1(k)u‐P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1‐Q1(g)o‐Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
①-5根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入 模3乘門的數量;
②采用窮舉法對三值FPRM電路進行功耗最佳極性搜索,得到三值FPRM電路的功耗最佳極性和該功耗最佳極性下三值FPRM電路的最小功耗。
實施例二:一種利用窮舉法的三值FPRM電路功耗優化方法,包括如下步驟:
①建立三值FPRM電路的功耗估計模型:
①-1將三值FPRM電路采用三值FPRM邏輯函數表示為如下形式:
fp(xn-1,xn-2,...,x0)=⊕Σi=03n-1ai*Πj=0n-1x·jij---(1)]]>
其中,n為函數fp(xn-1,xn-2,…,x0)的變量數,xn-1,xn-2,…,x0表示函數fp(xn-1,xn-2,…,x0)的n個輸入變量,p表示函數fp(xn-1,xn-2,…,x0)的極性,極性p用n位三進制形式表示為pn-1pn-2…p0,pj∈{0,1,2},j=0,1,2,…,n-1,表示多輸入模3加運算,∑為累加符號,符號“*”表示乘號,i=0,1,2,…,3n-1,i用n位三進制形式表示為in-1in-2…i0,ij∈{0,1,2},ai為FPRM系數;ai∈{0,1,2};∏表示多輸入模3乘運算,的展開式為:Πj=0n-1x·jij=x·n-1in-1x·n-2in-2...x·0i0,]]>其中x·j=(xj⊕pj),x·j0=1,x·j1=x·j,x·j2=x·j*x·j,]]>極性p和下標i決定變量的表示形式;
①-2p極性下的三值FPRM邏輯函數包含兩類多輸入運算,兩類多輸入運算分別為多輸入模3加運算和多輸入模3乘運算,根據三值FPRM邏輯函數展開式將三值FPRM邏輯函數分解為多個多輸入模3加運算和多個多輸入模3乘運算,然后將每個多輸入運算分別分解為二輸入運算,得到二輸入模3加運算和二輸入模3乘運算,具體分解過程為:
將多輸入運算的第1個輸入變量和第2個輸入變量作為第一個二輸入運算的兩個輸入變量,得到第一個二輸入運算的輸出變量;將第一個二輸入運算的輸出變量和多輸入運算的第3個輸入變量作為第二個二輸入運算的兩個輸入變量,得到第二個二輸入運算的輸出變量;將第二個二輸入運算的輸出變量和多輸入運算的第4個輸入變量作為第三個二輸入運算的兩個輸入變量,得到第三個二輸入運算的輸出變量;依此類推,直到所有的多輸入運算的輸入變量作為二輸入運算的輸入變量,完成多輸入運算的分解;
將p極性下的三值FPRM邏輯函數分解后得到多個多輸入模3加運算和多個多輸入模3乘運算,多輸入模3加運算也稱為多輸入模3加門,多輸入模3乘運算也稱為多輸入模3乘門,將p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量記為N,將p極性下三值FPRM邏輯函數分解后的多輸入模3乘門的數量記為W;將每個多輸入模3加運算分解后得到多個二輸入模3加運算,將每個多輸入模3乘運算分解后得到多個二輸入模3乘運算,二輸入模3加運算也稱為二輸入模3加門,二輸入模3乘運算也稱為二輸入模3乘門;將第u個多輸入模3加門分解后的二輸入模3加門的數量記為Nu,u=1,2,…,N;將第o個多輸入模3乘門分解后的二輸入模3乘門的數量記為Wo,o=1,2,…,W;
①-3將p極性下的三值FPRM邏輯函數分解后得到的所有二輸入模3加門和二輸入模3乘門引起的功耗作為p極性下的三值FPRM電路的功耗,二輸入模3加門引起的功耗采用其開關活動性表示,二輸入模3乘門引起的功耗采用其開關活動性表示,門電路的開關活動性用其輸出端的輸出變量概率表示,二輸入模3加門引起的功耗采用其輸出端的輸出變量概率表示,二輸入模3乘門引起的功耗采用其輸出端的輸出變量概率表示;
①-4根據公式(2)、(3)和(4)計算第u個多輸入模3加門分解后的第k個二輸入模3加門的輸出變量概率;k=1,2,…,Nu;
P1(k)u=Pky11*Pky20+Pky10*Pky21+Pky12*Pky22(2)
P2(k)u=Pky12*Pky20+Pky11*Pky21+Pky10*Pky22(3)
P0(k)u=1‐P1(k)u‐P2(k)u(4)
根據公式(5)、(6)和(7)計算第o個多輸入模3乘門分解后的第g個二輸入模3乘門的輸出變量概率,g=1,2,…,Wo:
Q1(g)o=Qgr11*Qgr21+Qgr12*Qgr22(5)
Q2(g)o=Qgr11*Qgr22+Qgr12*Qgr21(6)
Q0(g)o=1‐Q1(g)o‐Q2(g)o(7)
其中,P1(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為1的概率,P2(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為2的概率,P0(k)u表示第u個多輸入模3加門分解后的第k個二輸入模3加門輸出變量為0的概率,y1和y2表示二輸入模3加門的兩個輸入變量,Pky1m表示第k個二輸入模3加門中輸入變量y1為m的概率,m∈{0,1,2},Pky2m表示第k個二輸入模3加門中輸入變量y2為m的概率,當k=1時,Pky1m為多輸入模3加運算的第1個輸入變量為m的概率,Pky2m為多輸入模3加運算的第2個輸入變量為m的概率,當k>1時,Pky1m為第k-1個二輸入模3加門輸出變量為m的概率,Pky2m為多輸入模3加門的第k+1個輸入變量為m的概率;
Q1(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為1的概率,Q2(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為2的概率,Q0(g)o表示第o個多輸入模3乘門分解后的第g個二輸入模3乘門輸出變量為0的概率,r1和r2表示二輸入模3乘門的兩個輸入變量,Qgr1m表示第g個二輸入模3乘門中輸入變量r1為m的概率,Qgr2m表示第g個二輸入模3乘門中輸入變量r2為m的概率;當g=1時,Qgr1m為多輸入模3乘運算的第1個輸入變量為m的概率,Qgr2m為多輸入模3乘運算的第2個輸入變量為m的概率,當g>1時,Qgr1m為第g-1個二輸入模3乘門輸出變量為m的概率,Qgr2m為多輸入模3乘門的第g+1個輸入變量為m的概率;
輸入變量xj為1和2的概率是由隨即函數產生的概率對(P1,P2),P0=1-P1-P2;P0,P1和P2分別為0到1之間某個值,P0表示輸入變量為0的概率,P1表示輸入變量為1的概率,P2表示輸入變量為2的概率;
①-5根據二輸入模3加門的輸出變量概率和二輸入模3乘門的輸出變量概率計算三值FPRM電路的功耗,將三值FPRM電路的功耗估計模型表示為:
Eswd=2(Σu=1N(Σk=1Nu(P1(k)u+P2(k)u))+Σo=1W(Σg=1Wo(Q1(g)o+Q2(g)o)))---(8)]]>
其中,Eswd表示p極性下三值FPRM電路的功耗,N為p極性下三值FPRM邏輯函數分解后的多輸入模3加門的數量,W為p極性下三值FPRM邏輯函數分解后的多輸入 模3乘門的數量;
②采用窮舉法對三值FPRM電路進行功耗最佳極性搜索,得到三值FPRM電路的功耗最佳極性和該功耗最佳極性下三值FPRM電路的最小功耗。
本實施例中,步驟②中采用窮舉法對三值FPRM電路進行功耗最佳極性搜索的具體步驟為:
②-1采用三值FPRM電路的功耗估計模型計算最大極性下的三值FPRM電路功耗,將最大極性作為最佳極性,將最大極性下的三值FPRM電路的功耗作為最小功耗;
②-2依極性由大到小的順序用三值FPRM電路的功耗估計模型逐一計算其余3n-1個極性下的三值FPRM電路功耗;
②-3根據當前值小于最小值即更新的原則,以三值FPRM電路的功耗大小為評判依據,不斷更新最小功耗和最佳極性,得到最后一次更新后的三值FPRM電路的最小功耗和最佳極性;
②-4將最后一次更新后的三值FPRM電路的最小功耗和最佳極性作為三值FPRM電路的最小功耗和功耗最佳極性。
本發明的三值FPRM電路功耗優化方法在Windows764位操作系統,Intel(R)Core(TM)i3-2130CPU3.40GHZ,4GRAM運行環境下,用C語言通過VC6.0編譯實現,隨機采用13個MCNCBenchmark電路進行仿真驗證,將采用本發明的方法搜索到的最佳極性與0極性進行比較。為計算三值FPRM電路的開關活動性,隨機產生15組輸入信號概率:(P1,P2)={(0.21,0.53),(0.49,0.30),(0.33,0.24),(0.68,0.13),(0.15,0.26),(0.57,0.22),(0.18,0.51),(0.71,0.24),(0.08,0.35),(0.57,0.32),(0.46,0.28),(0.17,0.05),(0.32,0.43),(0.14,0.72),(0.25,0.61)}。
采用本發明的三值FPRM電路功耗優化方法進行功耗最佳極性搜索的結果如表1所示。表中,列1表示電路名稱,列2表示輸入/輸出變量個數;列3、列4和列5依次分別表示0極性下二輸入模3加門數量、二輸入模3乘門數量和電路功耗;列6、列7、列8和列9依次分別表示采用本發明的方法搜索到的最佳極性以及最佳極性下三值FPRM電路二輸入模3加門數量、二輸入模3乘門數量和功耗。
表1三值FPRM電路最佳極性搜索結果


與0極性相比,最佳極性在模3加門數量、模3乘門數量以及功耗上節省的百分比如表2所示。模3加門數量、模3乘門數量和功耗節省的百分比定義如下:
SaveMod3-A%=Mod3-A0-Mod3-ABPMod3-A0×100%---(9)]]>
SaveMod3-M%=Mod3-M0-Mod3-MBPMod3-M0×100%---(10)]]>
SaveSA%=SA0-SABPSA0×100%---(11)]]>
其中,SaveMod3-A示模3加門數量的節省,SaveMod3-M表示模3乘門數量的節省,SaveSA表示功耗的節省;Mod3-A0表示0極性下模3加門數量,Mod3-M0表示0極性下模3乘門數量,SA0表示0極性下功耗大小;Mod3-ABP表示最佳極性下模3加門數量,Mod3-MBP表示最佳極性下模3乘門數量,SABP表示最佳極性下功耗大小。
表2三值FPRM電路門數和功耗節省百分比


分析數據可知,本發明的三值FPRM電路功耗優化方法搜索到的功耗最佳極性與0極性相比優化效果明顯,其中t4電路在模3加門數量上節省了87.69%、模3乘門數量上節省了78.92%,功耗上節省了95.02%;13個測試電路在模3加門數量平均節省了54.94%,模3乘門數量平均節省了46.89%,功耗平均節省了72.72%。本發明的三值FPRM電路功耗優化方法功耗優化效果顯著。

關 鍵 詞:
一種 利用 窮舉 FPRM 電路 功耗 優化 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:一種利用窮舉法的三值FPRM電路功耗優化方法.pdf
鏈接地址:http://www.wwszu.club/p-6405400.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大