[發明專利]一種包含無關項的Reed?Muller邏輯電路的功耗優化方法

有效

• 申請號: 201510317476.2
• 申請日: 2015-06-11
• 公開（公告）號: CN104881549B
• 公開（公告）日: 2017-12-05
• 發明（設計）人: 王翔;張榮;王維克;何振學;沈全能;周成
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京慧泉知識產權代理有限公司11232
• 代理人: 王順榮,唐愛華

技術領域

本發明涉及一種針對Reed-Muller邏輯電路的極性優化方法，尤其涉及一種包含無關項的Reed-Muller邏輯電路的功耗優化方法。屬于集成電路優化設計技術領域。

背景技術

隨著集成電路的高速發展，其設計復雜度也在不斷增加，傳統的人工設計方法早已失效，計算機輔助設計(CAD)和電子設計自動化(EDA)應運而生。而CAD工具在不同設計抽象層中對電路優化設計時，邏輯級電路優化是集成電路優化設計的關鍵組成部分之一。集成電路邏輯級自動化設計對電路的功耗和面積的性能優化起重要作用。

目前，集成電路優化設計大多基于Boolean邏輯，并已建立了相對系統的自動設計方法。然而，相關研究已表明，在功耗、面積、速度和可測試性等多方面，對于部分電路(如算術電路、奇偶校驗電路、通信電路)而言，Reed-Muller(RM)邏輯實現形式比傳統的Boolean邏輯實現形式具有更大的優勢。

無關項是數字邏輯函數中的一種特殊的最小項，該項在邏輯函數展開式中出現與否均不影響邏輯電路的性能，但是相關研究表明，合理的利用無關項可以簡化邏輯函數的展開式，進而優化電路的面積和功耗。因此，包含無關項的RM邏輯電路優化是對集成電路設計技術的重要補充，進而提高RM邏輯電路的應用范圍。

RM邏輯函數有兩種主要的表示形式，分別是Fixed Polarity Reed-Muller(FPRM)和Mixed Polarity Reed-Muller(MPRM)表達式。對于FPRM邏輯而言，n輸入變量的邏輯函數有2ⁿ不同的極性，對應2ⁿ繁簡不同的邏輯表達式。對于MPRM邏輯而言，n輸入變量的邏輯函數有3ⁿ不同的極性，對應3ⁿ繁簡不同的邏輯表達式。若加入m個無關項，其優化空間均會相應增大，其中包含無關項的FPRM電路優化空間變為2^n+m，包含無關項的MPRM邏輯電路的優化空間變為3ⁿ·2^m。相比于未考慮無關項的RM邏輯電路，優化空間急劇變大。而極性是RM邏輯電路的關鍵因素，直接決定著電路表達式的繁簡，進而影響電路的功耗、面積以及速度等方面的性能。RM電路的極性優化是在具體的極性空間中搜索一個或多個極性，其所對應邏輯表達式的目標函數的值最優，即為最佳極性，而每個極性的優劣是根據對應極性展開式的目標函數值的大小來進行評定，其中目標函數一般是與電路的功耗、面積、速度及可測試性等性能相關。

基于快速列表技術的極性間轉換算法表明：由某已知極性下的RM展開式求另一待評估極性對應的RM展開式時，這兩個極性間不同位數越少，則轉換過程所需的操作越少，極性轉換速度也越快。對于小規模電路而言，可以按照格雷碼順序進行搜索，此時的轉換速度是最快的；但對于中大規模電路而言，隨著輸入變量個數的增加，極性數目與變量數目之間是成指數關系的，RM邏輯電路的優化空間也成指數倍增加，在傳統的基于遺傳算法的RM邏輯電路的功耗優化中，每一代個體集都由幾十甚至上百個個體按隨機的順序組合而成，如果直接按照隨機順序進行極性轉換，又會造成計算時間的嚴重浪費。因此，需要尋求更加有效的智能算法來搜索最佳極性。

綜上所述，現有的針對中大規模Reed-Muller邏輯電路的功耗優化方法存在著如下一些問題：

1)隨著RM邏輯電路輸入變量的增加，其功耗優化的極性搜索空間也隨之增大，單純的窮盡搜索算法已經不能滿足要求，若直接按照隨機順序評估RM邏輯電路的這些極性，會造成計算時間上的極大浪費。

2)遺傳算法雖然簡單通用、并行處理能力和全局搜索能力強，但是它收斂速度很慢，而且容易陷入局部最優，加上由于遺傳算法中交叉、變異等操作的隨機性，很容易破壞當前群體中適應度最好的個體。尤其是對于大規模的RM邏輯電路而言，影響搜索到最佳極性的效率。

3)標準的遺傳算法采用固定的交叉率和變異率，存在早熟及穩定性差的缺點。傳統的自適應遺傳算法雖能提高算法的收斂性，但卻難以提高優良解的多樣性，以及算法的魯棒性。

發明內容