基于AIG 的多級邏輯電路延遲近似優(yōu)化

趙維凱,于宗源,王倫耀

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

隨著晶體管技術(shù)達(dá)到納米級,集成電路設(shè)計(jì)越來越復(fù)雜,通過傳統(tǒng)設(shè)計(jì)方法提高電路的性能變得愈發(fā)困難[1].另一方面,許多新興應(yīng)用程序,例如機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘/分析和圖像處理等,其本質(zhì)上是容錯(cuò)的.在這種情況下,近似計(jì)算作為一種新的電路設(shè)計(jì)范式應(yīng)運(yùn)而生[2].其基本思想是在保證電路正常工作的情況下,通過引入誤差來修改其電路結(jié)構(gòu),從而獲得更小的面積、更低的功耗及延遲.近似計(jì)算主要分為近似電路設(shè)計(jì)以及近似邏輯綜合(Approximate Logic Synthesis,ALS)兩個(gè)方面,前者目前主要通過人工設(shè)計(jì),對精確加法器、乘法器等電路進(jìn)行近似優(yōu)化[3],而后者旨在給定誤差約束條件下,為容錯(cuò)應(yīng)用自動(dòng)生成最佳近似電路[4].

近年來,ALS 得到了研究者的廣泛關(guān)注,現(xiàn)有研究工作表明[5-10],利用近似計(jì)算技術(shù),在引入較小計(jì)算誤差的情況下,能顯著地提高電路性能.文獻(xiàn)[5]通過尋找兩個(gè)功能近似的信號,用一個(gè)替換另一個(gè)來優(yōu)化電路.文獻(xiàn)[6]針對文獻(xiàn)[5]提出了批量的精度可配置誤差估計(jì)方法,在相同誤差約束下獲得了更好的優(yōu)化結(jié)果,同時(shí)縮短了程序運(yùn)行時(shí)間.文獻(xiàn)[7]提出了一種基于深度學(xué)習(xí)的綜合流,通過在映射過程中移除或者替換網(wǎng)絡(luò)上的門實(shí)現(xiàn)電路功耗優(yōu)化.文獻(xiàn)[8]通過搜索、獲取電路中的ACS (Approximate Care Set),并對ACS 中的節(jié)點(diǎn)進(jìn)行近似替換,從而實(shí)現(xiàn)面積優(yōu)化.文獻(xiàn)[9]通過獲取電路關(guān)鍵路徑的切割集,對其采用常量替換的方式實(shí)現(xiàn)電路性能優(yōu)化,但常量替換的方式可能會(huì)使電路誤差激增從而無法在給定約束下獲得最優(yōu)結(jié)果.文獻(xiàn)[10]針對關(guān)鍵路徑中的節(jié)點(diǎn)構(gòu)建臨界誤差網(wǎng)絡(luò),通過最小割的方式尋找到最優(yōu)節(jié)點(diǎn)進(jìn)行常量替換,從而實(shí)現(xiàn)電路延遲優(yōu)化,但由于部分電路對應(yīng)的解空間較大,其構(gòu)建網(wǎng)絡(luò)過程會(huì)耗費(fèi)大量運(yùn)算時(shí)間.

然而,目前所提出的ALS 方法主要集中在電路面積上的優(yōu)化.雖然這些ALS 方法在優(yōu)化面積的同時(shí)也會(huì)降低電路延遲,但其在改善電路延遲方面的潛力并沒有被完全發(fā)掘.對于實(shí)時(shí)信號處理等應(yīng)用,它們是容錯(cuò)的,但對延時(shí)的要求是嚴(yán)格的[11].對于這類應(yīng)用,延遲優(yōu)化將成為主要目標(biāo).由于對電路全局進(jìn)行近似優(yōu)化十分困難,以往的ALS 方法通常對電路中某一個(gè)或幾個(gè)門不斷進(jìn)行局部近似變化(Local Approximate Change,LAC),直至給定的誤差約束.在這些方法中,由于節(jié)點(diǎn)數(shù)量等效于電路面積且每一個(gè)節(jié)點(diǎn)對于電路面積的貢獻(xiàn)近似相同,可以認(rèn)為在面積優(yōu)化時(shí)任何節(jié)點(diǎn)的刪除都會(huì)帶來電路面積的減小.但這與電路的延遲優(yōu)化思路是不相同的,因?yàn)檠舆t是由電路的關(guān)鍵路徑?jīng)Q定的,關(guān)鍵路徑指的是信號由輸入端傳遞到輸出端所經(jīng)過的最長路徑,且電路的關(guān)鍵路徑往往不止一條,單純對某一條關(guān)鍵路徑進(jìn)行LAC 往往無法使得電路延遲降低.因此,在每一次優(yōu)化過程中要關(guān)注電路中所有的關(guān)鍵路徑,即同時(shí)縮短每一條關(guān)鍵路徑長度.為此,本文提出一種針對電路延遲優(yōu)化的ALS方法.首先,根據(jù)所給定電路獲取關(guān)鍵路徑節(jié)點(diǎn)集.其次,針對關(guān)鍵路徑節(jié)點(diǎn)采取不同于常量替換的LAC 方式.本文以錯(cuò)誤率作為誤差衡量標(biāo)準(zhǔn),其估算方式采用蒙特卡洛算法[12],最后在錯(cuò)誤率約束下不斷迭代獲得最優(yōu)電路.實(shí)驗(yàn)結(jié)果表明,與最近所提出的ALS方式相比,本文在延遲優(yōu)化方面效果顯著,同時(shí)程序運(yùn)行時(shí)間也存有優(yōu)勢.

1 與非圖及誤差評價(jià)指標(biāo)

1.1 與非圖

由于“與”“非”運(yùn)算可以構(gòu)成邏輯運(yùn)算完備集,因此任何一個(gè)邏輯表達(dá)式都可以轉(zhuǎn)換為“與”“非”運(yùn)算的表達(dá)式.與非圖(AND-Inverter-Graph,AIG)就是一種僅包含“與”和“非”運(yùn)算,用來表示邏輯功能的有向無環(huán)圖[13].AIG 由二輸入與門、反相器、有向邊和輸入輸出端一同構(gòu)成.以圖1 所示的C17 電路對應(yīng)的AIG 為例,圖中正三角表示輸入(Primary Input,PI),倒三角表示輸出(Primary Output,PO),圓圈表示與門.AIG 中的有向連線表示節(jié)點(diǎn)之間存在信號輸出輸入關(guān)系,其中虛線表示對該節(jié)點(diǎn)的輸出信號取反,相當(dāng)于接入反相器.另外,為了方便描述,通常給AIG 中的節(jié)點(diǎn)、PI 和PO進(jìn)行編號.圖1中編號1～7為輸入,8～13為節(jié)點(diǎn),22 和23 為輸出.

圖1 C17 電路AIG

一般情況下,AIG 中PI 到PO 之間存在多條路徑,其中包含節(jié)點(diǎn)最多的路徑稱為關(guān)鍵路徑,關(guān)鍵路徑中節(jié)點(diǎn)數(shù)量越多,則表示電路信號傳遞時(shí)間越長,即延遲越大.由于AIG 中的每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)“與”運(yùn)算,因此AIG 中包含的節(jié)點(diǎn)數(shù)越多,意味著對應(yīng)的電路面積也越大.這也是基于AIG 的邏輯優(yōu)化中常利用AIG 節(jié)點(diǎn)數(shù)和關(guān)鍵路徑長度作為電路面積和延遲評估標(biāo)準(zhǔn)的原因[14].

1.2 誤差評價(jià)指標(biāo)

采用近似計(jì)算技術(shù)的邏輯優(yōu)化都必須滿足給定的近似度約束.近似度有多種衡量方式,本文將錯(cuò)誤率作為電路的誤差指標(biāo).

2 多級邏輯電路延遲優(yōu)化算法

本文的多級邏輯電路延遲優(yōu)化通過AIG 實(shí)現(xiàn),并用AIG 的關(guān)鍵路徑長度來衡量邏輯電路的延遲,通過減少AIG 關(guān)鍵路徑節(jié)點(diǎn)數(shù)實(shí)現(xiàn)電路延遲優(yōu)化.

2.1 獲取關(guān)鍵路徑不重復(fù)節(jié)點(diǎn)集

不同于面積優(yōu)化,在延時(shí)優(yōu)化中,首先必須考慮關(guān)鍵路徑上節(jié)點(diǎn)的刪除,才能達(dá)到優(yōu)化延時(shí)的目的.為此,在延時(shí)優(yōu)化過程中,必須先獲取當(dāng)前電路的所有關(guān)鍵路徑節(jié)點(diǎn)集.

對于電路延遲上的優(yōu)化,單單縮短一條關(guān)鍵路徑往往是不夠的.如圖1 所示的C17 電路,它一共存在節(jié)點(diǎn)編號為{9,10,11},{9,12,13},{9,10,13}的3 條關(guān)鍵路徑集合.例如單獨(dú)優(yōu)化節(jié)點(diǎn)11,則無法實(shí)現(xiàn)電路延遲的優(yōu)化.而若同時(shí)優(yōu)化節(jié)點(diǎn)11、13,則可以使電路延遲由3 縮短到2,但意味著更多節(jié)點(diǎn)被優(yōu)化而導(dǎo)致錯(cuò)誤率增加.

根據(jù)C17 的關(guān)鍵路徑可以發(fā)現(xiàn),所獲得的關(guān)鍵路徑存在許多重復(fù)的節(jié)點(diǎn).由于本文后續(xù)需要對所有關(guān)鍵路徑節(jié)點(diǎn)單獨(dú)進(jìn)行LAC 操作并獲得對應(yīng)的錯(cuò)誤率,這會(huì)使得處在不同路徑上的同一節(jié)點(diǎn)被重復(fù)計(jì)算.例如節(jié)點(diǎn)9 存在于C17 電路所有的關(guān)鍵路徑中,在計(jì)算錯(cuò)誤率時(shí)會(huì)進(jìn)行3 次重復(fù)的計(jì)算,而每一次優(yōu)化所產(chǎn)生的錯(cuò)誤率結(jié)果是相同的,從而造成程序運(yùn)行時(shí)間增加.由此本文提出了一種獲取不重復(fù)的關(guān)鍵路徑節(jié)點(diǎn)方法,偽代碼如下,其中G為輸入的AIG 電路.

在step1 中,通過Col_AIG_POs 函數(shù)獲取當(dāng)前輸入AIG 電路中的所有輸出端節(jié)點(diǎn)POs.由于電路的PO 并不一定都是關(guān)鍵路徑的起始節(jié)點(diǎn),因此在step2 中通過GetNtklevel 函數(shù)獲取當(dāng)前輸出端的層級,判斷輸出端層級是否與電路層級相同來選取正確的關(guān)鍵路徑起始探索節(jié)點(diǎn),自頂向下搜索所有關(guān)鍵路徑集合.同時(shí),為了避免關(guān)鍵路徑的重復(fù)記錄,step3 先判斷當(dāng)前節(jié)點(diǎn)是否已經(jīng)存在于關(guān)鍵路徑節(jié)點(diǎn)集中,若不存在,則將該節(jié)點(diǎn)進(jìn)行保存;若存在,則不重復(fù)記錄.step4 中GetNextNode 函數(shù)的作用是通過當(dāng)前節(jié)點(diǎn)獲取到關(guān)鍵路徑的下一個(gè)節(jié)點(diǎn).由于AIG 中每一個(gè)節(jié)點(diǎn)僅有兩個(gè)對應(yīng)的扇入,本算法通過判斷兩個(gè)扇入節(jié)點(diǎn)所處層級的大小來決定以哪一個(gè)節(jié)點(diǎn)作為關(guān)鍵路徑節(jié)點(diǎn).若兩者不一樣大,則將層級大的節(jié)點(diǎn)作為關(guān)鍵路徑節(jié)點(diǎn)繼續(xù)進(jìn)入循環(huán),層級小的節(jié)點(diǎn)視為非關(guān)鍵路徑節(jié)點(diǎn)而舍去;若兩者一樣大,則將兩個(gè)扇入節(jié)點(diǎn)都作為下一次關(guān)鍵路徑的節(jié)點(diǎn)進(jìn)行搜索.

以C17 電路為例說明算法1,從PO 端開始探索,首先節(jié)點(diǎn)11、13 的層級與電路層級相同,將這兩個(gè)節(jié)點(diǎn)作為關(guān)鍵路徑探索的首節(jié)點(diǎn):

(1)以節(jié)點(diǎn)11 為首節(jié)點(diǎn)進(jìn)行探索,節(jié)點(diǎn)8、10都為節(jié)點(diǎn)11 的扇入,通過判斷節(jié)點(diǎn)10 的level 為2,而節(jié)點(diǎn)8 的level 為1,將節(jié)點(diǎn)10 作為關(guān)鍵路徑進(jìn)行保存.隨后對于節(jié)點(diǎn)10,同樣進(jìn)行上述判斷,將節(jié)點(diǎn)9 保留為關(guān)鍵路徑.

(2)以節(jié)點(diǎn)13 為首節(jié)點(diǎn)進(jìn)行搜索,節(jié)點(diǎn)10、12為節(jié)點(diǎn)13 的扇入節(jié)點(diǎn),而節(jié)點(diǎn)10、12 所處層級都為2,則同時(shí)對兩個(gè)節(jié)點(diǎn)進(jìn)行探索.由于在以節(jié)點(diǎn)11 為首節(jié)點(diǎn)探索時(shí),節(jié)點(diǎn)10 已經(jīng)記錄于關(guān)鍵路徑中,則不進(jìn)行重復(fù)記錄,且節(jié)點(diǎn)10 的后續(xù)探索也已經(jīng)在上一次記錄中全部完成,可以認(rèn)為該路徑下的所有節(jié)點(diǎn)都已經(jīng)被記錄.對于節(jié)點(diǎn)12 的扇入節(jié)點(diǎn)7、9,因節(jié)點(diǎn)9 所在層級較高,并且已經(jīng)存在于關(guān)鍵路徑中,不進(jìn)行重復(fù)記錄.

由此C17 電路的不重復(fù)節(jié)點(diǎn)集搜索已完成,該集合為{9,10,12,11,13}.

2.2 近似局部變換及錯(cuò)誤率估算方法

根據(jù)AIG 節(jié)點(diǎn)的特性,允許某個(gè)節(jié)點(diǎn)擁有多個(gè)扇出端,進(jìn)而可以將許多功能相同的節(jié)點(diǎn)合并以實(shí)現(xiàn)電路性能上的優(yōu)化.不同于文獻(xiàn)[9-10]中對于節(jié)點(diǎn)集或者節(jié)點(diǎn)進(jìn)行常量替換造成目標(biāo)節(jié)點(diǎn)的所有扇入信息丟失,本文通過將目標(biāo)節(jié)點(diǎn)在關(guān)鍵路徑上的扇入節(jié)點(diǎn)與扇出節(jié)點(diǎn)直接相連,保留了關(guān)鍵路徑上的信息,僅犧牲了非關(guān)鍵路徑上扇入節(jié)點(diǎn)輸入的信息,同時(shí)又避免了出現(xiàn)常量信號傳遞到下一個(gè)節(jié)點(diǎn)造成電路大量節(jié)點(diǎn)刪除的情況,從而以更小的錯(cuò)誤率實(shí)現(xiàn)層級的壓縮.圖2(a)所示為C17 電路節(jié)點(diǎn)10 使用常量0 替換結(jié)果,節(jié)點(diǎn){10,11,13}刪除,電路延遲由3 縮短為2.圖2(b)為僅對節(jié)點(diǎn)10 所在的關(guān)鍵路徑進(jìn)行LAC 的結(jié)果.由于節(jié)點(diǎn)10 的扇入節(jié)點(diǎn)2 和9 中僅有節(jié)點(diǎn)9 存在于關(guān)鍵路徑中,且節(jié)點(diǎn)11、13 同為節(jié)點(diǎn)10 的關(guān)鍵路徑上的扇出,據(jù)此將節(jié)點(diǎn)11、13 分別與節(jié)點(diǎn)9 相連,忽略節(jié)點(diǎn)2 的輸入信息,僅刪除了節(jié)點(diǎn){10,12}.相比于常量替換方法,本文的方法對電路結(jié)構(gòu)的影響較小,從而控制錯(cuò)誤率的增加.

圖2 關(guān)鍵節(jié)點(diǎn)10 不同優(yōu)化方式

在本文算法中,針對每一個(gè)關(guān)鍵路徑節(jié)點(diǎn),都采用上述LAC 方法獲取對應(yīng)的錯(cuò)誤率.在錯(cuò)誤率計(jì)算方面,本文將原始電路保存,并將其與近似電路構(gòu)建Miter 電路[15]后,采用文獻(xiàn)[8]所提供的基于蒙特卡洛算法估算電路所對應(yīng)的錯(cuò)誤率.

2.3 基于AIG 的邏輯電路延遲近似優(yōu)化算法

本優(yōu)化算法是基于錯(cuò)誤率約束下的迭代優(yōu)化算法,主要優(yōu)化目標(biāo)為在錯(cuò)誤率約束下減少關(guān)鍵路徑上的節(jié)點(diǎn)數(shù)量.采取的策略是每一次迭代時(shí)同時(shí)縮短每一條關(guān)鍵路徑長度,以實(shí)現(xiàn)電路延遲優(yōu)化.對于每一條關(guān)鍵路徑,刪除任意一個(gè)節(jié)點(diǎn)對延遲的貢獻(xiàn)都是相同的,使得搜索最合適的LAC節(jié)點(diǎn)集的空間非常龐大.假設(shè)電路的關(guān)鍵路徑長度為n,電路存在m條關(guān)鍵路徑,則需要模擬nm次才可以得到最合適的LAC 節(jié)點(diǎn)集.當(dāng)電路規(guī)模較大時(shí),通過上述方式來獲得最優(yōu)候選集將會(huì)產(chǎn)生巨額的計(jì)算量.為提高運(yùn)算速度,本文通過選取每一條關(guān)鍵路徑在單獨(dú)LAC 過程中產(chǎn)生錯(cuò)誤率最低的節(jié)點(diǎn),近似地將該節(jié)點(diǎn)作為該條關(guān)鍵路徑中的最優(yōu)解節(jié)點(diǎn).該方法雖然無法獲取到最優(yōu)的近似結(jié)果,但是極大程度上縮短了尋找合適節(jié)點(diǎn)集的過程,減少了程序運(yùn)行時(shí)間.

算法2 為錯(cuò)誤率約束下基于近似計(jì)算技術(shù)的AIG 電路延遲優(yōu)化代碼,其中G為輸入的AIG 原始電路,et為優(yōu)化過程中電路允許的最大錯(cuò)誤率.

算法2 Delay_opt(G,et)

在step1 中首先將最原始電路保存,用于每一次進(jìn)行LAC操作后計(jì)算對應(yīng)的錯(cuò)誤率.在step2中,先獲取待優(yōu)化電路的不重復(fù)關(guān)鍵路徑節(jié)點(diǎn)集合,并通過GetLAC_ER 函數(shù)計(jì)算每一個(gè)不重復(fù)節(jié)點(diǎn)單獨(dú)進(jìn)行LAC 后對應(yīng)的錯(cuò)誤率.在step3 中選出每一條關(guān)鍵路徑對應(yīng)的錯(cuò)誤率最低節(jié)點(diǎn),構(gòu)成LAC 節(jié)點(diǎn)集.利用step3 得到的LAC 節(jié)點(diǎn)集,在step4 中對該節(jié)點(diǎn)集每一個(gè)節(jié)點(diǎn)同時(shí)進(jìn)行LAC 操作,計(jì)算當(dāng)前電路相對原始電路的錯(cuò)誤率.若錯(cuò)誤率超出約束,則放棄本次嘗試,將上一次優(yōu)化的電路作為最終結(jié)果,輸出錯(cuò)誤率以及近似優(yōu)化電路;若沒有超出錯(cuò)誤率,則繼續(xù)進(jìn)行新的一輪循環(huán).

同樣以C17 電路為例進(jìn)行說明,由于該電路規(guī)模較小,本文僅以一輪模擬進(jìn)行演示.根據(jù)算法1 得到C17 不重復(fù)關(guān)鍵路徑集合為{9,10,12,11,13},計(jì)算出單獨(dú)刪除上述節(jié)點(diǎn)時(shí)對應(yīng)的錯(cuò)誤率分別為{0.1875,0.59375,0.4375,0.8125,0.8125},選取每一條路徑中錯(cuò)誤率最小的LAC節(jié)點(diǎn),可以發(fā)現(xiàn)節(jié)點(diǎn)9存在于所有關(guān)鍵路徑中,且該節(jié)點(diǎn)在對應(yīng)的關(guān)鍵路徑中錯(cuò)誤率都是最小的,由此僅需對節(jié)點(diǎn)9 進(jìn)行LAC.從圖1 可以看到與節(jié)點(diǎn)9 相連的扇出節(jié)點(diǎn)10、12 都是關(guān)鍵路徑上的節(jié)點(diǎn),而節(jié)點(diǎn)9 的扇入節(jié)點(diǎn)都為輸入端節(jié)點(diǎn),由于本文的輸入模式為均勻輸入,則隨機(jī)選擇一個(gè)輸入端與扇出端相連,同時(shí)對兩條關(guān)鍵路徑進(jìn)行LAC,優(yōu)化后的結(jié)果如圖3所示.可以發(fā)現(xiàn),按照本文的方法,僅以刪除一個(gè)節(jié)點(diǎn)的代價(jià)將電路關(guān)鍵路徑長度由3 降低到了2.

圖3 C17 電路針對節(jié)點(diǎn)9 優(yōu)化結(jié)果

3 實(shí)驗(yàn)結(jié)果分析

本文提出的優(yōu)化算法用C++語言編程實(shí)現(xiàn)并結(jié)合邏輯綜合工具ABC[16]完成電路延遲優(yōu)化.運(yùn)行環(huán)境: 處理器頻率2.6 GHz,內(nèi)存16 GB,操作系統(tǒng)為Ubuntu 20.04.由于輸入電路可能存在冗余結(jié)構(gòu),因此對于每一個(gè)輸入電路都先用ABC 中的“resyn2”優(yōu)化命令進(jìn)行預(yù)處理,該命令為ABC 中內(nèi)置的電路精確優(yōu)化腳本命令,以提高程序優(yōu)化的效率.

表1 為本次實(shí)驗(yàn)中所需用到的LGsynth91[17]和ISCAS85 測試電路,其中的“面積”與“延遲”為經(jīng)ABC 腳本命令優(yōu)化后,用MCNC[17]通用標(biāo)準(zhǔn)單元庫映射所得到的結(jié)果,I/Os 表示該電路對應(yīng)的輸入與輸出的端口數(shù)量.

表1 本文使用的測試電路信息

在錯(cuò)誤率計(jì)算時(shí),假設(shè)所有PI 輸入分布為均勻分布,通過生成百萬級別的輸入向量對近似電路進(jìn)行測試,使得當(dāng)前電路計(jì)算所得到的錯(cuò)誤率與真實(shí)錯(cuò)誤率相近,以保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性.實(shí)驗(yàn)中優(yōu)化程度用優(yōu)化率O表示,

式中,Corg和Capp分別為原始電路和近似電路對應(yīng)的面積或延遲.

表2 是本文算法與文獻(xiàn)[9]的對比結(jié)果,錯(cuò)誤率設(shè)置與文獻(xiàn)[9]相同,都為25%,采用的測試電路為LGSynth91,在錯(cuò)誤率約束下對AIG 電路優(yōu)化完成后,再通過“amap”命令進(jìn)行映射獲取最終面積及延遲.從表2 中可以發(fā)現(xiàn),本文方法相較文獻(xiàn)[9]在面積和延遲優(yōu)化上分別提升了22.96%和31.49%.同時(shí)文獻(xiàn)[9]中有部分電路在25%錯(cuò)誤率下無法進(jìn)行任何延遲和面積上的優(yōu)化,這是由于其對于關(guān)鍵路徑節(jié)點(diǎn)或者節(jié)點(diǎn)集進(jìn)行常量替換過程可能會(huì)造成大量節(jié)點(diǎn)刪除,從而導(dǎo)致電路錯(cuò)誤率激增,無法在錯(cuò)誤率約束下實(shí)現(xiàn)優(yōu)化.而本文的LAC 方式對于電路結(jié)構(gòu)影響較小,可以很好地控制錯(cuò)誤率的增加,從而獲得優(yōu)于文獻(xiàn)[9]的近似電路.

表2 本文算法與文獻(xiàn)[9]結(jié)果比較 %

表3 為本文算法與文獻(xiàn)[10]對比的結(jié)果,測試電路為ISCAS85 電路.文獻(xiàn)[10]結(jié)果通過該文章在GitHub 中開源的代碼測試,錯(cuò)誤率約束設(shè)置為15%.由于本文與文獻(xiàn)[10]都是采用蒙特卡洛算法來估算錯(cuò)誤率,優(yōu)化電路結(jié)果存在隨機(jī)性,因此對測試電路都進(jìn)行了3 次測試,取對應(yīng)平均值作為最終優(yōu)化結(jié)果.

從表3 中可以看出,本文算法面積優(yōu)化相較于文獻(xiàn)[10]減少了1.15%,而延遲優(yōu)化提升了1.67%,可以看作在面積與延遲優(yōu)化效果相近,但是本文程序的運(yùn)行時(shí)間相較于文獻(xiàn)[10]平均縮短了61.88%.這是由于本文僅將所有關(guān)鍵路徑中錯(cuò)誤率最小的節(jié)點(diǎn)作為本輪優(yōu)化過程中最優(yōu)的LAC 節(jié)點(diǎn)集,并且獲取所有不重復(fù)關(guān)鍵路徑節(jié)點(diǎn)并計(jì)算其對應(yīng)的錯(cuò)誤率,減少了錯(cuò)誤率的重復(fù)計(jì)算.而文獻(xiàn)[10]通過構(gòu)建臨界誤差網(wǎng)絡(luò)來選擇該輪最優(yōu)LAC 節(jié)點(diǎn)時(shí),相較于本文直接選取錯(cuò)誤率最低的節(jié)點(diǎn),將會(huì)耗費(fèi)更多的時(shí)間.從實(shí)驗(yàn)結(jié)果來看,文獻(xiàn)[10]與本文算法所得到的電路優(yōu)化結(jié)果近似相同,但其在部分電路測試中無法很好地逼近錯(cuò)誤率上界.例如C7552 電路,文獻(xiàn)[10]僅能得到平均錯(cuò)誤率為7.4%的優(yōu)化結(jié)果,無法逼近錯(cuò)誤率閾值進(jìn)而無法獲得較好的近似電路.而對于C1355 電路優(yōu)化,兩個(gè)方式得到的近似優(yōu)化結(jié)果都幾乎將所有節(jié)點(diǎn)刪除,但由于本文算法每一次迭代中節(jié)點(diǎn)刪除數(shù)量相較于常量替換較少,導(dǎo)致全部節(jié)點(diǎn)刪除需要消耗多輪LAC,因此對于該電路程序運(yùn)行時(shí)間要高于文獻(xiàn)[10].

表3 本文算法與文獻(xiàn)[10]結(jié)果比較

4 結(jié)語

本文提出了一種基于AIG 在錯(cuò)誤率約束下實(shí)現(xiàn)多級邏輯電路延遲優(yōu)化的綜合流.該優(yōu)化方法獲取目標(biāo)電路所有關(guān)鍵路徑并收集其中對應(yīng)的不重復(fù)節(jié)點(diǎn).在電路延遲優(yōu)化過程中,為了避免常量替換造成的電路錯(cuò)誤率激增,提出了一種針對關(guān)鍵路徑節(jié)點(diǎn)的LAC 方式.通過該方式,對所有不重復(fù)的關(guān)鍵路徑節(jié)點(diǎn)集進(jìn)行LAC 并記錄其對應(yīng)的錯(cuò)誤率.為了縮短程序運(yùn)行時(shí)間,將每一條關(guān)鍵路徑中錯(cuò)誤率最低的節(jié)點(diǎn)近似地作為最優(yōu)LAC 節(jié)點(diǎn),基于此以迭代的方式不斷循環(huán)直至超過錯(cuò)誤率約束,得到最終的近似電路.本文算法相對已提出的針對面積以及延遲的常量替換方式,在電路性能和程序運(yùn)行時(shí)間上有著顯著的提升.