基于library-free映射的電路面積快速優(yōu)化算法

喻奇，王倫耀，夏銀水

(寧波大學(xué) 信息科學(xué)與工程學(xué)院， 浙江 寧波 315211)

邏輯電路綜合的效果，很大程度上取決于所使用的標(biāo)準(zhǔn)單元庫(standard cells library)包含的單元電路的質(zhì)量、種類和數(shù)量[1].集成電路技術(shù)的迅猛發(fā)展、工藝的不斷更新，給標(biāo)準(zhǔn)單元庫的維護(hù)和升級帶來了巨大挑戰(zhàn).另一方面，標(biāo)準(zhǔn)單元庫中功能有限的單元電路與電路功能的矛盾，也限制了邏輯電路在映射過程中進(jìn)一步優(yōu)化的可能性.而基于library-free映射，使用大型虛擬庫代替預(yù)先設(shè)計好的標(biāo)準(zhǔn)單元庫[2-3]，所有的門單元都是動態(tài)且按需生成的，映射過程中不必考慮使用的門單元是否存在，因此具有更大的解空間.同時，library-free映射因較靈活，常被應(yīng)用于新器件的映射[4-5].

基于library-free映射的面積優(yōu)化，主要包含動態(tài)單元電路的生成與性能評估[6-8]以及覆蓋策略[9-11]兩方面.在覆蓋策略方面，文獻(xiàn)[9]將電路表示為由“與/或/非”等基本邏輯運(yùn)算組合而成的n元樹(n-ary tree)，并以串并聯(lián)晶體管數(shù)量為約束條件，使用動態(tài)規(guī)劃對電路延時進(jìn)行優(yōu)化.文獻(xiàn)[10]使用多米諾邏輯進(jìn)行l(wèi)ibrary-free映射,首先使用節(jié)點(diǎn)映射算法獲得多米諾邏輯的初始映射，再沿關(guān)鍵路徑對邏輯單元重新排序，進(jìn)而實(shí)現(xiàn)延時優(yōu)化.文獻(xiàn)[11]使用邏輯努力(logical effort)對動態(tài)單元電路的延時進(jìn)行估算，并以延時為約束條件使用動態(tài)規(guī)劃實(shí)現(xiàn)面積的最優(yōu)覆蓋.動態(tài)規(guī)劃是一種常用的覆蓋策略方法，求解過程中須窮舉解空間的所有解，故隨著問題規(guī)模的增大，求解難度和時間復(fù)雜度將呈指數(shù)……