[發(fā)明專利]一種Reed?Muller邏輯電路功耗和面積優(yōu)化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710024543.0
• 申請(qǐng)日: 2017-01-11
• 公開（公告）號(hào): CN106874555A
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計(jì)）人: 王翔;李明哲;何振學(xué);王維克;周成;李林
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50;G06N3/12
• 代理公司: 北京慧泉知識(shí)產(chǎn)權(quán)代理有限公司11232
• 代理人: 王順榮,唐愛華

技術(shù)領(lǐng)域

本發(fā)明提供一種里德穆勒(即Reed-Muller，RM)邏輯電路功耗和面積優(yōu)化方法，用于解決Reed-Muller邏輯電路的最佳極性搜索問題，可以實(shí)現(xiàn)Reed-Muller邏輯電路的功耗和面積優(yōu)化。屬于Reed-Muller邏輯電路優(yōu)化設(shè)計(jì)技術(shù)領(lǐng)域。

背景技術(shù)

任意邏輯函數(shù)均有布爾(即Boolean)邏輯和RM邏輯兩種函數(shù)實(shí)現(xiàn)形式，前者是基于與/或/非(即AND/OR/NOT)的形式實(shí)現(xiàn)，而后者是基于與/異或(即AND/XOR)或者或/異或非(即OR/XNOR)的形式實(shí)現(xiàn)。RM邏輯可以用更少的門實(shí)現(xiàn)更多的算術(shù)運(yùn)算，眾所周知，邏輯展開式越精簡(jiǎn)，電路的實(shí)現(xiàn)就越簡(jiǎn)單，故需要的門電路個(gè)數(shù)就越少，從而節(jié)省大量芯片面積，提高工作頻率，降低功耗。到目前為止，集成電路優(yōu)化設(shè)計(jì)大多基于Boolean邏輯，而基于RM邏輯的優(yōu)化設(shè)計(jì)技術(shù)尚未成熟，但大量研究表明，在功耗、面積、速度和可測(cè)試性等多方面，RM邏輯實(shí)現(xiàn)形式比傳統(tǒng)的Boolean邏輯實(shí)現(xiàn)形式具有較大的優(yōu)勢(shì)。

RM邏輯函數(shù)有兩種主要的表示形式，分別是固定極性Reed-Muller(即Fixed Polarity Reed-Muller，F(xiàn)PRM)和混合極性Reed-Muller(即Mixed Polarity Reed-Muller，MPRM)表達(dá)式。對(duì)于n變量的邏輯函數(shù)有2ⁿ種不同的FPRM邏輯表達(dá)式，而n變量的邏輯函數(shù)有3ⁿ種不同的MPRM邏輯表達(dá)式，由此可知MPRM邏輯表達(dá)式的極性搜索空間大于FPRM，F(xiàn)PRM的極性搜索空間是MPRM邏輯電路的真子集。

極性是RM邏輯電路的關(guān)鍵因素，直接決定著電路表達(dá)式的繁簡(jiǎn)，進(jìn)而影響電路的面積、功耗以及速度方面的性能。RM邏輯電路極性優(yōu)化為在特定的極性空間中搜索某個(gè)(些)極性使其對(duì)應(yīng)電路的某個(gè)(些)性能指標(biāo)最優(yōu)，通常稱該極性為最佳極性。功耗和面積是集成電路設(shè)計(jì)和優(yōu)化的兩個(gè)關(guān)鍵的性能指標(biāo)，對(duì)于n輸入的AND/XOR或者OR/XNOR電路功耗和面積的最小化，即在2ⁿ個(gè)固定極性或者3ⁿ個(gè)混合極性中搜索最佳極性。

目前RM邏輯電路極性優(yōu)化中常用的兩種方法有枚舉法和遺傳算法，但枚舉法只適用于小規(guī)模邏輯電路的優(yōu)化，對(duì)大規(guī)模RM邏輯電路優(yōu)化并不適合，主要局限在運(yùn)行時(shí)間上，同時(shí)遺傳算法種群多樣性保持機(jī)制差、收斂速度慢、局部尋優(yōu)能力弱，因此，迫切需要一種更加高效和準(zhǔn)確的新的智能搜索算法。

綜上所述，現(xiàn)有針對(duì)中大規(guī)模RM邏輯電路的功耗和面積優(yōu)化方法存在如下問題：

1)隨著RM邏輯電路輸入變量的增加，其極性搜索空間呈指數(shù)增長(zhǎng)，單純地使用窮盡搜索算法已經(jīng)不能滿足要求，需要一種高效準(zhǔn)確求解最佳極性的智能搜索算法。

2)傳統(tǒng)的遺傳算法雖然并行性和全局搜索能力強(qiáng)，但是容易早熟，陷入局部最優(yōu)，并且局部搜索能力差。如果僅僅應(yīng)用傳統(tǒng)的遺傳算法，會(huì)影響最佳極性的搜索效果。

3)現(xiàn)有的中大規(guī)模RM邏輯電路功耗和面積優(yōu)化大都采用標(biāo)準(zhǔn)的遺傳算法，其交叉率和變異率是固定不變的，存在早熟及穩(wěn)定性差的缺點(diǎn)；而標(biāo)準(zhǔn)模擬退火算法溫度控制函數(shù)采用固定的溫度衰減系數(shù)，其收斂速度慢。

發(fā)明內(nèi)容

本發(fā)明的目的在于解決當(dāng)前RM邏輯電路的功耗和面積優(yōu)化問題，針對(duì)當(dāng)前RM邏輯電路最佳極性搜索收斂速度慢，容易早熟，陷入局部最優(yōu)的問題，提出了一種新的RM邏輯電路的功耗和面積優(yōu)化方法，即RM邏輯電路最佳極性智能搜索方法。并對(duì)本方法中的關(guān)鍵參數(shù)進(jìn)行了自適應(yīng)處理，優(yōu)化了搜索的效果。

本發(fā)明對(duì)標(biāo)準(zhǔn)遺傳算法中采用固定交叉率和變異率的情況進(jìn)行了改進(jìn)，不僅對(duì)遺傳因子的變化曲線進(jìn)行了非線性化調(diào)整，而且可以保證改變之后的遺傳因子可以隨著種群進(jìn)化的程度而隨之進(jìn)行相應(yīng)的變化，以此可以使得他們隨著適應(yīng)度的改變而靈活的改變。

本發(fā)明對(duì)人工神經(jīng)網(wǎng)絡(luò)的雙曲正切函數(shù)進(jìn)行了改進(jìn)，使其滿足遺傳算法中交叉率和變異率的變化范圍在[0,1]之間的要求，該函數(shù)的變換如下所示：

本發(fā)明采用上述變換后的雙曲正切函數(shù)來設(shè)計(jì)交叉率和變異率的自適應(yīng)調(diào)整公式，交叉率和變異率的自適應(yīng)調(diào)整公式如下所示：